习题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