首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
admin
2014-11-13
64
问题
阅读下列说明和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://kaotiyun.com/show/pZDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
网络设计流程通常由以下五个阶段组成:A.确定网络物理结构B.确定网络逻辑结构C.对现有网络的体系结构进行分析D.安装和维护E.需求分析根据网络开发设计的过程,给出上述五个阶段的先后排序:(1)。Ca
网络设计流程通常由以下五个阶段组成:A.确定网络物理结构B.确定网络逻辑结构C.对现有网络的体系结构进行分析D.安装和维护E.需求分析根据网络开发设计的过程,给出上述五个阶段的先后排序:(1)。为上
某交换机的配置命令如下,根据命令后面的注释,填写(1)~(3)处的空缺内容,完成配置命令。Switch(config)#(1)//将交换机命名为Sw1Swl(config)#interfacevlan1Swl(config
销售部的网络号是(1),广播地址是(2):技术部的网络号是(3),广播地址是(4);每个子网可用的IP地址有(5)个。在网关计算机上使用以下路由命令创建两个默认的路由:routeadd-net192.168.1.0255.255.2
DHCP允许服务器向客户端动态分配Ⅲ地址和配置信息。客户端可以从DHCP服务器获得(1)。(1)A.DHCP服务器的地址B.Web服务器的地址C.DNS服务器的地址图3-3是DHCP服务器安装中的添加排除窗口。 参照图
从网络拓扑图中可以看出该校园网采用了分层设计结构,回答以下问题:1.交换机按照所处的层次和完成的功能分为三种类型:核心交换机、汇聚交换机和接入交换机。下表是学校采购的三种交换机,请根据交换机的技术指标确定交换机的类型。在答题纸对应的解答栏内
阅读以下说明,回答问题1至问题3。【说明】如图5-1所示,某单位通过2M的DDN专线接入广域网,该单位内网共分为三个子网。服务器放置在子网192.168.5.0/24中,财务部工作站放置在子网192.168.10.0/24,销售部工作站放置在子网
阅读以下说明,回答问题1至问题4。【说明】2007年春,ARP木马大范围流行。木马发作时,计算机网络连接正常却无法打开网页。由于ARP木马发出大量欺骗数据包,导致网络用户上网不稳定,甚至网络短时瘫痪。
1.路由器第一次设置时,必须通过Console口连接运行终端仿真软件的计算机进行配置,此时终端仿真程序设置的波特率应为(1)b/s。2.路由器有多种配置模式,请根据以下命令提示状态,判断路由器处于何种配置模式下。Router(Config)
随机试题
典型心绞痛的发作部位主要是
某孕妇,末次月经为2005年2月25日,其预产期应为
女性,28岁。发热、咳嗽、咯血3天就医。X线胸片示右中肺野2.5cm×2.5cm圆形密影,边缘清晰,上方仅见一小透亮区和液平段。空腔壁甚薄。肺门不大。其余肺野未见异常。既往有类似发病史,根据临床和X线征象,其最可能的诊断是
己糖激酶法是测定血糖的
为孤立基牙,如想达到好的固位和支持作用应选用卡环固位体是
对建设工程项目的结构主要部位除了常规检查外,还要在分部工程验收时,要求建设单位将施工、设计、监理、建设单位各方分别签字的质量验收证明在验收后()天内报送工程质量监督机构备案。
下列各种情况中,使总收益增加的是()。
【弗洛伊德】(SigmundFreud,1856—1939)南京大学2000年世界近现代史真题;南京大学2005年世界近现代吏真题;苏州大学2015年世界吏专业基础综合真题
牙周组织内的胶原主要是()。
Afterretiringfrom30yearsofteaching,EthbellPeppercouldeasilyhavedecidedtositbackand【B1】______andenjoyapeaceful
最新回复
(
0
)