答：
深度优先序列 V0,V1,V2,V5,V4,V6,V3,V7 广度优先序列 V0 V1 V3 V4 V2 V6 V5 V7 【19，6，3】已知有向图如右图所示，请给出该图的 （1） 每个顶点的入度和出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 各个强连通分量。 答：
（1）各顶点的入度和出度如下：
①：3/0 ②2/2 ③ 1/2 ④1/2 ⑤ 2/1 ⑥2/3 （2）邻接矩阵如下： 1 2 3 4 1 0 0 0 0 2 1 0 0 1 3 0 1 0 0 4 0 0 1 0 5 1 0 0 0 6 1 1 0 0 （3）邻接表如下： 1 2 3 4 5 6
^ 1 6 3 1 1 ^ 4 2 5 2 ^ ^ 6 5 5 0 0 0 1 0 1 6 0 0 1 1 0 0 ^ ^ （4）逆邻接表如下： 1
2 3 4 2 4 3
26 6 ^ ^ 2 3 4 5 6
（5）有三个强连通分量:
^ ^ ^ ^ ⑥
① ⑤ ② ④
③
【20，6，3】试利用Dijkstra算法求下图在从顶点A到其它顶点的最短距离及对应的路径，写出计算过程中各步状态。
答： 1 c:2 2 c:2 f:6 3 c:2 f:6 e:10 4 c:2 f:6 e:10 d:11
27
5 c:2 f:6 e:10 d:11 g:14 6 c:2 f:6 e:10 d:11 g:14 b:15
【21，6，3】给出如下图所示的具有7个结点的网G。请：
（1） 画出该网的邻接矩阵；
（2） 采用Prim算法，从4号结点开始，给出该网的最小生成树（画出Prim算法的执行过程及最
小生成树的生成示意图）。
1 1 6 2 3 7 4
0 5 6 2 5 3 3 2 5 1 4 4
答：
void prim(MGraph g,int v0,int &sum){ int lowcost[MAXSIZE],vset[MAXSIZE];
int v,pre[MAXSIZE]; //pre[]存入前驱结点数组 int i,j,k,min;
v=v0; //初始起点 for(i=1;i<=g.n;i++){
lowcost[i]=g.edges[v0][i]; //lowcost[]的数组 pre[i]=v0; vset[i]=0; }
vset[v0]=1; sum=0; for(i=1;i min=INF;
for(j=1;j<=g.n;j++){
if(vset[j]==0&&lowcost[j] min=lowcost[j]; k=j; } }
vset[k]=1; //将此结点并入到所够造的生成树中 v=k;
28
if(min!=INF){
printf(\边的起点为： %d 终点为： %d 权值为 %d\\n\ sum+=min; }else{
break; }
for(j=1;j<=g.n;j++){//并入新结点后修改剩下的结点到生成树的权值 if(vset[j]==0&&g.edges[v][j] lowcost[j]=g.edges[v][j]; pre[j]=v; //并记其下全趋结点 } } } }
【22，7，4】给定数组{48, 25, 6, 90, 17, 84, 62, 48, 27, 96, 49, 72, 17}，请分别用简单选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。 答：
简单选择排序：
6，25，48， 90, 17, 84, 62, 48, 27, 96, 49, 72, 17 6，17， 48， 90,25, 84, 62, 48, 27, 96, 49, 72, 17 6，17， 17， 90,25, 84, 62, 48, 27, 96, 49, 72, 48 6，17， 17， 25,90 84, 62, 48, 27, 96, 49, 72, 48 6，17， 17， 25, 27, 84, 62, 48, 90 96, 49, 72, 48 6，17， 17， 25, 27, 48 62 84 90 96 49 72 48 6 17 17 25 27 48 48 84 90 96 49 72 62 6 17 17 25 27 48 48 49 90 96 84 72 62 6 17 17 25 27 48 48 49 62 96 84 72 90 6 17 17 25 27 48 48 49 62 72 84 96 90 6 17 17 25 27 48 48 49 62 72 84 96 90
29
6 17 17 25 27 48 48 49 62 72 84 90 96
直接插入排序
6 25 48 90 17 84 62 48 27 96 49 72 17 6 25 48 90 17 84 62 48 27 96 49 72 17 6 25 48 17 90 84 62 48 27 96 49 72 17 6 17 25 48 90 84 62 48 27 96 49 72 17 6 17 25 48 84 90 62 48 27 96 49 72 17 6 17 25 48 62 84 90 48 27 96 49 72 17 6 17 25 48 62 84 90 48 27 96 49 72 17 6 17 25 48 48 62 84 90 27 96 49 72 17 6 17 25 27 48 48 62 84 90 96 49 72 17 6 17 25 27 48 48 62 84 90 96 49 72 17 6 17 25 27 48 48 49 62 84 90 96 72 17 6 17 25 27 48 48 49 62 72 84 90 96 17 6 17 17 25 27 48 48 49 62 72 84 90 96
冒泡排序：
25 48 6 17 84 62 48 27 90 49 72 17 96 25 6 17 48 62 48 27 84 49 72 17 90 96 6 17 25 48 48 27 62 49 72 17 84 90 96 6 17 25 48 27 48 49 62 17 72 84 90 96 6 17 25 27 48 48 49 17 62 72 84 90 96 6 17 25 27 48 48 17 49 62 72 84 90 96 6 17 25 27 48 17 48 49 62 72 84 90 96 6 17 25 27 17 48 48 49 62 72 84 90 96 6 17 25 17 27 48 48 49 62 72 84 90 96
30