软考初级

对于n个元素的关键字序列K1，K2，…，Kn，若有Ki≤K2i≤且Ki≤2i+1(i=1，2，…，[n/2]，2i+1≤n)，则称其为小根堆。以下关于小根堆及其元素关系的叙述中，错误的是( )。A．关键字序列K1，K2，…，Kn呈非递减排序时一定为小根堆B．小根堆中的序列K1，K2，K4…，K2j(2j≤n)一定为非递减序列C．小根堆中元素K2i与K2i+1(2i≤n，2i+1≤n)之间的大小关系不能确定D．小根堆的最后一个元素一定是序列的最大元素

题目

对于n个元素的关键字序列K1，K2，…，Kn，若有Ki≤K2i≤且Ki≤2i+1(i=1，2，…，[n/2]，2i+1≤n)，则称其为小根堆。以下关于小根堆及其元素关系的叙述中，错误的是( )。

A．关键字序列K1，K2，…，Kn呈非递减排序时一定为小根堆

B．小根堆中的序列K1，K2，K4…，K2j(2j≤n)一定为非递减序列

C．小根堆中元素K2i与K2i+1(2i≤n，2i+1≤n)之间的大小关系不能确定

D．小根堆的最后一个元素一定是序列的最大元素

如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

对于n个元素的关键宇序列{k1,k2,...kn}，当且仅当满足关系ki≤k2i且ki≤k2i+1{i=1.2...[n/2]}时称其为小根堆（小顶堆）。以下序列中，（60）不是小根堆。

A.16,25,40,55,30,50,45
B.16,40,25,50,45,30,55
C.16,25,39.,41,45,43,50
D.16,40,25,53,39,55,45

答案：D
解析：
按照条件“ki≤k2i且ki≤k2i+1”要求，带入四个选项。以选项A为例，当i=时，K1（16）

第2题：

对于n个元素的关键字序列{K1,K2,…,Kn},当目仅当满足Ki<=K2i且Ki<=K2i+1（1="则称其为大顶堆。由此可知，以下选项中，（ ）是大顶堆。

A.2,1,4,5,3
B.5,3,2,4,1
C.5,3,4,1,2
D.4,2,5,1,3

答案：C
解析：
这种题代数是最合适的方法，可以设i=1，2，例如等于2时则有K2>=K4，K2>=K5，分别代入计算可以发现只有C选项序列满足大顶堆的要求。

第3题：

对于n个元素的关键字序列{K1,K2,…,Kn},当目仅当满足Ki<=K2i且Ki<=K2i+1（1="则称其为大顶堆。由此可知，以下选项中，（ ）是小顶堆。

A.1,2,7,4,5,6,3
B.1,5,3,2,6,4,7
C.1,2,3,4,6,5,7
D.1,6,4,2,5,7,3

答案：C
解析：
这种题代数是最合适的方法，可以设i=1，2，3，例如等于2时则有K2<=K4，K2<=K5，分别代入计算可以发现只有C选项序列满足小顶堆的要求。

第4题：

对于n个元素的关键字序列{K1,K2,…,Kn},当目仅当满足Ki<=K2i且Ki<=K2i+1(1="则称其为大顶堆。由此可知,( )是大顶堆。

A.7,2,3,4,5,6,1
B.7,5,4,2,6,3,1
C.7,6,4,2,5,3,1
D.7,5,3,1,6,4,2

答案：C
解析：
这种题代数是最合适的方法，如选项C中可以设i=2，则有K2>=K4，K2>=K5，对照序列“7,6,4,2,5,3,1”可以满足大顶堆的要求。

第5题：

对于n个元素的关键字序列{ki, k2,…，kn},当且仅当满足关系ki≤k2i且ki≤k2i+i（i=1, 2,…[n/2]）时称为小根堆（小顶堆）。以下序列中，（ ）不是小根堆。

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不是堆。

第6题：

对于n个元素的关键字序列{k1,k2,…,kn)，当且仅当满足关系Ki≤K2i且Ki≤K2i+1(2i≤n,2i+1≤n)称其为小根堆，反之则为大根堆。以下序列中，(58)不符合堆的定义。

A．(5,10,15,76,39,27,18)

B．(5,10,18,76,39,27,15)

C．(59,27,36,15,8,25,9)

D．(59,36,27,15,8,25,9)


正确答案：B
解析：将4个选项的序列中元素放入一棵完全二叉树，如图1-7所示，以便于观察节点ki、k2i、k2i+1≤n,2i+1≤n)之间的关系。按照小根堆的定义检查选项A、B的二叉树，按照大根堆的定义检查选项C、D的二叉树，显然，选项B不符合小根堆的定义。

第7题：

堆是一个键值序列{k1，k2,……kn)，对i=1，2…，|n/2|，满足(48)。

A．ki＜k2i+1＜k2i

B．ki≤k2i≤k2i+1

C．ki≤k2i 且ki≤k2i+1(2i+1≤n)

D．ki≤k2i或ki≤k2i+1(2i+1≤n)


正确答案：C
解析：本题考查堆的定义。在数据结构中，堆的定义如下：n个元素的序列{k1，k2，…，kn)当且仅当满足关系ki≤k2i且ki≤k2i+1或者kik2i且ki≤k2i+1(2i+1≤n)时，才称为堆。满足关系ki≤k2i且ki≤k2i+1的是小顶堆，满足关系kik2i且kik2i+1的是大顶堆。

第8题：

对于n个元素的关键字序列{k1，k2，…，kn}，当且仅当满足关系ki≤K2i且ki≤K2i(2i≤n,2i+1≤n)称其为小根堆，反之则为大根堆。以下序列中，(38)不符合堆的定义。

A．(5，10，15，76，39，27，18)

B．(5，10，18，76，39，27，15)

C．(59，27，36，15，8，25，9)

D．(59，36，27，15，8，25，9)


正确答案：B
解析：将4个选项序列的元素放入一棵完全二叉树，如图4-6所示，以便于观察节点ki、k2i、k2i+1(2i≤n，2i+1≤n)之间的关系。按照小根堆的定义检查选项A、B的二叉树，按照大根堆的定义检查选项C、D的二叉树，显然，选项B不符合小根堆的定义。

第9题：

对于n个元素的关键字序列{k1，k2，…，kn}，当且仅当满足关系ki≤k2i，且ki≤k2i+1(2i≤ n,2i+1≤n)称其为小根堆，反之则为大根堆。以下序列中，(56)不符合堆的定义。

A．(4,10,15,72,39,23,18)

B．(58,27,36,12,8,23,9)

C．(4,10,18,72,39,23,15)

D．(58,36,27,12,8,23,9)


正确答案：C
解析：本题考查堆的概念。将序列中的元素放入一棵完全二叉树，如下所示，以便于观察结点　ki,k2i和ki、k2i+1(2i≤n,2i+1≤n)之间的关系。

按照小根堆的定义检查选项A和C，按照大根堆的定义检查选项B和D，显然，选项C不符合小根堆的定义。

相关内容