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

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

1、一个算法的时间耗费数量级称为该算法的（ ）。

A、效率

B、难度

C、可实现性

D、时间复杂度

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

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

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

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

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

3、设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是（ ）。

A、p->next->next==head

B、p->next==head

C、p->next->next==NULL

D、p->next==NULL

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

A、edcba

B、decba

C、dceab

D、abcde

5、若元素的入栈顺序为1，2，3.....，n，如果第2个出栈的元素是n，则输出的第i（1<=i<=n）个元素是（ ）。

A、n-i

B、n-i+1

C、n-i+2

D、无法确定

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

A、688

B、678

C、692

D、696

7、对于广义表A，若head（A）等于tail（A），则表A为（ ）。

A、（ ）

B、（（ ））

C、（（ ），（ ））

D、（（ ），（ ），（ ））

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

A、BADC

B、BCDA

C、CDAB

D、CBDA

1、试题答案：D

试题解析：

【考点】本题考查算法的相关名词概念。

 【解析】对于A，算法的效率是算法的执行时间，而题干中所说的时间耗费的数量级是算法的运行时间的估算，并不是算法的执行时间，因此A错误。对于B，算法的复杂度是衡量算法难度的尺度，而算法的复杂度包括算法的时间复杂度和空间复杂度，因此B错误。算法的可行性是算法的五大特性之一，要求算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现，因此C错误。算法的时间复杂度是算法耗费时间的度量，是事前分析估算法的一种，因此D正确。故本题选D。

2、试题答案：D

试题解析：

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

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

3、试题答案：B

试题解析：

【考点】本题考查单循环链表的判断条件。 

【解析】本题为单循环链表，且带头结点，因此尾指针的next应当指向单链表的第一个结点，即头结点，因此B正确。对于A，p->next->next指向首元结点而非头结点，因此A错误。选项C和选项D与判空条件相关，而与本题题干所求的指向尾结点的的判断条件不相关，因此C和D错误，故本题选B。

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、试题答案：D

试题解析：

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

【解析】栈具有“后进先出”的特性。若第2个出栈元素是n，则第一个出栈的元素可能为1至n-1的任意一个元素，栈的操作可能是push(1)、pop(1)、push(2)、…、push(n)、pop(n)；或者为push(1)、push(2)、pop(2)、…、push(n)、pop(n)；…；可能是push(1)、push(2)、…、push(n-1)、pop(n)、push(n)、pop(n)。因此无法确定输出的第i个元素确切值，故本题选D。

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、试题答案：B

试题解析：

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

【解析】根据广义表的特性，任何一个非空的广义表均可以分为表头和表尾两个部分，表头可以是一个元素，也可以是一个子表，而表尾必定是一个子表。对于A，head（A）=null，tail（A）=（），因此A错误。对于B，head（A）=（），tail（A）=（），因此B正确。对于C，head（A）=（），tail（A）=（（）），因此C错误。对于D，head（A）=（），tail（A）=（（），（）），因此D错误。故本题选B。

8、试题答案：A

试题解析：

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

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

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