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인 다원 탐색 트리가 가질 수 있는 최대 노드 수는 이다. (단, 루트만 있는 트리의 높이는 1로 한다)해설
높이 h인 m원 탐색 트리의 최대 노드 수는 이므로, 최대 노드 수를 로 본 설명이 옳지 않다.
각 노드는 최대 m개의 자식을 가지므로 레벨별 최대 노드 수는 이고, 이 등비급수의 합이 이다. 은 노드 수가 아니라 노드당 개씩 저장되는 최대 키 수에 해당한다.
- 루트 노드가 최대 m개의 서브트리를 가질 수 있다는 설명은 m원 탐색 트리의 정의 그대로이다.
- 노드에 저장된 키들이 정렬되어 있어야 한다는 설명은 탐색 트리의 조건으로 옳다.
- 각 서브트리 역시 m원 탐색 트리라는 설명은 재귀적 정의로 옳다.
오류나 개정된 내용이 보이면 알려주세요