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

01 다음 초기 자료에 대하여 삽입 정렬(Insertion Sort)을 이용하여 오름차순 정렬한 경우 PASS 1의 결과는?

초기 자료 : 8, 3, 4, 9, 7

① 3, 4, 8, 7, 9

② 3, 4, 9, 7, 8

③ 7, 8, 3, 4, 9

④ 3, 8, 4, 9, 7

 

02 다음 자료를 버블 정렬을 이용하여 오름차순으로 정렬할 경우 PASS 1의 결과는?

9, 6, 7, 3, 5

① 3, 5, 6, 7, 9

② 6, 7, 3, 5, 9

③ 3, 5, 9, 6, 7

④ 6, 3, 5, 7, 9

 

03 다음 자료에 대하여 "선택 정렬"을 사용하여 오름차순으로 정렬할 경우 PASS 3의 결과는?

초기 상태 : 8, 3, 4, 9, 7

① 3, 4, 7, 9, 8

② 3, 4, 8, 9, 7

③ 3, 8, 4, 9, 7

④ 3, 4, 7, 8, 9

 

04 다음은 배열 A에 저장된 n개의 정수를 오름차순으로 정렬하는 삽입 정렬 (insertion sort) 알고리즘이다. ㉠과 ㉡에 순서대로 들어갈 내용으로 옳은 것은?

void sort(int A[], int n)
{
	int i, j, key;
    for(i=1; i<n; i++){
    	key=A[i];
        for (j=i-1; ㉠;j--)
        	 ㉡
        A[j+1]=key;
    }
}

            ㉠                                  ㉡

① j>=0&&key>A[j]           A[j+1]=A[j];

② j>0&& key>=A[j]          A[j-1]=A[j];

③ j>0 && key<A[j]           A[j]=A[j+1];

④ j>=0 && key<A[j]         A[j+1]=A[j];

 

05 다음의 정렬기법을 이용하여 다음의 정수 배열을 오름차순으로 정렬하라. 각 단계에서의 배열의 내용을 나타내어라.

7

4

9

6

3

8

7

5

(1) 선택 정렬

(2) 삽입 정렬

(3) 버블 정렬

(4) 쉘 정렬

 

06 다음의 정렬기법을 이용하여 다음의 정수 배열을 오름차순으로 정렬하라. 각 단계에서의 배열의 내용을 나타내어라.

71

49

92

55

38

82

72

53

(1) 퀵 정렬

(2) 합병 정렬

(3) 히프 정렬

 

07 다음과 같은 입력 배열을 퀵 정렬을 이용하여 정렬할 때, 피봇을 선택하는 방법을 다르게 하여 각 단계별 내용을 나타내어라.

 

1

2

3

4

5

6

7

8

(1) 왼쪽 첫 번째 요소를 피봇으로 하는 방법

(2) 왼쪽, 중간, 오른쪽 가운데 중간값(median of three) 방법

 

08 퀵정렬에서 함수가 수행되면서 정렬의 매 패스마다 다음과 같은 형식으로 화면에 출력하도록 함수를 수정하여 보라.

67  90  57  25  84  32  73  54

      low                                   high

67  54  57  25  84  32  73  90

                          low       high

67  54  57  25  73  32  84  90

                         low high

67  90  57  25  32  73  84  54

                         high low                 

32  90  57  25  67  73  73  54

                        high  low          

 

09 다음 중 안정적인 정렬 방법이 아닌 것은 무엇인가?

(1) 삽입 정렬

(2) 선택 정렬

(3) 히프 정렬

(4) 쉘 정렬

 

10 다음 중 삽입 정렬이 가장 효율적으로 적용될 수 있는 때는?

(1) 역순으로 정렬되어 있다.

(2) 어느 정도 정렬이 되어있다.

(3) 레코드들의 크기가 클 때

(4) 메모리 공간이 여유가 있을 때

 

11 퀵 정렬을 이용하여 다음의 정수 배열을 정렬하고자 한다.

5

7

4

9

8

5

6

3

(a) 첫 번째 분할이 끝난 후의 배열의 내용을 나타내라.

(b) 이 첫 번째 분할에서 몇 번의 비교연산이 수행되었는가?

(c) 분할이 이루어지면 피봇값은, 피봇값보다 더 작은 서브배열과 피봇값보다 더 큰 서브배열, 2개의 서브 배열의 중간에 위치하게 된다. 이 피봇값의 위치는 다음 단계가 진행되었을 때 변경이 되는가 아니면 되지 않는가? 그 이유는?

(d) 첫 번째 분할 다음에 호출되는 순환호출들은 무엇인가?

 

12 다음의 정수 배열을 기수 정렬을 이용하여 정렬하고자한다. 기수 정렬의 각 단계를 보여라

123

398

210

409

528

003

513

129

220

294

 

