키(key) 집합에 속하는 각 키에 대해 탐색이 일어날 확률이 알려져 … | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 18년 1회차
키(key) 집합에 속하는 각 키에 대해 탐색이 일어날 확률이 알려져 있을 때, 최적 이진 탐색 트리(optimal binary search tree)를 구성함으로써 한 번의 탐색에 대한 평균 비교 횟수를 최소화할 수 있다. p(x)p(x)를 키 xx에 대한 탐색 확률이라고 할 때, 키 집합 {1, 2, 3}에 속하는 각 키에 대한 탐색 확률은 다음과 같다. 키 값이 각각 1, 2, 3인 3개의 데이터를 사용하여 구성한 최적 이진 탐색 트리에서 탐색 1회당 평균 비교 횟수는? (단, p(1)+p(2)+p(3)=1p(1) + p(2) + p(3) = 1이므로, 1, 2, 3 외의 키를 탐색하는 경우는 없다)
p(1)=0.6, p(2)=0.3, p(3)=0.1p(1) = 0.6,\ p(2) = 0.3,\ p(3) = 0.1
1
1.4
2
1.5
3
1.6
4
1.7
해설

최적 이진 탐색 트리의 평균 비교 횟수는 1.5이다.

평균 비교 횟수는 각 키의 (깊이 × 탐색 확률)의 합이다. 확률이 큰 키를 루트 가까이 두어야 하므로 1을 루트로, 2를 그 오른쪽 자식, 3을 2의 오른쪽 자식으로 둔다.

0.6×1+0.3×2+0.1×3=1.50.6 \times 1 + 0.3 \times 2 + 0.1 \times 3 = 1.5

  • 루트 2(자식 1, 3): 0.3×1+(0.6+0.1)×2=1.70.3 \times 1 + (0.6 + 0.1) \times 2 = 1.7
  • 루트 1, 오른쪽 자식 3, 3의 왼쪽 자식 2: 0.6×1+0.1×2+0.3×3=1.70.6 \times 1 + 0.1 \times 2 + 0.3 \times 3 = 1.7
  • 루트 3인 트리: 확률이 가장 큰 키 1이 깊이 2 이상에 놓여 평균이 2를 넘는다.

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

이어서 풀어보기

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