文件名称：数据结构（图）试题及答案
文件大小：327KB
文件格式：DOCX
更新时间：2012-01-10 18:32:14
数据结构 图 试题 答案
......
（ B ）3. 有8个结点的无向图最多有 条边。
A．14 B. 28 C. 56 D. 112
（ C ）4. 有8个结点的无向连通图最少有 条边。
A．5 B. 6 C. 7 D. 8
（ C ）5. 有8个结点的有向完全图有 条边。
A．14 B. 28 C. 56 D. 112
（ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。
A．栈 B. 队列 C. 树 D. 图
......
二、填空题（每空1分，共20分）
1. 图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先遍历 、 广度优先遍历 等方法。
2. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。
3. 如果n个顶点的图是一个环，则它有 n 棵生成树。
4. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2) 。
5. n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。
.......
1. 【严题集7.1①】已知如图所示的有向图，请给出该图的:
每个顶点的入/出度；
邻接矩阵；
邻接表；
逆邻接表。
2. 【严题集7.7②】请对下图的无向带权图：
写出它的邻接矩阵，并按普里姆算法求其最小生成树；
写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。
........
五、算法设计题（每题10分，共30分）
1. 【严题集7.14③】编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
解：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表
{
InitALGraph(G);
scanf("%d",&v);
if(v<0) return ERROR; //顶点数不能为负
G.vexnum=v;
scanf("%d",&a);
if(a<0) return ERROR; //边数不能为负
G.arcnum=a;
for(m=0;m