C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2
⑵ 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2
12．采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 13．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
14．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。
A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 宽度优先遍历算法 D. 深度优先遍历算法 15．关键路径是事件结点网络中 。
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长的回路 D.最短的回路 16．下面不正确的说法是 。
（1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小； （2）AOE网工程工期为关键活动上的权之和；
（3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。
A.（1） B.（2） C.（3） D.（1）、（2）
17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是 。
A.逆拓朴有序的 B.拓朴有序的 C.无序的 18．在图7.3所示的拓朴排列的结果序列为 。
A.125634 B.516234 C.123456 D.521634
图7.3有向图 19．一个有n个顶点的无向连通图，它所包含的连通分量个数为 。
A.0 B.1 C.n D.n+1
20．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。
A.k1 B.k2 C.k1-k2 D.k1+k2
21．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。
A.k1 B.k2 C.k1-k2 D.k1+k2
7.2 填空题（将正确的答案填在相应饿空中）
1．n个顶点的连通图至少____条边。 2．在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。 3．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于____。
4．已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。 v5 v4 v2 v1
v2 v5 v3
v3 v6
v4 ^
v5 v4 v6 v3
v6 ^ 图7.4 图G的邻接表
5．已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。 6．已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。
7．如果含n个顶点的图形成一个环，则它有 棵生成树。 8．一个非连通无向图，共有28条边，则该图至少有 个顶点。
9．遍历图的过程实质上是 。BFS遍历图的时间复杂度为 ，DFS遍历图的时间复杂度为 ，两者不同之处在于 ，反映在数据结构上的差别是 。
10．一个图的 表示法是唯一的，而 表示法是不唯一的。 11．有向图中的结点前驱后继关系的特征是 。
12．若无向图G的顶点度数最小值大于等于 时，G至少有一条回路。 13．根据图的存储结构进行某种次序的遍历，得到的顶点序列是 的。 7.3 综合题
1．已知如图7.5所示的有向图，请给出该图的: （1）每个顶点的入/出度； （2）邻接距阵； （3）邻接表； （4）逆邻接表； （5）强连通分量。
1 6 2 3 5 4 图7。5一个有向图 2．请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7构造最小生成树： （1） a
16 15 11 b 15 c 15 d
14 12 13 16
21 f e
图7.6
（2） 12 6 1 13 6 15 2 4 16 5 7 2 20 9 10 12 5 4 3 图7.73．试列出图7.8中全部的拓扑排序序列。
1 2 4 3 5 6 图7.8
4．请用图示说明图7.9从顶点a到其余各顶点之间的最短路径。 b 5 d 6 3 a 2 3 2 f 3 c e 5 图7.9 4
5．已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下： (1)请画出该AOE图。
(2)计算完成整个计划需要的时间。 (3)求出该AOE网的关键路径。 ∝ 6 4 5 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 1 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 1 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 2 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 9 7 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 2 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝
习题答案
7.1 1. C 2.B 3.B 4. C 5. A 6. A 8.D 9. AC 10.DB 11. CB 12. A 13. D 14.D 16.A 17.A 18.B 19.B 20.B 21.A 7.2 1.n-1 2. 1;0 3. 1
4.v1,v2,v3,v6,v5, v4；v1,v2,v5,v4,v3, v6 5.求矩阵第i列非零元素之和 6. 将矩阵第i行全部置为零 7.n 8.9
9.对每个顶点查找其邻接点的过程；O（e）（e为图中的边数）；O（e）；
遍历图的顺序不同；DFS采用栈存储访问过的结点，BFS采用队列存储访问过 的结点。
10．邻接矩阵 邻接表
11．一个结点可能有若干个前驱，也可能有若干个后继 12．2 13．唯一
7.3 1.
1 5
6
2 4 2.
3 7.C 15.A
(1)．
（2） 3．
a 11 b 13 15 c 14 d 12 f e 6 12 5 23644 1 52634 156234 5612343 516234 512634 512364 1 12 7 5 6 5 4 10 9 4． b W=5 2 a 3 c
W=3
5．(1)该AOE图为：
d 3 W=6 3 f W=9 4 e W=7 26157197421543428649(2)完成整个计划需要18天。 (3)关键路径为：（V1，V2，V5，V7，V9）和（V1，V2， V5，V8，V9，）
习题8 查找
8.1 单项选择题
1.顺序查找法适合于存储结构为____的线性表。
A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 D. 索引存储
2.对线性表进行二分查找时，要求线性表必须____。
A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序
3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。
A．O（n） B. O(nlog2n) C. O(n) D. O(log2n) 5.二分查找和二叉排序树的时间性能____。
A. 相同 B. 不相同
6.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，____次比较后查找成功。
A. 1 B. 2 C. 4 D. 8
7.设哈希表长m=14，哈希函数H(key)=key。表中已有4个结点：
addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7 如用二次探测再散列处理冲突，关键字为49的结点的地址是____。 A. 8 B. 3 C. 5 D. 9
8.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。
A. 35/12 B. 37/12 C. 39/12 D. 43/12
9．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为 。
A.从第0个元素往后查找该数据元素 B.从第1个元素往后查找该数据元素 C.从第n个元素往开始前查找该数据元素 D.与查找顺序无关
10．解决散列法中出现的冲突问题常采用的方法是 。
A.数字分析法、除余法、平方取中法 B.数字分析法、除余法、线性探测法 C.数字分析法、线性探测法、多重散列法 D.线性探测法、多重散列法、链地址法
11．采用线性探测法解决冲突问题，所产生的一系列后继散列地址 。
A.必须大于等于原散列地址 B.必须小于等于原散列地址
C.可以大于或小于但不能等于原散列地址 D.地址大小没有具体限制 12．对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于 。
A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D两种表都不适合 13.散列表的平均查找长度 。
A.与处理冲突方法有关而与表的长度无关 B.与处理冲突方法无关而与表的长度有关 C.与处理冲突方法有关而与表的长度有关 D.与处理冲突方法无关而与表的长度无关 8.2 填空题（将正确的答案填在相应的空中）
1.顺序查找法的平均查找长度为____；折半查找法的平均查找长度为____；哈希表查找法采用链接法处理冲突时的平均查找长度为____。
2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____。 3.折半查找的存储结构仅限于____，且是____。
4. 假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为____，则比较二次查找成功的结点数为____，则比较三次查找成功的结点数为____，则比较四次查找成功的结点数为____，则比较五次查找成功的结点数为____，平均查找长度为____。
5. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为____；若采用折半法查找，则时间复杂度为____； 6．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行 次查找可确定成功；查找47时，需进行 次查找成功；查找100时，需进行 次查找才能确定不成功。
7．二叉排序树的查找长度不仅与 有关，也与二叉排序树的 有关。
8．一个无序序列可以通过构造一棵 树而变成一个有序树，构造树的过程即为对无序序列进行排序的过程。 9．平衡二叉排序树上任一结点的平衡因子只可能是 、 或 。 10． 法构造的哈希函数肯定不会发生冲突。 11．在散列函数H(key)=key%p中，p应取____。
12．在散列存储中，装填因子?的值越大，则____；?的值越小，则____。
2