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)代码
根据以上说明和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]
(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年专业软考教研倾力打造,官方教材参编作者和资深讲师坐镇,通过深研历年考试出题规律与考试大纲,深挖核心知识与高频考点,为学员考试保驾护航。面授、直播&录播,多种班型灵活学习,满足不同学员考证需求,降低课程学习难度,使学习效果事半功倍。
发表评论 查看完整评论 | |