首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下: 对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下: 对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。 在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素
admin
2011-04-06
95
问题
阅读下列说明和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代码,填充C代码中的空(1)~(5)。
选项
答案
(1)* (A->im_array) (2)A->int_array[0] =*((A->int_array)+arry_size-1) (3)A->array_size (4)key>A->int_array[PARENT(i)] (5)A->im_array[i]=key
解析
(1)按照题意,heapMaximum函数返回大顶堆A中的最大元素,由于大顶堆是按照队列方式存储的,所以队列的第一个元素就是堆中的最大元素。
(2)中只需要将队列的最后一个元素赋给队列的第一个元素即可。
(3)(4)(5)这段代码需要将key值插入到合适的堆中的位置。首先从最后一个元素开始,比较该元素的父节点是否比key大,如果不是,则将父节点换为该元素的兄弟结点,再继续从PARENT(i)的位置开始重复工作,直到发现key值比当前i的父节点小或者已达到堆顶。最后将key值赋给A->int_array
完成插入。
转载请注明原文地址:https://kaotiyun.com/show/2lDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
计算机系统中,CPU对主存的访问方式属于________________。
假设某计算机系统中进程的三态模型如下图所示,那么图中的a、b、c、d处应分别填写(13)________________。
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则________________是一个小顶堆结构。堆结构用二叉树表示,则适宜的二叉树类型为________________。对于10个结点的小顶堆,其
ISO/IEC9126《软件工程产品质量》统一了多种质量模型。其中,下述关于软件使用质量的描述,不正确的是______。A.它测量用户在特定环境中能达到其目标的程度,不是测量软件自身的属性B.使用质量的属性分为4个特性:有效性、生产率、安全性和满意度
以下说法不正确的选项包括(48)。①软件测试不仅仅指测试的执行,还包括很多其他的活动②软件测试是一个独立的流程,贯穿产品整个生命周期,与其他流程并发地进行③应用H模型有利于资源调配,有助于跟踪测试投入的流向④H模型指
若计算机存储数据采用的是双符号位(00表示正号、11表示负号),两个符号相同的数相加时,如果运算结果的两个符号位经()运算得1,则可断定这两个数相加的结果产生了溢出。
(38)属于概要设计说明书的评测内容。①分析该软件的系统结构、子系统结构,确认该软件设计是否覆盖了所有已确定的软件需求,软件每一成分是否可追溯到某一项需求。②系统定义的目标是否与用户的要求一致。③从软件维护的角度出发,确认该软件设计是否考虑了方便未来
在计算机系统中常用的输入/输出控制方式有无条件传送、中断、程序查询和DMA等。其中,采用______方式时,不需要CPU控制数据的传输过程。
静态图像压缩标准JPEG2000中使用的是(60)算法。
采用________________表示带符号数据时,算术运算过程中符号位与数值位采用同样的运算规则进行处理。
随机试题
A.风寒壅肺证B.表寒肺热证C.痰浊阻肺证D.肺气郁闭证喘息咳逆,呼吸急促,胸部胀闷,痰多稀薄而带泡沫,色白质黏。常有头痛,恶寒,或有发热,口不渴,无汗,苔薄白而滑,脉浮紧。证属
6个月以下婴儿患急性粟粒型肺结核的特点是
鹅口疮的主要特征是
蒸汽网路中某一管道,通过的流量Gt=4.8t/h,蒸汽的平均密度ρ=4.705kg/m3。室外高压蒸汽管径计算如下图所示,若选用DN100管道,则其实际的比摩阻为()。
根据理财规划的需求,一般把客户信息分为()。
W企业于2003年7月5日以每张1050元的价格购买A企业发行的利随本清的企业债券。该债券的面值为1000元,期限为3年,票面年利率为10%,不计复利。购买时市场年利率为8%。不考虑所得税。要求:(1)利用债券估价模型评价W企业购买该债券是否合算?(
会议强调,主要负责同志要有改革担当,在关键问题上要_______拍板,只要符合党中央要求、符合基层实际、符合群众需求,就要坚决改、大胆试。改革是奔着问题去的,要解决问题就要“_______”,提出的措施要有针对性。对党中央明确韵改革任务,要旗帜鲜明抓落实。
《宋史.刑法志三》:“徒、流折杖之法,禁纲加密,良民偶有抵冒,致伤肌体,为终身之辱;愚顽之徒,虽一时创痛,而终无愧耻。若使情理轻者复古居作之法,遇赦第减月日,使良善者知改过自新,凶顽者有所拘系。"沈家本《刑法分考》:“流罪得免远徙,徒罪得免役年,
Readthearticlebelowaboutareportonemployment.ChoosethecorrectwordtofilleachgapfromA,BorC.Foreachquestion(
A、Togetsomepocketmoneyfromherfather.B、Topersuadehimintoallowinghermorefreedom.C、Todistracthimfromaskingabou
最新回复
(
0
)