[C언어로 쉽게 풀어쓴 자료구조] 9장

01 히프트리에서 노드가 삭제되는 위치는 어디인가?

① 루트

② 마지막 노드

③ 가장 최근에 삽입된 노드

④ 가장 먼저 삽입된 노드

 

02 히프를 배열로 표현할 수 있는 이유는 무엇인가?

① 완전 이진 트리이기 때문에

② 어느 정도 정렬되어 있기 때문에

③ 이진 트리이기 때문에

④ 히프 조건을 만족하기 때문에

 

03 히프 연산 중에서 하나의 노드가 삽입되거나 삭제되는 시간은 무엇에 비례하는가?

① 노드의 개수

② 트리의 높이

③ 항상 일정하다.

④ 예측 불가능하다.

 

04 다음 중 히프 정렬이 특히 유용하게 사용될 수 있는 경우는?

① 데이터 100개 중에서 오름차순으로 20개만 뽑고자 할 때

② 비교적 데이터의 개수가 적을 때

③ 정렬의 대상이 되는 레코드의 크기가 클 때

④ 데이터가 역순으로 정렬되어 있을 때

 

05 최소 히프에서 가장 작은 데이터가 있는 노드는?

① 마지막 노드

② 첫 번째 노드

③ 간 노드

④ 알 수 없다.

 

06 최소 히프에서 2번째로 작은 데이터가 있는 노드는?

 

07 10개의 데이터를 저장하고 있는 히프트리의 높이는?

 

08 최소 히프를 구현한 배열의 내용이 다음과 같을 때 해당하는 히프트리를 그려라.

a[i]

0                  1                 2                 3                   4                  5                 6                  7               8

2

9

18

6

15

7

3

14

(1) 이 힙에서 삭제 연산을 한번 수행한 후의 배열의 내용을 적어라.

(2) 이 힙에서 데이터 7을 삽입한 후의 배열의 내용을 적어라.

 

09 다음의 최소 히프트리에서 답하라.

(1)2를 삽입하였을 경우, 히프트리를 재구성하는 과정을 보여라.

(2)삭제연산이 한번 이루어진 다음에 히프를 재구성하는 과정을 보여라

 

10 다음의 파일에 대하여 다음 물음에 답하시오.

10, 40, 30, 5, 12, 6, 15, 9, 60

(1)위의 파일을 순차적으로 읽어서 최대 히프트리를 구성하라. 공백 트리에서 최대 히프트리가 만들어지는 과정을 보여라.

(2)구성된 최대 히프트리가 저장된 배열의 내용을 표시하라.

(3)구성된 최대 히프트리에서 최댓값을  제거한 다음 재정비하는 과정을 설명하라.

 

11 자신의 할일에 우선순위를 매겨서 힙을 저장했다가 우선순위 순으로 꺼내서 출력하는 프로그램을 작성하여 보자.

삽입(i), 삭제(d): i
할일 : 이메일 작성
우선순위: 10
삽입(i), 삭제(d): i
할일: 청소하기
우선순위: 3
삽입(i), 삭제(d): d
제일 우선 순위가 높은 일은 "이메일 작성"

12 아래의 이진트리는 최소 히프트리인가? 그 이유는?

 

13 히프트리가 비어있는 상태에서 다음의 연산들을 차례로 수행한 후의 최소 히프트리의 모습을 그려라.

insert(20), insert(12), insert(3),insert(2), delete(), insert(5), insert(16), delete(), insert(1), is_empty()

 

14 정렬되지 않은 배열(array)을 이용하여 우선순위 큐 추상 자료형의 각종 연산들을 구현하여 보라.

 

15 연결리스트(linked list)를 이용하여 우선순위 큐 추상자료형의 각종 연산들을 구현하여 보라.

 

16 최소 히프에서 임의의 요소를 삭제하는 C함수를 작성하라. 결과 히프는 히프의 조건을 만족하여야 한다.

 

17 다음과 같이 각 글자들의 빈도가 있을 때, 호프만의 코드를 계산해보자. 생성되는 트리를 그려보자.

 

a: 1 b:1 c:2 d:3 e:5 f:8 g:13 h: 21