首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下。 对于n个元素的关键字序列{a1,a2……,an},当且仅当满足下列关系时称其为堆: 在一个堆中,若堆项元素为最大元素,
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下。 对于n个元素的关键字序列{a1,a2……,an},当且仅当满足下列关系时称其为堆: 在一个堆中,若堆项元素为最大元素,
admin
2018-07-25
58
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
堆数据结构定义如下。
对于n个元素的关键字序列{a
1
,a
2
……,a
n
},当且仅当满足下列关系时称其为堆:
在一个堆中,若堆项元素为最大元素,则称为大顶堆;若堆顶元素为最小元素,则称为小项堆。堆常用完全二叉树表示,图8.11是一个大顶堆的例子。
堆数据结构常用于优先队列中,以维护由一组元素构成的集合。对应于两类堆结构,优先队列也有最大优先队列和最小优先队列,其中最大优先队列采用大顶堆,最小优先队列采用小顶堆。以下考虑最大优先队列。
假设现已建好大项堆A,且已经实现了调整堆的函数heapify(A,n,index)。
下面将C代码中需要完善的3个函数说明如下。
(1)heapMaximum(A):返回大顶堆A中的最大元素。
(2)heapExtractMax(A):去掉并返回大顶堆A的最大元素,将最后一个元素“提前”到堆顶位置,并将剩余元素调整成大顶堆。
(3)maxHeapInsert(A,key):把元素key插入到大顶堆A的最后位置,再将A调整成大顶堆。
优先队列采用顺序存储方式,其存储结构定义如下:
#define PARENT(i)i/2
typedef struct array {
int *int_array;//优先队列的存储空间首地址
int array_size;//优先队列的长度
int capacity;//优先队列存储空间的容量
}ARRAY;
【C代码】
(1)函数heapMaximum
int heapMaximum(ARRAY*A){return_____(1);}
(2)函数heapExtractMax
int heapExtractMax(ARRAY *A){
int max;
max=A->int array[0];
____(2);
A->array size--;
Heapify(A,A->array size,0);//将剩余元素调整成大顶堆
return max;
}
(3)函数maxHeapInsert
int maxHeapInsert(ARRAY*A,int key){
int i,*p;
if(A->array-size==A->capacity){//存储空间的容量不够时扩充空间
p=(int*)realloc(A->int array,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);
return 0;
}
根据以上说明和C代码,填充C代码中的空(1)~(5)。
选项
答案
(1)A->int_array[0] (2)A->int_array[0]=A->inc_array[A->array_size-1] (3)A->array_size-1 (4)key>A->int_array[PARENT(i)] (5)A->int_atray[i]=key
解析
heapMaximum(A)函数返回大顶堆A中的最大元素。大项堆A的优先队列采用顺序存储方式,指针int array指向优先队列的存储空间首地址,其内容为大项堆A中的最大元素,因此空(1)处应填入A->int_array[0]。
heapExtractMax(A)的功能是去掉并返回大顶堆A的最大元素,将最后一个元素“提前”到堆项位置,并将剩余元素调整成大顶堆。可知空(2)处所填的语句应该是将最后一个元素的值存储在原最大元素所在的位置,即存储空间的首地址。
maxHeapInsert(A,key)的功能是把元素key插入大顶堆A的最后位置,再将A调整成大项堆。在将A调整成大顶堆的过程中需要用到上滤策略。maxHeaplnsert(A,key)函数中,首先用i指示元素key的位置,则i=array_size-1;然后将im_array
与其父节点进行比较,如果大于其父节点的值,将两者的位置进行交换,key的位置i=PARENT(i);往上比较,直至key的值不大于其父节点的值。
转载请注明原文地址:https://kaotiyun.com/show/97DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
请用100字以内的文字说明该网管软件项目采用快速原型开发方法的优缺点。请指出图7-15可能存在的关键路径是什么?(请用英文字母序号列出)
阅读以下关于以快速原型模型开发网管软件系统时的项目进度管理的叙述,回答问题1至问题5。【说明】某网络程序软件开发公司承接某项网络工程的网络流量统计管理软件开发任务。在进行可行性研究时,需要估算完成项目的时间进度。由于该软件公司近年来已经为采用快速
ADSL技术可以充分利用现有铜线网络,只要在用户线路两端加装ADSL设备即可为用户提供服务。请从以下术语选择适当的编号,将图5-9所示的拓扑结构中(1)~(4)空缺处的名称填写完整。【供选择的答案】A.程控交换机B.二层交换机
请说出图9-1的拓扑结构名称与特点。PC2、PC4与PCI、PC3、PC5要连网且能相互访问,需要增添什么设备?
阅读以下有关网络设备安装与调试的叙述,分析设备配置文件,回答问题1~3。虚拟局域网(VirtualLAN)是与地理位置无关的局域网的一个广播域,由一个工作站发送的广播信息帧只能发送到具有相同虚拟网号的其他站点,可以形象地认为,VLAN是在物理局域
该企业网络的核心层采用了ATM技术,由3台ATM交换机互联构成。试对ATM网络技术的主要特点、协议分层结构和优点作简要叙述。(控制在100个字以内)图中用了两台路由器Router1,和Router2,简述路由器的技术特点,并说明Router1和Rout
目前,通过移动电话接入互联网所采用的主要技术是什么?进行一次查询的数据信息见表1-1,网络的基本通信服务费用见表1-2,总费用=网络租用费+通信费。根据表中给出的数据,试计算销售员每月至少应进行多少次查询,才能使得使用移动电话的总费用比使用PDA的总费
如何根据网络流量选择联网设备,给出所选设备的作用。如何规划防火墙,将内部业务服务器和部分PC机与Internet隔离?
阅读以下关于RIP动态路由配置的技术说明,结合网络拓扑图回答问题1至问题3。[说明]某大学城局域网的网络拓扑结构如图7-18所示,图中路由器R1、R2,R3均运行基于距离矢量算法的RIP路由协议,并且图中给出了路由器R1、R2、R3各端口的IP地
随机试题
党的十八届三中全会既提出了全面深化改革的总目标,也在总目标统领下明确了经济体制、政治体制、文化体制、社会体制、生态文明体制和党的建设制度等方面深化改革的具体目标和任务。经济体制改革要紧紧围绕()
“荷花”牌洗衣机为客户提供终身上门维修服务,这属于产品概念层次中的()
调配前宜酒炙的药物是
患者男,28岁。突发胸痛2小时,以自发性气胸诊断入院。查体:T36.8℃,P90次/分,呼吸22次/分;右侧胸部肋间隙增宽,语颤消失,叩诊鼓音。其肝浊音界的改变是
某中外合资经营企业任命李某为公司的副总经理,后发现李某独断专行,造成公司严重亏损,公司董事会决议免去李某的副总经理职务,并委派他人接任此职务。新任副总经理接任时,李某拒不交出其持有的公司印章(包括合同专用章、财务专用章)等,致使原告无法进行正常的经营活动。
波长为λ的单色光垂直照射在折射率为n的劈尖薄膜上,在由反射光形成的干涉条纹中,第五级明条纹与第三级明条纹所对应的薄膜厚度差为()。
审计工作底稿三级复核制度是指会计师事务所以( )为复核人,对审计工作底稿进行逐级复核的一种质量检查制度。会计师事务所与P公司于2004年1月20日签订的2003年度会计报表审计业务约定书,作为审计档案,应当( )。
会计师事务所应当每年至少一次向所有受独立性要求约束的人员获取其遵守独立性政策和程序的书面确认函。书面确认函必须是纸质的。()
可以弥补教育现场观察不足和缺陷的观察类型是()。
Theword"wrath"inTheGrapesofWrathbytheNobelprizewinnerJohnSteinbeckprobablymeans:
最新回复
(
0
)