주어진 정수 배열 {26, 13, 77, 61, 35, 11, 8, 4… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 19년 1회차
주어진 정수 배열 {26, 13, 77, 61, 35, 11, 8, 48, 15, 19}에 대한 합병 정렬(merge sort)의 순환 알고리즘(recursive algorithm)을 다음과 같이 구현하였다. 이 프로그램의 수행 과정에서 형성되는 배열의 순서로 옳지 않은 것은?
#include <stdio.h>
#define MAX 10
void merge( int list[], int temp[], int left,
int middle, int right)
{
int i=left, j=middle+1, k=left, t;
for( ; i <= middle && j <= right ; ) {
if( list[i] <= list[j] )
temp[k] = list[i++];
else
temp[k] = list[j++];
k += 1;
}
if( i > middle ) {
for( t = j ; t <= right ;)
temp[k++] = list[t++];
} else {
for( t = i ; t <= middle ;)
temp[k++] = list[t++];
}
for( t = left ; t <= right ; t++ )
list[t] = temp[t];
}

void mergeSort( int list[], int temp[], int left,
int right)
{
int middle = 0;
if( left < right ) {
middle = (left+right)/2;
mergeSort(list, temp, left, middle);
mergeSort(list, temp, middle+1, right);

merge(list, temp, left, middle, right);
}
}

int main(){
int source[10]={26, 13, 77, 61, 35, 11, 8,
48, 15, 19};
int temp[10] = {0x0,};

mergeSort(source, temp, 0, 9);
}
1
13, 26, 35, 61, 77, 11, 8, 48, 15, 19
2
13, 26, 77, 61, 35, 11, 8, 48, 15, 19
3
13, 26, 35, 61, 77, 8, 11, 15, 19, 48
4
13, 26, 35, 61, 77, 8, 11, 15, 48, 19
해설

수행 중 나타나지 않는 배열은 13, 26, 35, 61, 77, 8, 11, 15, 48, 19이다.

mergeSort(0, 9)는 왼쪽 구간 [0..4]를 먼저 끝까지 정렬한 뒤 오른쪽 구간 [5..9]를 처리한다.
[0..2] 병합 후: 13, 26, 77, 61, 35, 11, 8, 48, 15, 19
[0..4] 병합 후: 13, 26, 35, 61, 77, 11, 8, 48, 15, 19
[5..7] 병합 후: 13, 26, 35, 61, 77, 8, 11, 48, 15, 19
[5..9] 병합 후: 13, 26, 35, 61, 77, 8, 11, 15, 19, 48

[8..9]의 15, 19는 병합해도 순서가 그대로이고, 마지막 병합에서 8, 11, 48과 15, 19가 한 번에 합쳐지므로 48이 19 앞에 남은 상태는 생기지 않는다.

  • 13, 26, 77, 61, 35, 11, 8, 48, 15, 19는 [0..2] 병합 직후 상태이다.
  • 13, 26, 35, 61, 77, 11, 8, 48, 15, 19는 [0..4] 병합 직후 상태이다.
  • 13, 26, 35, 61, 77, 8, 11, 15, 19, 48은 [5..9] 병합 직후 상태이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 19년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기