[C로 배우는 쉬운 자료구조] 7장 연습문제 답안: 트리 (Tree)

 

 

[7장 연습문제]

 

분홍색으로 형광펜이 그어져 있는 문제는 틀린 문제이다

 

 

 

 

01. 트리에 대한 설명으로 옳은 것은?

 

① 루트 노드가 많은 트리일수록 좋은 트리이다.

② 트리와 관련된 알고리즘을 재귀적인 방식으로 구현하면 실행 시간이 빨라진다.

③ 트리의 최대 레벨과 트리 높이와는 무관하다.

④ 트리의 노드 중 차수(Degree)가 0인 노드를 리프(Leaf) 노드라고 한다.

 

 

 

 

 

02. 다음 그림에서 트리의 차수는?

① 1 ② 2 ③ 3 ④ 4

 

 

 

 

03. 다음 트리의 차수와 단말 노드의 수는?

① 차수: 4, 단말 노드: 4 ② 차수: 2, 단말 노드: 4

③ 차수: 4, 단말 노드: 8 ④ 차수: 2, 단말 노드: 8

 

 

 

 

 

 

 

 

 

04. 이진 트리로 구성하는 것이 불가능한 것은? (단, 루트 노드의 레벨은 1이라고 가정한다.)

① 노드 개수가 23개이고 높이가 5인 이진 트리

② 높이가 5이고 노드 개수가 10개이며 단말 노드 개수가 6개인 이진 트리

③ 노드 개수가 20개이고 간선이 19개인 이진 트리

④ 높이가 6이고 노드 개수가 32개인 완전 이진 트리

 

 

 

 

 

05. 다음 그림에서 트리의 차수는?

① 2 ② 3 ③ 4 ④ 5

 

 

 

 

 

06. 다음 그림에서 트리의 차수는?

① 2 ② 3 ③ 4 ④ 5

 

 

 

 

 

07. 이진 트리의 레벨 k에서 가질 수 있는 최대 노드 수는?

 

① 2k ② 2k－1

③ 2k＋1 ④ 22k＋1

 

 

 

 

 

08. n개의 노드를 가진 완전 이진 트리에 대한 설명으로 옳지 않은 것은? (단, 루트 노드의 높이는 1로 한다.)

① 단말(Terminal) 노드 개수는 비단말(Non-terminal) 노드 개수와 같거나 하나가 더 많다.

② 높이가 K라면 노드 개수 n의 범위는 K ≤n≤ 2K-1이다.

③ 포화 이진 트리는 완전 이진 트리의 일종이다.

④ 완전 이진 트리를 최악으로 구성할 경우 높이는 n이다.

 

 

 

 

 

09. 깊이가 k인 이진 트리가 가질 수 있는 최대 노드 수를 A라고 하고, 최소 노드 수를 B라고 할 때, A－B의 값은? (단, 루트 노드의 레벨은 1로 한다.)

 

① 2k-1 + k + 1 ② 2k-1 + k－1

③ 2k－k－1 ④ 2k－k + 1

 

 

 

 

 

 

 

10. 깊이가 k인 포화 이진 트리의 비단말 노드 개수에서 단말 노드 개수를 뺀 값으로 옳은 것은? (단, k > 0)

 

① －1 ② 0 ③ 1 ④ k－1

 

 

 

 

 

 

 

 

11. 이진 트리를 전위 순회와 중위 순회로 방문한 결과가 다음과 같다. 이 이진 트리를 후위 순회로 방문한 결과는?

 

① [GFEDCBA] ② [FEGDCBA]

③ [CBDGFEA] ④ [CDBGFEA]

⑤ [CDBFGEA]

 

 

 

 

 

 

12. 다음은 어떤 일반 트리를 이진 트리로 변환한 후의 모습이다. 이에 대한 설명으로 옳은 것은? (단, 일반 트리를 이진 트리로 변환할 때, 이진 트리의 왼쪽 노드는 일반 트리의 자식 중 하나를 가리키기 위해 사용되며, 이진 트리의 오른쪽 노드는 일반 트리의 형제들을 연결하기 위해 사용된다).

① 일반 트리에서 B의 자식 노드 개수는 2개이다.

② 일반 트리에서 C의 부모 노드는 B이다.

③ 일반 트리에서 노드 D에서 J까지 경로 길이는 4이다.

④ 일반 트리에서 단말 노드 개수는 7개이다.

 

 

 

 

 

 

 

13. 다음 트리를 후위 순회 방법으로 운행한 결과는?

 

