탐색할 키 k_i와 탐색할 확률 p_i가 (가)와 같이 주어질 때 이진… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 14년 1회차
탐색할 키 kik_i와 탐색할 확률 pip_i가 (가)와 같이 주어질 때 이진 탐색 트리(binary search tree)를 (나)와 같이 구현하였다. 이진 탐색 트리의 총비용을 ∑i=1npi⋅level(ki)\sum_{i=1}^{n} p_i \cdot level(k_i)이라고 할 때, 이진 탐색 트리 (나)의 총비용은? (단, 실패한 비용은 없다고 가정하며, 루트(root) 노드의 단계(level)는 1이다)
(가)
kik_i12345
pip_i0.20.450.050.10.2
(나)
문제 이미지
1
1.65
2
1.75
3
1.85
4
1.95
해설

이진 탐색 트리 (나)의 총비용은 1.75이다.

(나)에서 루트는 k2k_2(단계 1), 그 자식은 k1,k5k_1, k_5(단계 2), k5k_5의 왼쪽 자식 k4k_4는 단계 3, k4k_4의 왼쪽 자식 k3k_3은 단계 4이다.

0.45×1+0.2×2+0.2×2+0.1×3+0.05×40.45 \times 1 + 0.2 \times 2 + 0.2 \times 2 + 0.1 \times 3 + 0.05 \times 4
=0.45+0.4+0.4+0.3+0.2=1.75= 0.45 + 0.4 + 0.4 + 0.3 + 0.2 = 1.75

  • 1.65는 각 키의 단계를 하나라도 낮게 잡았을 때 나오는 값이다.
  • 1.85나 1.95는 깊은 노드의 단계를 실제보다 높게 계산한 값이다.

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

이어서 풀어보기

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