2022年下半年软件设计师下午案例分析真题答案解析（试题四）

【点击查看：2022年下半年软件设计师下午案例分析真题答案解析（完整版）】

【点击查看：2022年下半年软件设计师真题答案解析（上午综合+下午案例）】

试题四（共15分）

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

【说明】

排序是将一组无序的数据元素调整为非递减顺序的数据序列的过程，堆排序是一种常用的排序算法。用顺序存储结构存储堆中元素。非递减堆排序的步骤是：

(1)将含n个元素的待排序数列构造成一个初始大顶堆，存储在数组R(R[1]，R[2]，...，R[n])中。此时堆的规模为 n，堆顶元素R[1]就是序列中最大的元素，R[n]是堆中最后一个元素。

(2)将堆顶元素和堆中最后一个元素交换，最后一个元素脱离堆结构，堆的规模减1，将堆中剩余的元素调整成大顶堆;

(3)重复步骤(2)，直到只剩下最后一个元素在堆结构中，此时数组R是一个非递减的数据序列。

【C代码】

下面是该算法的C语言实现。

(1)主要变量说明

n:待排序的数组长度

R[]：待排序数组，n个数放在R[1]，R[2]，...，R[n]中

(2)代码

【问题1】(8分)

根据以上说明和C代码，填充C代码中的空(1)～(4)。

【问题2】(2分)

根据以上说明和C代码，算法的时间复杂度为(5)(用O符号表示)。

【问题3】(5分)

考虑数据序列R=(7，10，13，15，4，20，19，8)，n=8，则构建的初始大顶堆为(6)，

第一个元素脱离堆结构，对剩余元素再调整成大顶堆后的数组R为(7)。

【参考答案】

【问题1】

（1） R[i]＜R[i]

（2）Heapify(R,I,n)

（3）i>1

（4）R[1]=R[0]

【问题2】

（5）O(nlog2n)

【问题3】

（6）(20，15，19，10，4，13，7，8)

（7）(19，15，·7，·0，4，13，8)