① A B C E I F J D G H K L ② I E J F C G K L H D B A

③ A B C D E F G H I J K L ④ E I C F J B G D K H L A

 

 

 

 

 

14. 다음의 tree를 postorder로 traverse한 결과는?

DEBFHIGCA

 

 

 

 

 

 

 

15. 다음 트리를 전위 순회 방법으로 운행할 경우 가장 먼저 탐색되는 것은?

① A ② B ③ D ④ G

 

 

 

 

 

 

16. 다음 트리를 전위 순회한 결과는?

 

① + * A B / * C D E ② A B / C * D * E +

③ A / B * C * D + E ④ + * * / A B C D E

 

 

 

 

 

 

17. 다음 트리를 전위 순회로 운행한 결과는?

① A B D E C F G H I ② D B E F C H G I A

③ A B C D E F G H I ④ D E B F H I G C A

 

 

 

 

 

 

 

18. 다음 이진 트리를 전위 순회와 중위 순회를 했을 때, 두 순회 결과에서 노드값의 방문 순서가 일치하는 횟수는? (단, 전위 순회의 k번째 노드값과 중위 순회의 k번째 노드값이 같을 때, 일치하는 횟수를 1회로 한다.)

 

① 3회 ② 4회 ③ 5회 ④ 6회

 

 

 

 

 

 

19. 다음은 이진 트리의 후위 순회와 중위 순회 결과이다. 이 두 가지 순회 결과를 이용해 이진 트리를 구성한 것으로 옳은 것은?

 

 

 

 

 

 

 

 

 

 

 

1번

 

 

 

20. 다음과 같이 데이터 아홉 개를 순서대로 입력하여 생성한 이진 탐색 트리의 높이는? (단, 루트 노드의 레벨은 1이다.)

① 3 ② 4 ③ 5 ④ 6

 

 

 

 

 

21. 다음 재귀 함수는 이진 트리의 루트를 가리키는 포인터를 사용해 특정한 작업을 수행한다. 구체적으로 어떤 작업을 수행하는가?

 

① 트리의 루트를 중심으로 좌우 대칭 이동

② 트리의 루트를 중심으로 왼쪽 자식 트리를 오른쪽 자식 트리로 복사

③ 트리의 루트를 중심으로 왼쪽 자식 트리를 오른쪽 자식 트리로 이동

④ 트리의 루트를 중심으로 오른쪽 자식 트리를 왼쪽 자식 트리로 이동

 

 

 

 

22. 다음은 이진 탐색 트리에서 최소 키값을 가지는 노드에 대한 포인터를 반환하는 함수를 C 언어로 구현한 프로그램의 일부이다. ㉠과 ㉡에 들어갈 문장으로 바르게 나열된 것은?

㉠ ㉡

① return T; return T → Left;

② return T → Right; return T → Left;

③ return T; return FindMin(T → Left);

④ return FindMin(T → Right); return FindMin(T → Left);

 

 

 

 

23. 이진 탐색 트리 T에서 k보다 큰 키의 개수를 찾는 클래스 함수 numGreaterThan(T, k)을 작성한다고 가정하자. 트리에 포함된 모든 키는 다르고, 각 노드 x는 링크 필드인 left 및 right와 데이터 필드인 data를 가지며, 추가로 데이터 필드 하나인 numDesc를 포함한다. numDesc는 x를 루트로 하는 부분 트리에 포함된 모든 키의 개수로 초기화되어 있다. 다음 코드에서 밑줄 친 부분에 해당되는 문장은?

 

① T.right.numDesc - 1

② numGreaterThan(T.left, k) + 1

③ T.right.numDesc + numGreaterThan(T.left, k) - 1

④ T.right.numDesc + numGreaterThan(T.left, k) + 1

 

 

 

 

 

24. 다음은 빈 상태인 히프 배열에 1~8의 키 순서로 삽입이 이루어질 때, 히프가 형성되는 과정을 순서대로 나타낸 그림이다. 빈 칸에 알맞은 것은?

① (6 4 1 5 3 2), (8 7 6 4 3 2 5 1) ② (6 4 5 1 2 3), (8 7 6 4 3 5 2 1)

③ (6 4 5 1 3 2), (8 7 6 3 4 2 5 1) ④ (6 4 5 1 3 2), (8 7 6 4 3 2 5 1)

 

 

 

 

