试题出自试卷《2009年下半年程序员考试上午真题（专业解析+参考答案）》

问题1选项
A.关键字序列K ₁，K ₂，…，K _n呈非递减排序时一定为小根堆
B.小根堆中的序列K ₁，K ₂，K ₄，…，K ₂ ^j（2 ^j≤ n）一定为非递减序列
C.小根堆中元素K _2i与K _2i+l（ 2i ≤n，2i ＋1 ≤n）之间的大小关系不能确定
D.小根堆的最后一个元素一定是序列的最大元素

D

    本题考查数据结构基础知识。
    下图所示为一小根堆。

    当关键字序列呈现非递减排列时符合小根堆的定义。在小根堆中，K₁是K₂的父结点，K₂是K₄的父结点，依此类推，根据定义，K₁，K₂，K₄，…， K_2j，呈现非递减排列。小根堆中，K_i是K_2i和K_2i+1的父结点，定义中保证K_i≤K_2i以及K_i≤K_2i+1，而K_2i与K_2i+1的大小关系则不确定。如上例中，K₂≤K₄且K₂≤K₅，但K₄≤K₅，同时K₃≤K₆且K₃≤K₇，而K₆≥K₇。小根堆的第一个元素一定是最小元素，而最后一个元素不能保证是最大元素。