一、选择题。
1．一个无向连通图有5个顶点8条边，则其生成树将要去掉( b )条边。
(a)3 (b)4 (c)5 (d)6
2．对于含有n个顶点e条边的无向连通图，利用prim算法生成最小代价生成树其时间复杂度为( b )，利用kruskal时间复杂度为( )
(a)o(1og2n) (b)o(n2) (c)o(ne) (d)o(e log2 e)
3．对下图v4的度为( c)。
(a)1 (b)2 (c)3 (d)4
4．在一个具有n个结点的无向完全图中，包含有( a )条边。
(a) n(n-1)/2 (b) n(n-1) (c) n(n+1)/2 (d) nn
5．n个顶点的无向图的邻接表中结点总数最多有( d )个。
(a)2n 〔b)n (c)n/2 (d)n(n-1)
6．设连通图g的顶点数为n，则g的生成树的边数为( b )
(a)n (b)n一1 (c)2n (d) 2n-1
二、填空题。
1．有向图g用邻接矩阵a存储，其第i列的所有元素等于顶点i的___入度___
2．有向图g用邻接矩阵a[1…m，1…m ]存储，其第i行的所有元素值之和等于顶点vi的___出度。
1. 3．一个具有m个顶点的有向完全图的弧数为___m(m-1)
4．设无向图g有100条边，则g至少有___11___个顶点。
5．如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图___无环路___
1. 6．无向图用邻接矩阵存储，其所有元素之和表示无向图的__所有顶点度之和。
7．有向图用邻接矩阵存储，其第i列的所有元素之和等于顶点i的___入度。
三、应用题。
1．已知下图是一个有向图。
1)画出该有向图的邻接矩阵。
2)基于你给出的邻接矩阵，求从顶点6出发的深度优先遍历。
2．对于下图，试给出。
1)每个顶点的入度和出度。
2)邻接矩阵，3)逆邻接表；
4)强连通分量。
3．巳知图如下所示。
1)要求用kruskal算法求出最小生成树。
2)指出生成树的第一条边。
4．已知下图是一个无向团。
1)画出该无向图的邻接链表。
2)基于你给出的邻接链表，求从顶点c出发的广度优先遍历。
5．用prim算法(一条顶点一条顶点加入生成树)求下图的最小生成树。
1)从顶点d开始，写出各顶点加人生成树的次序。decagbf
2)画出最终的最小生成树。
6．用kruskal算法(一条边一条边地加入生成树)求右下图的最小生成树。
1)写出各条边加入生成树的次序(用权值表示)。
2)画出最终的最小生成树。
7．已知一有向图如下图所示，试画出从a点出发的深度优先生成树。
四、算法设计。
1．设汁一个算法，建立无向图(n个顶点，e条边)的邻接表。
（1）邻接表的形式说明。
typedef struct nodeedgenode;
typedef struct vnodevertexnode；
typedef vertexnode adjlist[maxvertexnum]；/adjlist是邻接表类型。
typedef structalgraph； /对于简单的应用，无须定义此类型，可直接使用adjlist类型。
(2)建立无向图的邻接表算法。
void createalgraph(algrahp *g)
for(k=0；ke；k++)end for
}createalgraph
第7章作业
1 试述进油路节流调速回路与回油路节流调速回路的不同之处。2 液压系统中，当工件部件停止运动后，使泵卸荷有什么好处？试画出三种典型的卸荷回路。3 容积调速回路有哪些？各有什么特点？4 如图所示的液压系统，可以实现快进 工进 快退 停止的工作循环要求。1 说出图中标有序号的液压元件的名称。2 填出电磁...
第7章 作业
作业 1.某系统采用8255a不断检测8个开关k7 k0的通 断状态，实时在发光二极管led7 led0上显示其结果。开关闭合时，相应的led亮 开关断开时，相应的led灭。如图所示。请编写程序段实现之。2.如果8255采用方式0，a口输出，b口输入，c1口输入，c2口输出，请画出此芯片与cpu和外...
第7章作业
第七章作业。7.2 8xx51单片机的定时 计数器有哪几种工作方式？各有什么特点？答 m1m0 00 工作方式0 13位方式 m1m0 01 工作方式1 16位方式 m1m0 10 工作方式2 8位自动再装入方式 m1m0 11 工作方式3 t0为2个8位方式 1，方式0定时器 t0或t1 工作于1...