（8） 对n个顶点的连通图G来说，如果其中的某个子图有n个顶点、n-1条边，则该子图一定是G的生成树。

（9） 最小生成树是指边数最少的生成树。

（10） 从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树。 （11） 强连通图不能进行拓扑排序。

（12） 只要无向网络中没有权值相同的边，其最小生成树就是唯一的。 （13） 只要无向网络中有权值相同的边，其最小生成树就不可能是唯一的。 （14） 关键路径是有权值最大的变够成的。

（15） 如果表示某个邻接图的邻接矩阵是不对称矩阵，则该图一定是有向图。 （16） 求单源最短路径的狄克斯特拉算法不适用于有回路的有向网络。 （17） 求单源最短路径的狄克斯特拉算法不适用于有负权边的有向网络。 （18） 最短路径一定是简单路径。

答：（1）错误。n个顶点的无向图之多有n(n-1)/2条边。（2）正确。（3）正确。（4）正确。（5）错误。如完全有向图的邻接矩阵是对称矩阵。（6）错误。（7）正确。（8）错误（9）错误（10）错误，要求不能构成回路 （11）正确（12）正确（13）错误（14）错误（15）正确（16）错误 （17）正确 （18）正确 2．判断以下叙述的正确性

（1）连通分量是无向图中的极小连通子图。 （2）强连通分量是有向图中的极大强连通子图。

（3）在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条狐。

（4）对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。

（5）无向图中的极大连通子图称为连通分量。

（6）连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。 （7）图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点。 （8）有向图的遍历不可采用广度优先搜索方法。 答：（1）错误。连通分量是无向图中的极大连通子图。

（2）正确 （3）错误。拓扑序列顶点a在顶点b之前并不一定存在弧。

（4）错误。如果有向图构成双向有向环时，则从任意顶点出发均能访问到每个结点，但该图却非完全图。 （5）正确 （6）正确 （7）正确 （8）错误 9.4.4 简答题

1.无向图和有向图有哪几种存储结构？各种结构在图中的不同操作（图的遍历、有向图的拓扑排序等）中有什么样的优越性？

答：无向图的存储结构有邻接矩阵、邻接表和邻接多重表；有向图的存储结构有邻接矩阵、邻接表和十字链表。 （1） （2） 的。 （3） （4）

十字链表：容易找到以顶点为头或为尾的弧，因此容易求得顶点的入度和出度。在有向图的应邻接多重表：是无向图的一种非常有效的存储结构，在其中容易求得顶点和边的各种信息。

用中，十字链表是很有用的工具。 2.回答一下关于图的问题：

（1）有n个顶点的有向连通图最多有多少条边？最少有多少条边？

17

邻接矩阵：可判定图中任意两个顶点之间是否有边或弧相连，并容易球的各个顶点的度。此外，邻接链表：容易找到任意顶点的第一个邻接点，但要判断任意两个顶点之间是否有边或弧相连，

对于图的遍历也是可行的。

则需搜索第i个及第j个链表，者不如邻接矩阵方便。此外，对于图的遍历和有向图的拓扑排序也是可行

（2）表示一个有1000个结点、1000条边的有向图的邻接矩阵有多少个矩阵元素？是否为稀疏矩阵？ （3）对于一个有向图，不用拓扑排序，如何判定图中是否存在环？

答：（1）有n个顶点的有向强连通图最多有n（n-1）条边（构成一个有向完全图的情况）；最少有n条边（n个顶点一次首尾相接构成一个环的情况）。

（2）这样的矩阵共有1000个矩阵元素，不一定是稀疏矩阵，可能时特殊矩阵（如n个顶点依次首尾相接构成一个环时，假设顶点0到顶点1有弧，···，顶点i到顶点i-1有弧，···，顶点n-1到顶点0有弧，对应的邻接矩阵中元素A[i][j]有：j-i=1或i-j=n-1，这就是一个特殊的矩阵，可以采用特殊的矩阵，可以采用相关的压缩方法存储）。

（3）对于有向图进行深度优先遍历。如果从有向图上某个顶点v出发的遍历，DFS（v）结束之前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图中必定存在包含顶点v到顶点u的环。 3.一个有向图G的邻接表存储如图9.5所示，要求： （1）画出其邻接矩阵存储。 1 2 3 4 5 6 7 8 9

