给出右图所示有向图的邻接矩阵

1、20. 给出右图所示有向图的邻接矩阵、邻接表，并给出每个顶点的入度和出度。解：(a)邻接矩阵为： 邻接表为：V1V2V3V4V5V601234512435454 逆邻接表为：0V101V202V323V45314V5325V6123456ID011132OD212201入度和出度为： (b)邻接矩阵为： 邻接表=逆邻接表为：3210V14201V243102V34203V43214V5度为： 顶点V1V2V3V4V5度3343321对右图所示网分别给出：(2) 深度优先搜索遍历序列（分别从V1和V4开始）;（3）广度优先搜索遍历序列（分别从V1和V4开始）;（4）用普里姆算法求得最小生成树的过

2、程；（5）用克鲁斯卡尔算法求得最小生成树的过程；解：从V1开始的深度优先搜索序列为：1 2 4 3 5 6 7 8从V4开始的深度优先搜索序列为：4 2 1 3 5 6 7 8序列不唯一，可有其他形式。（3）广度优先搜索遍历序列（分别从V1和V4开始）;解：从V1开始的广度优先搜索序列为：1 2 3 4 5 6 7 8从V4开始的广度优先搜索序列为：4 2 3 5 6 1 7 8序列不唯一，可有其他形式。（4）用普里姆算法求得最小生成树的过程；解:3,4, 3,4,4,2, 3,4,4,2,2,1, 3,4,4,2,2,1,4,6, 3,4,4,2,2,1,4,6,6,5, 3,4,4,2,2

3、,1,4,6,6,5,6,8,3,4,4,2,2,1,4,6,6,5,6,8,8,7, (不唯一)（5）用克鲁斯卡尔算法求得最小生成树的过程；解： (不唯一)1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,6,8,7,1,2,4,3,4,5,6,6,8,7,1,2,2,4,3,4,5,6,6,8,7,1,2,2,4,3,4,5,6,6,8,8,7,1,2,2,4,3,4,4,6,5,6,6,8,8,7,23给出右图所示无环图的所有拓扑有序序列。解：有四种：1，2，3，4，6，5；1，3，2，4，6，5；1，3，4，2，6，

4、5；1，3，4，6，2，5。24 什么是排序算法？什么是内部排序？什么是外部排序？答：排序是数据处理中的重要运算，其功能是将一组数据元素（或记录）的任意序列，经重新排列整理成为按关键字值大小有序的序列。内部排序是指待排序文件放在内存中进行排序的排序。外部排序是指在待排序文件很大时，内存中不能一次容纳全部记录，还要借助于外存存放待排序文件，在排序过程中需要对外存进行访问的排序。25.给定排序码序列为(17,8,21,35,32,15,21,25,12,23)，试分别写出使用以下排序方法进行排序的过程。（1）直接插入排序（7）快速排序（8）直接选择排序（11）二路归并排序（12）基数排序。解：（1

5、）直接插入排序初始状态17 82135321521251223i=2插入88172135321521251223i=3插入218172135321521251223i=4插入358172135321521251223i=5插入328172132351521251223i=6插入158151721323521251223i=7插入218151721213235251223i=8插入258151721212532351223i=9插入128121517212125323523i=10插入238121517212123253235（7）快速排序初始状态17/i 82135321521251223/j

6、j向左扫描后17/i 821353215212512/j23Rj移入Ri后12 8/i21353215212517/j23i向右扫描后12 821/i353215212517/j23Ri移入Rj后12 817/i3532152125/j2123j向左扫描后12 817/i353215/j21252123Rj移入Ri后12 81535/i3217/j21252123i向右扫描后12 81535/i3217/j21252123Ri移入Rj后12 81517/i32/j3521252123j向左扫描后12 81517/i=j3235212521231趟排序后12 815173235212521232

7、趟排序后8 1215172321212532353趟排序后8121517212123253235排序结果8121517212123253235（8）直接选择排序初始状态17 82135321521251223第1趟后8 172135321521251223第2趟后8 122135321521251723第3趟后8 121535322121251723第4趟后8 121517322121253523第5趟后8 121517213221253523第6趟后8 121517212132253523第7趟后8 121517212123253532第8趟后8 121517212123253532第9趟后

8、8121517212123253235（11）二路归并排序初始状态17 82135321521251223第1趟归并后8172135153221251223第2趟归并后8172135152125321223第3趟归并后8151721212532351223第4趟归并后8121517212123253235（12）基数排序。初始状态：1782135321521251223第一趟分配之后E0E1E2E3E4E5E6E7E8E917821353215212512232121321223351525178第一趟收集之后第二趟分配之后E0 E1 E2 E3 E4 E5 E6 E7 E8 E98123221153521