자료구조 11장 연습문제 풀이

1. 다음의 자료들을 정렬하여라.

34, 27, 19, 51, 8, 24, 11

① 선택 정렬을 사용하여 정렬하여라.

8-27-19-51-34-24-11

8-11-19-51-34-24-27

8-11-19-51-34-24-27

8-11-19-24-34-51-27

8-11-19-24-27-51-34

8-11-19-24-27-34-51

 

② 버블 정렬을 사용하여 정렬하여라.

(34, 27)-19-51-8-24-11

27-(34, 19)-51-8-24-11

27-19-(34, 51)-8-24-11

27-19-34-(51, 8)-24-11

27-19-34-8-(51, 24)-11

27-19-34-8-24-(51, 11)

27-19-34-8-24-11-51

 

(27, 19)-34-8-24-11-51

19-(27, 34)-8-24-11-51

19-27-(34, 8)-24-11-51

19-27-8-(34, 24)-11-51

19-27-8-24-(34, 11)-51

19-27-8-24-11-34-51

 

(19, 27)-8-24-11-34-51

19-(27, 8)-24-11-34-51

19-8-(27, 24)-11-34-51

19-8-24-(27, 11)-34-51

19-8-24-11-27-34-51

 

(19, 8)-24-11-27-34-51

8-(19, 24)-11-27-34-51

8-19-(24, 11)-27-34-51

8-19-11-24-27-34-51

 

(8, 19)-11-24-27-34-51

8-(19, 11)-24-27-34-51

8-11-19-24-27-34-51

 

(8, 11)-19-24-27-34-51

8-11-19-24-27-34-51

 

③ 삽입 정렬을 사용하여 정렬하여라.

34-(27, 19, 51, 8, 24, 11)

27-34-(19, 51, 8, 24, 11)

19-27-34-(51, 8, 24, 11)

19-27-34-51-(8, 24, 11)

8-19-27-34-51-(24, 11)

8-19-24-27-34-51-(11)

8-11-19-24-27-34-51

 

④ 병합 정렬을 사용하여 정렬하여라.

⑤ 퀵 정렬을 사용하여 정렬하여라.

pivot = 51

34 - 27 - 19 - 11 - 8 - 24 - 51

 

pivot = 19

8 - 27 - 19 - 11 - 34 - 24 - 51

8 - 11 - 19 - 27 - 34 - 24 - 51

 

pivot = 8

8 - 11 - 19 - 27 - 34 - 24 - 51

 

pivot = 34

8 - 11 - 19 - 27 - 24 - 34 - 51

 

pivot = 27

8 - 11 - 19 - 24 - 27 - 34 - 51

 

⑥ 힙 정렬을 사용하여 정렬하여라.

⑦ 트리 정렬을 사용하여 정렬하여라.

중위 순회 -> 8 - 11 - 19 - 24 - 27 - 34 - 51

 

⑧ 셸 정렬을 사용하여 정렬하여라.

interval = 3

11 - 8 - 19 - 34 - 27 - 24 - 51

 

interval = 1

8 - 11 - 19 - 24 - 27 - 34 - 51

 

⑨ 기수 정렬을 사용하여 정렬하여라.

51 - 11 - 34 - 24 - 27 - 8 - 19

8 - 11 - 19 - 24 - 27 - 34 - 51

 

 

 

2. 정렬 방법 중에서 별도의 메모리가 추가로 필요한 정렬 방법은 무엇인가?

 

답 : 기수 정렬

 

 

 

3. 큐를 사용하는 정렬 방법은 무엇인가? 그리고 큐를 사용하는 이유는 무엇인가?

 

답 : 기수 정렬

? : FIFO 방식을 채택해야 하기 때문이다.

 

 

 

4. 정렬 알고리즘 선택 시 고려사항으로 거리가 먼 것은?

가. 증가 데이터의 배열 상태

나. 키값들의 분포 상태

다. 소요 공간 및 작업 시간

라. 정렬에 필요한 기억공간의 크기

 

답 : 가. 증가 데이터의 배열 상태

? : 정렬 알고리즘 선택 시 고려사항은 다음과 같다.

ㆍ키값들의 분포 상태

ㆍ소요 공간 및 작업 시간

ㆍ정렬에 필요한 기억공간의 크기

ㆍ데이터의 양

ㆍ초기 데이터의 배열 상태

ㆍ사용 컴퓨터 시스템의 특성

 

 

 

5. 자료가 다음과 같이 주어졌다고 하자. 선택 정렬을 적용하여 오름차순으로 정렬할 경우 2단계를 진행한 후의 정렬 상태는?

9, 4, 5, 11, 8

가. 4, 5, 9, 8, 11

나. 4, 5, 9, 11, 8

다. 4, 5, 8, 11, 9

라. 4, 5, 8, 9, 11

 

답 : 나. 4, 5, 9, 11, 8

? : 

4 - 9 - 5 - 11 - 8

4 - 5 - 9 - 11 - 8

4 - 5 - 8 - 11 - 9

4 - 5 - 8 - 9 - 11

이므로 답은 나

 

 

 

6. 인접한 데이터를 비교하면서 그 크기에 따라 데이터의 위치를 바꾸어 정렬하는 방법은?
가. 퀵 정렬    나. 힙 정렬    다. 셸 정렬    라. 버블 정렬

 

답 : 라. 버블 정렬

 

 

 

7. 삽입정렬을 사용하여 다음의 자료를 오름차순으로 정렬하고자 한다. 3회전 후의 결과는?

5, 4, 3, 2, 1

가. 2, 3, 4, 5, 1

나. 4, 5, 3, 2, 1

다. 3, 4, 5, 2, 1

라. 1, 2, 3, 4, 5

 

답 : 다. 3, 4, 5, 2, 1

? : 

5 - (4, 3, 2, 1)

4 - 5 - (3, 2, 1)

3 - 4 - 5 - (2, 1)

이므로 답은 다

 

 

 

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

9, 6, 7, 3 ,5

가. 3, 5, 6, 7, 9

나. 6, 7, 3, 5, 9

다. 6, 3, 5, 7, 9

라. 3, 5, 9, 6, 7

 

답 : 다. 6, 3, 5, 7, 9

? :

(9, 6)-7-3-5

6-(9, 7)-3-5

6-7-(9, 3)-5

6-7-3-(9, 5)

6-7-3-5-9

 

(6, 7)-3-5-9

6-(7, 3)-5-9

6-3-(7, 5)-9

6-3-5-7-9

이므로 답은 다