在各种查找方法中，平均查找承担与结点个数n无关的查找方法是（）。

单项选择题在各种查找方法中，平均查找承担与结点个数n无关的查找方法是（）。

A.顺序查找
B.折半查找
C.哈希查找
D.分块查找

1.单项选择题一个有序表为（1，3，9，12，32，41，45，62，75，77，82，95，100），当二分查找值为82的结点时，查找成功时的比较次数为（）

A.1
B.4
C.2
D.8

2.单项选择题在散列查找中，平均查找长度主要与（）有关。

A.散列表长度
B.散列元素个数
C.装填因子
D.处理冲突方法

3.单项选择题设哈希表长m=14，哈希函数H（key）=keyMOD11。表中已有4个结点：addr（15）=4，addr（38）=5，addr（61）=6，addr（84）=7其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为（）。

A.8
B.3
C.5
D.9

4.单项选择题已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（）次。

A.1
B.2
C.3
D.4

5.问答题 已知图G的邻接矩阵A= ，试画出它所表示的图G，并根据Prim算法求出图的的最小生成树（给出生成过程）。

（1）图形态：

(2)prim算法求最小生成树:

6.问答题 如下所示的有向图，回答下面问题：

（1）该图是强连通的吗？若不是，给出强连通分量。
（2）请给出图的邻接矩阵和邻接表表示。

（2）

7.问答题 已知有向图如下所示，请写出该图所有的拓扑序列。

8.问答题 已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）

9.问答题 AOE网G如下所示，求关键路径。（要求标明每个顶点的最早发生时间和最迟发生时间，并画出关键路径）

（1）最早发生时间和最迟发生时间：

（2）关键路径：

10.问答题 写出下图中全部可能的拓扑排序序列。

1，5，2，3，6，4
1，5，6，2，3，4
5，1，2，3，6，4
5，1，6，2，3，4
5，6，1，2，3，4