m원 탐색 트리(m-way search tree)에 대한 설명으로 옳지… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 19년 1회차
m원 탐색 트리(m-way search tree)에 대한 설명으로 옳지 않은 것은?
1
공백(empty)이 아닌 m원 탐색 트리의 루트(root) 노드는 최대 m개의 서브-트리(sub-tree)를 가질 수 있다.
2
공백이 아닌 m원 탐색 트리의 루트 노드에 저장된 키(key)들은 정렬되어 있어야 한다.
3
공백이 아닌 m원 탐색 트리의 각 노드가 가지는 서브-트리 역시 m원 탐색 트리이다.
4
차수(degree)가 m이고 높이(height)가 h인 다원 탐색 트리가 가질 수 있는 최대 노드 수는 (mh−1)(m^h - 1)이다. (단, 루트만 있는 트리의 높이는 1로 한다)
해설

높이 h인 m원 탐색 트리의 최대 노드 수는 (mh−1)/(m−1)(m^h-1)/(m-1)이므로, 최대 노드 수를 mh−1m^h-1로 본 설명이 옳지 않다.

각 노드는 최대 m개의 자식을 가지므로 레벨별 최대 노드 수는 1,m,m2,…,mh−11, m, m^2, \dots, m^{h-1}이고, 이 등비급수의 합이 mh−1m−1\dfrac{m^h-1}{m-1}이다. mh−1m^h-1은 노드 수가 아니라 노드당 m−1m-1개씩 저장되는 최대 키 수에 해당한다.

  • 루트 노드가 최대 m개의 서브트리를 가질 수 있다는 설명은 m원 탐색 트리의 정의 그대로이다.
  • 노드에 저장된 키들이 정렬되어 있어야 한다는 설명은 탐색 트리의 조건으로 옳다.
  • 각 서브트리 역시 m원 탐색 트리라는 설명은 재귀적 정의로 옳다.

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

이어서 풀어보기

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