对于n个元素的关键字序列{ki,k2,…,kn},当且仅当满足关系ki≤k2i且

资格题库2022-08-02  38

问题 对于n个元素的关键字序列{ki,k2,…,kn},当且仅当满足关系ki≤k2i且ki≤k2i+i(i=1,2,…[n/2])时称为小根堆(小顶堆)。以下序列中,( )不是小根堆。A.12,20,36,48,25,50,40B.12,36,20,48,40,25,50C.12,20,25,36,40,48,50D.12,36,20,48,25,50,40

选项 A.12,20,36,48,25,50,40
B.12,36,20,48,40,25,50
C.12,20,25,36,40,48,50
D.12,36,20,48,25,50,40

答案 D

解析 在完全二义树中对结点可如下编号:根结点为1号,其左孩子结点为2号,右孩子结点为3号,对于编号为i的结点,其左孩子结点若存在,则编号为2i,其右孩子结点若存在,则编号为2i+1。可将序列中的元素放入一棵完全二叉树上进行判断,如下图所示。根据堆的定义,可知选项D不是堆。
转载请注明原文地址:https://tihaiku.com/congyezige/2407210.html

最新回复(0)