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

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

1、下列链表中，（ ）不能从当前结点出发访问到其它任何一个结点。

A、单循环链表

B、带表头的单链表

C、双向链表

D、带表头的单循环链表

2、长度为n的线性表采用顺序存储结构，在其第i（0≤i≤n）个位置插入一个新元素的算法的平均时间复杂度为（ ）

A、O(0)

B、O(1)

C、O(n)

D、O(n²)

3、森林F中有三棵树，第一、二和三棵树的结点个数分别为m1，m2 和m3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。

A、m1

B、m1+m2

C、m3

D、m2+m3

4、下述二叉树中，（ ）满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。

A、堆

B、哈夫曼树

C、AVL树

D、二叉搜索树

5、一棵三叉树中，已知度为3的结点个数等于度为2的结点数，且树中叶结点数目为10，则度为2的结点数目为（ ）。

A、3

B、2

C、4

D、6

6、在线性表中采用对半搜索方法搜索元素，该线性表应为（ ）。

A、有序表且顺序存储

B、有序表且链接存储

C、无序表且顺序存储

D、无序表且链接存储

7、散列文件一般采用（ ）解决冲突。

A、拉链法

B、线性探查法

C、伪随机探查法

D、双散列法

8、在图采用邻接矩阵存储时，深度优先遍历算法的时间复杂度应为（ ）。

A、O(n*e)

B、O(n+e)

C、O(e)

D、O(n²)

9、下面（ ）算法可以判断一个有向图是否有环。

A、求最小代价生成树

B、拓扑排序

C、求最短路径

D、求关键路径

10、分别采用直接插入和快速排序算法对下列四个序列进行排序（由小到大）。使得直接插入排序时间最长的序列是（ ），使得快速排序时间最短的序列是（ ） 。

A、 10，20，30，40，50，60，70

B、 70，60，50，40，30，20，10

C、 40，10，30，20，60，50，70

D、 40，20，10，30，50，70，60

1、试题答案：B

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构--线性表的链式存储结构--链表的综合对比。
【解析】单循环链表和带表头的单循环链表无论从哪一个结点开始，访问到尾结点时均可以通过尾结点的指针域访问头结点，由此访问全部的结点。双向链表从任意结点开始均可以向前或向后遍历，由此可以访问全部的结点。而对带表头的单链表而言，只能从头结点开始才能访问任一个结点，若从中间的某个结点开始访问，则只能访问到该结点后面的结点，无法访问其前面的结点。综上所述，带表头的单链表不能从当前结点出发访问到其它任何一个结点。故本题选B。

2、试题答案：C

试题解析：

【考点】本题考查数据结构--线性表--线性表的存储结构--线性表的顺序存储结构--线性表的顺序存储结构的特点。
【解析】在顺序表中，插入一个新元素的位置共有n+1个。若在第零个位置插入，则需要移动n个元素；若在第一个位置插入，需要移动n-1个元素；…；若在第n-1个位置插入，需要移动1个元素；若在第n个位置插入，需要移动0个元素。因此，在顺序表中插入一个新元素平均需要移动n/2个元素，其数量级为O(n)，所以，在其第i(0≤i≤n)个位置插入一个新元素的算法的平均时间复杂度为O(n)。故本题选C。

3、试题答案：D

试题解析：

【考点】本题考查数据结构--树与二叉树--树与森林--树、森林、二叉树的相互转换--森林转换为二叉树。
【解析】森林转换为二叉树的过程：先将森林中的每棵树转换为二叉树，由于任何一棵和树对应的二叉树的右子树为空，若把森林中第二棵树根视为第一棵树根的右兄弟，即将第二棵树对应的二叉树当做第一棵二叉树根的右子树，将第三棵树对应的二叉树当做第二棵二叉树根的右子树…以此类推，即可将森林转换为二叉树。由此知，第二棵和第三棵树均作为右子树部分，所以森林F对应的二叉树根结点的右子树上的结点个数是m2+m3。故本题选D。

4、试题答案：A

试题解析：

