2009年数据结构考研真题答案及解析_考研_希赛网(02331数据结构 2019年)

本文提供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

点击查看答案与解析