9장. 연습문제

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

① 리스트   ② 스택   ③ 큐   ④ 트리

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

⇒ AB*CD*+

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

① 이진 트리     ② 포화 이진 트리   ③ 완전 이진 트리   ④ 편향 이진 트리

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

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

정해진 노드로 만들 수 있는 최대 높이의 이진 트리는 편향이진트리이므로,

최대 높이 h = n-1 = 20-1 = 19

정해진 노드로 만들 수 있는 최소 높이의 이진 트리는 완전이진트리이다. 높이가 h인 포화이진트리의 노드의 개수는 2h+1-1개.

포화이진트리의 노드의 개수 >= 완전이진트리의 노드의 개수

2h+1-1 >= 20

2h+1 >= 21

2h>= 10.5

위의 관계가 성립하기위한 최소의 h는 4이므로, 최소 높이는 4가 된다.

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

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

6. 위의 최대 히프에 대해서 삭제연산을 수행하여 원소가 삭제되는 순서를 써라.

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

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

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

8. 다음 트리를 포스트오더(Postorder)로 운행할 때 노드 E는 몇 번째로 검사되는가? (2007년 기출문제)

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