软件设计师案例分析每日一练试题（2023/5/30）

当前位置：信管网 >> 软件设计师 >> 每日一练 >> 文章内容

来源：信管网 2023年05月31日【所有评论】

软件设计师案例分析当天每日一练试题地址：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总：www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题（2023/5/30）在线测试：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2023/5/30

软件设计师案例分析每日一练试题内容（2023/5/30）

试题四（共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)。
信管网试题答案与解析：www.cnitpm.com/st/5389421543.html
信管网考友试题答案分享：

信管网cnitpm639375188254：
（1）r[j]＞r[2j]&&r[j]＞r[2j+1] （2）（3）i＞=1 （4）n-- （5）o（n^2）（6）（7）

信管网qcfnihao：
一、 i＞2 r[1] ＝ r[0] 二 o（nlgn）三、3 20 15 19 10 4 13 7 8 19 15 13 10 4 8 7

信管网cnitpm405177456862：
问题1 r[i] ＜ r[j] heapify（r,1,i-1） i＞=1 r[1]=r[0] 问题2 o（nlog2^n）问题3 20 7 15 10 4 13 9 8 8 7 15 10 4 13 19

信管网cnitpm638693719689：
o（n） r（20,7,10,13,15,4,19,8） r（19,8,7,10,13,15,4）

信管网cnitpm638198840222：
（1）r[i] ＞ r[j]；（2）heapify（r,n/2,n-i）；（3）i ＞ n/ 2；（4）r[1] ＝ r[0] ；（5）o（n2）；（6）（20, 15, 19 , 13, 7, 4,10 , 8 ）（7）（）

信管网试题答案与解析：www.cnitpm.com/st/5389421543.html