1과 1000 사이의 정수로 구성된 이진 탐색 트리(binary sea… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 17년 1회차
1과 1000 사이의 정수로 구성된 이진 탐색 트리(binary search tree)에서 숫자 629를 탐색한다고 할 때, 옳지 않은 비교 순서는?
1
19, 929, 172, 891, 224, 735, 405, 674, 537, 629
2
876, 807, 24, 186, 314, 717, 690, 428, 512, 629
3
29, 829, 815, 137, 369, 504, 805, 589, 692, 629
4
926, 87, 813, 318, 572, 826, 635, 598, 580, 629
해설

옳지 않은 비교 순서는 926, 87, 813, 318, 572, 826, …으로 이어지는 순서이다.

이진 탐색 트리에서는 비교할 때마다 탐색 범위가 좁아지므로, 이후 비교되는 값은 항상 지금까지의 하한과 상한 사이에 있어야 한다.

  • 926, 87, 813, … 순서: 629가 813보다 작아 왼쪽으로 내려갔으므로 이후 값은 813보다 작아야 하는데 826이 나와 모순이다.
  • 19, 929, 172, … 순서: 범위가 (19, 929) → (172, 929) → (172, 891) → … → (537, 674)로 일관되게 좁아져 가능하다.
  • 876, 807, 24, … 순서: 범위가 (24, 807) → … → (512, 690)으로 좁아지며 모든 값이 범위 안에 있어 가능하다.
  • 29, 829, 815, … 순서: 범위가 (29, 815) → … → (589, 692)로 좁아지며 모순이 없어 가능하다.

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

이어서 풀어보기

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