6개 외부 노드의 가중치가 각각 q_1 = 3, q_2 = 4, q_3… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 19년 1회차
6개 외부 노드의 가중치가 각각 q1=3q_1 = 3, q2=4q_2 = 4, q3=6q_3 = 6, q4=8q_4 = 8, q5=10q_5 = 10, q6=15q_6 = 15인 허프만 트리의 설명으로 옳은 것은? (단, 허프만 트리는 ∑1≤i≤nqidi\displaystyle\sum_{1 \leq i \leq n} q_i d_i가 최소가 되는 트리로서, qiq_i는 외부 노드의 가중치이고 did_i는 루트 노드에서부터 외부 노드까지의 거리이며, n은 외부 노드의 수이다)
1
외부 노드에서 루트까지의 거리와 외부 노드의 가중치 곱의 총합(∑1≤i≤nqidi\displaystyle\sum_{1 \leq i \leq n} q_i d_i)은 112이다.
2
루트까지의 거리가 가장 긴 외부 노드에서 루트까지 거리는 5이다.
3
루트까지의 거리가 가장 긴 외부 노드는 q1q_1, q2q_2, q3q_3이다.
4
루트까지의 거리가 가장 짧은 외부 노드는 q6q_6이고 그 다음으로 짧은 외부 노드는 q4q_4와 q5q_5이다.
해설

이 허프만 트리의 가중 외부 경로 길이 합은 112이다.

가장 작은 두 가중치를 반복해서 합치면 3+4=7, 6+7=13, 8+10=18, 13+15=28, 18+28=46 순으로 트리가 만들어진다.
가중 경로 길이 합 = 내부 노드 값의 합 = 7+13+18+28+46 = 112

거리로 확인하면 q1,q2q_1, q_2가 4, q3q_3이 3, q4,q5,q6q_4, q_5, q_6가 2이므로 3⋅4+4⋅4+6⋅3+(8+10+15)⋅2=1123 \cdot 4 + 4 \cdot 4 + 6 \cdot 3 + (8+10+15) \cdot 2 = 112이다.

  • 루트까지 가장 긴 거리는 4이며 5가 아니다.
  • 가장 긴 거리를 갖는 외부 노드는 q1,q2q_1, q_2뿐이고, q3q_3은 거리 3이다.
  • q4,q5,q6q_4, q_5, q_6는 모두 거리 2로 같으므로 q6q_6만 가장 짧다고 할 수 없다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 19년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기