问答题
请回答下列关于堆(Heap)的一些问题。【清华大学2000五(12分)】
问答题
堆的存储表示是顺序的，还是链接的?
【正确答案】正确答案：堆的存储是顺序的。
【答案解析】
问答题
设有一个最小堆，即堆中任意结点的关键字均大于它的左子女和右子女的关键字。其具有最大值的元素可能在什么地方?
【正确答案】正确答案：最大值元素一定是叶子结点，可以在[n／2]+1..n间的任何位置上。说明：原题“设有一个最小堆，即堆中任意结点的关键码均
大于
它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方”的叙述有误，应将“大于”改为“小于”。最大值元素一定是叶子结点。
【答案解析】
问答题
对，1个元素进行初始建堆的过程中，最多做多少次数据比较(不用大0表示法)?
【正确答案】正确答案：在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下：由于第i层上的结点数至多是2
r-1
，以它为根的二叉树的深度为h一i+1，则调用[n／2]次筛选算法时总共进行的关键字比较次数不超过下式之值：
【答案解析】