2018 7급 국가직 기출풀이 - 자료구조론 마형 12번

문제 풀이에 앞서,

안녕하세요. 자료구조론 문제풀이는 오랫만입니다.

오늘은 풀이과정을 따로 블로그 에디터 내에서는 쓰기 힘들어서

그림으로 대체됩니다. 항상 감사합니다.

---

문제

문12. 다음 이진 트리(binary tree)를 <보기>에서 제시한 방법을 사용하여 1차원 배열로 표현할 때, 필요한 배열의 최소 크기는? (단, 배열의 인덱스(index)는 0부터 시작하며 배열의 크기는 배열 원소의 개수이다)

[ 깨뱌 자체 제작 ]

<보기> * 루트 노드는 배열의 인덱스가 1인 위치에 저장한다. * 배열 인덱스가 k인 위치에 있는 노드가 자식 노드를 가질 경우, 왼쪽 자식 노드는 인덱스가 2k인 위치에 있으며 오른쪽 자식 노드는 인덱스가 2k+1인 위치에 있다.

 

① 17

② 18

③ 34

④ 35

---

정답

④번인 35

---

풀이전 기초

오늘은 따로 이론 설명은 없구요. 자주 까먹으실 수 있는 사실만 언급하고 가겠습니다.

배열의 시작은 인덱스가 0부터입니다.

그러나 문제에서는 루트노드가 인덱스 1을 가진다고 서술한 점을 인지하셔야 합니다.

---

풀이과정

[ 깨뱌 자체 제작 풀이과정 자료 ]

 

----> 보기에서 나온 그대로 계산을 하면 마지막 배열 인덱스는 34가 나옵니다.

그러나 문제에서 물어본 것은 배열의 크기! 임을 잊지 마시기 바랍니다.

따라서 인덱스의 번호가 아닌 배열의 크기인 35인 4번이 정답니다.

---

마치며...

오늘은 비교적 이해하기 쉬운 문제이나, 많이 헷갈리셨을 겁니다.ㅠㅠ

다들 함정에 속지말고 합격합시다. 감사합니다.