자료구조 9장 연습문제 풀이

1. 다음 중 선형 자료구조가 아닌 것은?

가. 리스트    나. 스택    다. 큐    라. 트리

 

답 : 라. 트리

? : 트리는 비선형 자료구조이다.

 

 

 

2. 다음의 수식 이진 트리를 후위 순회하여 수식에 대한 후위 표기식을 구하여라.

+
*		*
A	B	C	D

답 : AB*CD*+

 

 

 

3. 다음 중 같은 개수의 노드를 트리로 저장하는 경우 트리의 높이가 가장 큰 트리는 무엇인가?

가. 이진 트리    나. 포화 이진 트리    다. 완전 이진 트리    라. 편향 이진 트리

 

답 : 라. 편향 이진트리

? : 편향 이진 트리는 왼쪽이나 오른쪽 서브트리만 가지는 이진 트리이기 때문에 높이가 가장 높다.

 

 

 

4. 20개의 노드로 구성된 이진 트리에서 간선의 개수와 가능한 최대 높이와 최소 높이를 구하여라.

 

답 :

간선의 개수 = 19

최대 높이 = 19

최소 높이 = 4

 

? : 

간선 개수 = 노드 개수 - 1 = 20 - 1 = 19

최대 높이(편향 이진 트리) = 노드 개수 - 1 = 19

최소 높이(완전 이진 트리) = 2^h+1 - 1 >=20, 2^h+1 >= 21 이므로 h = 4

 

 

 

5. 다음의 원소를 차례로 삽입하면서 최대 힙을 구성하여라.

3, 15, 56, 7, 33, 45, 20, 19

답 : 

56
33			45
19		7	15	20
3

 

 

 

6. 위의 최대 힙에 대해서 삭제 연산을 8번 반복 수행할 경우에 원소가 삭제되는 순서를 써라.

 

답 : 56 - 45 - 33 - 20 - 19 - 15 - 7 - 3

? : 큰 순서대로 삭제된다.

 

 

 

7. 트리를 표현할 때 가장 적합한 자료구조는?

가. Stack    나. Queue    다. Linked List    라. Circular Queue

 

답 : 다. Linked List

? : 트리를 구현할 때 연결 리스트로 구현하는 것이 가장 적합하다.

 

 

 

8. 다음 트리를 포스트오더로 운행할 때 노드 E는 몇 번째로 검사되는가?

A
B				C
				D		E
							F

가. 4번째    나. 3번째    다. 2번째    라. 5번째

 

답 : 가. 4번째

? : A - C - D - E