首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
admin
2014-11-13
72
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
从下列选项中选取合适的答案分别填入图4-1中的(1)~(4)处。A.DES算法B.MD5算法C.会话密钥D.数字证书E.甲的公钥F.甲的私钥G.乙的公钥H.乙的私钥以下关于摘要
网络设计流程通常由以下五个阶段组成:A.确定网络物理结构B.确定网络逻辑结构C.对现有网络的体系结构进行分析D.安装和维护E.需求分析根据网络开发设计的过程,给出上述五个阶段的先后排序:(1)。为上
某交换机的配置命令如下,根据命令后面的注释,填写(1)~(3)处的空缺内容,完成配置命令。Switch(config)#(1)//将交换机命名为Sw1Swl(config)#interfacevlan1Swl(config
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加密
在校园网设计过程中,划分了很多VLAN,采用了VTP来简化管理。1.VTP信息只能在(1)端口上传播。2.运行VTP的交换机可以工作在三种模式:(2)、(3)、(4)。3.共享相同VLAN数据库的交换机构成一个(5)。该校园网内
DHCP允许服务器向客户端动态分配Ⅲ地址和配置信息。客户端可以从DHCP服务器获得(1)。(1)A.DHCP服务器的地址B.Web服务器的地址C.DNS服务器的地址通常采用IP地址与MAC地址绑定的策略为某些设备保留固定的IP地址
请选择恰当的内容填写在(1)、(2)、(3)空白处。一般用Host表、网络信息服务系统(NIS)和域名服务(DNS)等多种技术来实现主机名和IP地址之间的转换。Host表是简单的文本文件,而DNS是应用最广泛的主机名和IP地址的转换机制,它使用(1
从网络拓扑图中可以看出该校园网采用了分层设计结构,回答以下问题:1.交换机按照所处的层次和完成的功能分为三种类型:核心交换机、汇聚交换机和接入交换机。下表是学校采购的三种交换机,请根据交换机的技术指标确定交换机的类型。在答题纸对应的解答栏内
在控制面板的“添加/删除程序”对话框中选择(1),然后进入“应用程序服务器”选项,在(2)组件复选框中选择“文件传输协议(FTP)服务”,就可以在Windows2003中安装FTP服务。(1)A.更改或删除程序B.添加新程序C.添加/删除
请在(1)、(2)、(3)、(4)空白处填写恰当的内容。Web客户机与服务器共同遵守(1)协议,其工作过程是;Web客户端程序根据输入的(2)连接到相应的Web服务器上,并获得指定的Web文档。动态网页以(3)程序的形式在服务器端处理,并给客户端返
随机试题
酶联免疫反应的影响因素不包括
定期考核不合格的医师暂停执业活动期满,再次考核仍不合格的
综合钢筋的强度、塑性、工艺性和经济性等因素,既可作为非预应力钢筋混凝土选用也可作为预应力钢筋混凝土选用的钢筋牌号是()。[2008年真题]
下列关于契税计税依据的说法中,正确的是()。
某公司中标一不锈钢轧钢水处理和铁合金及辅原料系统施工总承包工程。工程包括年产170万t碳钢和不锈钢的炼钢工业净环水、浊环水、软水系统和铁合金及辅原料地下料仓、FDC(气浮式皮带)输送系统的土建、钢结构制作、机电、仪器设备安装专业工程。工程合同金额2.8亿元
某混凝土结构施工采用木模板。木模板一次净用量为200m2,模板现场制作安装不可避免的操作损耗率为3%,该模板可周转使用5次,每次补损率为5%,该模板周转使用量为()m2。
依照我国现行法律,下列自然人中为限制民事行为能力或无民事行为能力的人的是:
下面代码的输出结果是x=0b1010print(x)
A、同学B、朋友C、老板和秘书D、顾客和售货员D“打折”买东西时的常用语,“我们商场”可见男的是售货员,答案选择C。
DougMorrellhadalreadyinstalledsolarpanelsonhishouseinCoopersville,Mich.,buthewaseagertogetalittlebitgreen
最新回复
(
0
)