首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
关于堆的一些问题： 对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?
关于堆的一些问题： 对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O表示法)?
admin
2019-08-01
59
问题
关于堆的一些问题：
对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://www.kaotiyun.com/show/HNCi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列对1918年德国十一月革命说法不正确的是()。
经六朝时期的发展，南方形成了三个农业发达地区即()。
中国近代第一所外语学校、同时也是新式学堂的是()。
1940年毛泽东的《新民主主义论》:“而所谓民主主义，现在已不是旧范畴的民主主义，已不是日民主主义，而是新范畴的民主主义，而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
简述三十年战争的过程及其结果。
巴黎和会上，英美主张把原德国在山东的权利转让给日本，华盛顿会议又表示支持中国让日本归还山东的要求，英美态度发生变化的根本原因是()。
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述，不确切的是()。
下列哪部戏剧不是曹禺的作品()。
某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和汽车类，上渡船有如下规定：同类车先到先上船，客车先于货车上船，且每上4辆客车，才允许上一辆货车，若等待客不足4辆，则以货车代替，若无货车等待允许客车都上船。写一算法模拟渡口管理。
设某多道程序系统中有用户使用内存1000M，打印机1台。系统采用可变分区动态分配算法管理内存，而对打印机采用静态分配。假设输入输出操作时间忽略不计，采用最短剩余时间优先的进程调度算法，进程最短剩余时间相同时采用先来先服务的算法，进程调度时机选择在进程执行结
随机试题
Thedatashowedthatthereareupto20timesmorelightningflasheswithinclouds________bytheground-basednetwork.
乳房保健检查的最佳时间一般选择在
A、粉碎成原粉B、回流法C、提取有效成分D、提取挥发油E、煎煮法选择中药片剂原料最适宜的处理方法，含挥发性成分较多的药材用
甲(女，1984．年7月20日生)因其同居男友乙已另有新欢丙而生恨意。2004．年6月7日，甲得知当晚丙一人独居于郊外的出租屋，遂叫来好友丁(男，1986，年12月13日生)，叫其晚上去强奸丙，并给了500元“报酬”给丁，丁同意。晚9点，甲领着丁来到丙住处
《合同法》规定：当事人订立合同后分立的，除债权人和债务人另有约定的以外，( )。
1848年，芝加哥的82位谷物商发起组建了芝加哥期货交易所(CBOT)。交易所成立之初，只是一个集中进行现货交易和现货中远期合同转让的场所。远期交易方式在发展过程中，逐渐暴露出一系列问题，交易双方就商品品质、等级、价格、交货地点及时问等方面问题总是存在分歧
邓小平理论首要的基本问题是( )。
(2017年真题)高一学生小峰的父母不履行监护职责，放任小峰强行索要他人财物。依据《中华人民共和国预防未成年人犯罪法》，有权对小峰父母给予训诫的是()。
设函数在x=1处连续，则A=________．
手写笔可分为
最新回复
(
0
)
