이진 탐색트리(binary search tree) T에서 k보다 큰 키… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 07년 1회차
이진 탐색트리(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
해설

빈칸에는 T.right.numDesc + numGreaterThan(T.left, k) + 1이 들어간다.

T.key > k이면 오른쪽 부분 트리의 키는 모두 T.key보다 커서 그 개수 numDesc가 전부 포함되고, T 자신도 1개로 더해진다. 왼쪽 부분 트리는 k보다 큰 키가 일부만 있을 수 있어 재귀로 센다.

  • 오른쪽 부분 트리 개수에서 1만 빼는 식: 루트와 왼쪽 부분 트리를 모두 빠뜨린다.
  • 왼쪽 재귀 결과에 1만 더하는 식: 오른쪽 부분 트리 전체를 빠뜨린다.
  • 오른쪽 개수와 왼쪽 재귀 결과에서 1을 빼는 식: 루트 T를 더해야 할 자리에서 오히려 1을 뺀다.

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

이어서 풀어보기

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