두근두근 자료구조 3장 (스택) 연습문제

문자 A, B, C, D, E를 스택에 넣었다가 다시 꺼내어 출력하면 어떻게 되는가?

2. E, D, C, B, A

 

10, 20, 30, 40, 50을 스택에 넣었다가 3개의 항목을 삭제하였다. 남아 있는 항목은?

10, 20

 

스택에서 사용되는 정보의 입출력 방법은 무엇인가?

1. LIFO

 

다음 중 스택에 대한 올바른 설명을 모두 골라라.

3. 함수 호출시 복귀 주소를 저장하는데 사용된다.

4. 배열을 사용하여 구현할 수 있다.

 

다음 중 배열로 구현된 스택에서 공백상태에 해당하는 조건은? 또 포화상태에 해당되는 조건은?

1. top == -1

3. top == MAX_STACK_SIZE - 1

 

배열로 구현된 스택에 항목들을 삽입하고 삭제하는 연산은 시간 복잡도가 어떻게 되는가?

o(1)

 

순서가 A, B, C, D로 정해진 입력 자료를 스택에 입력하였다가 출력할 때, 가능한 출력 순서의 결과가 아닌 것은?

1. D, A, B, C

 

스택의 응용 분야로 거리가 먼 것은?

3. 운영체제의 작업 스케줄링

 

스택에 대한 설명으로 틀린 것은?

2. HEAD와 TAIL의 2개의 포인터를 갖고있다.

 

스택의 자료 삭제 알고리즘이다. 괄호 안의 내용으로 가장 적합한 것은?

3. Underflow

 

스택 알고리즘에서 T가 스택 상단의 위치이고, m이 스택의 길이일 때, 서브루틴 "AA"가 처리 해야 하는 것은?

1. 오버플로 처리

 

스택에서 삽입작업이 발생하면 top의 값은 어떻게 변경되는가?

4. top = top + 1

 

다음과 같은 중위식 표현을 후위식으로 옳게 표현한 것은?

4. ABC+D/*E-

 

괄호검사 프로그램에서 다음과 같은 수식이 주어졌을 경우, 알고리즘을 추적해서 각 단계에서의 스택의 내용을 그려라.

 

다음은 어떤 수식의 후위 표기이다. 이 때 최초로 수행되는 연산은 어느 것인가?

1. B + E

 

배열로 구현된 저장된 요소의 수를 반환하는 size 연산을 구현하여 보라.

int size() { return top + 1; }

 

다음과 같이 스택을 사용하는 프로그램이 하는 일은 무엇인가?

이진수 변환

 

사용자로부터 문자열을 읽고 이것을 역순으로 출력하는 프로그램 reverse.c를 작성해보자. 스택을 사용한다

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
typedef char Element;

Element data[MAX_STACK_SIZE];
int top;

void error(const char str[]) {
    printf("%s\n", str);
    exit(1);
}

void init_stak() { top = -1; }
int is_empty() { return top == -1; }
int is_full() { return top == MAX_STACK_SIZE - 1; }
int size() { return top + 1; }

void push(Element e) {
    if (is_full == 1) error("스택 포화 에러");
    data[++top] = e;
}

Element pop() {
    if (is_empty == 1) error("스택 공백 에러");
    return data[top--];
}

Element peek() {
    if (is_empty == 1) error("스택 공백 에러");
    return data[top];
}

int main()
{
    init_stak();
    char str[100];
    int count = 0;
    printf("문자열을 입력해보세요 : ");
    scanf("%s", str);

    for (int i = 0; i < sizeof(str) / sizeof(char); i++) {
        if (str[i] == '\0')
            break;
        else 
            count++;
    }

    for (int i = 0; i < count; i++) {
        push(str[i]);
    }

    for (int i = 0; i < count; i++) {
        printf("%c", pop());
    }
    return 0;
}

 

회문이란 앞뒤 어느 쪽에서 읽어도 똑같은 단어나 문장을 의미한다. 회문인지 아닌지 결정하는 프로그램을 작성하라

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
typedef char Element;

Element data[MAX_STACK_SIZE];
int top;

void error(const char str[]) {
    printf("%s\n", str);
    exit(1);
}

void init_stak() { top = -1; }
int is_empty() { return top == -1; }
int is_full() { return top == MAX_STACK_SIZE - 1; }
int size() { return top + 1; }

void push(Element e) {
    if (is_full == 1) error("스택 포화 에러");
    data[++top] = e;
}

Element pop() {
    if (is_empty == 1) error("스택 공백 에러");
    return data[top--];
}

Element peek() {
    if (is_empty == 1) error("스택 공백 에러");
    return data[top];
}

int main()
{
    init_stak();
    char str[100];
    int count = 0;
    char tmp[100];
    printf("문자열을 입력해보세요 : ");
    scanf("%s", str);

    for (int i = 0; i < sizeof(str) / sizeof(char); i++) {
        if (str[i] == '\0')
            break;
        else 
            count++;
    }

    for (int i = 0; i < count; i++) {
        push(str[i]);
    }

    for (int i = 0; i < count; i++) {
        tmp[i] = pop();
    }

    for (int i = 0; i < count; i++) {
        if (str[i] != tmp[i]) {
            printf("회문이 아닙니다.");
            exit(1);
        }
    }
    printf("회문입니다.");
    return 0;
}