首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
关于堆的一些问题: (1)堆的存储表示是顺序的,还是链接的? (2)设有一个最小堆,即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中,最多做多少次数据比
admin
2019-08-15
45
问题
关于堆的一些问题:
(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
学硕统考专业
相关试题推荐
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题西周建立之后,派遣同姓贵族和异姓贵族及归顺的异族首领到各地区,建立国家以藩屏护卫周室,()分封诸侯的规模最大
卡诺莎事件
在4×100米接力赛中,4个运动员之间存在如下关系:运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交棒给运动员3;运动员3也只有接到运动员2传来的接力棒后才能往前跑,他跑完100米
在集中式总线仲裁中,()方式响应时间最快。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
TCP使用()机制来进行流量控制。
下列的网络协议中,()的运输层协议是使用TCP的。
设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页(Page)数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame)。在时刻260前的该进程访问情况见表B一2(访问位即使
float型数据通常用IEEE754单精度浮点数格式表示。若编译器将float型变量x分配到一个32位浮点寄存器FRl中,且x=一8.25,则FRl的内容是____。
以下关于CPU的叙述中,错误的是()。
随机试题
一般而言,按照农业生产力水平划分,世界农业发展经历了原始农业、传统农业和()三个阶段。
二审全部改判的案件,判决结果应当首先写明
A.氨苄西林B.苯唑西林C.羧苄西林D.青霉素E.苄星青霉素耐药金黄色葡萄球菌感染
面瘫伴舌麻,味觉减退,除主穴外,还应选取的配穴是
溶血反应的早期特征是
A.高氯酸滴定液B.亚硝酸钠滴定液C.氢氧化钠滴定液D.硫酸盐滴定液E.硝酸银滴定液以下药物含量测定所使用的滴定液是盐酸普鲁卡因()。
下列费用应由保险人负担的有:()
注:从2012年起,城市环境基础设施建设投资中不仅包括城市的环境基础设施建设投资,还包括县城的相关投资,下同。2012年全国城市环境基础设施建设投资中,与2011年相比增长最快的投资是()。
(江西财大2016)简述直接融资与间接融资的差异。
Whereisthenearestrestaurant?
最新回复
(
0
)