2022-11-08 19:30

  为帮助考生在考后进行估分,课课家小编在考后为考生整理了网友回忆版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年软考的考生现在就可以开始备考了,报名课课家软考各科目考试赠送:辅导教材、历年真题、考前冲剌资料、在线模拟测试题库、老师专属答疑指导等,以保障学员顺利通过考试。

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


评论