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

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

1、在数据的存储结构中，一个存储节点存储一个（ ）。

A、数据项

B、数据元素

C、数据结构

D、数据类型

2、下面关于线性表的叙述错误的是（ ）。

A、线性表采用顺序存储必须占用一片连续的存储空间

B、线性表采用链式存储不必占用一片连续的存储空间

C、线性表采用链式存储便于插入和删除操作的实现

D、线性表采用顺序存储便于插入和删除操作的实现

3、栈和队列都是（ ）。

A、限制存取位置的线性结构

B、顺序存储的线性结构

C、链式存储的线性结构

D、限制存取位置的非线性结构

4、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）。

A、edcba

B、decba

C、dceab

D、abcde

5、已知t=“abcaabbc"， 该模式串的next数组值为（ ）。

A、-1，0，0，0，1，1，2，0

B、0，1，0，0，1，1，2，0

C、-1，0，1，1，1，1，2，0

D、-1，0，0，0，1，1，2，3

6、设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，则A[3][3]存放在什么位置（ ）。

A、688

B、678

C、692

D、696

7、已知广义表L=（（x，y，z），（u，t，w）），从L表中取出原子t的运算是（ ）。

A、head[tail[tail[L]]]

B、tail[head[head[tail[L]]]]

C、head[tail[head[tail[L]]]]

D、head[head[tail[tail[L]]]]

8、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树到的序列为（ ）。

A、BADC

B、BCDA

C、CDAB

D、CBDA

9、已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（ ）。

A、-A+B*C/DE

B、-A+B*CD/E

C、-+*ABC/DE

D、-+A*BC/DE

10、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。

A、9

B、11

C、15

D、不确定

1、试题答案：B

试题解析：

【考点】本题考查存储结构相关术语的概念。 

【解析】数据元素是数据的基本单元；数据项是数据的最小单元；数据结构研究数据的物理关系、逻辑关系，以及它们之间的相互关系；数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据的存储节点存储的是数据元素。故本题选B。

2、试题答案：D

试题解析：

【考点】本题考查顺序存储和链式存储的特点。

 【解析】顺序存储需要分配一片连续的存储空间，而链式存储存储用一组任意的存储单元存储线性表的数据元素，这个存储单元可以是连续的也可以是不连续的，因此A和B正确。链式存储插入和删除元素仅 需修改指针不需要移动元素，时间复杂度为O(1)，而顺序存储插入和删除操作均需要移动元素，其时间复杂度为O(n)，因此C正确D错误。故本题选D。

3、试题答案：A

试题解析：

【考点】本题考查栈和队列的特性。 

【解析】栈和队列均为线性结构，因此D错误。栈只能从一端存储并从该端获取元素，而队列只能从一端存储从另一端获取元素，因此A正确。栈和队列既可以采用顺序存储结构实现也可以采用链式存储结构实现，因此B和C均错误，故本题选A。

4、试题答案：C

试题解析：

【考点】本题考查栈的基本操作。 

【解析】对于A，当栈的操作为push(a)，push(b)，push(c)，push(d)，push(e)，pop(e)，pop(d)，pop(c)，pop(b)，pop(a)，其输出序列即为A所示，因此A正确。对于B，当栈的操作为push(a)，push(b)，push(c)，push(d)，pop(d)，push(e)，pop(e)，pop(c)，pop(b)，pop(a)，其输出序列即为B所示，因此B正确。对于C，a在b之前入栈，则b应该在a之前出栈，因此C错误。对于D，当栈的操作为push(a)，pop(a)，push(b)，pop(b)，push(c)，pop(c)，push(d)，pop(d)，push(e)，pop(e)，其输出序列即为D所示，因此D正确。故本题选C。

5、试题答案：A

试题解析：

【考点】本题考查模式匹配算法的应用。

 【解析】题干所给模式串的next数组值求解过程如下：

① 最开始的0位和1位的A.b的next分别为-1和0。② 第2位的c前一位为b，其next为0，在下标为0的元素获取a，a!=b，因此下标为2的next为0。③ 第3位的a前一位为c，其next为0，在下标为0的元素获取a，a!=c，因此下标为3的next为0。④ 第4位的a前一位为a，其next为0，在下标为0的元素获取a，a=a，因此next为下标为3的next+1=1。⑤ 第5位的b前一位为a，其next为1，在下标为1处获取b，b!=a，继续向前寻找，下标为1的next为0，在下标为0处获取a，a=a，因此该位置的next=在下标为1的next+1=1。⑥ 第6位的b前一位为b，其next数组为1，在下标为1处获取b，b=b，下标为6的next=下标为5的next+1=2。⑦ 第7位的c前一位为b，其next为2，在下标为2处获取c，c!=b，继续向前寻找，下标为2处的next为0，在下标为0处为a，a!=b，寻找失败，因此该位置的next=0。将下标改为1至8同理，此时的next数组应当为0,1,1,1,2,2,3,1。故本题选A。

6、试题答案：C

试题解析：

【考点】本题考查二维数组的存储。 

【解析】假设每个元素存储时占用的字节为k。address(A[2][2])=address(A[0][0])+(n*2+2)*k。带入题干已知量，上述式子可以化为676=644+2*(n+1)*k，解得(n+1)*k=16。address(A[3][3])=address(A[0][0])+(n*3+3)*k= address(A[0][0])+3*(n+1)*k=644+3*16=692，故本题选C。

7、试题答案：C

试题解析：

【考点】本题考查广义表的基本操作。 

【解析】根据广义表的特性，任何一个非空的广义表均可以分为表头和表尾两个部分，表头可以是一个元素，也可以是一个子表，而表尾必定是一个子表。对A选项进行分析，tail[L]=((u，t，w))；tail[tail[L]]=(())；因此A选项错误。对B选项进行分析，tail[L]=((u，t，w))；head[tail[L]]=(u，t，w)；head [head[tail[L]]]=u；因此B选项错误。对C选项进行分析，tail[L]=((u，t，w))；head[tail[L]]=(u，t，w)；tail [head[tail[L]]]=（t，w）；head[tail [head[tail[L]]]]=t；因此C正确。D选项与A选项同理，因此D选项错误，故本题选C。

8、试题答案：A

试题解析：

【考点】本题考查二叉树的遍历。 

【解析】根据二叉树的中序序列和前序序列可以唯一的确定一棵二叉树，画出该二叉树如下所示：

对上述树结构进行后序遍历，得到遍历的结果为BADC，故本题选A。

9、试题答案：D

试题解析：

【考点】本题考查算术表达式的相互转换。

 【解析】根据后缀表达式对中缀表达式加括号以区别运算的先后关系：((A+(B*C))-(D/E))。将运算符放在括号前面，-(+(A*(BC))/(DE))，将括号去掉以后的序列为-+A*BC/DE，故本题选D。

10、试题答案：B

试题解析：

【考点】本题考查二叉树的性质。 

【解析】对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明为：因为二叉树中所有结点的度均小于或等于2，所以其结点总数为n=n0+n1+n2。二叉树中，除根结点以外，其余结点均有一个分支进入，设分支总数为B，则有n=B+1。由于这些分支是由度为1或者度为2的结点射出的，所以有B=1*n1+2*n2。带入B=n-1可得，n0+n1+n2-1=n1+2*n2，即n0=n2+1。故本题选B。