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