Data Structures in C (C언어로 쉽게 풀어쓴 자료구조) - 천인국 8장 연습문제

Posted by Patchman
2009.05.01 00:31 Univ Study/자료구조와 실습

1. (2) 마지막 행을 제외하고는 모든 행이 노드로 채워져 있다.

2. (1) 루트

3. (1) 루트

4. (1) 특정한 값 탐색하기

5. (3) 항상 맨 마지막 행에 있다.

6. (2) 트리의 높이

7. (1) 왼쪽 노드값이 오른쪽 노드값보다 작다.

8. (1) 데이터 100개중에서 오름차순으로 20개만 뽑고자 할때

9. (2) 첫번째 노드

10. 노드의 개수가 인 완전이진트리의 높이는 이므로 =5가 된다.

11.

위의 트리는 최소 히프 트리이다.

* 완전이진트리이다.

* 부모노드의 값이 자식노드보다 작다.

12.

(1) 최소히프트리

(2) 데이터에 해당되는 히프트리를 그려보면 다음과 같다.

1

56

8 9 10

(3)

5

86

10 9

(4) (3)번의 삭제된 후의 히프에 7를 삽입하는 것으로 가정

5

86

10 9 7

0

1

2

3

4

5

6

7

0

5

8

6

10

9

7

UNDEF

13.

(1) 2를 삽입

3

67

12 13 15 20 ->

2

3

67

2 13 15 20 ->

12

3

27

6 13 15 20 ->

12

2

37

6 13 15 20 (완료)

12

(2) 삭제연산후 재구성과정((1)번의 2가 삽입된 후라고 가정)

12

37

6 13 15 20 ->

3

127

6 13 15 20 ->

3

67

12 13 15 20 (완료)

14.

* insert(20)

20

* insert(12)

12

20

* insert(3)

3

2012

* insert(2)

2

3 12

20

* insert(2)

2

3 12

20