해설 보기
정답높이 h, 차수 m인 다원 탐색 트리의 최대 노드 수는 (m^h-1)이 아니라 (m^h-1)/(m-1)개이므로 틀린 설명입니다.
핵심 개념
m원 탐색 트리(m-way search tree)의 정의와 최대 노드 수
m원 탐색 트리는 각 노드가 최대 m개의 서브트리와 최대 (m-1)개의 키를 갖는 탐색 트리입니다. 한 노드 안의 키들은 반드시 정렬된 상태로 저장되며, 키 사이의 각 포인터가 가리키는 서브트리 역시 그 자체로 m원 탐색 트리가 되는 재귀적 구조입니다. 여기서 자주 출제되는 것이 높이 h일 때의 최대 노드 수인데, 각 레벨의 노드 수가 1, m, m², …, m^(h-1)로 늘어나므로 총합은 등비수열의 합인 (m^h-1)/(m-1)개입니다. 최대 키 개수와 최대 노드 개수를 혼동하지 않도록 구분해서 기억하시는 것이 중요합니다.
선지별 해설
①m원 탐색 트리의 정의상 한 노드는 최대 (m-1)개의 키와 최대 m개의 서브트리 포인터를 가집니다. 루트 노드도 예외가 아니어서 최대 m개의 서브트리를 가질 수 있으므로 옳은 설명입니다.
②노드 내부의 키가 정렬되어 있어야 비교를 통해 어느 서브트리로 내려갈지 결정할 수 있습니다. 노드 내 키 정렬은 m원 탐색 트리의 필수 조건이므로 옳은 설명입니다.
③m원 탐색 트리는 재귀적으로 정의되며, 각 포인터가 가리키는 서브트리도 동일한 조건을 만족하는 m원 탐색 트리입니다. 따라서 옳은 설명입니다.
④레벨별 최대 노드 수가 1, m, m², …, m^(h-1)이므로 총합은 (m^h-1)/(m-1)개입니다. (m^h-1)은 최대 키의 개수에 해당하는 값이므로 노드 수 공식으로는 틀렸습니다. 이 선지가 정답입니다.
해설 보기
정답㉠은 *rear = (*rear+1) % MAX_QUEUE_SIZE;로 rear를 전진시키고, ㉡은 front == *rear로 포화를 판별합니다.
핵심 개념
원형 큐(circular queue)의 삽입 연산과 포화 상태 판별
원형 큐는 선형 큐에서 발생하는 공간 낭비를 해결하기 위해 배열의 끝과 처음을 논리적으로 연결한 구조입니다. 삽입(addq)에서는 먼저 rear를 모듈로 연산으로 한 칸 전진시킨 뒤, 그 위치가 front와 같아지는지를 검사해 포화 여부를 판단합니다. 즉 순서가 "rear 증가 → 포화 검사 → 저장"입니다. 이때 front와 rear가 같으면 공백 상태와 포화 상태를 구분할 수 없으므로, 한 자리를 비워 두고 front == rear일 때를 포화로 처리하는 것이 표준 구현입니다. 삽입은 rear를, 삭제는 front를 움직인다는 원칙도 함께 기억해야 합니다.