[7급 국가직 자료구조론 2007년 9번]

이진 탐색트리(binary search tree) T에서 k보다 큰 키들의 개수를 찾는 클래스 함수 numGreaterThan(T, k)을 작성한다고 가정하자. 트리에 포함된 모든 키들은 상이하고, 각 노드 x는 링크 필드인 left 및 right와 데이터 필드인 data를 가지며, 추가적으로 하나의 데이터 필드 numDesc를 포함한다. numDesc는 x를 루트(root)로 하는 부분 트리에 포함된 모든 키들의 개수로 초기화되어 있다. 아래 코드에서 밑줄 친 부분에 해당되는 문장은 무엇인가?
int numGreaterThan(T, k)
{
   if (T == NULL) return 0;
   else if (T.key <= k) return numGreaterThan(T.right, k);
   else return _________________________________;
}
자료구조론
  1. ①T.right.numDesc - 1
  2. ②numGreaterThan(T.left, k) + 1
  3. ③T.right.numDesc + numGreaterThan(T.left, k) - 1
  4. ④T.right.numDesc + numGreaterThan(T.left, k) + 1

선지를 골라 바로 채점해 보세요.

정답 ④

출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)

신고가 접수됐습니다. 감사합니다.

오류 신고