数据结构课后答案 - 北邮 下载本文

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