2014年数据结构考研真题答案及解析（二）

本文提供2014年数据结构考研真题答案及解析，以下为具体内容

1、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ）。

A、20

B、30

C、40

D、45

2、执行一趟快速排序能够得到的序列是（ ）。

A、["41，12，34，45，27"]

B、["45，34，12，41"]

C、["63，12，34，45，27"]

D、["12，27，45，41"]

3、设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。

A、head==0

B、head->next==0

C、head->next==head

D、head!=0

4、时间复杂度不受数据初始状态影响而恒为O（nlog2n）的是（ ）。

A、堆排序

B、冒泡排序

C、希尔排序

D、快速排序

5、设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）。

A、空或只有一个结点

B、高度等于其结点数

C、任一结点无左孩子

D、任一结点无右孩子

6、一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。

A、堆排序

B、冒泡排序

C、快速排序

D、希尔排序

7、设某棵三叉树中有40个结点，则该三叉树的最小高度为（ ）。

A、3

B、4

C、5

D、6

8、顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ）。

A、O（n）

B、O（n²）

C、O（n^1/2）

D、O（1og₂n）

9、二路归并排序的时间复杂度为（ ）。

A、O（n）

B、O（n²）

C、O（nlog₂n）

D、O（1og₂n）

10、深度为k的完全二叉树中最少有（ ）个结点。

A、2^k-1-1

B、2^k-1

C、2^k-1+1

D、2^k-1

1、试题答案：D

试题解析：

【考点】本题考查哈夫曼树的构造。
【解析】假设上述权值对应关键字序列abcde，构造哈夫曼树如下： 

根据构造的哈夫曼树，计算带权路径长度为：（4+5+6）*2+（2+3）*3=45。故本题选D。

2、试题答案：A

试题解析：

【考点】本题考查快速排序的思想。
【解析】快速排序一趟排序之后，枢纽左边的值都比枢纽小，枢纽右边的值比枢纽大。本题中，枢纽=55，A选项中左边序列的值均比55小，右边序列的值均比55大，因此A选项正确。B选项中，枢纽右边的27比55小，因此B选项错误。C选项中63不应在左边，41不应在右边。因此C选项错误。D选项中，34不应在右边，因此D选项错误。故本题选A。

3、试题答案：A

试题解析：

【考点】本题考查单链表的判空条件。
【解析】不带头节点的单链表，为空时head==0，因此A正确。带头结点的单链表判空：head->next=0，因此B错误。带头结点的单循环链表为空：head->next=head，因此C错误。D中“!=0”不是判空的条件，因此D错误。故本题选A。

4、试题答案：A

试题解析：

【考点】本题考查排序算法的时间复杂度。
【解析】堆排序在平均情况、最坏情况、最好情况下的时间复杂度均为O（nlog₂n）。而B、C、D均受数据初始状态的影响，故本题选A。

5、试题答案：B

试题解析：

【考点】本题考查二叉树的遍历。
【解析】先序遍历二叉树先访问根结点，再遍历左子树，最后遍历右子树。后序遍历二叉树先遍历左子树，再遍历右子树，最后访问根结点。因此，当该树任一结点的左孩子不存在时，先序遍历的顺序成了根->右，后序遍历的顺序成了右->根，满足序列正好相反；同理，当该树任一结点的右孩子不存在时，先序遍历的顺序成了根->左，后序遍历的顺序成了左->根，满足序列正好相反。因此，当二叉树任一结点无左孩子或任一结点无右孩子时，其先序遍历和后序遍历得到的序列正好相反。C和D选型没有包含所有情况，A选项不满足题干要求，故本题选B。

6、试题答案：D

试题解析：

【考点】本题考查排序算法的对比。
【解析】对于A，堆排序通过建立大根堆或小根堆，每次都可以把序列中的最大值或最小值选择出来，因此一趟排序后，能够选出一个值放在最终位置上。对于B，冒泡排序的思想为通过对无序序列中关键字间的比较和交换，将大值向一头下沉，小的值向另一头漂浮，因此一趟冒泡排序也能够选择出序列中的极大值或极小值。对于C，快速排序每趟排序都可以最终确定枢纽的位置，使得枢纽左边的值小于枢纽，枢纽右边的值大于枢纽。对于D，希尔排序是增量的排序，一趟排序后无法最终选择出一个元素最终的位置。故本题选D。

7、试题答案：B

试题解析：

【考点】本题考查三叉树的性质。
【解析】根据题干，当三叉树为满三叉树时，三叉树的高度最小。第1层结点数为1，第二层结点数为3，第三层结点数为9，第4层结点数为27，1+3+9+27=40。此时三叉树的高度最小，为4。故本题选B。

8、试题答案：A

试题解析：

【考点】本题考查顺序查找的时间复杂度。
【解析】顺序查找时需遍历其表，故时间复杂度为O（n），而B、C、D选项均不符合顺序查找的特性，故本题选A。

9、试题答案：C

试题解析：

【考点】本题考查归并排序的时间复杂度。
【解析】归并排序的基本思想为：在待排序的原始记录序列R[s……t]中取一个中间位置（s+t）/2，先分别对子序列R[s……（s+t）/2]和R[（s+t）/2+1……t]进行排序，再将子序列归并为一个有序记录序列。该算法是一个递归排序。归并排序在平均情况、最坏情况、最好情况下的时间复杂度均为O（nlog₂n） ，故本题选C。

10、试题答案：B

试题解析：

【考点】本题考查完全二叉树的性质。
【解析】二叉树的定义为二叉树是一种树形结构，特点为每个结点最多只有两棵子树，其子树有左右之分。二叉树有如下性质：
（1）在二叉树的第i层上至多有2^i-1个结点（i>=1）。
（2）深度为k的二叉树至多有2^k-1个结点。
（3）对任何一棵二叉树，若终端结点为n0，度为2的结点为n2，则n0=n2+1。
（4）具有n个结点的完全二叉树的深度为⎿lon₂n⏌ +1。
根据题干，深度为k的完全二叉树第1至第k-1层为满二叉树，第k层为1个结点，此时完全二叉树的结点数最少。即总的结点数为=1+2¹+2²+……+2^k-2+1=2^k-1。故本题选B。