[C언어로 쉽게 풀어쓴 자료구조] 13장

01 이진 탐색 알고리즘의 특징이 아닌 것은?

① 탐색 효율이 좋고 탐색 시간이 적게 소요된다.

② 검색할 데이터가 정렬되어 있어야 한다.

③ 피보나치 수열에 따라 다음에 비교할 대상을 선정하여 검색한다.

④ 비교를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어든다.

 

02 키 값 28을 가지고 아래의 리스트를 탐색할 때 다음의 탐색 방법에 따른 탐색 과정을 그리고 탐색 시에 필요한 비교 연산 횟수를 구하여라.

0            1            2           3           4          5            6          7           8            9         10          11         12         13        14         15

8

11

12

15

16

19

20

23

25

28

29

31

33

35

38

40

(1) 순차 탐색

(2) 이진 탐색

(3) 보간 탐색

 

03 AVL 트리에서 회전은 언제 이루어지는가?

(1) 삽입 전

(2) 삽입 후

(3) 탐색 중

(4) 탐색 후

 

04 정렬된 100,000,000개의 원소가 있다. 이진 탐색 알고리즘을 사용했을 때 최악의 경웨 대하여 비교 횟수를 구하라.

 

05 데이터(60, 50, 20, 80, 90, 70, 55, 10, 40 , 35)를 차례대로 삽입하면서 다음과 같은 균형트리를 구축하는 과정을 그림으로 설명하고 이들 3가지 트리를 사용한 결과를 서로 비교하라.

(a) 이진탐색트리

(b) AVL 트리

(c) 2-3 트리

 

06 데이터 (10,20,30,40,50,60,70, 80, 90, 100)를 차례대로 삽입했을 때의 결과 트리를 그려라. 어떤 트리가 탐색을 가장 효율적으로 수행하는가?

(a) 이진탐색트리

(b) AVL트리

(c) 2-3 트리

 

07 난수발생기를 이용하여 1부터 n까지의 정수를 생성하라. 이들 정수를 공백 상태의 AVL 트리에 차례대로 넣어서 생성되는 트리의 높이를 측정한다. 이 실험을 서로 다른 난수들의 집합에 대하여 되풀이하여 평균적인 높이를 계산하라. 이 값을 2⎡log₂(n+1⎤와 비교하라. n=100; 500; 1000; 10,000; 50,000이라고 가정하라.

 

08 이진 탐색 트리는 숫자를 정렬시키는데 이용이 가능하다. 배열 a[]에 저장된 n개의 정수를 받아서 비어있는 이진탐색트리에 삽입하고 중위 순회 순서대로 다시 배열에 넣으면 정렬된 숫자를 얻을 수 있다. 간단하게 하기 위하여 배열에 들어있는 값은 중복되지않았다고 가정하라. 이 정렬 방법을 구현하고 이 방법의 시간 복잡도를 삽입 정렬과 히프 정렬과 비교하라.

 

09 탐색키가 정수가 아닌 알파벳으로 되어있는 경웨 공백 트리에서 시작하여 다음과 같은 순서로 AVL 트리에 삽입될 때, 각 단계에서 회전의 유형을 표시하라. 

Dec, Jan, Apr, Mar, July, Aug, Oct, Feb, Sept, Nov, June, May