C 언어 함수로 구현된 <정렬 알고리즘>과 크기가 5인 배열… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 18년 1회차
C 언어 함수로 구현된 <정렬 알고리즘>과 크기가 5인 배열 list를 이용하여 sort(list, 5)를 수행하였다. <설명>에서 옳은 것만을 모두 고르면? (단, sort(list, 5) 수행 전에 list 배열에 4, 9, 8, 6, 3이 순서대로 저장되어 있다)<정렬 알고리즘>#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))
void sort(int list[ ], int n)
{
int i, j, least, temp;
for (i = 0; i < n - 1; i++) {
least = i;
for (j = i + 1; j < n; j++)
if (list[j] < list[least]) least = j;
SWAP(list[i], list[least], temp);
}
}<설 명>
ㄱ. sort(list, 5)의 수행이 완료될 때까지 SWAP은 4회 수행된다.
ㄴ. SWAP이 두 번째 수행된 후 배열 list에는 3, 4, 8, 6, 9가 순서대로 저장되어 있다.
ㄷ. 정렬 알고리즘의 시간 복잡도를 빅세타(Θ) 표기법으로 표현한 것은 Θ(nlogn)이다.
1
ㄱ
2
ㄱ, ㄴ
3
ㄱ, ㄷ
4
ㄴ, ㄷ
해설
옳은 것은 ㄱ, ㄴ이다. 이 코드는 매 단계 최솟값을 골라 앞자리와 교환하는 선택 정렬이다.
4, 9, 8, 6, 3 → (i=0, 최솟값 3) 3, 9, 8, 6, 4 → (i=1, 최솟값 4) 3, 4, 8, 6, 9 → (i=2, 최솟값 6) 3, 4, 6, 8, 9 → (i=3, 최솟값 8, 자기 자신과 교환) 3, 4, 6, 8, 9
- ㄱ(옳음): SWAP은 바깥 반복마다 조건 없이 한 번씩 수행되므로 회이다.
- ㄴ(옳음): 두 번째 SWAP 직후 배열은 3, 4, 8, 6, 9이다.
- ㄷ(틀림): 입력 상태와 관계없이 비교가 회 일어나므로 시간 복잡도는 이다.
오류나 개정된 내용이 보이면 알려주세요