25. 우선순위 큐를 최대 히프로 구현하려 한다. 우선순위를 나타내는 데이터 아홉 개를 다음과 같은 순서로 큐에 삽입하였다. 데이터 한 개가 큐에서 삭제된 후, 재정렬된 히프에서 가장 마지막 원소는 무엇인가? (단, 숫자가 클수록 우선순위가 높다고 가정한다.)

① 17 ② 18 ③ 20 ④ 21

 

 

 

 

 

 

 

 

 

 

26. 다음 데이터들을 공백 히프에 차례대로 삽입하여 최대 히프를 생성하였다. 생성된 최대 히프에 삭제 연산을 두 번 수행한 후의 결과는?

1번

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

27. 다음 이진 트리에 대하여 후위 순회를 할 때 다섯 번째 방문하는 노드는?

 

① A ② C ③ D ④ F

 

 

 

 

 

28. 다음 트리가 모두 같은 수의 노드를 가지고 있을 때, 트리 높이가 가장 낮은 것은?

 

① 완전 이진 트리 ② 왼쪽 편향 이진 트리

③ 이진 탐색 트리 ④ AVL 트리

 

 

 

 

 

29. 다음 정수들을 순서대로 삽입하여 AVL 트리를 구성하였다. AVL 트리의 구성 과정 중에 사용된 회전 방법으로 옳은 것은?

 

① LL 회전, RR 회전, RL 회전 ② RR 회전, RL 회전

③ LL 회전, LR 회전 ④ LL 회전, LR 회전, RL 회전

 

 

 

 

 

 

30. 다음과 같이 정수 열네 개가 최대 히프를 표현하는 배열 1번 위치부터 14번 위치까지에 저장되어 있다. 이 배열에서 최댓값을 제거하는 연산을 세 번 수행한 후, 최대 히프의 1번 위치부터 11번까지의 위치에 저장되어 있는 수들을 올바르게 나열한 것은? (단, 제거 연산을 할 때 할 수 있다면 최대 히프 내용을 최소로 변경한다고 가정한다.)

 

① [72, 63, 62, 60, 52, 38, 37, 22, 16, 11, 5]

② [72, 52, 63, 38, 16, 60, 62, 37, 22, 11, 5]

③ [72, 52, 63, 16, 38, 60, 62, 11, 5, 37, 22]

④ [72, 52, 63, 16, 38, 60, 62, 5, 11, 37, 22]

 

 

 

 

 

 

 

 

31. 다음과 같은 키값을 갖는 데이터를 순서대로 삽입하여 AVL 트리를 구성했을 때, 각 키를 탐색하기 위한 평균 비교 횟수는?

 

① 14/6

 

 

 

 

 

 

 

32. 다음 데이터를 이용해 AVL 트리를 생성할 때, 설명으로 옳지 않은 것은?

 

① AVL 트리에서 7을 탐색하려면 비교를 네 번 해야 한다.

② AVL 트리의 루트값은 5이다.

③ 4가 삽입될 때, AVL 트리의 균형이 깨져 재구성이 발생한다.

④ 6은 리프 노드이다.

 

 

 

 

 

 

 

 

33. 노드가 스무 개인 이진 트리에서 간선 개수와 가능한 최대 높이와 최소 높이는?

19개, 최대20, 최소5

 

 

 

 

 

34. 다음 트리에 대하여 답하시오.

 

(가) 트리의 차수와 높이는?

차수, 높이 = 2

(나) 완전 이진 트리인지 아닌지를 설명하시오.

B의오른쪽 자식 노드가 비어있다. 완전 이진 트리가 아니다

(다) 중위 순회 경로는?

D B A E C F

(라) 후위 순회 경로는?

D B E F C A

 

 

 

 

 

35. 다음 원소를 공백 트리에 순서대로 삽입하여 만들어지는 트리에 대하여 답하시오.

 

(가) 이진 탐색 트리에 삽입하여 만들어지는 이진 탐색 트리를 설명하시오.

 

(나) AVL 트리에 삽입하여 만들어지는 AVL 트리를 설명하시오.

 

 

 

 

 

(다) 최대 히프에 삽입하여 만들어지는 최대 히프를 설명하시오.

최대 히프 : 99 80 65 59 78 25 52 23 49 7

(라) 최소 히프에 삽입하여 만들어지는 최소 히프를 설명하시오.

최소 히프 : 7 23 25 49 59 65 52 78 99 80

 

 

 

 

 

 

 

36. AVL 트리의 장점과 회전 연산에 대해 설명하시오.

왼쪽 자식 노드의 높이와 오른쪽 자식 노드의 높이가 비슷해 탐색 연산이 빠르다.