首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
admin
2014-11-13
52
问题
阅读下列说明和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代码,函数heapMaximum,heapExtractMax和maxHeaplnsert的时间复杂度的上界分别为(6)、(7)和(8)(用O符号表示)。
选项
答案
(6)O(1) (7)O(1gn) (8)O(1gn)
解析
heapMaximum函数不需要进行比较,直接输出存储空间首地址中的内容。时间复杂度的上界O(1)。heapExtractMax函数将最后一个元素“提前”到堆顶位置,并将剩余元素调整成大顶堆,在最坏的情况下,需要从根节点下滤比较到最底层,时间复杂度的上界O(lgn)。maxHeaplnsert(A,key)函数把元素key插入到大顶堆A的最后位置,再将A调整成大顶堆。在最坏的情况下,需要从最底层上滤比较到根节点,时间复杂度的上界O(lgn)。
转载请注明原文地址:https://kaotiyun.com/show/ZZDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
从下列选项中选取合适的答案分别填入图4-1中的(1)~(4)处。A.DES算法B.MD5算法C.会话密钥D.数字证书E.甲的公钥F.甲的私钥G.乙的公钥H.乙的私钥当乙收到了地
启动init进程前,不需要经过______步骤。A.LIIO加载内核B.检测内存C.加载文件系统D.启动网络支持假设root用户执行init0命令,系统将会______。A.暂停B.关机C.重新
网络设计流程通常由以下五个阶段组成:A.确定网络物理结构B.确定网络逻辑结构C.对现有网络的体系结构进行分析D.安装和维护E.需求分析根据网络开发设计的过程,给出上述五个阶段的先后排序:(1)。将答
在校园网设计过程中,划分了很多VLAN,采用了VTP来简化管理。1.VTP信息只能在(1)端口上传播。2.运行VTP的交换机可以工作在三种模式:(2)、(3)、(4)。3.共享相同VLAN数据库的交换机构成一个(5)。该校园网在
在校园网设计过程中,划分了很多VLAN,采用了VTP来简化管理。1.VTP信息只能在(1)端口上传播。2.运行VTP的交换机可以工作在三种模式:(2)、(3)、(4)。3.共享相同VLAN数据库的交换机构成一个(5)。该校园网内
请阅读下列SwitchA的配置信息,并在(1)~(5)处解释该语句的作用。Switch>enable(进入特权模式)Switch#configterminal(进入配置模式)Switch(config)#hostnameSwi
阅读以下说明,回答问题1至问题5。【说明】某网络拓扑结构如图3-1所示,DHCP服务器分配的地址范围如图3-2所示。
请选择恰当的内容填写在(1)、(2)、(3)空白处。一般用Host表、网络信息服务系统(NIS)和域名服务(DNS)等多种技术来实现主机名和IP地址之间的转换。Host表是简单的文本文件,而DNS是应用最广泛的主机名和IP地址的转换机制,它使用(1
从网络拓扑图中可以看出该校园网采用了分层设计结构,回答以下问题:1.交换机按照所处的层次和完成的功能分为三种类型:核心交换机、汇聚交换机和接入交换机。下表是学校采购的三种交换机,请根据交换机的技术指标确定交换机的类型。在答题纸对应的解答栏内
从网络拓扑图中可以看出该校园网采用了分层设计结构,回答以下问题:1.交换机按照所处的层次和完成的功能分为三种类型:核心交换机、汇聚交换机和接入交换机。下表是学校采购的三种交换机,请根据交换机的技术指标确定交换机的类型。在答题纸对应的解答栏内
随机试题
在山区冰雪道路上遇到这种前车正在上坡的情况如何处置?
下列物质不是三大合成材料的是()。
德国“狂飙突进”作家的创作主张是()
博客的赢利模式包括
下面关于充分竞争描述错误的是()
试述教师主导作用与学生主体作用相统一的规律。
骨髓中原始细胞>30%(NEC)且分化差,对AML-M0诊断最特异的指标是
“十四五”期间,加快发展现代产业体系、巩固壮大实体经济根基,要建设现代化基础设施体系。下列相关说法错误的是()。
Excel工作表D列保存了18位身份证号码信息,为了保护个人隐私,需将身份证信息的第9~12位用“*”表示,以D2单元格为例,最优的操作方法是()。
NaturalgasVehiclesKermittheFrogoncesaid,"It’snotthateasybein’green."Althoughhewasn’treferringtocars,his
最新回复
(
0
)