第7章图

第七章图一、选择题1．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是()。A．逆拓扑有序B．拓扑有序C．无序的【中科院软件所1998】2．下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学20004、2（4分）】A．深度优先遍历B.拓扑排序C.求最短路径D.求关键路径3.求解最短路径的Floyd算法的时间复杂度为()。【合肥工业大学1999一、2（2分）】A．O（n）B.O（n+c）C.O（n*n）D.O（n*n*n）4．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V7【北京航空航天大学2000一、7（2分）】5．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（）。A．存在B．不存在【中科院计算所1998二、6(2分）】【中国科技大学1998二、6（2分）】6．一个有向无环图的拓扑排序序列（）是唯一的。【北京邮电大学2001一、3（2分）】A．一定B．不一定7.关键路径是事件结点网络中（）。【西安电子科技大学2001应用一、4（2分）】A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路8．下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成【北方交通大学1999一、7（3分）】【北京工业大学1999一、1(2分)】二、判断题1．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（）【上海交通大学1998一、13】2.关键路径是AOE网中从源点到终点的最长路径。（）【青岛大学2000四、10（1分）】三、填空题1．克鲁斯卡尔算法的时间复杂度为______,它对______图较为适合。【中科院计算所1999二、3（2分）】2．求最短路径的Dijkstra算法的时间复杂度为______。【哈尔滨工业大学2001一、5（2分）】3．在AOV网中，存在环意味着______，这是______的；对程序的数据流图来说，它表明存在______。【厦门大学1999一、2】四、应用题1．请回答下列关于图(Graph)的一些问题：（每题4分）（1）．有n个顶点的有向强连通图最多有多少条边?最少有多少条边?（2）．表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？（3）．对于一个有向图，不用拓扑排序，如何判断图中是否存在环？【清华大学2000一(12分）】2．下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：（1）．该带权有向图的图形；（2）．从顶点V1为起点的广度优先周游的顶点序列及对应的生成树（即支撑树）；（3）．以顶点V1为起点的深度优先周游生成树；（4）．由顶点V1到顶点V3的最短路径。【中山大学1994四（12分）】五、算法设计题1．我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。【复旦大学1997六（13分）】V1V2V3V4V5V6233429625336230338542110618123456(顶点边)（出边表）2．欲用四种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色（点相交不算相邻）。（1）．试用一种数据结构表示地图上各国相邻的关系，（６分）。（2）．描述涂色过程的算法。（不要求证明）（１２分）。【浙江大学2002八（18分）】六、上机作业图遍历的演示1.问题描述很多涉及图上操作的问题都是以图的遍历算法作为基础。试写一个程序，演示在连通无向图上访问全部结点的操作。2.基本要求以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。3.测试数据教科书图7.33.