편집복원내용 검수 완료2024년 정보처리기사 2회 필기 · 데이터베이스 구축 · 47번

완전 이진 트리를 1번부터 시작하는 배열로 저장한다. 배열 인덱스 14에 있는 노드의 부모 인덱스는?

1-based 배열 표현에서 노드 i의 부모는 floor(i/2)이다.

ITPASSLAB 재구성 문제 자료

1
6
오답 이유12와 13의 부모는 6이지만 14의 부모는 7이다.
2
7
정답 근거floor(14/2)=7이므로 인덱스 7의 노드가 14번 노드의 부모다.
3
13
오답 이유13은 14의 직전 배열 원소일 뿐 부모 위치가 아니다.
4
28
오답 이유1-based 배열에서 28은 14번 노드의 왼쪽 자식 인덱스(2×14)다. 부모를 찾을 때는 반대로 floor(14/2)를 적용해야 한다.

정답·상세해설

정답 2번

배열 기반 완전 이진 트리에서는 부모와 자식 위치를 산술식으로 계산한다. 14를 2로 나눈 몫이 7이므로 부모 인덱스는 7이다.

콘텐츠 기록