（2）写出图的所有强连通分量。

a b c d h i e g f 2

2 4 5 7 3 2 9 2 6 3 8 11.4 补充练习题及参考答案

11.4.1 单项选择题

1.下列排序方法中，时间复杂性不受数据初始状态影响，恒为O（nlbn）的是（A） A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序 2.下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（C） A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序 3.下列排序方法中，在待排序的数据已经成为有序时,花费时间反而最多的是（A） A.快速排序 B.希尔排序 C.冒泡排序 D.堆排序

4.依次将待排序序列中的元素和有序子序列合并为一个新的有序子序列的排序方法是（B） A.快速排序 B.插入排序 C.冒泡排序 D.堆排序 5.若表R在排序前已按键值递增顺序排列,则(A)方法的比较次数最少. A.直接插入排序 B.快速排序 C.归并排序 D.选择排序

18

6.已知表A中每个元素距其最终位置不远,采用(B)方法最节省时间.

A.堆排序 B.冒泡排序 C.快速排序 D.直接选择排序 7.下列排序方法中，关键字比较次数与记录的初始排序无关的是（D） B.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 8.快速排序方法在(C)情况下最不利发挥其长处.

A.要排序的数据量大 B.要排序的数据中含有多个相同值 C.要排序的数据已基本有序 D.要排序的数据个数为奇数

9.数据表A中有10000个元素,如果仅要求求出其中最大的10个元素,则采用(A)方法最省时间. A.堆排序 B.希尔排序 C.快速排序 D.直接选择排序

(只有堆排序每次输出一个堆顶(即最大或最小值的元素),然后对堆进行再调整,保证对顶元素是当前剩下元素中最大或最小的,)

10.若一组记录的排序码为{46,79,56,38,40,84},则利用堆排序的方法建立的初始堆为( ) B A．79，46，56，38，40，80 B. 84，79，56，38，40，46 C. 84，79，56，46，40，38 D. 84，56，79，40，46，38

11.若一组记录的关键码为{46,79,56,38,40,84},则利用快速排序的方法，以第1个记录为基准得到的一次划分结果为（）

A.38,40,46,56,79,84 B.40,38,46,79,56,84 C.40,38,46,56,79,84 D. 40,38,46, 84,56, 79

答：对于{40,79,56,38,40,84},取出46，对{79,56,38,40,84}进行划分，先将79与40交换，得到{40, 56, 38,79, 84}，再将56与38交换，得到{40, 38, 56, 79, 84}，将46插入得到{40, 38, 46，56, 79, 84}。本题答案为C。

12.一组记录的关键码为{25，48，16,35,79,82,23,40,36,72}，其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）

A．16,25, 35,48, 23, 40,79,82, 36,72 B. 16,25, 35,48, 79, 82,23, 36 ,40, 72 C. 16,25, 48, 35, 79, 82, 23, 36,40, 72 D.16,25, 35,48, 79,23, 36,40, 72, 82

答：对于{25，48，16,35,79,82,23,40,36,72}，{25，48}和{16，35}两个子序列归并得结果为{16,25, 35,48}，{79,82}和{23, 40}两个子序列归并后的结果为{23，40，79，82}，余下的两个记录不归并，所以一趟归并后的结果为{16,25, 35,48, 23, 40,79,82, 36,72}。本题答案为A。

13.已知10个数据元素为{54,28,16,34,73,62,95,60,26,43},对该数列按从小到大排序，经过一趟冒泡排序后的序列为（）

A．16, 28, 34, 54,73,62, 60,26,43,95 B. 28,16,34, 54, 62, 73, 60,26,43,95 C. 28,16,34, 54, 62, 60, 73,26,43,95 D. 16,28, 34, 54, 62, 60,73, 26,43,95 答：冒泡排序每趟经过比较交换从无序区中产生一个最大的元素，所以答案为B。

14.用某种排序方法对线性表{25，84，21，47，15，27，68，35，20}进行排序时，元素序列的变化情况如下：

(1) 25,84,21,47,15,27,68,35,20 (2) 20,15, 21,25, 47, 27,68,35, 84 (3) 15, 20,21,25, 35, 27,47, 68, 84 (4) 15, 20,21,25, 27,35, 47, 68, 84 其所采用的排序方法是（）

