首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题: 对n个元素进行初始建堆的过程中,最多做多少次数据比较(不用大O表示法)?
关于堆的一些问题: 对n个元素进行初始建堆的过程中,最多做多少次数据比较(不用大O表示法)?
admin
2019-08-01
41
问题
关于堆的一些问题:
对n个元素进行初始建堆的过程中,最多做多少次数据比较(不用大O表示法)?
选项
答案
在建含有n个元素、深度为h的堆时,其比较次数不超过4n,推导如下: 由于第i层上的结点数至多是2
i-1
,以它为根的二叉树的深度为h-i+1,则调用[n/2]次筛选算法时总共进行的关键字比较次数不超过下式之值: [*]
解析
此题考查的知识点是堆的基本定义及效率。堆定义为n个关键字序列K
1
,K
2
,…,K
n
,当且仅当该序列满足如下性质(简称为堆性质):
(1)k
i
≤K
2
,且k
i
≤K
2i+1
或
(2)k
i
≥K
2
;且k
i
≥K
2i+1
(1≤i≤n)。k
i
相当于二叉树的非叶结点,K
2i
则是左孩子,k
2i+1
是右孩子。
转载请注明原文地址:https://kaotiyun.com/show/HNCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
明朝初加强专制统治的措施中,与后来宦官专权有直接关系的是()。
下列不属于苏联高度集中的经济政治体制产生的条件的是()。
1962年2月,中共中央发出《关于改变农村人民公社基本核算单位问题的指示》,规定人民公社的基本核算单位是()。
南京政府通过的《中华民国国民政府组织法》中,最终确立的“五院政府"包括()。
1928年10月,国民党中央常务委员会通过的废除议会制度的文件是()。
文件系统的主要目的是()。
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
某会议有n个参与者,等大家到齐后会议才能开始,利用P、V原语操作实现会议参与者进程。
设某多道程序系统中有用户使用内存1000M,打印机1台。系统采用可变分区动态分配算法管理内存,而对打印机采用静态分配。假设输入输出操作时间忽略不计,采用最短剩余时间优先的进程调度算法,进程最短剩余时间相同时采用先来先服务的算法,进程调度时机选择在进程执行结
CSMA/CA是如何实现“冲突避免”的?
随机试题
WhatdowemeanbyaperfectEnglishpronunciation?Inone【C1】______thereareasmanydifferentkindsofEnglishastherearesp
下列不属于肌张力障碍的是
检查者被动屈伸偏瘫侧肘关节,伸肘一半后感到阻力稍增加,按改良Ashworth分级为
有关纤维蛋白溶解药叙述错误的是
A.支气管癌B.肺脓肿C.百日咳D.支气管内异物E.空洞型肺结核咳嗽带有鸡鸣样吼声常见于()
经产妇,40岁。近2年痛经并逐渐加重,伴经量增多及经期延长,届时需服强止痛药。查子宫均匀增大如孕8周,质硬,有压痛,经期压痛明显。
【背景资料】某项目部在北方地区承担某城市主干路道路工程施工任务,设计快车道宽11.25m,辅路宽9m。项目部应业主要求,将原计划安排在次年5月初施工的沥青混凝土面层,提前到当年12月上旬和中旬,抢铺出一条快车道以缓解该市交通。【问题】为保证
根据《检疫法》的规定,入境的交通工具和人员,必须在()的指定地点接受检疫。
“精卫填海”“夸父逐日”等神话故事出自下列哪部作品?
A.rubbishB.sayC.manyD.greatE.hardlyF.visitG.fearalotof
最新回复
(
0
)