완전 이진트리(complete binary tree)를 배열에 저장할 … | [7급 국가직 자료구조론] 13년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 13년 1회차
완전 이진트리(complete binary tree)를 배열에 저장할 때, 루트 노드를 배열 A[1]에 저장하고 나머지 노드들은 트리의 레벨순서에 따라 왼쪽에서 오른쪽으로 연속적으로 저장한다. 노드 A[k]와 관계된 노드를 찾는 규칙이 바르게 짝지어지지 않은 것은?
1
부모 노드 - A[⌊k/2⌋]
2
왼쪽 자식 노드 - A[2k]
3
오른쪽 자식 노드 - A[2k+1]
4
형제 노드 - A[k+1]
해설

형제 노드를 항상 A[k+1]로 찾는 규칙은 틀렸다.

k가 짝수면 왼쪽 자식이라 형제가 A[k+1]이지만, k가 홀수면 오른쪽 자식이라 형제는 A[k−1]이다(루트는 형제가 없다).

  • 부모 노드 − A[⌊k/2⌋]: 자식 2k와 2k+1을 2로 나눈 몫이 모두 k이므로 옳다.
  • 왼쪽 자식 노드 − A[2k]: 레벨순서 연속 저장의 정의대로 옳다.
  • 오른쪽 자식 노드 − A[2k+1]: 왼쪽 자식 바로 다음 칸이므로 옳다.

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

이어서 풀어보기

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