习题6
1． 填空题
（1）n个顶点的无向图，最多能有（___________）条边。 答案： [n*(n-1)]/2
（2）有n个顶点的强连通图G最多有（___________）条弧。 答案：n*(n-1)
（3）有n个顶点的强连通图G至少有（___________）条弧。 答案：n
（4）G为无向图，如果从G的某个顶点出发，进行一次广度优先遍历，即可访问图的每个顶点，则该图一定是（___________）图。 答案：连通
（5）若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为（___________）。 答案：O（n）
（6）n个顶点的连通图的生成树有（___________）条边。 答案：n-1
（7）图的深度优先遍历类似于树的（___________）遍历；图的广度优先遍历类似于树的（___________）遍历。 答案：前序 层序
（8）对于含有n个顶点e条边的连通图，用普里姆算法求最小生成树的时间复杂度为（___________）。 答案：O（n2）
（9）已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（___________）。 答案：O（n+e）
（10）一棵具有n个顶点的生成树有且仅有（___________）条边。 答案：n-1
2． 单选题
（1）在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 A. 1/2
B. 1
C. 2
D. 4
（2）在一个具有n个顶点的有向图中，若所有顶点的出度数之和为S，则所有顶点的度数之和为（ ）。 A. S A. n
B. S－1 B. n(n-1)
C. S+1
D. 2S
（3）具有n个顶点的有向图最多有（ ）条边。
C. n(n+1) D. 2n
2
（4）若一个图中包含有k个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须调用（ ）次深度优先搜索遍历的算法。
A. k B. 1 C. k-1 D. k+1
（5）若一个图的边集为{<1，2>，<1，4>，<2，5>，<3，1>，<3，5>，<4，3>}，则从顶点1开始对该图进行深度优先遍历，得到的顶点序列可能为（ ）。 A. 1，2，5，4，3 C. 1，2，5，3，4
B. 1，2，3，4，5 D. 1，4，3，2，5
（6）若一个图的边集为{（A，B），（A，C），（B，D），（C，F），（D，E），（D，F）}，则从顶点A开始对该图进行广度优先遍历，得到的顶点序列可能是（ ）。 A. A，B，C，D，E，F C. A，B，D，C，E，F
B. A，B，C，F，D，E D. A，C，B，F，D，E
说明：教材中某结点的邻接点选择次序默认都是自小而大，如果按此进行广度优先遍历，则结果应该为ABCDFE，但题目问可能的序列，则邻接点选择次序可以随便确定，此时，D是正确的。
（7）存储无向图的邻接矩阵是（ A ），存储有向图的邻接矩阵是（ B ）。 A. 对称的 B. 非对称的 （8）采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 （9）设有一个无向图G＝（V，E）和G′＝（V′，E′），如果G′为G的生成树，则下面不正确的说法是（ ）。 A. G′为G的子图
B. G′为G的连通分量
C. G′为G的极小连通子图，且V＝V D. G′为G的一个无环子图
3． 画出图6－32所示的无向图的邻接表（顶点由小到大排列），并根据所得邻接表给出深
度优先和广度优先搜索遍历该图所有的顶点序列。
BCDAGEHF
答案：
01234567ABCDEFGH1012341072345621666673574657深度优先：ABCDEFGH 广度优先：ABHCGFDE
4． 使用普里姆算法构造出图6－33中图G的一棵最小生成树。
161253566346 答案：生成最小树的顺序如下
55241①2④⑤5
43②6
③习题7
1. 填空题
（1）由10000个结点构成的二叉排序树，在等概率查找的条件下，查找成功时的平均查找长度的最大值可能达到（___________）。
答案：5000.5
（2）长度为11的有序序列：1，12，13，24，35，36，47，58，59，69，71进行等概率查找，如果采用顺序查找，则平均查找长度为（___________），如果采用二分查找，则平均查找长度为（___________），如果采用哈希查找，哈希表长为15，哈希函数为H（key）＝key，
采用线性探测解决地址冲突，即di=(H(key)+i)，则平均查找长度为（保留1位小数）（___________）。 答案：6，3，1.6
（3）在折半查找中，查找终止的条件为（___________）。 答案：找到匹配元素或者low>high?
（4）某索引顺序表共有元素275个，平均分成5块。若先对索引表采用顺序查找，再对块元素进行顺序查找，则等概率情况下，分块查找成功的平均查找长度是（___________）。 答案：31
（5）高度为8的平衡二叉树的结点数至少是（___________）。 答案： 54 计算公式：F(n)=F(n-1)+F(n-2)+1
（6）对于这个序列{25，43，62，31，48，56}，采用的散列函数为H(k)=k%7，则元素48的同义词是（___________）。
答案：62
（7）在各种查找方法中，平均查找长度与结点个数无关的查找方法是（___________）。 答案：散列查找
（8）一个按元素值排好的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，平均比较次数分别是s和b，在查找成功的情况下，s和b的关系是（___________）；在查找不成功的情况下，s和b的关系是（___________）。
答案：(1)(2s-1)b=2s([log2(2s-1)]+1)-2[log(2s-1)]+1+1
2
(2)分两种情况考虑，见解答。
解： (1)设所有元素的个数为n，显然有s=n*(n+1)/(2n),则
n=2s-1
设折半查找树高度为k，则前k-1层是满二叉树，最后一层的节点数为
n-(2k-1 -1）
因此，总比较次数
nb=20*1+21*2+22*3+…+2k-2*(k-1)+(n-(2k-1 -1))*k, 而
2*1+2*2+2*3+…+2*(k-1)=2*k-2+1
因此
nb=2*k-2+1+(n-(2-1))*k=(n+1)k-2+1
又k=[log2n]+1,n=2s-1,所以有
(2s-1)b=2s([log2(2s-1)]+1)-2[log(2s-1)]+1+1
(2)查找不成功，对于顺序查找有：s=n。对于折半查找，找不到的情况有n+1种,查找
2
012k-2k-1k
k-1kk-1k
到每个叶子节点或度为1的节点后就不再查找，设折半查找树高度为k，则第k-1层的节点数x=2k-2，第k层的节点数y=n-(2k-1 -1）
（a）当第k层的节点数y小于等于第k-1层的节点数x时， 则第k-1层有y结点度为1，其余x-y个结点度为0。
则查找次数为：(n+1)b=2yk+2(x-y)(k-1)+y(k-1)=2x(k-1)+yk (n+1)b=2 *(k-1)+(n-(2 -1))*k
（b）当第k层的节点数y大于第k-1层的节点数x时，
则第k-1层不存在度为0的结点，有2x-y个结点度为1，其余y-x个结点度为2
则查找次数为：(n+1)b=2yk+(2x-y)(k-1)=2x(k-1)+y(k+1)
(n+1)b=2k-1 *(k-1)+(n-(2k-1 -1))*(k+1)
k-1
k-1