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

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

1、计算机算法指的是解决问题的有限运算序列，它必须具备输入、输出和（ ）等5个特性。

A、可执行性、可移植性和可扩充性

B、可行性、确定性和有穷性

C、确定性、有穷性和稳定性

D、易读性、稳定性和安全性

2、某算法代码段如下，其时间复杂度是（ ）。for(i=1;i<=n;++i) for(j=1;j<=n;++j) { c[i][j]=0; for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j]; }

A、O(n²)

B、O(n³)

C、O(n)

D、O(nlog₂n)

3、和顺序（连续）存储结构相比，线性表的链式存储结构的优点是（ ）。

A、所有操作/运算的算法都简单

B、便于随机存取

C、便于插入和删除

D、便于查找

4、在某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A、单链表

B、仅有头指针的单循环链表

C、双向链表

D、仅有尾指针的单循环链表

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

A、插入

B、删除

C、排序

D、查找

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

A、队列

B、栈

C、链表

D、都不是

7、栈和队列的共同点有（ ）。

A、都是先进先出

B、都是后进先出

C、不会删除中间的元素

D、完全没有共同点

8、设循环队列中数组的下标范围是0…n-1，其头指针front指向队首元素，rear指向队尾元素，则队列的长度为（ ）。

A、rear-front

B、rear-front+1

C、(rear-front+1)%(n+1)

D、(rear-front+n+1)%n

9、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行优先存放时，元素A[8][5]的起始地址为（ ）。

A、SA+141

B、SA+222

C、SA+144

D、SA+225

1、试题答案：B

试题解析：

算法的5个特性分别为：
（1）有穷性：对于任意一组合法的输入值，在执行有穷步骤后一定能结束，即算法中的操作步骤有限且每个步骤都能在有限的时间内完成。
（2）确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或者阅读者都能明确其含义以及如何执行。并且在任何条件下，算法都只有一条执行路径。
（3）可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现。该特性也有书称之为有效性：算法中的每一个步骤都应当能有效的执行，并得到确定的结果。
（4）输入：作为算法加工对象的量值，通常体现为算法的一组变量。有些输入量需要在算法执行的过程中输入，而有的算法表面上可以没有输入，实际上输入已经嵌入算法之中。
（5）输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果。这种确定关系即为算法的功能。
故本题选B。

2、试题答案：B

试题解析：

上述代码是由三层for循环构成的，每层循环的时间复杂度为O(n)，因此三层循环嵌套的时间复杂度为O(n³)，故本题选B。

3、试题答案：C

试题解析：

对于A，针对已知下标的查找而言，顺序存储的时间复杂度为O(1)，而链式存储需要从头开始遍历查找，其时间复杂度为O(n)，D同理，因此A和D错误；对于B，顺序存储是一种随机存储结构而链式存储不是，因此B错误；对于C，顺序表的插入和删除均需要移动元素，时间复杂度为O(n)，而链表插入和删除不需要移动元素，仅需要移动指针，其时间复杂度为O(1)，故本题选C。

4、试题答案：D

试题解析：

对于单链表而言，在结尾插入元素的时间复杂度为O(n)，删除首元素的时间复杂度为O(1)；对于仅有头指针的单循环链表，在结尾处插入元素的时间复杂度为O(n)，删除首元素的时间复杂度为O(1)；对于双向链表而言，在结尾插入元素的时间复杂度为O(n)，删除首元素的时间复杂度为O(1)；对于仅有尾指针的单循环链表，在结尾插入元素的时间复杂度为O(1)，删除首元素的时间复杂度为O(1)。故本题选D。

5、试题答案：D

试题解析：

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

6、试题答案：A

试题解析：

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

7、试题答案：C

试题解析：

栈和队列是受限的线性表，栈具有“后进先出”的特性，而队列具有“先进先出”的特性，因此A和B错误。栈只能从一端插入元素，并从该端删除元素，队列只能从一端插入元素从另一端删除元素，因此这二者均不会删除中间元素。故本题选C。

8、试题答案：D

试题解析：

在本题中，front指向队首元素，rear指向队尾元素，因此元素个数应当为rear-front+1，因此A错误；加n是为了保证当rear<front时，计算出的结果是非负数，因此B错误；数组的最大容量为n，因此C错误。故本题选D。

9、试题答案：B

试题解析：

画出该数组如下（用绿色表示待存储的元素，用红色表示A[8][5]的位置）：

A[8][5]之前需要存放元素的个数=7*10+4=74。由于每个元素长度为3个字节，存储这些元素占据的总的存储空间为74*3=222。再加上首地址，则A[8][5]的地址为SA+222，故本题选B。