试题内容
试题四（共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)。
查看答案
试题四（共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)。
查看答案
你可能感兴趣的试题
第2题
试题二
阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内
【说明】
某省针对每年举行的足球联赛，拟开发一套信息管理系统，以方便管理球队、球员、主教练、主裁判、比赛等信息。
（1）系统需要维护球队、球员、王教练需要维护球队、球员、主教练、主裁判、比赛等信息。
球队信息主要包括：球队编号、名称、成立时间、人数、主场地址、球队主教练
球员信息主要包括：姓名、身份证号、出生日期、身高、家庭住址。
主教练信息主要包括：姓名、身份证号、出生日期、资格证书号、级别。
主裁判信息王要包括：姓名、身份证号、出生日期、资格证书号、获取证书时间、级别。
（2)每支球队有一名主教练和若干名球员。一名主教练只能受聘于一支球队，一名球员只能效力于一支球队。每支球队部有自己的唯一主场场地，且场地不能共用。
(3)足球联赛采用王客场循环制，一周进行一轮比赛，一轮的所有比赛同时进行。
（4)一场比赛有两支球队参答案解析与讨论：https://www.ruantiku.com/shiti/253801690.html
第4题
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
对有向图进行拓扑排序的方法是：
（1）初始时拓扑序列为空；
（2）任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧；
（3）重复（2），直到不存在入度为0的顶点为止（若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序）。
函数int* TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为v1，v2，…，vn，图G采用邻接表示，其数据类型定义如下：
#define MAXVNUM 50 /*最大顶点数*/
typedef struct ArcNode{ /*表结点类型*/
int adjvex; /*邻接顶点编号*/
struct ArcNode *nexta答案解析与讨论：https://www.ruantiku.com/shiti/3809416600.html
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
对有向图进行拓扑排序的方法是：
（1）初始时拓扑序列为空；
（2）任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧；
（3）重复（2），直到不存在入度为0的顶点为止（若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序）。
函数int* TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为v1，v2，…，vn，图G采用邻接表示，其数据类型定义如下：
#define MAXVNUM 50 /*最大顶点数*/
typedef struct ArcNode{ /*表结点类型*/
int adjvex; /*邻接顶点编号*/
struct ArcNode *nexta答案解析与讨论：https://www.ruantiku.com/shiti/3809416600.html