정렬(sort)에 대한 설명으로 옳지 않은 것은? | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 12년 1회차
정렬(sort)에 대한 설명으로 옳지 않은 것은?
1
퀵정렬(quick sort)은 스택을 이용하여 수행한다.
2
쉘정렬(shell sort)은 최적의 경우에 선택정렬(selection sort) 보다 빠르다.
3
힙정렬(heap sort)은 배열을 이용한 포화 이진트리(full binary tree)를 사용한다.
4
10개 데이터의 버블정렬(bubble sort)은 최대 45번의 비교 연산을 수행한다.
해설

힙정렬은 배열로 표현한 완전 이진트리(complete binary tree)를 사용하므로, 포화 이진트리를 사용한다는 설명이 옳지 않다.

포화 이진트리는 모든 레벨이 꽉 찬 트리라 노드 수가 2k−12^{k}-1일 때만 성립하지만, 힙은 마지막 레벨이 왼쪽부터 채워진 완전 이진트리면 된다.

  • 퀵정렬은 분할된 구간을 재귀 호출(스택)로 처리한다 — 옳다.
  • 쉘정렬은 이미 정렬된 최선의 경우 O(nlog⁡n)O(n \log n) 수준으로, 입력과 무관하게 항상 O(n2)O(n^{2})인 선택정렬보다 빠르다 — 옳다.
  • 10개 데이터의 버블정렬 최대 비교 횟수는 9+8+…+1 = 45이다 — 옳다.

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

이어서 풀어보기

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