[7급 국가직 자료구조론 2019년 8번] 6개 외부 노드의 가중치가 각각 q1 ＝ 3, q2 ＝ 4, q3 ＝ 6… 정답과 해설

[7급 국가직 자료구조론 2019년 8번]

6개 외부 노드의 가중치가 각각 q₁ ＝ 3, q₂ ＝ 4, q₃ ＝ 6, q₄ ＝ 8, q₅ ＝ 10, q₆ ＝ 15인 허프만 트리의 설명으로 옳은 것은? (단, 허프만 트리는

\sum_{1 \leq i \leq n} q_{i} d_{i}

가 최소가 되는 트리로서,

q_{i}

는 외부 노드의 가중치이고

d_{i}

는 루트 노드에서부터 외부 노드까지의 거리이며, n은 외부 노드의 수이다)

자료구조론

①외부 노드에서 루트까지의 거리와 외부 노드의 가중치 곱의 총합( $\sum_{1 \leq i \leq n} q_{i} d_{i}$ )은 112이다.
②루트까지의 거리가 가장 긴 외부 노드에서 루트까지 거리는 5이다.
③루트까지의 거리가 가장 긴 외부 노드는 $q_{1}$ , $q_{2}$ , $q_{3}$ 이다.
④루트까지의 거리가 가장 짧은 외부 노드는 $q_{6}$ 이고 그 다음으로 짧은 외부 노드는 $q_{4}$ 와 $q_{5}$ 이다.

선지를 골라 바로 채점해 보세요.

정답 ①

출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)

신고가 접수됐습니다. 감사합니다.

오류 신고