2022下半年软件设计师下午真题答案（四）

　　为帮助考生在考后进行估分，课课家小编在考后为考生整理了网友回忆版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]< p="">

　　(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)

      课课家教育专注软考培训10年以上，一直坚持自主研发，将丰富的软考培训经验有效融入教程研发过程，自成体系的软考视频教程、软考培训教材和软考在线题库，使考生的学习更具系统性，辅导更具针对性。想要报考2022年软考的考生现在就可以开始备考了，报名课课家软考各科目考试赠送：辅导教材、历年真题、考前冲剌资料、在线模拟测试题库、老师专属答疑指导等，以保障学员顺利通过考试。

　　>>>>>>点击进入软考报名专题