다음과 같이 배열에 저장된 데이터에 대하여 내림차순으로 히프 정렬(he… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 19년 1회차
다음과 같이 배열에 저장된 데이터에 대하여 내림차순으로 히프 정렬(heap sort)을 수행할 때, 첫 번째 데이터를 출력하고 히프를 재구성 한 후에 배열의 여섯 번째에 있는 값은? (단, 배열의 첫 번째 색인 값은 1이다)
[1][2][3][4][5][6][7][8][9]
2137221711305109
1
5
2
9
3
10
4
11
해설

첫 데이터를 출력하고 재구성한 히프에서 여섯 번째 위치의 값은 9이다.

내림차순으로 출력하므로 최대 히프를 만든다. 마지막 비단말 노드부터 아래로 조정하면 22와 30, 21과 37이 교환되어 히프는 37, 21, 30, 17, 11, 22, 5, 10, 9가 된다.

루트 37을 출력하고 마지막 원소 9를 루트로 올린 뒤 아래로 재조정하면 9가 30과, 다시 22와 교환되어 30, 21, 22, 17, 11, 9, 5, 10이 된다. 따라서 여섯 번째 칸에는 9가 놓인다.

  • 5는 일곱 번째 칸에 그대로 남는다.
  • 10은 여덟 번째 칸에 그대로 남는다.
  • 11은 다섯 번째 칸에 그대로 남는다.

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

이어서 풀어보기

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