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

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

1、下列四个序列中，哪一个是堆（ ）。

A、75，65，30，15，25，45，20，10

B、75，65，45，10，30，25，20，15

C、75，45，65，30，15，25，20，10

D、75，45，65，10，25，30，20，15

2、栈和队列都是（ ）。

A、顺序存储的线性结构

B、链式存储的线性结构

C、限制存取点的线性结构

D、限制存取点的非线性结构

3、如果数据结构中每个元素的前驱和后继的数目都不限，即元素之间存在M对N的联系，且M和N均可能大于1，则该结构为四种基本逻辑结构中的（ ）结构。

A、线性

B、集合

C、树

D、图

4、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时间。

A、单链表

B、单循环链

C、带头节点的双循环链表

D、带尾指针的单循环链表

5、下面的叙述不正确的是（ ）。

A、线性表在链式存储时，查找第i个元素的时间同i的值成正比。

B、线性表在链式存储时，查找第i个元素的时间同i的值有关。

C、线性表在顺序存储时，查找第i个元素的时间同i的值无关。

D、线性表在顺序存储时，查找第i个元素的时间同i的值有关

6、一个递归算法必须包括（ ）。

A、递归部分

B、终止条件和递归部分

C、循环部分

D、终止条件和循环部分

7、将一个A[1…100，1…100]的三对角矩阵，按行优先存入一堆数组B[1...298]中，元素A [66，65]即该元素下标i=66、j=65，在B数组的k位置为（ ）。

A、198

B、195

C、197

D、297

8、下面二叉树一定是完全二叉树的是（ ）。

A、扩充二叉树

B、满二叉树

C、AVL搜索树

D、二叉搜索树

9、森林中有4棵树，其中第1、2、3、4棵树的结点个数分别4、5、6、7；则与森林对应的二叉树中的根结点的右子树上的结点个数为（ ）。

A、9

B、11

C、18

D、22

10、已知图的边集合E（G）={<2，3>，<1，2>，<4，5>，<4，1>，<5，3>，<0，1>}，则序列（ ）不是该图可能的拓扑序列。

A、041523

B、045123

C、425310

D、450123

1、试题答案：C

试题解析：

【考点】本题考查堆的性质。

【解析】堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：① 堆中某个结点的值总是不大于或不小于其父结点的值；② 堆总是一棵完全二叉树。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。对上述选项构造完全二叉树并检验是否符合堆的性质如下图所示：

由上图可知，本题选C。

2、试题答案：C

试题解析：

【考点】本题考查数据结构--栈和队列--栈和队列的综合应用。
【解析】栈和队列满足线性结构的定义：集合中必存在唯一的一个“第一个元素”；集合中必存在唯一的一个“最后的元素”；除最后元素之外，其他数据元素均有唯一的“后继”；除第一元素之外，其他数据元素均有唯一的“前驱”。栈只能在栈顶进行插入删除访问，而队列只能访问或删除队头元素，在队尾插入元素，限制了存取点。故本题选C。

3、试题答案：D

试题解析：

【考点】本题考查数据结构--绪论--数据结构的三要素--数据的逻辑结构--逻辑结构的分类。
【解析】线性结构是一种一对一的结构，树结构是一种一对多的结构，集合中不存在明确的对应关系，图是一种多对多的结构。故本题选D。

4、试题答案：D

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构--线性表的链式存储结构--链表的综合对比。
【解析】虽然选项中四种链表在删除尾结点时都需要遍历链表找到尾结点的前驱结点，但是在末尾插入结点时，带尾指针的单循环链表只需要O(1)的时间复杂度就可以找到尾结点，便于在末尾插入尾结点。相较之下，选用带尾指针的单循环链表最节省时间。故本题选D。

5、试题答案：D

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构。
【解析】在链式存储的线性表中，每个元素在内存中可能连续可能不连续，所以只能从头遍历整个链表以确定第i个元素的位置，查找第i个元素的时间同i的值有关，且i值越大，查找第i个元素的时间越长。在顺序存储的线性表中，每个元素在内存中都是连续存储的，因此可以通过计算元素的存储地址来直接访问第i个元素，查找的时间与i无关。因此，线性表在顺序存储时，查找第i个元素的时间是固定的，与i值无关。综上所述，本题选D。

6、试题答案：B

试题解析：

【考点】本题考查数据结构--算法设计与分析--递归与分治--递归方法。
【解析】一个递归算法必须包括递归出口和递归体，即终止条件和递归部分。故本题选B。

7、试题答案：B

试题解析：

【考点】本题考查数据结构--数组与广义表--矩阵的压缩存储--特殊矩阵的压缩存储--三对角矩阵的压缩存储。
【解析】整个三对角矩阵中，除了第一行和最后一行的元素个数为2以外，其余各行的元素个数均为3。因此，对于A[i，j]而言，前i-1行共有3(i-1)-1个元素。接着，当j-i=-1时，A[i，j]位于第i行第一个元素；当j=i时，A[i，j]位于第i行第二个元素；当j-i=1时，A[i，j]位于第i行第三个元素。那么，A[i，j]是第i行的j-i+2个元素，A[i，j]为三对角矩阵的第3(i-1)-1+ j-i+2=2i+j-2个元素。本题中i=66，j=65，A [66，65]是第2*66+65-2=195，所以在B数组的k位置为195。故本题选B。

8、试题答案：B

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--二叉树的定义--完全二叉树的定义。
【解析】在完全二叉树中，除了最后一层之外的所有层都是完全填满的，最后一层也是从左到右填充的。而满二叉每一层都是满的，满足完全二叉树的定义。因此，满二叉树一定是完全二叉树。而扩充二叉树、AVL搜索树和二叉搜索树都不一定是完全二叉树。故本题选B。

9、试题答案：C

试题解析：

【考点】本题考查数据结构--树与二叉树--树与森林--树、森林、二叉树的相互转换--森林转换为二叉树。
【解析】根据左孩子右兄弟的转换原则，第一棵树作为根结点的树，其余树作为兄弟连接到第一棵树根结点的右边，即为右孩子。因此，该森林对应的二叉树中的根结点的右子树上的结点个数为5+6+7=18。故本题选C。

10、试题答案：C

试题解析：

【考点】本题考查数据结构--图--有向无环图--拓扑排序。
【解析】所有可能的拓扑序列如下，由此知，选项C最中的425310不是该图的可能的拓扑序列。故本题选C。