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

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

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

A、可随机访问任一元素

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

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

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

2、数据元素的逻辑结构分为（ ）种基本类型。

A、2

B、3

C、4

D、5

3、若线性表最常用的操作是存取第i个元素及其前驱的值，则采取（ ）存储方式最节省时间。

A、单链表

B、双链表

C、顺序表

D、单向循环链表

4、若某堆栈的输入序列为1，2，3，…，n-1，n，输出序列的第1个元素为n，则第i个输出元素为（ ）。

A、n-i+1

B、n-1

C、i

D、哪个元素都有可能

5、若循环队列的最大长度是MAXSIZE。则循环队列中，当使用“少用一个元素空间”来解决队列的“满”与“空”状态时，判满的条件是（ ）。

A、rear==front

B、

C、rear==NULL

D、(rear+1) mod MAXSIZE==front

6、稀疏矩阵一般的压缩存储方法有两种，即（ ）。

A、二维数组和三维数组

B、三元组和散列

C、三元组和十字链表

D、散列和十字链表

7、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。

A、按层遍历

B、先序遍历

C、中序遍历

D、后序遍历

8、含有10个结点的树有（ ）条分支。

A、0

B、10

C、9

D、不确定

9、n个顶点的强连通图至少有（ ）条边。

A、n

B、n+1

C、n-1

D、n(n-1)

10、对n个记录的集合进行冒泡排序使之形成非递减有序序列，在从小到大排列好的情况下比较的次数最少，其比较次数为（ ）。

A、n+1

B、n

C、n-1

D、n(n-1)/2

1、试题答案：A

试题解析：

链表不具有的特点是可随机访问任一个元素。链表是一种线性结构，元素的访问只能从头结点或尾结点开始，沿着指针一个一个遍历，无法像数组一样通过下标随机访问任意一个元素。故本题选A。

2、试题答案：C

试题解析：

根据数据元素之间关系的不同特性，通常有下列4类基本结构：
（1）集合，结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系；
（2）线性结构，结构中的数据元素之间存在一个对一个的关系；
（3）树形结构，结构中的数据元素之间存在一个对多个的关系；
（4）图状结构或网状结构，结构中的数据元素之间存在多个对多个的关系。
故本题选C。

3、试题答案：C

试题解析：

顺序表最适合存取第i个元素及其前驱的值。因为顺序表中的元素在物理上是相邻的，所以访问第i个元素和其前驱的值可以通过简单的指针操作和算术运算来实现。而对于链表来说，要访问第i个元素及其前驱的值需要从链表头开始遍历，时间复杂度较高。双向链表可以存取前驱元素，但也不如顺序表快速。因此，选项C顺序表是最佳选择。故本题选C。

4、试题答案：A

试题解析：

该堆栈采用先进后出的原则，因此，当第1个输出元素为n时，n已经是最先进入栈的元素，即n先于其它所有元素进入堆栈。因此，对于第i个输出元素，它是在n之前进入堆栈的第n-i个元素，因此第i个输出元素为n-i+1。故本题选A。

5、试题答案：D

试题解析：

若循环队列的最大长度是MAXSIZE，且使用“少用一个元素空间”来解决队列的“满”与“空”状态时，判满的条件是(rear+1) mod MAXSIZE == front，即当队尾指针的下一个位置等于队首指针时，队列就满了。故本题选D。

6、试题答案：C

试题解析：

稀疏矩阵是指大部分元素为0的矩阵，因此常用压缩存储方法来节省存储空间。常见的稀疏矩阵压缩存储方法有两种：
（1）三元组：将矩阵中的非零元素按行、列、值三个属性分别存储，可以用一个三元组(i,j,a[i][j])来表示一个非零元素。此方法适用于存储元素数量较少的稀疏矩阵。
（2）十字链表：将矩阵分成行链表和列链表两部分，每个非零元素既是某个行链表中的一个结点，也是某个列链表中的一个结点，两部分链表通过结点共享表示矩阵。此方法适用于存储元素数量较多的稀疏矩阵。故本题选C。

7、试题答案：A

试题解析：

广度优先遍历算法是一种遍历图的算法，用于按照广度优先的顺序遍历图中所有顶点。该算法通过邻接表存储的图，从指定的起始顶点开始，首先访问与其相邻的所有顶点，然后按照它们的访问顺序依次访问它们的相邻顶点，直到遍历完整个图。类比于二叉树，广度优先遍历算法类似于按层遍历。在按层遍历二叉树时，也是从根节点开始，依次访问每一层的节点，直到遍历完整个树。故本题选A。

8、试题答案：C

试题解析：

含有10个结点的树有9条分支。这是由于树中每个结点（除了根结点）都有一条从其父结点引出的分支，因此10个结点的树共有9条分支。故本题选C。

9、试题答案：C

试题解析：

一个强连通图表示其中任意两个顶点都有至少一条有向路径相互连通。当一个有向图中存在一个简单环，并且它包含了图中的所有结点，那么这个图就是一个强连通图，并且只有n条边。故本题选C。

10、试题答案：C

试题解析：

冒泡排序中，最好情况下记录已经按非递减有序排列，只需要进行一趟比较即可完成排序，此时比较次数为n-1。故本题选C。