【考点】本题考查数据结构--排序--内部排序--选择排序--堆排序--堆--堆的性质。
【解析】
A：堆中任意一个结点不大于（或不小于）其左右孩子结点，所以满足从任一结点出发到根的路径上所经过的结点序列按其关键字有序这一性质。
B：哈夫曼树中，所以关键字只出现在叶子结点上，其非叶子结点上没有关键字。
C：AVL树本质可以说是一棵平衡的二叉搜索树。
D：二叉树搜索树只有中序遍历的结果是一个有序序列。
综上所述，本题选A。

5、试题答案：A

试题解析：

【考点】本题考查数据结构--树与二叉树--二叉树--二叉树的性质。
【解析】在任意一棵树中，结点个数总和等于总度数加一。因此，在三叉树中存在这样一个等量关系：n0+n1+n2+n3=n1+2n2+3n3+1，化简得n0 =n2+2n3+1。又由题干知，n0=10，n2=n3，则有10=3n2+1，解得n2=3。故本题选A。

6、试题答案：A

试题解析：

【考点】本题考查数据结构--查找--静态查找表--折半查找--折半查找的适用条件。
【解析】对半搜索算法是通过不断缩小搜索范围，将待查找的元素与线性表中间位置的元素进行比较，并根据比较结果将搜索范围缩小一半，以此类推，直到找到要查找的元素或者搜索范围缩小到空集为止。如果线性表无序，那么无法确定缩小搜索范围的方向，从而无法实现对半搜索算法。另外，由于对半搜索算法是通过索引值来定位元素位置的，所以必须使用顺序存储结构才能实现随机访问。如果使用链式存储结构，则需要遍历线性表才能访问某个位置的元素，时间复杂度将会增加。因此，对半搜索算法要求线性表为有序表且顺序存储。故本题选A。

7、试题答案：A

试题解析：

【考点】本题考查数据结构--查找--散列/哈希表--哈希表的构造--处理冲突的方法--开放地址法--二次探测再散列。
【解析】在拉链法中，每个散列地址指向一个链表，如果有多个元素映射到同一地址，则它们被添加到该链表的末尾。这种方法可以避免大量的探测步骤，因此对于处理大量数据的情况来说比较高效，散列文件一般采用该方法解决冲突。故本题选A。

8、试题答案：D

试题解析：

【考点】本题考查数据结构--图--图的遍历--图的深度优先遍历/搜索。
【解析】当采用邻接矩阵表示图时，深度优先遍历过程中每个顶点都要检查与其相邻的所有其他顶点，这需要在O(n)的时间内完成，因为每个顶点最多有n-1个相邻顶点。由于共有n个顶点，因此深度优先遍历的总时间复杂度为O(n²)。此外，对于一个无向图，由于每条边都可以看作是连接两个顶点的单向边，因此总边数为2e。因此，如果采用邻接表表示图，每个顶点最多有2e个相邻顶点，邻接表表示图的深度优先遍历时间复杂度为O(n+e)。综上所述，在图采用邻接矩阵存储时，深度优先遍历算法的时间复杂度应为O(n²)。故本题选D。

9、试题答案：B

试题解析：

【考点】本题考查数据结构--图--有向无环图--拓扑排序--拓扑排序算法--拓扑排序算法的应用。
【解析】求最小代价生成树和求最短路径算法都可以允许图中存在环，无法判断有向图中是否有环。而求关键路径算法第一步是用拓扑排序求出拓扑序列，该算法本身是无法判断有向图是否有环的。拓扑排序算法可以在算法结束后，判断图中是否有顶点未被纳入拓扑序列输出来判断有向图中是否有环。综上所述，拓扑排序算法可以判断一个有向图是否有环。故本题选B。

10、试题答案：B;C

试题解析：

【答案】B、C
【考点】本题考查
1、数据结构--排序--内部排序--插入类排序--直接插入排序--直接插入排序的应用；
2、数据结构--排序--内部排序--快速排序--快速排序的应用。
【解析】
（1）对于直接插入排序而言，若要求实现序列从小到大排序，那么整个序列逆序时排序时间最长。选项B中元素逆序排列，采用直接插入排序时间最长。故第一空选B。
（2）逆序或正序时，快速排序时间最长，所以首先排除选项A和B。而选项D相较于选项C，元素大致上有序排列，所以选项C中序列采用快速排序时间最短。故第二空选C。