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

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

1、m阶B-树中的m是指（ ）。

A、每个结点至少具有m棵子树

B、每个结点最多具有m棵子树

C、分支结点中包含的关键字的个数

D、m阶B-树的深度

2、设给定权值总数有n个，其哈夫曼树的结点总数为（ ）。

A、不确定

B、2n

C、2n+1

D、2n-1

3、设关键字序列为：3，7，6，9，8，1，4，5，2，将之进行排序的最小交换次数是（ ）。

A、6

B、7

C、8

D、20

4、一棵左子树为空的二叉树在先序线索化后，其中的空链域个数为（ ）。

A、0

B、1

C、2

D、不确定

5、将一棵树T转换为孩子--兄弟链表表示的二叉树h，则T的后根序遍历是h的（ ）。

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

6、若在序列中采用折半查找法进行查找，用来描述该查找过程的判定树的形状与（ ）有关。

A、序列中元素的值

B、序列中元素的排序次序

C、序列中元素的类型

D、序列中元素的个数

7、在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）。

A、

B、

C、

D、

8、以下术语中与数据结构的存储无关的是（ ）。

A、线索树

B、哈希表

C、栈

D、循环队列

9、需要分配较大的空间，插入和删除不需要移动元素的线性表，其存储结构为（ ）。

A、单链表

B、静态链表

C、顺序表

D、双链表

1、试题答案：B

试题解析：

【考点】本题考查数据结构--查找--动态查找表--B-树--B-树的性质。
【解析】一棵m阶非空B树满足以下特点：
（1）每个结点至多有m个子树，也就是说每个结点至多有m-1个关键字；
（2）若根结点不是终端结点，那么至少有两棵子树；
（3）除根结点以外的所有非叶子结点至少有⌈m/2⌉棵子树，及至少含有⌈m/2⌉-1个关键字；
（4）所有非叶子结点中的关键字是顺序排列的，且非叶子结点的子树总比关键字多一个。
综上所述，m阶B-树中的m是指每个结点最多具有m棵子树。故本题选B。

2、试题答案：D

试题解析：

【考点】本题考查数据结构--树与二叉树--树与二叉树的应用--哈/赫夫曼树及其编码--哈/赫夫曼树的构造。
【解析】哈夫曼树中只存在度为0和度为1的结点，且树中存在数量关系n0+n2=2n2+1，即n0=n2+1。由题干知n0=n，则该哈夫曼树的结点总数为n+(n-1)=2n-1。故本题选D。

3、试题答案：A

试题解析：

【考点】本题考查数据结构--排序。
【解析】采用简单选择排序的交换次数为6次，过程如下。而6为选项中的最小交换次数。故本题选A。
第一趟排序选择最小元素1与3交换得：176983452；
第二趟排序选择最小元素2与7交换得：126983457；
第三趟排序选择最小元素3与6交换得：123986457；
第四趟排序选择最小元素4与9交换得：123486957；
第五趟排序选择最小元素5与8交换得：123456987；
第六趟排序选择最小元素6，无需交换：123456987；
第七趟排序选择最小元素7与9交换得：123456789；

4、试题答案：C

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--线索二叉树。
【解析】一棵左子树为空的二叉树在先序线索化后，其根结点没有前驱结点，则该结点的左指针域为空；其最右下结点（先序序列最后一个结点）没有后继结点，则该结点的右指针域为空。因此，一棵左子树为空的二叉树在先序线索化后，其中的空链域个数为2。故本题选C。

5、试题答案：B

试题解析：

【考点】本题考查数据结构--树与二叉树--树与森林--树、森林、二叉树的相互转换--树转换为二叉树。
【解析】由下表知，树的先根遍历对应二叉树的中序遍历。故本题选B。

6、试题答案：D

试题解析：

【考点】本题考查数据结构--查找--静态查找表--折半查找--折半查找的应用。
【解析】折半查找判定树一定是一棵平衡二叉树，序列中元素的个数可以决定该判定树的高度，而序列中元素的值、排序次序和类型对判定树的形状没有影响。故本题选D。

7、试题答案：B

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构--线性表的链式存储结构--单链表--单链表的基本操作--单链表的插入。
【解析】单链表只能从头开始遍历以查找应该插入的位置，所以在保持链表有序的情况下插入一个新结点的时间复杂度为O（n）。故本题选B。

8、试题答案：C

试题解析：

【考点】本题考查数据结构--绪论--数据结构的三要素--数据的存储结构/物理结构。
【解析】数据的存储结构包括顺序存储、链式存储、索引存储和散列存储。线索树属于链式存储结构，哈希表属于散列存储结构，循环队列属于顺序存储结构。而栈是一种逻辑结构，既可以顺序存储，称之为顺序栈，也可以链式存储，称之为链栈。故本题选C。

9、试题答案：B

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构--线性表的链式存储结构--链表的综合对比。
【解析】单链表和双链表虽然插入和删除不需要移动元素，但是其结点空间是动态分配的，不需要一次性分配较大的空间。而顺序表插入和删除可能需要移动大量元素。静态链表中定义一个较大的结构数组作为存储结点的空间，删除和插入元素时也只需要修改游标即可，插入和删除可以不需要移动元素。因此需要分配较大的空间，插入和删除不需要移动元素的线性表，其存储结构为静态链表。故本题选B。