首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
专升本
下列四个序列中,( )是堆。
下列四个序列中,( )是堆。
admin
2014-10-20
39
问题
下列四个序列中,( )是堆。
选项
A、75,65,30,15,25,45,20,10
B、75,65,45,10,30,25,20,15
C、75,45,65,30,15,25,20,10
D、75,45,65,10,25,30,20,15
答案
C
解析
堆排序是另一种基于选择的排序方法。n个元素的序列{k
1
,k
2
,k
3
,…,k
n
),当且仅当满足以下关系时,称之为堆:k
i
<=k
2i
;k
i
<=k
2i+1
或者 k
i
>=k
2i
;k
i
>=k
2i+1
其中i=1,2,…,n/2。若将同以上序列对应的一维数组看成是一棵完全二叉树,则堆的含义表明:该完全二叉树的所有非终端结点均不大于(或不小于)其左、右孩子结点的值。由此,若{k
1
,k
2
,k
3
,…,k
n
)是堆,则堆顶元素(或完全二叉树的根结点)必定是该序列n个元素中的最小值(或者最大值)。若将堆看成是一棵以k
1
为根的完全二叉树,则这棵完全二叉树中的每个非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此可以看出,若一棵完全二叉树是堆,则根结点一定是这n个结点中的最小者(或最大者)。下面图给出的两个堆的示例。
从堆的定义可以看出,若将堆用一棵完全二叉树表示,则根结点是当前堆中所有结点的最小者(或最大者)。堆排序的基本思想是:首先将待排序的记录序列构造一个堆,此时,选出了堆中所有记录的最小者或最大者,然后将它从堆中移走,并将剩余的记录再调整成堆,这样又找出了次小(或次大)的记录,以此类推,直到堆中只有一个记录为止,每个记录出堆的顺序就是一个有序序列。
转载请注明原文地址:https://kaotiyun.com/show/IqvR777K
本试题收录于:
计算机科学与技术题库普高专升本分类
0
计算机科学与技术
普高专升本
相关试题推荐
目前医院常用的灭菌剂是()。
病例书写不要求()。
可变荷载的代表值_________、_________和_________。
中国共产党成立的标志是——()
不是纵向循行的经脉是:()
关十刺激强度与刺激时间的关系是
可识别DNA特异序列,并在识别位点或其周围切割双链DNA的一类酶称为()
下列只能获得有关被审计单位内部控制执行方面证据的审计程序是()。
若一个叶子是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序遍历的最后一个结点。()
根据数据元素之间关系的不同,数据的逻辑结构划分为_______、_______、_______和_______。
随机试题
地西泮作为镇静催眠药的优点不包括
根尖大喇叭口的年轻恒牙死髓牙根尖诱导成形术的常用药物是
显微鉴别时确认淀粉粒应加
下列与个人任职有关的收入中,可按全年一次性奖金的计税方法计算缴纳个人所得税的有()。
供应链是围绕()建立的稳定商业关系。
()鼓励应聘者继续与面试考官交流,表达出对信息的关心和理解,
化学是一门以实验为基础的学科。关于以“实验为基础”中实验的含义正确的一项是()。
2017年发布的《汽车产业中长期发展规划》把大力发展汽车先进技术,形成新能源汽车、智能联网汽车和先进节能汽车梯次合理的产业格局以及完善的产业配套体系,引领汽车产业转型升级作为重点任务之一来抓。抓住这一重点任务体现的方法论要求有()。①善于把握复杂
公共设施
Whatthepassagetellsuscanbesummarizedbythestatementthat______.Thispassagesuggeststhatawell-organizedfamilyis
最新回复
(
0
)