자료구조 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보다 클 경우 스택 포인터가 스택의 길이를 넘어섰기 때문에 오버플로우가 발생하고, 이를 처리한다.