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

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

1、下面程序段的时间复杂度是（ ）。m=10;n=10;s=0;for(i=0;i<m;i++) for(j=0;j<n;j++) s+=i*j;

A、O(m)

B、O(n)

C、O(m*n)

D、O(1)

2、在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。

A、插入

B、删除

C、排序

D、查找

3、线性表采用链表存储时地址（ ）。

A、必须是连续的

B、部分地址必须是连续的

C、一定是不连续的

D、连续不连续都可以

4、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依相同次序从该缓冲区中取出数据打印。该缓冲区作为数据结构是一个（ ）结构。

A、栈

B、队列

C、哈希表（HashTable）

D、线性表

5、一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列（ ）？

A、2，3，4，1

B、4，3，1，2

C、1，3，2，4

D、3，4，2，1

6、设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。

A、栈

B、队列

C、顺序结构线性表

D、链式结构线性表

7、在长度为n顺序实现的线性表的第i（1≤i≤n）个位置之前插入一个元素，需要后移（ ）个元素。

A、0

B、i

C、1

D、n-i+1

8、链表不具有的特点是（ ）。

A、可随机访问任一元素

B、插入、删除不需要移动元素

C、不必事先估计存储空间

D、所需空间与线性表长度成正比

9、将一个A[20][20]（下标从1开始计算）的矩阵按行优先顺序存放，每个元素占4个存储单元，并且A[1][2]的存储地址是1004，则A[20][2]的地址是（ ）。

A、1004

B、1380

C、1520

D、2524

10、树根的层数为1，则一棵含12个结点的二叉树的高度至多为（ ）。

A、3

B、4

C、11

D、12

1、试题答案：D

试题解析：

时间复杂度反映的是算法的执行时间随数据规模增长的变化趋势，题干所示的代码执行了100次，是一个常量的执行时间，与输入的规模无关，因此其时间复杂度为O(1)，故本题选D。

2、试题答案：D

试题解析：

插入和删除操作均会改变线性表中的元素个数，从而改变数据元素之间的结构关系；排序操作会导致数据元素的相对位置改变从而改变数据元素之间的结构关系；查找操作仅读取元素，不会改变元素个数和相对位置，因此查找不会改变数据元素之间结构关系，故本题选D。

3、试题答案：D

试题解析：

线性表的链式存储结构其地址可以连续可以不连续，而线性表的顺序存储结构其地址必须是连续的，故本题选D。

4、试题答案：B

试题解析：

对于A，栈具有“后进先出”的特性，而在实际情况中打印机是按输入顺序打印的，因此A错误；对于B，根据题干可知缓冲区将输入的数据依次输出，这种数据处理的方法符合队列的“先进先出”的特性，因此缓冲区是一个队列结构；对于C，题干的描述与哈希表无关，因此C错误。对于D，线性表没有队列描述准确，因此D错误。故本题选B。

5、试题答案：B

试题解析：

对于A，经过这样的操作可以得到序列A：push(1)，push(2)，pop(2)，push(3)，pop(3)，push(4)，pop(4)，pop(1)；对于B，若第一个出栈的元素是4，则出栈序列只有一种可能性，即4，3，2，1，因此B错误；对于C，经过这样的操作可以得到序列C：push(1)，push(2)，push(3)，pop(3)，pop(2)，push(4)，pop(4)；对于D，经过这样的操作可以得到序列D：push(1)，push(2)，push(3)，pop(3)，push(4)，pop(4)，pop(2)，pop(1)。故本题选B。

6、试题答案：A

试题解析：

栈具有“后进先出”的特点，进行括号匹配检验时，遍历表达式，遇到左括号则进栈，遇到右括号则将栈顶元素出栈，并检验是否与右括号匹配，若匹配则继续遍历；否则判定表达式括号不匹配。遍历结束后检验栈是否为空，若为空，则判定表达式括号匹配，否则括号不匹配。故本题选A。

7、试题答案：D

试题解析：

顺序表第i个位置之前插入一个元素，则第i至第n的元素均需要向后移动一位，因此需要后移的元素总数为n-i+1，故本题选D。

8、试题答案：A

试题解析：

对于A，链表不是随机访问结构，顺序表才是；对于B，链表在插入和删除元素时无需移动元素，仅需要改变指针的指向；对于C，链表是动态存储，存储空间无需连续，因此不必事先估计存储空间；对于D，链表的每个结点分配的存储空间是固定的，因此所需的总的空间与线性表的长度成正比。故本题选A。

9、试题答案：D

试题解析：

在二维数组中元素A[i][j]的地址=SA+[(i-1)*20+(j-1)]*4。代入A[1][2]，求出其地址=SA+4=1004，求得SA=1000。A[20][2]= SA+[(20-1)*20+(j-1)]*4=1000+1524=2524。故本题选D。

10、试题答案：D

试题解析：

当树的每层只有1个结点时高度最高，含12个结点的二叉树最大高度为12，故本题选D。