자료구조 7장 연습문제 풀이
1. 주변에서 LIFO(Last In First Out) 방식을 사용하는 스택의 예를 찾아 설명하시오.
답 : 웹 브라우저 뒤로 가기(가장 나중에 열린 페이지로 시작해서 되돌아간다.
2. 스택의 응용에서 다음의 수식을 후위 표기법으로 표기했을 때 옳은 것은?
| (((A / B) + C) - (D * E)) |
가. A / B + C - D * E 나. AB / C + DE *- 다. A / B + C -* DE 라. AB / C + - DE *
답 : 나. AB / C + DE *-
? : 중위 표기법의 수식을 후위 표기법으로 변환하는 방법
1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.
3) 괄호를 제거한다.
(((A / B) + C) - (D * E)) → (((A B) / C) + (D E) *- → AB / C + DE *-
3. 스택 메모리에 대한 정보의 입/출력 방식은?
가. FIFO 나. FILO 다. LILO 라. LIFO
답 : 라. LIFO
4. 스택의 응용 분야와 거리가 먼 것은?
가. 운영체제의 작업 스케줄링
나. 함수 호출의 순서 제어
다. 인터럽트의 처리
라. 수식의 계산
답 : 가. 운영체제의 작업 스케줄링
? : 운영체제의 작업 스케줄링은 큐의 응용 분야이다.
5. 다음 식에 대하여 Postfix 기법으로 옳게 기술된 것은?
| (A * B) + (C * D) |
가. + A B * C D 나. + * A B * C D 다. A B * C D * + 라. * A B + * C D
답 : 다. A B * C D * +
? : 중위 표기법의 수식을 후위 표기법으로 변환하는 방법
1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.
3) 괄호를 제거한다.
(A * B) + (C * D) → (A B) * (C D) *+ → AB * CD *+
6. 다음은 Stack에 자료를 삽입하는 알고리즘이다. 빈칸에 적합한 내용은?
procedure Insert(data, n, top, Stack)
if top >= n then call Stack-Full;
top = top + 1;
Stack(top) = ( );
end Insert가. top 나. data 다. top - 1 라. data - 1
답 : 나. data
7. 다음 문장의 빈칸에 들어갈 단어는?
| A ( ) is an ordered list in which all insertions and deletions are made at one end, called the top. |
가. stack 나. queue 다. list 라. tree
답 : 가. stack
? : 스택에 대한 설명이다.
8. 다음과 같이 infix로 표현된 수식을 postfix 표기로 옳게 변환한 것은?
| A = (B - C) * D + E |
가. = A * - B C + D E 나. = A + + - B C D E 다. A B C - D * E + = 라. A B C * D - E + =
답 : 다. A B C - D * E + =
? : 중위 표기법의 수식을 후위 표기법으로 변환하는 방법
1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.
3) 괄호를 제거한다.
A = (B - C) * D + E → A = (B C) - D * E + → A B C - D * E +=
9. 다음 영문의 괄호 안에 적합한 수식의 표현은?
| The reverse Polish notation is in a form suitable for stack manipulation. The expression (A+B)*(C+D) is written in reverse Polish notation as ( ). |
가. A B + C D + * 나. A B + C D * + 다. + A B + C D * 라. * + A B + C D
답 : 가. A B + C D + *
? : 중위 표기법의 수식을 후위 표기법으로 변환하는 방법
1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.
3) 괄호를 제거한다.
(A+B)*(C+D) → (A B) + (C D) +* → AB + CD +*
10. 데이터의 삽입, 삭제가 TOP이라고 부르는 한쪽 끝에서만 이루어지는 후입선출(LIFO)형태의 자료구조를 무엇이라고 하는가?
가. 스택 나.큐 다.덱 라.원형큐
답 : 가. 스택
11. 다음과 같은 중위식(infix)을 후위식(postfix)으로 올바르게 표현한 것은?
| A / B * (C + D) + E |
가. +*/AB+CDE 나. CD+AB/*E+ 다. AB/(CD+)*/E+ 라. AB/CD+*E+
답 : 라. AB/CD+*E+
? : 중위 표기법의 수식을 후위 표기법으로 변환하는 방법
1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.
3) 괄호를 제거한다.
A / B * (C + D) + E → AB / (C D) +*E+ → A B / C D + * E +
12. 스택 알고리즘에서 T가 스택포인터이고, m이 스택의 길이일 때, 서브루틴 “AA"가 처리해야하는 것은?
T ← T+1;
if T>m then goto AA;
else STACK(T) ← item;가. 오버플로우 처리 나. 언더플로우 처리 다. 삭제 처리 라. 삽입 처리
답 : 가. 오버플로우 처리
? : T가 m보다 클 경우 스택 포인터가 스택의 길이를 넘어섰기 때문에 오버플로우가 발생하고, 이를 처리한다.