⑵错误。二分查找只能在可以进行随机查找的存储结构上进行，即只能顺序存储的有序表上进行。 ⑶正确。 ⑷错误。二叉排序树主要用于改进一般二叉树的查找效率。
⑸正确。 ⑹错误。对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字；右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字进行比较。 ⑺错误。 ⑻正确。 ⑼正确。 ⑽错误。每个结点的平衡因子值的绝对值小于2。 ⑾正确。 ⑿正确。每个元素的存储位置通过哈希函数和解决冲突的方法得到。 ⒀错误。哈希冲突是指多个不同一个关键字对应相同的哈希地址。 ⒁错误。只与装填因子有关。 ⒂错误。不一定。 2. 判断以下叙述的正确性。
⑴。用顺序表和单链表表示的有序表均可使用二分查找方法来提高查找速度。
⑵有n个数存放在一堆数组A[1?n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。
⑶若哈希表的装填因子α<1，则可避免冲突的产生。
⑷二叉排序树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。 ⑸在二叉排序树上删除一个节点时，不必移动其他结点，只要将该结点的父亲结点的相应指针域置空即可。 ⑹哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法。 ⑺对二叉排序树的查找都是从根节点开始的，则查找失败一定落在叶子上。 答：⑴错误。链表表示的有序表不能用二分查找法查找。
⑵错误。因顺序查找既适合于有续表也适合于无序表。对这两种表，若对每个元素的查找概率相等，则顺
n?1序查找的ASL相同，并且都是2；对于查找概率不同的情况，则按查找概率由大到小排列的无序表其ASL要比有序表的ASL小。
⑶错误。α越小则只能说明发生冲突的概率越小，但仍有可能发生冲突。 ⑷正确。 ⑸错误。如果删除的是非树叶结点，则必须调整某些结点，使调整后的二叉树仍为二叉排序树。 ⑹正确。 ⑺错误。若非叶子结点无左子树或无右子树时，也都可以是查找失败的外部节点。 10.4.4 简答题
1.试述顺序查找法、二分查找法和分块查找法对被查找的表中元素要求。对长度为n的表来说，三种查找法在查找成功时的平均查找长度各是多少？
2.试问含有8个关键字的3阶B-树最多有几个结点？最少有几个结点？画出其形态。 3.已知一棵3阶B-树如图10.7所示，画出在其中插入关键字18的过程。
图10.7 一棵3阶B-树
4.证明二叉排序树的中序遍历序列是从小到大有序的。
5.某人认为他发现了二叉树的一个重要性质。假设二叉树中对某关键字K的查找在一叶结点处结束，考虑三个集合：集合A包含查找路径左边的关键字；集合B包含查找路径上的关键字；集合C包含查找路径右边的关键字。他由此认为：任何三个关键字a，b，c，a∈A，b∈B，c∈C，都满足a≤b≤c。你认为正确，请说明理由；认为不正确，则给出一个反例并加以说明。
13
9.4 补充练习题及参考答案
9.4.1 单项选择题
1. 所谓简单路径是指 。B
A.任何一条边在这条路径上不重复出现 B.任何一个定点在这条路径上不重复出现 C.这条路径由一个顶点序列构成，不包含边 D.这条路径由一个变得序列构成，不包含顶点 2. 带权有向图G用邻接矩阵A存储，则vi的入度等于A中 。 D A.第i行非∞的元素之和 B.第i列非∞的元素之和 C.第i行非∞且非0的元素个数 D.第i列非∞且非0的元素个数 3.无向图的邻接矩阵是一个 。 A
A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵 4.在一个无向图中，所有顶点的度之和等于边数的 倍。 C A.1/2 B.1 C.2 D.4 5.一个有n个顶点的无向图最多有 条边。 C
A. n B. n(n-1) C. n(n-1)/2 D. 2n A. 5 B. 6 C. 7 D.8 A. n B. n+1 C. n-1 D.n/2
6.具有6个顶点的无向图至少应有 几条边才能确保是一个连通图。 A 7.在一个具有n个顶点的无向图中，要联通全部顶点至少需要 条边。 C 8.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是 。 D
A. n B. (n?1) C. n-1 D. n
229.一个有向图G的邻接表存储如图9.2所示，现按深度优先搜索遍历，从v1出发，所得到的顶点序列是 。 B
V3 V4 V1 V2 A. 1，2，3，4，5 B. 1，2，3，5，4 C. 1，2，4，5，3 D. 1，2，5，3，4
2 3 5 3 5 4 Λ Λ Λ Λ 4 Λ V5 图 9.2 有向图G的邻接表 10.对图9.3所示的无向图，从顶点v1开始进行深度优先遍历，可得到顶点的访问序列 。
A. 1，2，4，3，5，7，6 B. 1，2，4，3，5，6，7 C. 1，2，4，5，6，3，7 D. 1，2，3，4，5，7，6
答：选项B中从顶点5到顶点6不符合深度优先遍历规则；选项C中从顶点5到顶点6不符合深度优先遍历规则；选项D中从顶点2到顶点3不符合深度优先遍历规则。答案为A。
14
2 5 1 4 7
3 图9.3
6
11.对图9.3所示的无向图，从V1开时进行广度优先遍历，可得到顶点访问序列 。
A. 1，3，2，4，5，6，7 B. 1，2，4，3，5，6，7 C. 1，2，3，4，5，6，7 D. 2，5，1，4，7，3，6
答：选项B中124子序列不符合广度优先遍历规则；选项C中457子序列不符合广度优先遍历规则；
选项D中从2开始不符合广度优先遍历规则。答案为A
12.在图9.4所示的有向图中，存在一个强连通分量G=（V，E），其中， A 。
A. V={v2，v3，v5，v6}
E={
E={
E={
E={
13.如果从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点图一定是（Ｂ） Ａ完全图 Ｂ连通图 Ｃ有回路 Ｄ一棵树
14．采用邻接表存储的图的深度优先遍历算法类似于二叉树的 _____ 算法 （A） A前序遍历 B中序遍历 C后序遍历 D按层遍历
15采用邻接表存储的图的广度优先遍历算法类似于二叉树的 _____ 算法 （D） A前序遍历 B中序遍历 C后序遍历 D按层遍历 16任何一个无相连通图_________ 最小生成树 （B）
A只有一棵 B有一棵或多棵 C一定有多棵 D可能不存在 17一个无向连通图的生成树是含有该连通图的全部顶点的_______（A）
A极小连通子图 B极小子图 C极大联通子图 D极大子图 18判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用_____ （A）
A求关键路径的方法 B求最短路径的迪克斯特方法 C广度优先遍历算法 D深度优先遍历算法 19若一个有向图中的顶点不能排成一个拓扑序列，则可判定该有向图______ D
A是个有根有向图 B是个强连通图 C含有多个入度0的顶点 D含有定点数目 大于1的强联通分量
20 对于含有n个顶点的带权连通图，他的最小生成树是指途中任意一个_____ D A由n-1条权值最小的便构成的子图 B由n-1条权值之和最小的边构成的联通子图 C由n-1条权值之和最小的边构成的联通子图 D由n个顶点构成的边的权值之和最小的联通子图
21若图的连接矩阵中主对角线上的元素全是0，其余元素全是1，则可以断定该图一定是_______ D A无向图 B不是带权图 C有向图 D完全图 22关键路径是事件是事件结点网络中______ A
A从源点到汇点的最长路径 B从源点到汇点的最短路径 C最长的回路 D最短的回路 23设有无向图G=（V，E）和G’=(V’,E’),如G’是G的生成树，则下面不正确的说法是_____ A A G’是G的连通分量 B G’是G的无环子图 C G’是G的子图 D G’为G的极个连通子图且V’=V
15
24求最短路径的迪克斯特拉算法的时间复杂度为 C A.O(n) B.O(n=e) C.O(n2) D.O(ne) 9.4.2填空题
1．有n个结点的无向图最多有_____条边 n（n-1）/2 2．有n个顶点的强连通有向图G至少有___条 n-1
3．在有n个顶点的有向图中，每个顶点的度最大可达______ 2(n-1)
4、若无向图G的顶点度数最小值大于等于 时，G至少有一条回路。 答：2 5、一个图的 表示法是唯一的，而 表示法是不唯一的。
答：图的表示法主要有链接矩阵和邻接表，前者唯一，后者不唯一。本题答案为：①链接矩阵 ②邻接表 6、用链接矩阵A[1?n,1?n]存储有向图G，其第i行的所有元素之和等于顶点的 。 答：出度 7、有n个顶点的有向图G最多有 条弧。 答：n（n-1）
8、对于一个具有n个顶点和e条边的无向图。若才用邻接表表示，则表头向量的大小为＿ 所有连接表中的节点总数为 答：①n ②2e
9、已知一个有向图的邻接矩阵表示，删除所有从第i个节点出发的弧的表示方法是 答：将邻接矩阵第i行全部置零
10、对于n个顶点的无向图，采用邻接矩阵表示，求图中边数的方法是 ，判断任意两个顶点i和j是否有边相邻的方法是 ，求任意一个顶点的度的方法是 。
答：①邻接矩阵中1的个数出于2 ②A[i][j]是否为1 ③吉萨该行中1的个数
11、对于n各顶点的有向图。采用邻接表表示，求图中边数的方法是 ，判断任意两个顶点i和j是否有边相邻的方法是 ，求任意一个顶点的度的方法是 。
答：①邻接矩阵中1的个数 ②A[i][j]是否为1 ③出度为该行中1的个数，入读为该行列中1的个数 12、对于n各顶点的无向图。采用邻接表表示，求图中边数的方法是 ，判断任意两个顶点i和j是否有边相邻的方法是 ，求任意一个顶点的度的方法是＿＿＿。
答：①邻接表中结点个数（除表头结点外）出于二 ②从i表头结点开头的链表中是否包含 结点 ③以i表头结点开头的链表中的结点个数 13、无向图的连通分量是指 。答：最大连通子图
14、若无向图中有m条边；则表示该无向图的邻接表中就有 结点。 答：2m 15、对n个顶点的图来说，他的生成树一定有 条边。 答：n-1 16、连通分量是无向图中的 的连通子图。 答：极大 17、一个连通图的 是一个极小连通子图。 答：生成树
18、普里姆算法算法适用于求 的网的最小生成树，克鲁斯卡尔算法适用于求 的网的最小生成树。 答：①边稠密 ②边稀疏
19、可以进行拓扑排序的有向图一定是 。 答：无环图
20、从原点到汇点长度最长的路径称关键路径，该路径上的活动成为 。 答：关键活动 9.4.3 判断题
1、 判断以下叙述的正确性。
（1） n个顶点的无向图至多有n(n-1)条边
（2） 在有向图中，各顶点的入度和等于各顶点的出度之和。 （3） 邻接矩阵只存储了边的信息，没有存储顶点的信息。
（4） 对同一个有向图来说，只保存出边的邻接表中结点的数目总是和只保存入边的邻接表中结点的数目一样多。
（5） 如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。
（6） 如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是完全有向图 （7） 连通图的生成树包含了图中所有顶点。
16