13 삽입 정렬의 코드를 수정하여 숫자가 아니고 레코드를 삽입 정렬하는 프로그램을 구성해보자. 즉 정렬이 되는 단위가 숫자가 아니고 레코드이다. 먼저 레코드를 표현하기 위해 다음과 같은 구조체를 사용한다. 실무와 연관된 실제 프로그램들은 대부분 레코드를 정렬하여야 함을 기억해두길 바란다.

 

typedef struct /*레코드를 정의하기 위한 구조체*/
{
	int key;
    char name[NAME_SIZE];
} record;

 

14 삽입 정렬의 코드를 수정하여 삽입 정렬의 각 단계를 출력하도록 하라. 아래 그림에서 왼쪽 괄호 안에 있는 숫자는 정렬이 되어 있는 숫자들이다. 오른쪽은 정렬을 해야 할 숫자들이다. 삽입정렬의 단계에서 다음과 같이 출력하도록 insertion_sort 함수를 수정하라. 이를 위하여 사용자로부터 숫자들을 입력받을 수 있도록 하라

()                            (17, 9, 21, 6, 3, 12)

(17)                        ( 9, 21, 6, 3, 12)       17삽입

(9,17)                     ( 21, 6, 3, 12)       9삽입

(9,17,21)                 ( 6, 3, 12)       21삽입

(6,9,17,21)              ( 3, 12)       6삽입

(3,6,9,17,21)            (12)       3삽입

(3,6,9,12,17,21)       ()          12삽입

 

15 삽입 정렬에서 입력과 출력이 모두 동적 연결 리스트로 주어지는 경우의 삽입 정렬 함수를 구현하라.

 

16 선택 정렬의 코드를 수정하여 선택 정렬의 각 단계를 출력하도록 하라. 아래 그림에서 왼쪽 괄호 안에 있는 숫자는 정렬이 되어 있는 숫자들이다. 오른쪽은 정렬을 해야 할 숫자들이다. 선택 정렬의 단계에서 다음과 같이 출력하도록 selection_sort 함수를 수정하라. 이를 위하여 사용자로부터 숫자들을 입력받을 수 있도록 하라.

()                            (17,9,21,6,3,12)

(3)                        (9,21,6,17,12)       3선택 후 17과 교환

(3,6)                     (21,9,17,12)       6선택 후 9와 교환

(3,6,9)                 (21,17,12)       9선택 후 21과 교환

(3,6,9,12)              (17,21)      12선택 후 21과 교환

(3,6,9,12,17)            (21)       17선택 후 17과 교환

(3,6,9,12,17,21)       ()          21선택 후 21과 교환

 

17 재귀 호출을 추적하기 위하여 quick_sort() 함수가 호출될 때마다 함수 이름과 인수의 값을 화면에 출력하라.

quick_sort(0,99)

quick_sort(0,50)

quick_sort(0,25)

...

quick_sort(0,1)

...

 18 퀵정렬함수인 quick_sort함수에서 피봇 값을 결정할 때, 부분 리스트의 첫 번째, 중간, 마지막 키 중 중간 값을 사용하면 성능이 향상된다. quick_sort 함수가 이와 같은 3-중간값(median of three) 방법을 사용하도록 수정하여라. median{10,5,7}=7 이 된다.

 

19 합병정렬에서의 재귀 호출을 추적하기 위하여 함수 merge_sort가 호출되면 함수 이름과 인수의 값을 화면에 출력하게 변경하여보라. 예측한 것처럼 출력되는지를 확인하라.

 

20 히프 정렬이 진행되는 모습을 좀 더 이해하기 쉽게 화면에 출력하여보라. 즉 히프 정렬이 진행되는 동안의 list[] 배열의 내용을 출력하여 보라. 이미 정렬이 끝난 숫자들과 정렬중인 숫자를 분리하여 표시하여 보라.

숫자의 개수: 10
41 67 34 0 69 24 78 58 62 64

69 67 41 62 64 24 34 58 0 [78]
67 64 41 62 0 24 34 58 [69 78]
64 62 41 58 0 24 34 [67 69 78]
62 58 41 34 0 24 [64 67 69 78]
58 34 41 24 0 [62 64 67 69 78]
41 34 0 24 [58 62 64 67 69 78]
34 24 0 [41 58 62 64 67 69 78]
24 0 [34 41 58 62 64 67 69 78]
0 [24 34 41 58 62 64 67 69 78]
[0 24 34 41 58 62 64 67 69 78]

정렬된 배열 :
0 24 34 41 58 62 64 67 69 78

21 기수 정렬 프로그램에서 다음과 같이 각 버킷의 내용을 화면에 출력하는 함수 print_bucket() 를 프로그램에 추가하라

==========
[0]->0
[1]->
[2]->62
[3]->
[4]-> 64  24 34
[5]->
[6]->
[7]
[8]->58 78
[9]->69
==========