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

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

1、具有12个关键字的有序表，折半查找的平均查找长度（ ）。

A、3.1

B、4

C、2.5

D、5

2、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（   ）。

A、求子串

B、联接

C、匹配

D、求串长

3、稀疏矩阵一般的压缩存储方法有两种，即（ ）。

A、二维数组和三维数组

B、三元组和散列

C、三元组和十字链表

D、散列和十字链表

4、二叉树在线索化后，仍不能有效求解的问题是（ ）。

A、先序线索化二叉树中求先序后继

B、中序线索化二叉树中求中序后继

C、后序线索化二叉树中求后序后继

D、中序线索化二叉树中求中序前驱

5、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度是（ ）。

A、O(1)

B、O(n)

C、

D、

6、在线性表中最常用的操作是存取第i个元素及其前驱的值，采用（ ）存储方式最省时间？

A、顺序表

B、带头结点的单向链表

C、带头指针的双向循环链表

D、带头指针的单向循环链表

7、设head为一带头结点的循环链表的头指针，则其判断空表的条件是（ ）。

A、

B、

C、

D、

8、设n个元素进栈序列是p1，p2，p3，...，n，其输出序列是1，2，3，...，n，若p3=1，则p1的值（ ）。

A、可能是2

B、一定是2

C、不可能是3

D、不可能是2

9、以数组Q[0..m-1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ）。

A、rear-qulen

B、rear-qulen+m

C、m-qulen

D、(1+rear+m-qulen)%m

1、试题答案：A

试题解析：

各关键字的查找长度如表1所示：

根据上表平均查找长度=(1*1+2*2+3*4+4*5)/12=3.083≈3.1，故本题选A。

2、试题答案：C

试题解析：

现在要求q在p中首次出现的位置，即在p中找到一个起始位置，使得从该位置开始的连续一段字符正好是q。这个过程称为字符串匹配。字符串匹配可以使用不同的算法来实现，其中比较常见的有暴力匹配算法、KMP算法、Boyer-Moore算法等。故本题选C。

3、试题答案：C

试题解析：

稀疏矩阵是指大部分元素为0的矩阵，因此常用压缩存储方法来节省存储空间。常见的稀疏矩阵压缩存储方法有两种：
（1）三元组：将矩阵中的非零元素按行、列、值三个属性分别存储，可以用一个三元组(i,j,a[i][j])来表示一个非零元素。此方法适用于存储元素数量较少的稀疏矩阵。
（2）十字链表：将矩阵分成行链表和列链表两部分，每个非零元素既是某个行链表中的一个结点，也是某个列链表中的一个结点，两部分链表通过结点共享表示矩阵。此方法适用于存储元素数量较多的稀疏矩阵。故本题选C。

4、试题答案：C

试题解析：

在二叉树的后序线索化过程中，如果要求某个结点的后继，则需要遍历整棵树，因为后序遍历的顺序是左子树、右子树、根节点，所以在后序线索化后的二叉树中，一个结点的后继可能在其右子树中，也可能在其祖先结点的右子树中，因此需要遍历整棵树才能找到后继。而对于其他线索化方式，都可以通过对结点的左、右指针进行判断来快速找到后继或前驱。对于先序线索化二叉树，可以通过判断结点的左指针是否为线索指针来找到先序后继；对于中序线索化二叉树，可以通过判断结点的右指针是否为线索指针来找到中序后继或前驱。故本题选C。

5、试题答案：A

试题解析：

在单链表中，插入一个新结点需要进行以下操作：
（1）将新结点的next指针指向*p的next指针所指向的结点。
（2）将*p的next指针指向新结点。
由于只需要操作两个结点的指针，所以插入操作的时间复杂度为O(1)。故本题选A。

6、试题答案：A

试题解析：

在顺序表中，可以通过下标直接定位到第i个元素及其前驱，时间复杂度为O(1)。而在链式存储结构中，需要遍历链表找到第i个元素及其前驱，时间复杂度为O(n)。因此，顺序表存储方式最省时间。故本题选A。

7、试题答案：D

试题解析：

循环链表中即使没有数据结点，头指针也不为空，因此选项C不正确。判断空表的条件应该是判断头结点的next指针是否指向头结点本身，因此选项D正确，即head->next==head。故本题选D。

8、试题答案：D

试题解析：

根据题意，首先入栈的是p1，然后p2，再然后p3=1，此时p3出栈，栈顶元素为p2，因此p1必须在p2出栈以后再出栈。由于输出序列中2紧跟在1之后出栈，因此p1的值不可能是2。故本题选D。

9、试题答案：D

试题解析：

循环队列中队首元素的实际位置可以用(rear-qulen+1+m)%m计算得到。因为循环队列是循环的，队首元素的位置有可能比队尾元素的位置更靠后，所以需要加上m并取模。故本题选D。