首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下: 对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下: 对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素
admin
2011-04-06
49
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在指令系统的各种寻址方式中,获取操作数最快的方式是________________。
操作系统通过______来组织和管理外存中的信息。
在一个完整的功能测试过程中,______不属于应该编写的测试文档。A.测试需求文档B.测试用例文档C.测试标准D.问题报告单
软件测试信息流的输入包括______。①软件配置(包括软件开发文档、目标执行程序、数据结构)②开发工具(开发环境、数据库、中间件等)③测试配置(包括测试计划、测试用例、测试驱动程序等)④测试工具(为提高软件测试效率,使用测试
程序质量评审通常是从开发者的角度进行评审,其内容不包括____________。
测试用例是测试使用的文档化的细则,其规定如何对软件某项功能或功能组合进行测试。测试用例应包括下列(32)内容的详细信息。①测试目标和被测功能。②测试环境和其他条件。③测试数据和测试步骤。④测试记录和测试结果。
以下关于软件测试分类定义的叙述,不正确的是(42)。
现有四级指令流水线,分别完成取指、取数、运算、传送结果4步操作。若完成上述操作的时间依次为9ns、10ns、6ns、8ns,则流水线的操作周期应设计为(2)ns。
在计算机系统中常用的输入/输出控制方式有无条件传送、中断、程序查询和DMA等。其中,采用______方式时,不需要CPU控制数据的传输过程。
下图是________________设计模式的类图,该设计模式的目的是________________,图中,Decorator和Component之间是________________关系,ConcreteDecorator和Decorator之间是_
随机试题
分析下列句子,如果是单句,请根据谓语确定其句型;如果是复句,则分析分句之间的层次和关系。(1)他来信说,只要我们愿意去,他一定奉陪。(2)他不但细心听取了我们的意见,而且立刻通知组内同志前来商量,态度甚至比我们还要积极。(3)一批珍贵历史文献近年来被
临床乳房检查的最主要的方法是
肘关节脱位的特有体征
A.H--2’,H—6的化学位移为7.10~7.30(d)B.H—2’,H—6’的化学位移为7.20~7.50(d)C.H—2’,H—6’的化学位移为7.60~7.80(d)D.H—2’,H—6’的化学位移为7.70~7.90(d)E.H—2’,H
关于自动化仪表系统,正确的说法是()。
个人教育贷款信用风险的防控措施包括()。
创新意识和创新能力的辅导是学生健康心理辅导的哪项内容?()
【2014年山东省属真题】直接制约教育的社会性质和发展方向的社会因素是()。
2009年1─10月份我国商品房销售面积总计66368.73万平方米,同比增长48.4%,总销售额为31529.12亿元,同比增长79.2%。分地区看,东部地区商品房销售面积为35190.87万平方米,同比增长56.3%,商品房销售额为21789
Readthistextfromanarticleaboutovercomingthelanguagebarrier.Choosethebestsentencefromtheoppositepagetofilli
最新回复
(
0
)