2. 从业资格
  3. 对于n个元素的关键字序列K1，K2，…，Kn，若有Ki≤K2i且Ki≤K2i+l

对于n个元素的关键字序列K1，K2，…，Kn，若有Ki≤K2i且Ki≤K2i+l

练习题库2022-08-02  35
问题 对于n个元素的关键字序列K1，K2，…，Kn，若有Ki≤K2i且Ki≤K2i+l（i= 1，2…， [n/2]，2i+1≤n），则称其为小根堆。以下关于小根堆及其元素关系的叙述中，错误的是（  ）。A.关键字序列K1，K2，…，Kn呈非递减排序时一定为小根堆B.小根堆中的序列K1，K2，K4，…，K2j（2j≤n）一定为非递减序列C.小根堆中元素K2i与K2i+l（2i≤n，2i＋1≤n）之间的大小关系不能确定D.小根堆的最后一个元素一定是序列的最大元素
选项 A.关键字序列K1，K2，…，Kn呈非递减排序时一定为小根堆
B.小根堆中的序列K1，K2，K4，…，K2j（2j≤n）一定为非递减序列
C.小根堆中元素K2i与K2i+l（2i≤n，2i＋1≤n）之间的大小关系不能确定
D.小根堆的最后一个元素一定是序列的最大元素
答案 D
解析 本题考查数据结构基础知识。    下图所示为一小根堆。当关键字序列呈现非递减排列时符合小根堆的定义。在小根堆中，K1是K2的父结点，K2是K4的父结点，依此类推，根据定义，K1，K2，K4，…， K2j，呈现非递减排列。小根堆中，Ki是K2i和K2i+1的父结点，定义中保证Ki≤K2i以及Ki≤K2i+1，而K2i与K2i+1的大小关系则不确定。如上例中，K2≤K4且K2≤K5，但K4≤K5，同时K3≤K6且K3≤K7，而K6≥K7。小根堆的第一个元素一定是最小元素，而最后一个元素不能保证是最大元素。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2427854.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)