다음 이진 트리(binary tree)를 <보기>에서 제시한… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 18년 1회차
다음 이진 트리(binary tree)를 <보기>에서 제시한 방법을 사용하여 1차원 배열로 표현할 때, 필요한 배열의 최소 크기는? (단, 배열의 인덱스(index)는 0부터 시작하며 배열의 크기는 배열 원소의 개수이다)
<보 기>
○ 루트 노드는 배열의 인덱스가 1인 위치에 저장된다.
○ 배열 인덱스가 kk인 위치에 있는 노드가 자식 노드를 가질 경우, 왼쪽 자식 노드는 인덱스가 2k2k인 위치에 있으며 오른쪽 자식 노드는 인덱스가 2k+12k+1인 위치에 있다.

문제 이미지
1
17
2
18
3
34
4
35
해설

가장 큰 인덱스가 34이고 인덱스가 0부터 시작하므로 필요한 배열의 최소 크기는 35이다.

루트 A가 1이면 B는 2, C는 3, D는 2×2=42\times2=4, E는 C의 왼쪽 자식이므로 2×3=62\times3=6이다.

F는 D의 왼쪽 자식으로 8, G는 F의 오른쪽 자식으로 2×8+1=172\times8+1=17, H는 G의 왼쪽 자식으로 2×17=342\times17=34가 된다. 사용하지 않는 인덱스 0 자리를 포함해 0~34까지 칸이 있어야 한다.

  • 17: G의 인덱스 값일 뿐이며 H의 위치 34를 담지 못한다.
  • 18: G(인덱스 17)까지만 담는 크기로 H의 위치 34를 담지 못한다.
  • 34: 최대 인덱스 34를 담으려면 인덱스 0을 포함해 원소가 35개 필요하므로 하나 부족하다.

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

이어서 풀어보기

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