[2014년] C++ 자료구조 5주차 연습문제

목차

1. 트리의 정의를 쓰시오.
2. 다음 트리의 용어를 설명하시오.
3. 다음 트리를 보고 물음에 답하시오.
4. 위 트리를 차수가 2인 이진트리로 변환하시오.
5. 이진트리의 정의를 쓰시오.
6. 트리와 이진트리의 차이점을 쓰시오.
7. 깊이가 k인 포화이진트리(full binary tree)의 단말노드의 수는 ?
8. 이진트리에서 n0=n2+1의 관계가 성립함을 증명하시오.
9. 노드의 수가 30개인 완전이진트리의 높이를 구하시오.
10. 다음 이진트리를 보고 물음에 답하시오.
11. threaded binary tree의 목적을 쓰시오.
12. threaded binary tree를 만드는 방법을 쓰시오.
13. heap의 정의를 쓰시오.
14. 다음과 같은 키값들이 입력되는 경우 max heap을 만들어 배열에 저장된 상태를 그리시오.
15. 위 14번의 max heap에서 최대값이 두 번 삭제된 다음 재구성된 max heap이 저장된 상태를 그리시오.
16. 이진탐색트리의 정의를 쓰시오.
17. 이진탐색트리의 장단점을 쓰시오.
18. 위 14번의 키값들로 이진탐색트리를 만드시오.
19. 위 18번의 이진탐색트리에서 키값 15와 21을 삭제한 경우의 이진탐색트리를 그리시오. (삭제할 때 자노드가 2개이면 오른쪽 sub tree의 값으로 치환한다고 가정하시오)
20. 다음과 같은 7개의 런으로 만들어지는 승자선택트리가 배열에 저장된 상태를 그리시오.
21. 위 20번의 선택트리에서 킷값이 2개 출력된 다음의 선택트리를 그리시오.
22. 위 20번의 런으로 패자선택트리를 그리시오.
23. 위 22번의 패자선택트리에서 킷값이 2개 출력된 다음의 선택트리를 그리시오.
24. 트리를 이진트리로 변환하여 기억시키는 이유를 쓰시오.
25. 트리를 이진트리로 변환하는 방법을 쓰시오.
26. 다음 forest를 이진트리로 변환하시오.
27. 중위운행을 하면 a,b,c,d,e,f,g,h,i이고 후위운행을 하면 a,c,d,b,g,f,i,h,e인 이진트리를 그려라.
28. 노드가 5 개인 이진트리는 모두 몇 가지인가 ?

본문내용

1. 트리의 정의를 쓰시오.
정보의 항목들이 데이터가 조직으로 이루어지는 것을 말한다. 트리는 한 개 이상의 노드로 이루어진 유한 집합으로서 노드 중에는 루트라고 하는 노드가 존재하고 그 외 노드들은 0개 이상의 분리 집합으로 분할될 수 있다.

2. 다음 트리의 용어를 설명하시오.
1) 노드(node)
-한 정보에다가 다른 노드로 뻗어진 가지를 합함
2) 차수(degree)
-한 노드의 서브트리의 수
3) 자노드(child node)
-서브트리의 루트들
4) 단말노드(terminal node)
-차수가 0인 노드
5) 제노드(brother node)
-부모가 같은 자식들
6) 레벨(level)
-루트의 레벨은 1로 정의된다.
7) 트리의 차수(degree of tree)
-전체 서브트리의 수
8) 트리의 깊이(depth)
-그 트리에 속한 노드의 최대 레벨
9) 숲(forest)
-0개 이상의 분리트리들의 집합

참고자료

· 없음