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

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

1、算法的时间复杂度与（ ）有关。

A、问题规模

B、计算机硬件性能

C、编译程序质量

D、程序设计语言

2、若串s=" software"，其子串的个数是（ ）。

A、8

B、37

C、36

D、9

3、设二维数组a[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址是（ ）。

A、1000

B、860

C、1140

D、1200

4、在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是（ ）。

A、p->next=s;s->prior=p;p->next->prior=s; s->next=p->next;

B、s->prior=p; s->next=p- >next;p->next=s;p->next- >prior=s;

C、p->next=s;p->next- >prior=s;s->prior=p;s->next=p->next;

D、s->prior=p;s->next=p ->next;p->next- >prior=s; p->next=s;

5、若元素a，b，c，d，e，f 依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是（ ）。

A、dcebfa

B、cbdaef

C、bcaefd

D、afedcb

6、广义表A=((x,(a,B)),(x,(a,B),y))，则运算Head(Head(Tail(A)))的结果为（ ）。

A、x

B、（a，B）

C、（x，（a，B））

D、A

7、一棵二叉树中有35个节点，其中所有节点的度之和是（ ）。

A、35

B、16

C、33

D、34

8、根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（ ）。

A、是完全二叉树

B、不是完全二叉树

C、是满二叉树

D、不是满二叉树

9、一棵深度为k的平衡二叉树，其每个非叶子节点的平衡因子均为0，则该树共有（ ）个节点。

A、2^k-1-1

B、2^k-1

C、2^k-1+1

D、2^k-1

1、试题答案：A

试题解析：

【考点】本题考查算法时间复杂度的含义。 

【解析】算法效率的度量方法主要有两种，一种是事后统计法，一种是事前分析估算法。而时间复杂度就是事前估算法，时间复杂度能够估算出当输入的规模不断增大时算法的增长规律。事后统计法是指计算机计时器对不同的算法编写的程序运行时间的计算。因此B.C.D与事后统计法相关，故本题选A。

2、试题答案：B

试题解析：

【考点】本题考查子串的应用。 

【解析】

串s的长度为8，其长度为8的子串有一个：" software"；长度为7的子串有两个：" softwar"、" oftware"；长度为6的子串有三个：" softwa"、" oftwar"、" ftware"；…；长度为1的子串有8个，空串也是其子串，因此子串的个数=1+2+3+4+…+8+1=37，故本题选B。

3、试题答案：A

试题解析：

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

【解析】A[3][5]之间存在的元素个数=3*10+5=35。每个元素占4个存储单元，因此一共占有的存储单元=35*4=140。A[0][0]起始地址=860，因此A[3][5]的地址为860+140=1000。故本题选A。

4、试题答案：D

试题解析：

【考点】本题考查双向循环链表的插入操作。

【解析】在双向循环链表的插入操作中，要防止p的后继结点的丢失。若p->next=s在p->next->prior=s之前，则p->next结点会丢失。而A.B.C均存在后继结点丢失的情况。D选项执行的步骤入下图所示：

故本题选D。

5、试题答案：D

试题解析：

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

 【解析】

6、试题答案：A

试题解析：

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

【解析】根据广义表的特性，任何一个非空的广义表均可以分为表头和表尾两个部分，表头可以是一个元素，也可以是一个子表，而表尾必定是一个子表。本题从内到外进行分析，Tail(A)=( (x,(a,B),y))。
Head(Tail(A))= x,(a,B),yHead(Head(Tail(A)))=x，故本题选A。

7、试题答案：D

试题解析：

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

 【解析】树中节点的度=节点的孩子结点的个数=节点的分支=边数。35个节点的二叉树有34条边。故本题选D。

8、试题答案：A

试题解析：

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

 【解析】根据二叉树的先序序列和中序序列可以唯一的确认一棵二叉树，画出这棵二叉树如下：

由上述图结构可知，该二叉树是完全二叉树，不是满二叉树，因此B和C错误。A选项是肯定结论且其表述的范围比D选项表述的范围更加精确，故本题选A。

9、试题答案：D

试题解析：

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

【解析】一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：
① 左子树与右子树的高度之差的绝对值小于等于１；② 左子树和右子树也是平衡二叉排序树。根据该性质，符合题干表述二叉树只能是满二叉树，深度为k的满二叉树的节点=2^k-1，故本题选D。