게임알고리즘 14주차 - 기말 시험

A. 1부터 100까지의 정수가 오름차순으로 저장되어 있는 배열(S)이 있을 때, 배열 S에서 정수 99를 찾고자 한다. 
다음의 주어진 문제를 푸시오 (총 4문제)

 

1. 위 배열 S에서 순차탐색알고리즘을 이용하여 99를 찾을 때까지의 비교횟수는 얼마인가?
그리고 그 이유는 무엇인가?


2. 위 배열 S에서 이진탐색알고리즘을 이용하여 99를 찾고자 한다. 이진탐색알고리즘을 이용한 탐색 과정을 순서대로 기술하시오 (99를 찾을 때까지의 index 계산과정을 순서대로 작성합니다.)



3. 위의 배열 S에서 선형보간탐색알고리즘을 이용하여 99를 찾을 때 탐색 과정을 순서대로 작성하시오.

(99을 찾을 때까지의 index 계산과정을 순서대로 작성합니다.)

 

4. 위에서 배열 S에서 값 99를 찾을 때까지의 순차탐색알고리즘, 이진탐색알고리즘, 선형보간탐색알고리즘의 비교 횟수는 각각 몇 회인가? 아래 빈칸을 채우시오.

 

B. 다음은 순차탐색알고리즘, 이진탐색알고리즘, 선형보간탐색알고리즘의 효율성에 대한 내용이다.
주어진 각 문제를 푸시오 (총 4문제)

 

5. 각 탐색 알고리즘의 평균탐색시간 복잡도를 빅오(O)로 쓰시오.
총 데이터 갯수가 N일때, 아래 빈칸을 채우시오. (주의사항 : 답은 공백(space) 없이 작성합니다)

 

6. 순차탐색알고리즘의 복잡도가 위의 결과가 나온 이유를 간단히 설명하시오.



7. 이진탐색알고리즘의 복잡도가 위의 결과가 나온 이유를 간단히 설명하시오.



8. 선형보간탐색알고리즘의 복잡도가 위의 결과가 나온 이유를 간단히 쓰시오.



C. 정수를 키 값으로 갖는 노드들로 이루어진 힙트리를 구성하고자 한다.
큰 정수 값이 우선순위가 높으며, 키 입력 순서가 다음과 같을 때 아래 물음에 답하시오. (총 4문제)

 

키 입력 순서 : 
     20 -> 15 -> 10 -> 7 -> 50 -> 5 -> 13 -> 11 -> 8 -> 100 -> 18 -> 1 -> 30

 

 

9. 다음 중 힘트리에 대한 설명으로 틀린 것은 ? 하나를 선택하세요.
1. 우선 순위가 높은 키 값은 항상 루트(root) 노드에 위치한다.
2. 힙트리는 우선순위가 가장 높은 값(최대값 또는 최소값)을 빠르게 찾을 수 있도록 고안된 포화이진트리구조이다.
3. 힙 트리에 데이터를 삽입할 때의 복잡도는 O(lg N)을 보장한다.
4. 힙 트리에서 데이터를 추가하거나 삭제할 때마다 힙을 재구성(rebuilding) 해야 한다.
5. 힙의 데이터가 배열에 저장되어 있을 경우, 인덱스 k의 오른쪽 자식 노드의 위치는 (2k+2) 이다.

10. n개의 데이터로 구성된 힙 트리에서 모든 노드를 제거하면서  힙을 재구성(rebuilding)할 때의 효율을 O(big o)로 나타내면 ?

 

 

11. 위의 키 값을 차례대로 추가할 때 힙 트리를 구성하는 과정을 그림으로 나타내시오

 

키 입력 순서 : 
     20 -> 15 -> 10 -> 7 -> 50 -> 5 -> 13 -> 11 -> 8 -> 100 -> 18 -> 1 -> 30
답안은 1개 파일로 업로드합니다.
결과는 첨부파일로 제출합니다.

 

12. 위에서 구성한 힙트리에서 root 노드를 제거할 때 힙을 재구성(rebuilding) 하는 과정을 그림으로 설명하시오.
결과는 첨부파일로 첨부합니다.

 

 

D. 정수를 키 값으로 갖는 노드들로 이루어진 트리를 구성하고자 한다.

키 입력 순서가 다음과 같을 때 아래 물음에 답하시오. (총 5문제

 

키 입력 순서 : 
     20 -> 15 -> 10 -> 7 -> 50 -> 5 -> 13 -> 11 -> 8 -> 100 -> 18 -> 1 -> 30

 

13. 위의 키 값을 순서대로 입력받아 구성한 최종 이진탐색트리를 나타내시오.
결과는 첨부파일로 제출합니다.

 

 

14. 최종 구성된 이진탐색트리에서 아래의 키 값을 차례대로 삭제했을 때의 최종 이진탐색트리를 나타내시오
삭제순서 : 1 -> 10 -> 20 -> 15 -> 50
결과는 첨부파일로 제출합니다.

 

15. 문제에서 주어진 키 값을 순서대로 입력받아 AVL 트리를 구성하시오.
이 때, 트리의 회전이 필요할 때마다 각 노드의 Balance factor를 표시합니다.
또한, 회전을 실시하는 서브트리를 별도로 표시하고 회전과정을 간단하게 설명합니다.
회전 후에는 그 때까지 구성된 트리를 별로도 나타냅니다.

 

키 입력 순서 :
20 -> 15 -> 10 -> 7 -> 50 -> 5 -> 13 -> 11 -> 8 -> 100 -> 18 -> 1 -> 30
결과는 첨부파일로 제출합니다. (첨부파일 1개로 정리하여 첨부)




16. 문제에서 주어진 키 값을 순서대로 입력받아 2-3트리를 구성합니다.
이 때, Rebuilding할 때마다 각 과정을 간단하게 설명하고, 그 때까지 구성된 트리를 별도로 나타냅니다.

키 입력 순서 : 
   20 -> 15 -> 10 -> 7 -> 50 -> 5 -> 13 -> 11 -> 8 -> 100 -> 18 -> 1 -> 30
결과는 첨부파일로 제출합니다. (파일 1개로 정리하여 제출)

 

 

17. 문제에서 주어진 키값을 순서대로 입력받아 node coloring 방법을 이용하여 Red-Black 트리를 구성합니다.
이 떄, 각 단계마다 노드의 색깔을 표시해야 한다.

또한, Red-Black 트리의 속성을 위반할 때마다 트리를 재구성하는 과정을 설명하고,
재구성 후 그 때까지 구성된 트리를 별도로 나타낸다.

키 입력 순서 : 
   20 -> 15 -> 10 -> 7 -> 50 -> 5 -> 13 -> 11 -> 8 -> 100 -> 18 -> 1 -> 30
결과는 첨부파일로 제출합니다.(파일은 1개로 정리하여 제출합니다.)