24求最短路径的迪克斯特拉算法的时间复杂度为 C A.O(n) B.O(n=e) C.O(n2) D.O(ne) 9.4.2填空题
1．有n个结点的无向图最多有_____条边 n（n-1）/2 2．有n个顶点的强连通有向图G至少有___条 n-1
3．在有n个顶点的有向图中，每个顶点的度最大可达______ 2(n-1)
4、若无向图G的顶点度数最小值大于等于 时，G至少有一条回路。 答：2 5、一个图的 表示法是唯一的，而 表示法是不唯一的。
答：图的表示法主要有链接矩阵和邻接表，前者唯一，后者不唯一。本题答案为：①链接矩阵 ②邻接表 6、用链接矩阵A[1?n,1?n]存储有向图G，其第i行的所有元素之和等于顶点的 。 答：出度 7、有n个顶点的有向图G最多有 条弧。 答：n（n-1）
8、对于一个具有n个顶点和e条边的无向图。若才用邻接表表示，则表头向量的大小为＿ 所有连接表中的节点总数为 答：①n ②2e
9、已知一个有向图的邻接矩阵表示，删除所有从第i个节点出发的弧的表示方法是 答：将邻接矩阵第i行全部置零
10、对于n个顶点的无向图，采用邻接矩阵表示，求图中边数的方法是 ，判断任意两个顶点i和j是否有边相邻的方法是 ，求任意一个顶点的度的方法是 。
答：①邻接矩阵中1的个数出于2 ②A[i][j]是否为1 ③吉萨该行中1的个数
11、对于n各顶点的有向图。采用邻接表表示，求图中边数的方法是 ，判断任意两个顶点i和j是否有边相邻的方法是 ，求任意一个顶点的度的方法是 。
答：①邻接矩阵中1的个数 ②A[i][j]是否为1 ③出度为该行中1的个数，入读为该行列中1的个数 12、对于n各顶点的无向图。采用邻接表表示，求图中边数的方法是 ，判断任意两个顶点i和j是否有边相邻的方法是 ，求任意一个顶点的度的方法是＿＿＿。
答：①邻接表中结点个数（除表头结点外）出于二 ②从i表头结点开头的链表中是否包含 结点 ③以i表头结点开头的链表中的结点个数 13、无向图的连通分量是指 。答：最大连通子图
14、若无向图中有m条边；则表示该无向图的邻接表中就有 结点。 答：2m 15、对n个顶点的图来说，他的生成树一定有 条边。 答：n-1 16、连通分量是无向图中的 的连通子图。 答：极大 17、一个连通图的 是一个极小连通子图。 答：生成树
18、普里姆算法算法适用于求 的网的最小生成树，克鲁斯卡尔算法适用于求 的网的最小生成树。 答：①边稠密 ②边稀疏
19、可以进行拓扑排序的有向图一定是 。 答：无环图
20、从原点到汇点长度最长的路径称关键路径，该路径上的活动成为 。 答：关键活动 9.4.3 判断题
1、 判断以下叙述的正确性。
（1） n个顶点的无向图至多有n(n-1)条边
（2） 在有向图中，各顶点的入度和等于各顶点的出度之和。 （3） 邻接矩阵只存储了边的信息，没有存储顶点的信息。
（4） 对同一个有向图来说，只保存出边的邻接表中结点的数目总是和只保存入边的邻接表中结点的数目一样多。
（5） 如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。
（6） 如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是完全有向图 （7） 连通图的生成树包含了图中所有顶点。
16
（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