6개 외부 노드의 가중치가 각각 q_1 = 3, q_2 = 4, q_3… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 19년 1회차
6개 외부 노드의 가중치가 각각 , , , , , 인 허프만 트리의 설명으로 옳은 것은? (단, 허프만 트리는 가 최소가 되는 트리로서, 는 외부 노드의 가중치이고 는 루트 노드에서부터 외부 노드까지의 거리이며, n은 외부 노드의 수이다)
1
외부 노드에서 루트까지의 거리와 외부 노드의 가중치 곱의 총합()은 112이다.2
루트까지의 거리가 가장 긴 외부 노드에서 루트까지 거리는 5이다.
3
루트까지의 거리가 가장 긴 외부 노드는 , , 이다.
4
루트까지의 거리가 가장 짧은 외부 노드는 이고 그 다음으로 짧은 외부 노드는 와 이다.
해설
이 허프만 트리의 가중 외부 경로 길이 합은 112이다.
가장 작은 두 가중치를 반복해서 합치면 3+4=7, 6+7=13, 8+10=18, 13+15=28, 18+28=46 순으로 트리가 만들어진다.
가중 경로 길이 합 = 내부 노드 값의 합 = 7+13+18+28+46 = 112거리로 확인하면 가 4, 이 3, 가 2이므로 이다.
- 루트까지 가장 긴 거리는 4이며 5가 아니다.
- 가장 긴 거리를 갖는 외부 노드는 뿐이고, 은 거리 3이다.
- 는 모두 거리 2로 같으므로 만 가장 짧다고 할 수 없다.
오류나 개정된 내용이 보이면 알려주세요