[9장 연습문제]
01. 정렬 알고리즘을 선택할 때 고려할 사항으로 거리가 먼 것은?
① 증가 데이터의 배열 상태 ② 키값의 분포 상태
③ 소요 공간 및 작업 시간 ➃ 정렬에 필요한 기억 공간의 크기
02. 다음 자료를 Selection Sorting으로 오름차순 정렬할 경우에 3Pass의 결과는?
① 3, 4, 7, 9, 8 ② 3, 4, 8, 9, 7
③ 3, 8, 4, 9, 7 ➃ 3, 4, 7, 8, 9
03. 다음 자료를 버블 정렬을 이용하여 오름차순으로 정렬할 경우 1Pass의 실행 결 과는?
① 3, 1, 4, 5, 2, 6, 7, 8 ② 1, 3, 4, 2, 5, 6, 7, 8
③ 4, 3, 1, 5, 7, 2, 6, 8 ➃ 1, 3, 2, 4, 5, 6, 7, 8
04. 정렬에 대한 설명으로 옳지 않은 것은?
① 배열에 저장되어 있는 자료를 정렬할 경우, 병합 정렬은 히프 정렬보다 메모리 공간을 더 필요로 한다.
② 병합 정렬로 n개 자료를 정렬할 때, 정렬된 입력이나 그렇지 않은 입력이나 걸
리는 시간은 항상 Θ(nlogn)이다.
③ 배열에 저장된 자료 n개를 정렬하는 선택 정렬에서 최악의 경우 자료 비교 횟수 는 Θ(n2)이고 최악의 경우 배열에서의 자료 이동 횟수도 Θ(n2)이다.
➃ 정렬된 입력에 대하여 퀵 정렬(첫 번째 원소를 기준으로 분할)은 히프 정렬보다
시간이 많이 걸린다.
05. 정렬에 대한 설명으로 옳지 않은 것은?
① 퀵 정렬은 스택을 이용해 수행한다.
② 셸 정렬은 최적의 경우에 선택 정렬보다 빠르다.
③ 히프 정렬은 배열을 이용한 포화 이진 트리를 사용한다.
➃ 데이터 열 개를 버블 정렬로 정렬하면 최대 45번의 비교 연산을 수행한다.
06. 최적, 최악의 경우에도 수행 시간이 O(nlog₂n)가 되는 정렬 알고리즘은?
① 힙 정렬 ② 퀵 정렬
③ 버블 정렬 ➃ 삽입 정렬
07. 다음 중 정렬 알고리즘에 대한 설명으로 옳은 것은?
① 선택 정렬과 힙 정렬 알고리즘의 시간 복잡도는 O(nlog)이다.
② 퀵 정렬과 합병 정렬은 분할 정복 방법을 사용하는 알고리즘이다.
③ 힙 정렬과 삽입 정렬은 안정적인 정렬 알고리즘이다.
➃ 최악의 경우 퀵 정렬의 성능은 O(nlogn)이다.
⑤ 선택 정렬과 버블 정렬은 제자리 정렬을 할 수 없다.
08. 주어진 파일에서 인접한 두 개의 레코드 키값을 비교하여 그 크기에 따라 레코 드 위치를 서로 교환하는 정렬 방식은?
① 선택 정렬 ② 삽입 정렬
③ 퀵 정렬 ➃ 버블 정렬
09. 다음 중 교환 방식의 정렬 방법이 아닌 것은?
① 선택 정렬 ② 삽입 정렬
③ 퀵 정렬 ➃ 버블 정렬
10. Internal sort에 해당하지 않는 것은?
① bubble sort ② balanced merge sort
③ quick sort ➃ radix sort
11. 다음 정렬 방식 중 공간 복잡도가 가장 큰 것은?
① 퀵 정렬 ② 병합 정렬
③ 선택 정렬 ➃ 버블 정렬
12. 비교가 아닌 분배에 의한 정렬 방식으로 옳은 것은?
① 기수 정렬 ② 버블 정렬
③ 퀵 정렬 ➃ 히프 정렬
13. 자료를 버블 정렬을 이용하여 오름차순으로 정렬할 경우 1회전 후의 결과는?
① 8, 5, 2, 4, 6 ② 2, 4, 5, 6, 8
③ 5, 6, 2, 4, 8 ➃ 8, 5, 6, 2, 4
14. 다음 자료를 선택 정렬을 이용하여 오름차순으로 정렬하고자 한다. 3회전 후의 결과로 옳은 것은?
① 14, 17, 37, 40, 35 ② 14, 37, 17, 40, 35
③ 17, 14, 37, 35, 40 ➃ 14, 17, 35, 40, 37
15. 정렬 알고리즘의 수행 시간을 Big-O 표기법으로 나타낼 때 최악의 경우에 수행 시간이 같은 것으로만 나열된 것은?
① 합병 정렬, 퀵 정렬, 힙 정렬
② 힙 정렬, 선택 정렬, 퀵 정렬
③ 합병 정렬, 선택 정렬, 삽입 정렬
➃ 합병 정렬, 힙 정렬, 삽입 정렬
⑤ 선택 정렬, 삽입 정렬, 퀵 정렬