新浪博客

第七章　图练习题（二）

2007-06-14 16:30阅读：

http://blog.sina.cn/dpool/blog/u/1283642807

41、任何一个无向连通图的最小生成树( )
A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在
42、图有 、 等存储结构，遍历图有 、 等方法。
43、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 。
44、如果n个顶点的图是一个环，则它有 棵生成树。 （以任意一顶点为起点，得到n-1条边）
45、n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 。
46、n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 。
47、设有一稀疏图G，则G采用 存储较省空间。
48、设有一稠密图G，则G采用 存储较省空间。
49、图的逆邻接表存储结构只适用于 图。
50、
已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是 。
51、图的深度优先遍历序列 惟一的。
52、n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 ；若采用邻接表存储时，该算法的时间复杂度为 。
53、图的BFS生成树的树高比DFS生成树的树高 。
54、用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 。
55、若要求一个稀疏图G的最小生成树，最好用 算法来求解。
56、若要求一个稠密图G的最小生成树，最好用 算法来求解。
57、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来得到最短路径的。
58、拓扑排序算法是通过重复选择具有 个前驱顶点的过程来完成的。
59、已知如图所示的有向图，请给出该图的:
（1）每个顶点的入/出度；
（2）邻接矩阵；
（3）邻接表；
60、请对下图的无向带权图：
（1）写出它的邻接矩阵;
（2）写出它的邻接表。

61、已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
62、试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。
63、给定下列网G:
(1) 试着找出网G的最小生成树，画出其逻辑结构图；
(2) 用两种不同的表示法画出网G的存储结构图；
(3)用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。
64、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
65、试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？ 提示： 将邻接矩阵的第i行全部置0 ）
66、试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。
67、采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。（注：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。）

我的更多文章

下载客户端阅读体验更佳

APP专享