首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
admin
2014-11-13
33
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
堆数据结构定义如下:对于n个元素的关键字序列{a
1
,a
2
,…,a
n
},当且仅当满足下列关系时称其为堆。
在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素,则称为小顶堆。堆常用完全二叉树表示,图15.2是一个大顶堆的例子。
堆数据结构常用于优先队列中,以维护由一组元素构成的集合。对应于两类堆结构,优先队列也有最大优先队列和最小优先队列,其中最大优先队列采用大顶堆,最小优先队列采用小顶堆。以下考虑最大优先队列。假设现己建好大顶堆A,且已经实现了调整堆的函数heapify(A,n,index)。下面将C代码中需要完善的三个函数说明如下:
(1)heapMaximum(A).返回大顶堆A中的最大元素。
(2)heapExtractMax(A):去掉并返回大顶堆A的最大元素,将最后一个元素“提前”到堆顶位置,并将剩余元素调整成大项堆。
(3)maxHeaplnsert(A,key).把元素key插入到大顶堆A的最后位置,再将A调整成大顶堆。优先队列采用顺序存储方式,其存储结构定义如下:
#definePARENT(i)i/2
typedefstructarray{
int*intarray;//优先队列的存储空间首地址
intarraysize;//优先队列的长度
intcapacity;//优先队列存储空间的容量
}ARRAY;
【C代码】
(1)函数heapMaximum
intheapMaximum(ARRAY*A)(return(1))
(2)函数heapExtractMax
intheapExtractMax(ARRAY*A)(
intmax;
max=A->int—array[0];
(2);
A一>array_size-一;
Heapify(A,A一>array—size,0);//将剩余元素调整成大顶堆
returnmax;
}
(3)函数maxHeaplnsert
intmaxHeaplnsert(ARRAY*A,intkey){
inti,*P;
if(A一>array一size==A一>capacity){//存储空间的容量不够时扩充空间
p=(int*)realloc(A一>intarray,A一>capacity*2*sizeof(int));
if(!P)return一1;
A一>int_array=P;
A一>capacity=2*A一>capacity;
}
A一>array_size++:
i=(3);
while(i>0&&(4){
A一>int_array
=A一>int_array[PARENT(i)];
i=PARENT(i);
}
(5);
return0;
}
根据以上说明和C代码,填充C代码中的空(1)~(5)。
选项
答案
(1)A->int_array[0] (2)A->int_array[0]=A->int_array[A->array_size一1] (3)A->array_size-1 (4)key>A->int_array[PARENT(i)] (5)A->int_array[i]=key
解析
heapMaximum(A)函数返回大顶堆A中的最大元素。大顶堆A的优先队列采用顺序存储方式,指@int_array指向优先队列的存储空间首地址,其内容为大项堆A中的最大元素,因此空(1)处应填入A一>inLarray[0]。heapExtractMax(A)功能是去掉并返回大顶堆A的最大元素,将最后一个元素“提前”到堆顶位置,并将剩余元素调整成大顶堆。可知空(2)处所填的语句应该是将最后一个元素的值存储在原最大元素所在的位置,即存储空间的首地址。maxHeaplnsert(A,key)的功能是把元素key插入到大顶堆A的最后位置,再将A调整成大顶堆。在将A调整成大堆的过程中需要用到上滤策略。maxHeaplnsert(A,key)函数中,首先用i指示元素key的位置,则i=array_size_1;然后将int_array
-~其父节点进行比较,如果大于其父节点的值,也两者的位置进行交换,key的位置i=PARENT(i);往上比较,直至key的值不大于其父节点的值。
转载请注明原文地址:https://jikaoti.com/ti/07i7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
从下列选项中选取合适的答案分别填入图4-1中的(1)~(4)处。A.DES算法B.MD5算法C.会话密钥D.数字证书E.甲的公钥F.甲的私钥G.乙的公钥H.乙的私钥当乙收到了地
从下列选项中选取合适的答案分别填入图4-1中的(1)~(4)处。A.DES算法B.MD5算法C.会话密钥D.数字证书E.甲的公钥F.甲的私钥G.乙的公钥H.乙的私钥甲使用Out
从下列选项中选取合适的答案分别填入图4-1中的(1)~(4)处。A.DES算法B.MD5算法C.会话密钥D.数字证书E.甲的公钥F.甲的私钥G.乙的公钥H.乙的私钥以下关于摘要
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持根据说明中inittab文件的内容,系统引导成功后,工作在______状态。A.单用户字符模式
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加密
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加密
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加密
在“管理工具”中运行“管理IP筛选器列表”,创建一个名为“SNMP消息”的筛选器。在如图12-3所示的“IP筛选器向导”中指定IP通信的源地址,下拉列表框中应选择(1);在如图12-4中指定IP通信的目标地址,下拉列表框中应选择(2)。在图
在校园网设计过程中,划分了很多VLAN,采用了VTP来简化管理。1.VTP信息只能在(1)端口上传播。2.运行VTP的交换机可以工作在三种模式:(2)、(3)、(4)。3.共享相同VLAN数据库的交换机构成一个(5)。该校园网在
随机试题
Whilewe’veknownforsometimeaboutthemanylong-termbenefitsofexercise,newresearchshowsaerobicexercisealsomayhave
等离子弧既可用来进行切割,也可用来进行焊接。
( )是指符合国家规范要求的,供给居民生活、公共建筑和工业企业生产作燃料用的,公用性质的燃气。
根据《中华人民共和国海关法》的规定,中华人民共和国海关是属于下述哪类性质的机关?()
以下DM广告的形式,不属于新兴的DM广告的是()。
下列选项中,与“地球一北极”逻辑关系相同的是()。
简要分析科尔伯格的道德认知发展理论的主要方法——道德两难问题讨论法。
形成赤潮韵直接原因是__________。
基层群众性自治组织首次出现是在下列哪一宪法中()
•Readthetextbelowabouttheartofleadership—leadingwithakindheart.•Inmostofthelines41—52thereisoneextraword.
最新回复
(
0
)