다음 키(key) 값을 갖는 9개의 데이터를 순서대로 삽입하여 이진 탐… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 18년 1회차
다음 키(key) 값을 갖는 9개의 데이터를 순서대로 삽입하여 이진 탐색 트리(binary search tree)를 구성하였다. 구성된 이진 탐색 트리에서 루트 노드를 삭제한 후 구성되는 이진 탐색 트리에 대한 설명으로 옳지 않은 것은?
5, 6, 2, 8, 4, 1, 9, 3, 7
1
루트 노드의 키는 4와 6 중 한 개의 값을 가진다.
2
중위 순회(inorder traversal)할 경우 키 값이 1, 2, 3, 4, 6, 7, 8, 9인 노드들을 순서대로 방문한다.
3
모든 단말 노드들의 키 값들의 합은 21이다.
4
모든 노드들의 차수(degree)들의 합은 7이다.
해설

옳지 않은 설명은 단말 노드 키 값의 합이 21이라는 것으로, 실제 합은 20이다.

원래 트리는 루트 5, 왼쪽 2(자식 1, 4), 4의 왼쪽 자식 3, 오른쪽 6, 6의 오른쪽 자식 8(자식 7, 9)이다. 루트를 삭제하면 왼쪽 서브트리 최댓값 4 또는 오른쪽 서브트리 최솟값 6이 루트 자리로 올라온다.

어느 쪽으로 대체해도 단말 노드는 1, 3, 7, 9로 같아 합은 20이다.

  • 루트 키가 4와 6 중 하나: 삭제 노드를 중위 선행자나 중위 후속자로 대체하므로 옳다.
  • 중위 순회 순서 1, 2, 3, 4, 6, 7, 8, 9: 이진 탐색 트리의 중위 순회는 남은 키의 오름차순이므로 옳다.
  • 차수의 합 7: 노드가 8개이면 간선은 7개이고, 각 간선이 부모의 차수를 1씩 늘리므로 옳다.

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

이어서 풀어보기

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