A.直接选择堆序 B. 希尔排序C. 归并排序 D.快速排序

答：从中看到，每趟从无序区中找出一个最大的元素定位，所以答案为A。

15.有一组序列{48,36,68,99,75,24,28,52}进行快速排序，要求结果从小到大排序，则进行一次划分之后结果为（）

A. (24,28, 36,)48,(52,68, 75,99) B. (28, 36, 24,)48,(75,99,68,52) C . (36, 68, 99)48 (75, 24,28, 52) D. (28, 36, 24)48, (99, 75, 68,52)

19

答：B

16.一下排序方法中，最好时间复杂度为O(n)的依次是（1，2）。 A．直接插入排序 B.直接选择排序 C.冒泡排序 D. 快速排序 答：1.A 2.C

17.以下排序方法中，最坏时间复杂度为O(n2)的依次是（1、2）。 A．直接插入排序 B.直接选择排序 C.堆排序 D. 归并排序 答：1.A 2.B

18.以下排序方法中，平均时间复杂度为O(n2)的依次是（1、2）。 A．直接插入排序 B.冒泡排序 C.希尔排序 D.基数排序 答：1.A 2.B 11.4.2 填空题

1.在对一组记录{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第四次交换和选择后，未排序记录（即无序表）为（） 答：{50，70，60，95，80}

2．在对一组记录{50,40,95,20,15,70,60,45,80}进行堆排序时，根据初始记录构成初始堆后，最后4条记录为（）

答：{50，60，40，20}

3.在对一组记录{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当吧第7个记录60插入到有序表时，为寻找插入位置需比较（）次

答：第6趟的结果为{ 15,20,40, 50, 70,95, 60,45,80}，此时插入60，要与95，70和50进行比较，共比较三次。答案为3次

4.在对一组记录{50,40,95,20,15,70,60,45,80}进行希尔排序事，假定取di+1=[di/2],0<=i<=t-1，其中t=[lbn],d0=n,dt=1,n为待排序记录的个数，则第二趟排序结束后前4条记录为（）

答：t=3,d0=9,d1=4,d2=2,d3=1,第一趟（d1=4）后的结果为{15,40, 60, 20, 50, 70,95, 45,80}，第2趟（d2=2）后的结果为{15,20, 50,40, 60, 45, 80, 70,95}，本题答案为{15，20，50，40}

1 ）趟归并。在第三趟归并中，是把长度为5.在归并排序中，若待排序记录的个数未0，则共需要进行（○2）的有序表归并为长度为（○3）的有序表。 （ ○

答：n=20，共需进行[lbn]=5趟归并，第一趟归并后成为10个有序表，第2趟归并后成为5个有序表（每1 5，○24，○38 个长度为4），第三趟归并将长度为4的有序表归并为长度为8的有序表。本题答案：○1）2）6.在堆排序和快速排序中，若原始记录接近正序或反序，则选用（ ○；若原始记录无序，则最好选用（○ 1堆排序，○2快速排序 答：根据堆排序和快速排序的特点可知本题答案为：○

1）2）7.在直接插入和直接选择排序中，若初始数据基本有序，则选用（ ○，若初始数据基本反序，则选用（ ○ 1直接插入排序 ○2直接选择排序 答：○

8.在排序过程中，任何情况下都不比较关键字大小的排序方法是（） 答：基数排序方法

1. 判断一下叙述的正确性。

（1）只有在线性表的初始状态为逆序排列的情况下，冒泡排序过程中元素的移动次数才会达到最大值。 （2）只有在线性表的初始状态为逆序排列的情况下，直接选择排序过程中元素的移动次数才会达到最大值。 （3）对n个元素执行直接选择排序，关键字的比较次数总是n（n-1）/2次。

（4）只有在线性表的初始状态为逆序排列的情况下，直接插入排序过程中元素的移动次数才会达到最大值。 （5）只有在线性表的初始状态为顺序排列的情况下，快速排序过程中关键字的比较次数才会达到最大值。 （6）

对n个元素执行快速排序，在进行第一次分组时，关键字的比较次数总是n-1次。

错误。（3）

正确。（4）

正确。（5）

错误。（6）

正确。

答：（1） 正确。（2）

2. 判断一下叙述的正确性。

20