首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下: 对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下: 对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素
admin
2011-04-06
48
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
堆数据结构定义如下:
对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。
在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素,则称为小顶堆。堆常用完全二叉树表示,图4—1是一个大顶堆的例子。
堆数据结构常用于优先队列中,以维护由一组元素构成的集合。对应于两类堆结构,优先队列也有最大优先队列和最小优先队列,其中最大优先队列采用大顶堆,最小优先队列采用小顶堆。以下考虑最大优先队列。
假设现已建好大顶堆A,且已经实现了调整堆的函数heapify(A,n,index)。
下面将C代码中需要完善的三个函数说明如下:
(1)heapMaximum(A):返回大顶堆A中的最大元素。
(2)heapExtractMax(A):去掉并返回大顶堆A的最大元素,将最后一个元素“提前”到堆顶位置,并将剩余元素调整成大顶堆。
(3)maxHeaplnseit(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)函数maxHeaplnsert
int maxHeaplnsert(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代码,函数heapMaximum,heapExtractMax和maxHeaplnsert的时间复杂度的紧致上界分别为(6)、(7)和(8)(用0符号表示)。
选项
答案
(6)O(1) (7)O(LOG(n)) (8)O(LOG(n))
解析
很明显,(6)heapMaximum函数只需要访问数组元素,所以复杂度为O(1)
(7)假设堆中的结点个数为n,则heapExtractaMax函数的复杂度主要消耗在heapify函数上,调整大顶堆的复杂度如(8)解释,该二叉树的层数,即O(logn)
(8)同上假设,maxHeaplnsert函数的复杂度主要集中在while循环里面,而while循环最多循环次数为O(logn),即为该二叉树的层数,所以该函数复杂度为0(logn)。
转载请注明原文地址:https://kaotiyun.com/show/9lDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
对于关键字序列(10,34,37,51,14,25,56,22,3),用线性探查法解决冲突构造哈希表,哈希函数为H(key)=key%11,关键字25存入的哈希地址编号为________________。
导致软件缺陷的原因有很多,①~④是可能的原因,其中最主要的原因包括(55)。①软件需求说明书编写的不全面,不完整,不准确,而且经常更改。②软件设计说明书。③软件操作人员的水平。④开发人员不能很好的理解需求说明书和沟通不足。
面向对象分析与设计是面向对象软件开发过程中的两个重要阶段,下列活动中,(25)不属于面向对象分析阶段。
为了能按时交付系统,开发小组在实现“确定最优任务分配方案”功能时采用了蛮力的方法。在系统交付后,对可能出现更多任务量的情况,采用更有效的方法来实现该功能,这属于()。
测试成本控制的目标是使测试开发成本、测试实施成本和测试维护成本最小化,以下理解正确的是______。A.测试准备成本属于测试实施成本B.可以通过加强软件测试的配置管理来降低测试维护成本C.测试设计成本控制的目标是尽可能地减少测试总执行时间和所需的测试
下面关于漏洞扫描系统的叙述,错误的是(7)。
若计算机存储数据采用的是双符号位(00表示正号、11表示负号),两个符号相同的数相加时,如果运算结果的两个符号位经()运算得1,则可断定这两个数相加的结果产生了溢出。
下面为C语言程序,边界值问题可以定位在(45)。 int data(3), int i, for(i=1, i<=3, i++)data(i)=100
下图是①设计模式的类图,该设计模式的目的是②,图中,Abstraction和RefinedAbstraction之间是③关系,Abstraction和Implementor之间是④关系。③处应填入?
序言性注释是指在每个程序或模块开头的一段说明,起辅助理解程序的作用,一般包括:程序的表示、名称和版本号;程序功能描述;接口与界面描述;输入输出数据说明:开发历史;与运行环境有关的信息等。下列叙述中不属于序言性注释的是(23)。
随机试题
肾结石性体外冲击波碎石主要禁忌症是
患者女性,40岁。有输尿管-膀胱反流病史30年。30年来间断出现尿频、尿急,右侧腰痛,未系统治疗。最近发现血压升高,血压160/100mmHg,尿常规示红细胞5个/HP、白细胞20个/HP,双肾彩超示:右肾有局灶粗糙的肾皮质瘢痕,伴相应的肾盏变形,最可能的
女,4岁。面容特殊,眼距宽,鼻梁平,舌厚肥大,面部臃肿,皮肤粗糙,头发干稀,智力低下,身高80cm。腕部x线检查显示一枚骨化中心。最可能的诊断是()
本案中,合同是否已变更?为什么?假如本案中,定作方某商场单方要求解除合同,合同能否解除?为什么?
增值税一般纳税人提供的收派服务,可以选择适用简易计税方法计税。()
属于气象旅游资源的是()。
阅读下列材料并回答问题。材料:下面是某教师讲授“大化改新”的教学过程。(一)导入教师指“亚洲封建时代”的地图,请学生关注与我国一衣带水的邻邦——日本。教师说明日本的自然特点:它是个岛国,国土有限,资源匮乏。日本人常有对国家和民族的忧
使用VC6打开考生文件夹下的源程序文件modi2.cpp。请完成函数fun(intx),该函数功能是将x的值转换成二进制数输出到屏幕,并且在函数中调用写函数WriteFile()将结果输出到modi2.txt文件中。例如:x=13,13的二进制
WhatistrueaboutSusan?
中国北方的大部分地区,包括北京在内,常被雾霾(heavysmog)——一种空气颗粒污染(particulatematterairpollution)——所笼罩。长期接触空气中的细小颗粒,尤其是在浓度极高的情况下,会增加患呼吸系统疾病(respirat
最新回复
(
0
)