首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
admin
2014-11-13
77
问题
阅读下列说明和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.重新
IIS安装的硬盘分区最好选用NTFS格式,是因为(1)和(2)。A.可以针对某个文件或文件夹给不同的用户分配不同的权限B.可以防止网页中的Applet程序访问硬盘中的文件C.可以使用系统自带的文件加密系统对文件或文件夹进行加密
在“管理工具”中运行“管理IP筛选器列表”,创建一个名为“SNMP消息”的筛选器。在如图12-3所示的“IP筛选器向导”中指定IP通信的源地址,下拉列表框中应选择(1);在如图12-4中指定IP通信的目标地址,下拉列表框中应选择(2)。在图
在“管理工具”中运行“管理IP筛选器列表”,创建一个名为“SNMP消息”的筛选器。在如图12-3所示的“IP筛选器向导”中指定IP通信的源地址,下拉列表框中应选择(1);在如图12-4中指定IP通信的目标地址,下拉列表框中应选择(2)。在图
销售部的网络号是(1),广播地址是(2):技术部的网络号是(3),广播地址是(4);每个子网可用的IP地址有(5)个。在网关计算机/etc/sysconfig/network-scripts/目录中有以下文件,运行某命令可以启动网络,该命令是(9),其
完成下列命令行,对网络接口进行地址初始化配置。firewall(config)#ipaddressinside(1)(2)firewall(config)#ipaddressoutside(3)(4)以下命令针对网络服务的端口配
DHCP允许服务器向客户端动态分配Ⅲ地址和配置信息。客户端可以从DHCP服务器获得(1)。(1)A.DHCP服务器的地址B.Web服务器的地址C.DNS服务器的地址通常采用IP地址与MAC地址绑定的策略为某些设备保留固定的IP地址
从网络拓扑图中可以看出该校园网采用了分层设计结构,回答以下问题:1.交换机按照所处的层次和完成的功能分为三种类型:核心交换机、汇聚交换机和接入交换机。下表是学校采购的三种交换机,请根据交换机的技术指标确定交换机的类型。在答题纸对应的解答栏内
随机试题
Everysporthasitsgreatlegends:soccerhasPele,andbasketballhasMichaelJordan.Isthereone【B1】______whompeopleconside
TheearliestimmigrantstoNorthAmericafoundIndiansalreadylivingthere.TheIndiansnumberedabout500,000atthattime.Th
A.赤色B.白色C.黄色D.青色E.黑色主脾虚,湿证的是()
胃苏颗粒的功能有
患儿,男,11个月。因呕吐、腹泻3天来院,初步诊断为婴儿腹泻伴脱水。患儿经6小时补液治疗后,脱水基本纠正,开始排尿,但又出现精神萎靡、腹胀、肠鸣音减弱、心音低钝,护士考虑该患儿可能是
冬季开挖路堑必须()开挖。
《诗经》中属于民间音乐部分的是()。
小李和朋友相约:“如果明天阳光灿烂,我就和你一起去踏青。”据此,可以推出小李爽约的情形是()。
在许多人看来,从一而终的就是好婚姻。其实,这种看法并不正确。婚姻不仅意味着身体的忠诚,而且还包含了情感的相互扶持。所以不能说只要没有第三者,婚姻就没有问题。当下中国有许多婚姻是这样一种模式:夫妻并没有出轨,但双方都无法从婚姻中获得抚慰、滋养和治愈。实际上,
Longlongagotherelivedabeautifulgirl______namewasHelen.
最新回复
(
0
)