关于堆的一些问题： (1)堆的存储表示是顺序的，还是链接的? (2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对n个元素进行初始建堆的过程中，最多做多少次数据比

admin2019-08-15 56

问题关于堆的一些问题：
(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ⁱ×(h一i)=[*]2^h-j×j≤(2n)[*]j／2^j≤4n 提示：此题考查的知识点是堆的基本定义及效率。堆定义为n个关键字序列K₁，K₂，…，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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

清政府在鸦片战争中战败的主要原因是()。

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题当代史学界认为安禄山、史思明反唐是一场叛乱，其基本理由是他们()

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

西周的分封制相当发达，是西周的重要政治制度，也是西周历史的一个显著特点。根据所学知识，回答问题西周建立之后，派遣同姓贵族和异姓贵族及归顺的异族首领到各地区，建立国家以藩屏护卫周室，()分封诸侯的规模最大

米勒兰事件

下面关于进程的叙述中，正确的是()。

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

float型数据通常用IEEE754单精度浮点数格式表示。若编译器将float型变量x分配到一个32位浮点寄存器FRl中，且x=一8．25，则FRl的内容是____。

防止高压储罐爆炸的四项措施为()。

不变期间

《公路工程国内招标文件范本》规定，索赔事件发生后的()天内，承包人应向监理工程师提交索赔意向通知。

凯恩斯认为，投机动机形成的投机需求与利率(　　)。

因材施教就是根据教材的特点进行教学。()

如果你这次公选成功，走上领导岗位后，却发现自己并不适应，甚至不能胜任新的领导岗位的工作，身边的同志对你也有些看法，你如何办?面对这种情况，以后你将如何打开工作局面?

(2018年第9题)近代中国半殖民地半封建社会的主要矛盾，呈现出错综复杂的状况。其中，贯穿整个中国半殖民地半封建社会的始终，并对中国近代社会的发展变化起着决定性作用的最主要的矛盾是

设，若f’(0)存在，则k为()。

InthewesternUnitedStatesonecanstillfindpoststowhichnineteenth-centurycowboyshitchedtheirhorses.

计算机408

学硕统考专业

清政府在鸦片战争中战败的主要原因是()。

唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落，而且对后来的历史产生了严重影响。据此回答问题当代史学界认为安禄山、史思明反唐是一场叛乱，其基本理由是他们()

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

西周的分封制相当发达，是西周的重要政治制度，也是西周历史的一个显著特点。根据所学知识，回答问题西周建立之后，派遣同姓贵族和异姓贵族及归顺的异族首领到各地区，建立国家以藩屏护卫周室，()分封诸侯的规模最大

米勒兰事件

下面关于进程的叙述中，正确的是()。

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

float型数据通常用IEEE754单精度浮点数格式表示。若编译器将float型变量x分配到一个32位浮点寄存器FRl中，且x=一8．25，则FRl的内容是____。

防止高压储罐爆炸的四项措施为()。

不变期间

《公路工程国内招标文件范本》规定，索赔事件发生后的()天内，承包人应向监理工程师提交索赔意向通知。

凯恩斯认为，投机动机形成的投机需求与利率( )。

因材施教就是根据教材的特点进行教学。()

如果你这次公选成功，走上领导岗位后，却发现自己并不适应，甚至不能胜任新的领导岗位的工作，身边的同志对你也有些看法，你如何办?面对这种情况，以后你将如何打开工作局面?

(2018年第9题)近代中国半殖民地半封建社会的主要矛盾，呈现出错综复杂的状况。其中，贯穿整个中国半殖民地半封建社会的始终，并对中国近代社会的发展变化起着决定性作用的最主要的矛盾是

设，若f’(0)存在，则k为()。

InthewesternUnitedStatesonecanstillfindpoststowhichnineteenth-centurycowboyshitchedtheirhorses.

凯恩斯认为，投机动机形成的投机需求与利率(　　)。