C언어로 쉽게 풀어쓴 자료구조 9장 해설(3판/천인국)

소개글

1. 본 파일의 정답 및 해설은 공식 정답이 아닌 직접 풀어서 작성한 것이며 오타, 오답 및 프로그램에 버그가 존재할 수 있으므로 반드시 확인하시길 바랍니다.
2. 간단한 문제는 해설이 생략되었을 수 있습니다.
3. 프로그램의 설명은 주석을 참조하시길 바랍니다.
4. 작성자가 과제로 지정된 문제의 해설만을 작성한것으로 일부 문제가 누락되었을 수 있습니다. 본문내용의 포함된 문제를 반드시 확인하시길 바랍니다.

목차

1. 히프트리에서 노드가 ... 어디인가?
2. 히프를 배열로 ... 무엇인가?
3. 히프 연산 중에서 하나의 노드가 ... 비례하는가?
4. 다음 중 히프 정렬이 ... 경우는?
5. 최소 히프에서 ... 노드는?
6. 최소 히프에서 ... 노드는?
7. 10개의 데이터를 ...의 높이는?
8. 최소 히프를 구현한 ... 그려라.
9. 다음의 최소 ... 답하라.
10. 다음의 파일에 ... 답하시오.
11. 자신의 할일에 우선순위를 매겨서 힙에 ... 보자.
12. 아래의 이진트리는 ... 이유는?
13. 히프트리가 비어있는 상태에서 다음의 연산들을 ... 그려라.
14. 정렬되지 않은 배열(array)을 ... 구현하여보라.
15. 연결리스트(linked list)를 이용하여 ... 구현하여 보라.
16. 최소 히프에서 임의의 요소를 삭제하는 ... 한다.
17. 다음과 같이 각 글자들의 빈도가 있을 때 ... 그려보자.

본문내용

문제 1.
(1) 루트
최대히프 기준 가장 큰 키값을 가진 노드를 삭제하는 것이며, 최대히프 방식은 가장 큰 키값을 가진 노드가 맨 위, 루트 노드에 있다.

문제 2.
(1) 완전 이진 트리이기 때문에
히프는 완전 이진트리이며 밀집된 배열로 구성되어있다.

문제 3.
(2) 트리의 높이
삽입 또는 삭제 시 지속적으로 값을 비교하며 위로 올라가거나 내려가기 때문.

문제 4.
(1) 데이터 100개 중에서 오름차순으로 20개만 뽑고자 할 때 히프정렬을 하면 트리에 순차적으로 저장되어있다.
이 방법을 이용하여 오름차순으로 값들을 뽑아낼 수 있다.

문제 5.
(2) 첫 번째 노드
최소 히프에서는 가장 작은 값이 맨 위에, 즉 첫번째 노드로 있다.

<중 략>

참고 자료

없음