2010年数据结构考研真题答案及解析

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

1、m阶B-树中的m是指（ ）。

A、每个结点至少具有m棵子树

B、每个结点最多具有m棵子树

C、分支结点中包含的关键字的个数

D、m阶B-树的深度

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

A、任何一个关键活动提前完成，将使整个工程提前完成

B、关键活动不按期完成就会影响整个工程的完成时间

C、所有关键活动都提前完成，则整个工程将提前完成

D、某些关键活动若提前完成，将使整个工程提前完成

3、若某线性表中最常用的操作是取第i个元素和找i个元素的前驱元素，则采用（ ）存储方式最节省运算时间。

A、单链表

B、顺序表

C、双向链表

D、单循环链表

4、中序遍历和后序遍历结果相同的二叉树为（ ）。

A、根结点无左孩子的二叉树

B、根结点无右孩子的二叉树

C、所有结点只有左子树的二叉树

D、所有结点只有右子树的二叉树

5、一棵有124个叶结点的完全二叉树，最多有（ ）个结点。

A、247

B、248

C、249

D、250

6、若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历结果为（ ）。

A、 gcefhabd

B、 gdbecfha

C、 bdgaechf

D、 gdbehfca

7、在求图的最小生成树时，Kruskal算法对（ ）较为合适。

A、完全图

B、稀疏图

C、有向图

D、无向图

8、n个顶点强连通图的邻接矩阵中至少有（ ）个非零元素。

A、n-1

B、n

C、2n-2

D、2n

9、在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度相当于（ ）的长度。

A、顺序查找

B、折半查找

C、斐波那契查找

D、随机查找

10、数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中（ ）的两趟排序后的结果。

A、快速排序

B、冒泡排序

C、选择排序

D、插入排序

1、试题答案：B

试题解析：

【考点】本题考查数据结构--查找--动态查找表--B-树--B-树的性质。
【解析】一棵m阶非空B树满足以下特点：
（1）每个结点至多有m个子树，也就是说每个结点至多有m-1个关键字；
（2）若根结点不是终端结点，那么至少有两棵子树；
（3）除根结点以外的所有非叶子结点至少有⌈m/2⌉棵子树，及至少含有⌈m/2⌉-1个关键字；
（4）所有非叶子结点中的关键字是顺序排列的，且非叶子结点的子树总比关键字多一个。
综上所述，m阶B-树中的m是指每个结点最多具有m棵子树。故本题选B。

2、试题答案：A

试题解析：

【考点】本题考查数据结构--图--有向无环图--关键路径--AOE网。
【解析】AOE网中的关键路径不是唯一的。对于有多条关键路径的网，只缩短其中一条关键路径上的活动并不能缩短工期，只有加快存在于所有关键路径上的关键活动才能缩短工期。因此，不是任何一个关键活动提前完成，就可以使整个工程提前完成的。故本题选A。

3、试题答案：B

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构--线性表的顺序存储结构。
【解析】顺序表可以随机存取，所以在O(1)的时间复杂度内就可以找到第i个元素和第i个元素的前驱元素。而链表只能从头遍历整个表，才能找到第i个元素，这一操作的时间复杂度为O(n)。因此，若某线性表中最常用的操作是取第i个元素和找i个元素的前驱元素，则采用顺序表存储方式最节省运算时间。故本题选B。

4、试题答案：C

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--遍历二叉树。
【解析】中序遍历和后序遍历分别按照“左根右”、“左右根”的方式遍历二叉树。当中序遍历过程为“左根”，后序遍历过程为“左根”，中序遍历和后序遍历结果相同，此时这棵二叉树的所有结点只有左子树的二叉树。故本题选C。

5、试题答案：B

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--完全二叉树--完全二叉树的性质。
【解析】在二叉树中，存在这样的一个数量关系：n0=n2+1。由题干知，n0=124，则n2=123。又因为完全二叉树中度为1的结点只能有一个或者零个，即n1=1或n1=0。因此，当n1=1时，一棵有124个叶结点的完全二叉树中结点个数最多，为124+123+1=248。故本题选B。

6、试题答案：D

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--遍历二叉树--先/前序遍历二叉树--使用非递归的先/前序遍历。
【解析】根据先序遍历序列abdgcefh和中序遍历序列dgbaechf构造的二叉树如下所示，由此易得出后序遍历序列为gdbehfca。故本题选D。

7、试题答案：B

试题解析：

【考点】本题考查数据结构--图--最小代价生成树--构造最小生成树--Kruskal算法。
【解析】Kruskal算法是从最小边出发，不断将最小边纳入所要构建的树中，直至包含n-1条边为止。其时间复杂度为O(ElogE)，与顶点个数无关，只与边有关，所以适用于求稀疏图的最小生成树。故本题选B。

8、试题答案：B

试题解析：

【考点】本题考查数据结构--图--图的基本概念--图的术语--连通性--有向图连通性--强连通图。
【解析】n个顶点强连通图至少有n条边，且有向图中一条边在邻接矩阵只存储了一次，所以其邻接矩阵中至少有n个非零元素。故本题选B。

9、试题答案：B

试题解析：

【考点】本题考查数据结构--查找--动态查找表--二叉排序树--二叉排序树的应用。
【解析】在关键字随机分布的情况下，用二叉排序树的方法进行查找时的判定树基本平衡，而折半查找判定树一定是平衡的。因此，这一情况下利用二叉排序树查找的查找长度相当于折半查找的长度。故本题选B。

10、试题答案：A

试题解析：

【考点】本题考查数据结构--排序--内部排序。
【解析】冒泡排序和选择排序在经历两趟排序后，必定会有两个最大（或最小）的元素位于其最终位置上，而数据序列（2，1，49，8，10，6，20）中最大的两个元素49和20并不在最终位置上。因此，该序列不是冒泡排序或选择排序两趟排序后的结果。插入排序在经历两趟排序后，序列前两元素必定是有序的，显然数据序列的前两个元素是“2、1”，不符合插入排序在经历两趟排序后结果的特点。因此，该序列不是插入排序两趟排序后的结果。故本题选A。