首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2019-08-15
86
问题
关于堆的一些问题:
(1)堆的存储表示是顺序的,还是链接的?
(2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?
(3)对n个元素进行初始建堆的过程中,最多做多少次数据比较(不用大0表示法)?
选项
答案
(1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点,在最下两层上。 (3)在建含有n个元素、深度为h的堆时,其比较次数不超过4n,推导如下: 由于第i层上的结点数至多是2
i-1
,以它为根的二叉树的深度为h一i+1,则调用[n/2]次筛选算法时总共进行的关键字比较次数不超过下式之值: [*]2
i-1
×2(h一i)=[*]2
i
×(h一i)=[*]2
h-j
×j≤(2n)[*]j/2
j
≤4n 提示:此题考查的知识点是堆的基本定义及效率。堆定义为n个关键字序列K
1
,K
2
,…,K
n
,当且仅当该序列满足如下性质(简称为堆性质): (1)K
i
≤K
2i
且K
i
≤K
2i+1
或 (2)K
i
≥K
2i
且K
i
≥K
2i+1
(1≤i≤n)。K
i
相当于二叉树的非叶结点,K
2i
则是左孩子,k
2i+1
是右孩子。
解析
转载请注明原文地址:https://kaotiyun.com/show/xKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
二里头文化是我国考古史上的重大发现,具有重大的意义。根据所学知识,回答问题:二里头文化在类型上可以分为()
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:我国银行最早的雏形是唐朝时期出现的()
在一个8级中断的系统中,硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8,通过中断屏蔽技术,将中断处理优先顺序设置为1→3→5→7→2→4→6→8,如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达,CPU在按优先顺序处理到第
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
某浮点机字长16位,其浮点数格式为:阶码5位(含1位阶符),采用补码表示,尾数11位(含1位数符),采用补码表示,且尾数为规格化形式。已知X=0.1011000011×20.0101,Y=0.0001100000×20.1000,试求X+Y.要求写出详细的
采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中,正确的是____。
假定不采用Cache和指令预取技术,且机器处于“开中断”状态,则在下列有关指令执行的叙述中,错误的是____。
在使用信号量机制实现互斥时,互斥信号量的初值一般为():而使用信号量机制实现同步时,同步信号量的初值一般为()。
下列选项中,用于提高RAID可靠性的措施有I.磁盘镜像Ⅱ.条带化Ⅲ.奇偶校验Ⅳ.增加cache机制
随机试题
ThePetrarchansonnetwasfirstintroducedintoEnglandby______.
下列哪项心电图改变不支持左房肥大的诊断
为防止和减少因订购期间需求增长或到货延误所引起的缺货而设置的,对作业失误和发生随机事件起着预防和缓冲作用的库存是()。
昊天国有独资公司(以下简称“昊天公司”)因经营决策失误造成严重亏损,继续经营困难,根据规定,由有关国有资产监督管理机构等政府部门组成清算组,对昊天公司的资产、债权、债务进行清理;确认该公司不能清偿到期债务,于是向其所在地的人民法院申请破产。人民法院于201
甲游客与乙国际旅行社签订了一份出国旅游合同,在合同中没有明确约定哪一方负担出境手续费。根据我国有关的法律规定,该手续费应当由()负担。
启发式教学是一种()
假设程序PA和PB单独执行时所需的时间分别用TA和TB表示,并且假设TA=1h,TB=1.5h,其中处理器工作时间分别为TA=18min,TB=27min,如果采用多道程序设计方法,让PA和PB并行工作,假定处理器利用率达到50%,系统开销为15
A、 B、 C、 D、 B
下列关于IPS的描述中,错误的是______。
学校图书馆规定,一名旁听生同时只能借一本书,一名在校生同时可以借5本书,一名教师同时可以借10本书,在这种情况下,读者与图书之间形成了借阅关系,这种借阅关系是()。
最新回复
(
0
)