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

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

1、数据的四种存储结构是（ ）。

A、顺序存储结构、链接存储结构、索引存储结构和散列存储结构

B、线性存储结构、非线性存储结构、树型存储结构和图型存储结构

C、集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构

D、顺序存储结构、树型存储结构、图型存储结构和散列存储结构

2、在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（ ）。

A、O(1）

B、O(logn）

C、O(n）

D、O(n²）

3、指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（ ）。

A、p1->next=p2->next; p2 ->next=p1->next;

B、p2->next=p1->next; p1->next=p2->next;

C、p=p2->next; p1->next=p; p2->next=p1->next;

D、p=p1->next; p1->next=p2->next; p2->next=p;

4、设栈的初始状态为空，入栈序列为1，2，3，4，5，6，若出栈序列为2，4，3，6，5，1，则操作过程中栈中元素个数最多时为（ ）。

A、2

B、3

C、4

D、6

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、已知10x12的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A[1][1]的存储地址为420，则A[5][5]的存储地址为（ ）。

A、470

B、471

C、472

D、473

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

1、试题答案：A

试题解析：

【考点】本题考查数据结构的存储结构的分类。 

【解析】数据结构包括数据的逻辑结构和数据的物理结构两个层次，如下图所示：

对于A，数据结构的四种存储结构分别为顺序存储结构、链接存储结构、索引存储结构、散列存储结构，因此A正确。对于B，线性结构和非线性结构是数据结构的逻辑结构而非存储结构，树型结构和图型结构均为非线性存储结构的一种，因此B错误。对于C，集合存储结构是逻辑结构的一种，一对一存储结构即线性结构，一对多存储结构即树型结构，多对多存储结构即图状或网状存储结构，这三类存储结构均为数据的逻辑结构，因此C错误。对于D，顺序存储结构和散列存储结构属于数据的存储结构，树型和图型存储结构是数据的逻辑结构，因此D错误。故本题选A。

2、试题答案：C

试题解析：

【考点】本题考查顺序表插入操作的时间复杂度。 

【解析】在一个有n个元素的顺序表中，顺序表的插入操作是指在第i-1个元素和第i个元素之间插入一个数据元素，使长度为n的线性表长度变为n+1，需要将第n到i的元素向后移动一位，共需移动元素的个数为n-i+1，插入一个元素平均要移动的元素个数为n/2。因此其时间复杂度O(n），故本题选C。

3、试题答案：D

试题解析：

【考点】本题考查循环链表的链接操作。 

【解析】对于A，第1步骤p1->next已经被覆盖，第2步骤p2->next指向的p1->next丢失，因此A错误；对于B，与A同理，因此B错误；对于C，第2步骤的p1->next已经被覆盖，第2步骤p2->next指向的p1->next丢失，因此C错误；D选项正确，其操作步骤示意图如下所示：

故本题选D。

4、试题答案：B

试题解析：

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

【解析】

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

试题解析：

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

【解析】根据题干可知该二维数组以“行优先”存储，且起始地址的位置在A[1][1]。因此，地址A[5]5]之前的元素个数=4*12+2=52。由于每个元素占1个存储单元，因此所占有的存储单元为52。起始地址=420，则A[5][5]的存储地址=420+52=472，故本题选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

试题解析：

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

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