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

1[7급 국가직 자료구조론] 13년 1회차
다음 배열에 저장된 데이터에 대해 내림차순으로 히프정렬(heap sorting)을 수행한다. 첫 번째 데이터를 출력하고 히프를 재구성한 후에 배열의 6번째에 있는 데이터로 옳은 것은? (단, 배열의 첫 번째 인덱스는 1이다)
[1][2][3][4][5][6][7][8][9]
2137221711305109
1
5
2
9
3
10
4
22
해설

배열을 최대 히프로 구성하고 루트를 출력·재구성하면 인덱스 6에는 9가 온다.

히프 구성: 마지막 부모부터 올라가며 조정하면 인덱스 3의 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이 된다.

  • 5: 인덱스 7에 그대로 남는다.
  • 10: 인덱스 8에 남는다.
  • 22: 인덱스 3으로 올라간다.

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

이어서 풀어보기

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