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