<보기>에서 이진 트리(binary tree)의 성질에 대한… | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 자료구조론] 26년 1회차
<보기>에서 이진 트리(binary tree)의 성질에 대한 설명으로 옳은 것을 모두 고른 것은? (단, 트리의 높이는 루트 노드의 레벨을 1로 하여 계산한다.)
ㄱ. 총 nn개의 노드를 가진 이진 트리의 높이(hh)는 적어도 h≥⌈log⁡2(n+1)⌉h \ge \lceil \log_2(n+1) \rceil 이다.
ㄴ. 완전 이진 트리(complete binary tree)에서 모든 단말 노드는 항상 같은 레벨에 존재한다.
ㄷ. 이진 탐색 트리(binary search tree)의 삽입에 드는 점근적 시간은 검색에 드는 시간과 동일하다.
ㄹ. nn개의 노드를 가진 이진 탐색 트리의 점근적 평균 검색 시간은 Θ(n)\Theta(n)이다.
1
ㄱ
2
ㄱ, ㄷ
3
ㄴ, ㄹ
4
ㄱ, ㄷ, ㄹ
해설

옳은 것은 ㄱ, ㄷ이다.

높이 hh인 이진 트리의 최대 노드 수는 2h−12^h-1이므로 n≤2h−1n \le 2^h-1, 즉 h≥⌈log⁡2(n+1)⌉h \ge \lceil \log_2(n+1) \rceil이다. 이진 탐색 트리의 삽입은 탐색으로 자리를 찾은 뒤 상수 시간에 연결하므로 검색과 점근적 시간이 같다.

  • ㄴ: 완전 이진 트리는 마지막 레벨을 왼쪽부터 채우므로 단말 노드가 마지막 두 레벨에 걸쳐 있을 수 있다.
  • ㄹ: 이진 탐색 트리의 평균 검색 시간은 Θ(log⁡n)\Theta(\log n)이며, Θ(n)\Theta(n)은 한쪽으로 치우친 최악의 경우이다.

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

이어서 풀어보기

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