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

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

1、在线索化二叉树中，T所指结点没有左子树的充要条件是（ ）。

A、T-> lchild=NULL

B、T->ltag=1

C、t->ltag=1且t-> lchild =Null

D、以上都不对

2、一个带有头结点的单链表为空的判定条件是（ ）。

A、head == NULL

B、head->next == NULL

C、head->next == head

D、head != NULL

3、线性链表不具有的特点是（ ）。

A、随机访问

B、不必预估所需存储空间大小

C、插入与删除时不必移动元素

D、所需空间与线性表长度成正比

4、在下面的排序方法中，稳定的是（ ）。

A、希尔排序

B、堆排序

C、插入排序

D、快速排序

5、设有n个待排序的记录关键字，则在堆排序中需要（ ）辅助记录空间。

A、O（1）

B、O（n）

C、O（nlog2n）

D、O（n2）

6、数组A［５］［６］的每个元素占5个字节，将其按行优先次序存储。假设A[1][1]元素的存储地址为1000，则元素A［５，５］的存储地址为（ ）。

A、1140

B、1145

C、1120

D、1125

7、高度为n的完全二叉树的结点数至少为（ ）。

A、2n-1

B、2n-1+1

C、2n

D、2n+1

8、设有一个无向图G=（V，E）和G’=（V’，E’），如果G’为G的生成树，则下面不正确的说法是（ ）。

A、G’为G 的子图

B、G’为G 的连通分量

C、G’为G的极小连通子图且V’=V

D、G’为G的一个无环子图

1、试题答案：B

试题解析：

本题考查线索二叉树的判断条件。
在线索二叉树中，区分某结点的指针域存放的是指针还是线索的方法为为每个结点增设两个标志域ltag和rtag来实现。当ltag=0时，lchild指向结点的左孩子；当ltag=1时，lchild指向结点的前驱结点；当rtag=0时，rchild指向结点的右孩子；当rchild=1时，rchild指向结点的后继节点。因此B正确。对于A，T-> lchild=NULL有左子树，只是左子树为空，因此A错误。C与A同理。故本题选B。

2、试题答案：B

试题解析：

本题考查单链表的基本操作。
单链表的head指向头结点，因此head==NULL指的是头结点为空，因此A错误。head的next指向链表的第一个元素，当head->next为空时，该单链表为空，因此B正确。C选项是带头结点的单循环链表为空是的判空操作，因此C错误。D选项不是判空操作，故本题选B。

3、试题答案：A

试题解析：

本题考查线性链表的特点。
线性链表无法随机访问，当需要访问结点时，必须从头结点开始。因此A错误。链表采用动态分配内存，因此不必预估空间，因此B正确。当插入一个新结点时，只需添加结点并修改相应的指针链接，插入和删除都不需要移动元素，因此C正确。链表的每一个结点均需要分配空间，所需空间与线性表长度成正比，因此D正确。故本题选A。

4、试题答案：C

试题解析：

本题考查排序方法的稳定性。
算法的稳定性是指若排序后的序列不改变原序列中相同关键字的相对位置，则称为稳定性排序，否则为不稳定性排序。插入排序是稳定性排序，而希尔排序、堆排序、快速排序在排序的过程中可能改变相同元素的相对位置，故本题选C。

5、试题答案：A

试题解析：

本题考查堆排序的辅助空间。
堆排序只需要一个记录大小的辅助空间，每个待排记录仅占有一个存储空间。故本题选A。

6、试题答案：A

试题解析：

本题考查数组的存储。
矩阵在计算机中按照线性表进行存储的，有行存储和列存储。本题按行存储，且首地址为A[1][1]，因此计算公式为：[（5-1）*6+（5-1）]*5+1000=1140。故本题选A。

7、试题答案：A

试题解析：

本题考查完全二叉树的性质。
高度为n的完全二叉树从第1层到第n-1层是一个满二叉树，因此每层的结点个数为2i-1个，当高度为n-1层时，结点个数为20+21+22+……+2n-2=2n-1-1。题干要求至少有多少个结点个数，则第n层需要有一个结点，总的结点数为2n-1。故本题选A。

8、试题答案：B

试题解析：

本题考查图的连通性。
对于A，图的生成树是其子图，因此A正确。对于C和D，G的生成树是G的极小连通子图，而G的连通分量是G的极大连通子图，因B错误C正确。对于D，生成树是一个无环图，因此D正确。故本题选B。