《数据结构与算法》课后习题答案

（5）强连通分量。 【解答】

（1）每个顶点的入度和出度：顶点1（2，1）、顶点2（2，2）、顶点3（1，3）、

顶点4（3，0）、顶点5（2，3）、顶点6（1，2）。

（2）邻接矩阵：

0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 （3）邻接表：

3 ^ 0 1 1 2 2 ^ 0 2 3 3 4 5 ^ 3 4 ^ 4 5 0 1 3 ^ 5 6 4 ^ 1 （4）逆邻接表： 0 1 1 2 1 4 4 ^ 5 ^ 2 3 1 ^ 3 4 0 2 4 ^ 4 5 2 5 ^ 5 6 2 ^ （5）强连通分量： 5

1 4 6

2

2．设无向图G如图2所示，试给出： （1）该图的邻接矩阵； （2）该图的邻接表； （3）该图的多重邻接表；

（4）从V1出发的“深度优先”遍历序列； （5）从V1出发的“广度优先”遍历序列。 【解答】

3 v2 v1 v3 （图2）

v5 v4 v6 v7 （1）该图的邻接矩阵：

0 1 1 0 0 0 0

1 0 1 0 0 0 0

1 0 0 1 0 0 0

0 1 1 0 1 1 0

0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0

（2）该图的邻接表： 1 1 v2 0 2 v3 0 3 3 v4 4 v5 3 5 v6 3 4 6 v7 （3）该图的多重邻接表： 1 v1 0 v2 v3 v4 1 ^ 3 v5 v6 v7 0 v1 2 ^ 2 ^ 2 ^ 2 6 ^ 6 ^ 5 ^ 4 5 ^ 0 ^ 2 3 2 ^ 3 4 3 ^ 5 6 4 ^ 6 ^ 5 ^ （4）从v1出发的“深度优先”遍历序列：v1v2v4v3v5v7v6 （5）从v1出发的“广度优先”遍历序列：v1v2v3v4v5v6v7

3．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？ 【解答】

设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方。矩阵元素的个数与图的边数无关。

4．设有向图G如图3所示，试画出图G的十字链表结构，并写出图G的两个拓扑序列。

v2 v1 v3 图3

v5 v4v6

【解答】

（1）G的十字链表结构： 0 v1 ^ 0 1 0 2 ^ ^ 1 v2 1 4 1 5 ^ ^ 2 v3 2 5 ^ 3 v4 ^ 4 v5 4 3 ^ 5 v6 5 3 ^ 5 4 ^ ^ （2）G的两个拓扑序列：v1v2v3v6v5v4; v1v3 v2v6v5v4 5．如图4所示AOE网：

（1）列出各事件的最早、最迟发生时间； （2）列出各活动的最早、最迟发生时间；

（3）找出该AOE网中的关键路径，并回答完成该工程需要的最短时间。 B E a5=9 a9=5 a1=3 a3=6 a6=10 A D F H a10=3

a4=7 a8=6 a2=5 a7=8 a11=2 C G

图4

（1）ve(A)=0 ve(B)= ve(A)+3=3 ve(C)= ve(A)+5=5

ve(D)=max(ve(B)+6, ve(C)+7)=12 ve(E)= ve(D)+9=21 ve(G)=ve(D)+8=20 ve(F)= max(ve(D)+10, ve(G)+6)=26 ve(H)= max(ve(E)+E, ve(G)+2, ve(F)+3)=29 vl(H)=29 vl(E)= vl(H) – 5=24 vl(F)= vl(H) – 3=26 vl(G)= min(vl(H) – 2, vl(F) – 6)=20 vl(D)= min(vl(E) – 9, vl(F) – 10, vl(G) – 8)=12 vl(B)= vl(D) – 6=6 vl(C)= vl(D) – 7=5 vl(A)= min(vl(B) – 3, vl(C) – 5)= 0

（2）

e(a1)=0 e(a2)=0 e(a3)=3 e(a4)=5 e(a7)=12 e(a8)=20 e(a9)=21 e(a10)=26 l(a1)=3 l(a2)=0 l(a3)=6 l(a4)=5 (a7)=12 l(a8)=20 l(a9)=24 l(a10)=26

（3）关键路径如下图，完成该工程需要的最短时间：29

A D F H a10=3 a4=7 a8=6 a2=5 a7=8

C G

e(a5)=12 e(a11)=20 l(a5)=15 l(a11)=27

e(a6)=12 l(a6)=16

7.3 课后习题解答 (P152)

7.3.1 选择题

1．静态查找表与动态查找表的根本区别在于（B）

A．它们的逻辑结构不一样 B．施加在其上的操作不一样 C．所包含的数据元素类型不一样 D．存储实现不一样 2．在表长为n的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（A）。 A．n B．1 C．n+1 D．n-1 3．顺序查找适用于存储结构为（C）的线性表。 A．哈希存储 B．压缩存储 C．顺序存储或链式存储 D．索引存储

4．用顺序查找法对具有n个结点的线性表查找一个结点的时间复杂度为（C）。

A．O(log２n2) B．O(nlog２n) C．O(n) D．O(log２n) 5．适用于折半查找的表的存储方式及元素排列要求为（D）。 A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序

6．有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（B）。

A．35/12 B．37/12 C．39/12 D．43/12

7．在有序表{1，3，9，12，32，41，62，75，77，82，95，100}上进行折半查找关键字为82的数据元素需要比较（C）次。

A．1 B．2 C．4 D．5 8．设哈希表长为14，哈希函数为H(key)=key。当前表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7。如用二次探测再散列处理冲突，则关键字为49的结点的地址是（D）。

A．8 B．3 C．5 D．9

9．散列函数有一个共同的性质，即函数值应当以（D）取其值域的每个值。 A．最大概率 B．最小概率 C．平均概率 D．同等概率

10．假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( D )

A．k-1次 B．k次 C．k+1次 D．k（k+1）/2次 11．在哈希函数H(k)=k％m中，一般来讲，m应取（C） 。 A．奇数 B．偶数 C．素数 D．充分大的数

12．在采用线性探测法处理冲突所构成的哈希表上进行查找，可能要探测多个位置，在