搜索
1第七章图一、选择题1．图中有关路径的定义是（）。【北方交通大学2001一、24（2分）】A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n2【清华大学1998一、5（2分）】【西安电子科技大1998一、6（2分）】【北京航空航天大学1999一、7（2分）】3．一个n个顶点的连通无向图，其边的个数至少为（）。【浙江大学1999四、4(4分)】A．n-1B．nC．n+1D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。【北京航空航天大学2000一、6(2分）】A．n-lB．nC．n+lD．2n5．n个结点的完全有向图含有边的数目（）。【中山大学1998二、9（2分）】A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6．一个有n个结点的图，最少有（B）个连通分量，最多有（）个连通分量。A．0B．1C．n-1D．n【北京邮电大学2000二、5（20/8分）】7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。【哈尔滨工业大学2001二、3（2分）】A．1/2B．2C．1D．48．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为()。【中山大学1999一、14】A．5B．6C．8D．99．下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学2001一、11（2分）】A．有向图B．无向图C．AOV网D．AOE网10.下列说法不正确的是（）。【青岛大学2002二、9（2分）】A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程11．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。【南京理工大学2001一、14（1.5分）】A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b12.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A.O(n)B.O(n+e)C.O(n2)D.O(n3)13.下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（1），下面步骤重复n-1次:a：（2）；b：（3）；最后：（4）。【南京理工大学1997一、11_14（8分）】（1）．A．VT，ET为空B．VT为所有顶点，ET为空C．VT为网中任意一点，ET为空D．VT为空，ET为网中所有边（2）．A.选i属于VT，j不属于VT，且（i，j）上的权最小B．选i属于VT，j不属于VT，且（i，j）上的权最大C．选i不属于VT，j不属于VT，且（i，j）上的权最小D．选i不属于VT，j不属于VT，且（i，j）上的权最大（3）．A．顶点i加入VT，（i,j）加入ETB.顶点j加入VT，（i,j）加入ETC.顶点j加入VT，（i,j）从ET中删去D．顶点i,j加入VT，（i,j）加入ET（4）．A．ET中为最小生成树B．不在ET中的边构成最小生成树C．ET中有n-1条边时为生成树，否则无解D．ET中无回路时，为生成树，否则无解14．已知有向图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,V72【北京航空航天大学2000一、7（2分）】15．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（）。A．存在B．不存在【中科院计算所1998二、6(2分）】【中国科技大学1998二、6（2分）】16．一个有向无环图的拓扑排序序列（）是唯一的。【北京邮电大学2001一、3（2分）】A．一定B．不一定17.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。A．G中有弧Vi，VjB．G中有一条从Vi到Vj的路径C．G中没有弧Vi,VjD．G中有一条从Vj到Vi的路径【南京理工大学2000一、9（1.5分）】18.在用邻接表表示图时，拓扑排序算法时间复杂度为()。A.O(n)B.O(n＋e)C.O(n*n)D.O(n*n*n)【合肥工业大学2000一、2（2分）】【南京理工大学2001一、9（1.5分）】【青岛大学2002二、3（2分）】19.关键路径是事件结点网络中（）。【西安电子科技大学2001应用一、4（2分）】A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路20.下面关于求关键路径的说法不正确的是（）。【南京理工大学1998一、12（2分）】A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D．关键活动一定位于关键路径上二、填空题1．AOV网中,结点表示___,边表示__。AOE网中,结点表示____,边表示__。2．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为___。3．一个连通图的__是一个极小连通子图。【重庆大学2000一、1】4．具有10个顶点的无向图，边的总数最多为____。【华中理工大学2000一、7（1分）】5．若用n表示图中顶点数目，则有__条边的无向图成为完全图。【燕山大学1998一、6（1分）】6.有向图G可拓扑排序的判别条件是__。7．G是一个非连通无向图，共有28条边，则该图至少有_9_个顶点。【西安电子科技大2001软件一、8（2分）】8.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要____条弧。【合肥工业大学2000三、8（2分）】9.Prim（普里姆）算法适用于求__的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求___的网的最小生成树。【厦门大学1999一、4】10．设G为具有N个顶点的无向连通图，则G中至少有____条边。【长沙铁道学院1997二、2(2分)】11．n个顶点的连通无向图，其边的条数至少为____。【哈尔滨工业大学2000二、2（1分）】12．N个顶点的连通图的生成树含有___条边。【中山大学1998一、9（1分）】13．构造n个结点的强连通图，至少有____条弧。【北京轻工业学院2000一、4（2分）】14．有N个顶点的有向图，至少需要量__条弧才能保证是连通的。【西南交通大学2000一、3】15．右图中的强连通分量的个数为（）个。【北京邮电大学2001二、5（2分）】16.已知一无向图G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__遍历方法。17.为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_存放被访问的结点以实现遍历。【南京理工大学1999二、9（2分）】18．求图的最小生成树有两种算法，___算法适合于求稀疏图的最小生成树。【南京理工大学2001二、6（2分）】3三、应用题1．解答问题。设有数据逻辑结构为：B=(K,R),K={k1,k2,…,k9}R={k1,k3,k1,k8,k2,k3,k2,k4,k2,k5,k3,k9,k5,k6,k8,k9,k9,k7,k4,k7,k4,k6}（1）．画出这个逻辑结构的图示。（3分）（2）．相对于关系r,指出所有的开始接点和终端结点。（2分）（3）．分别对关系r中的开始结点，举出一个拓扑序列的例子。（4分）（4）．分别画出该逻辑结构的正向邻接表和逆向邻接表。（6分）【山东工业大学1999三（15分）】2．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。【天津大学1999一】2题图3题图3．给出图G：（1）．画出G的邻接表表示图；（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。【南开大学1997五(14分)】4．某田径赛中各选手的参赛项目表如下:姓名参赛项ZHAOABEQIANCDSHUNCEFLIDFAZHOUBF设项目A,B,…，F各表示一数据元素,若两项目不能同时举行,则将其连线(约束条件).（1）．根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构;（2）．写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列.【北京科技大学1999五2000五（12分）】5．考虑右图：(1)从顶点A出发，求它的深度优先生成树(2)从顶点E出发，求它的广度优先生成树（3）根据普利姆(Prim)算法，求它的最小生成树【上海交通大学1999六(12分)】6．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。【哈尔滨工业大学1999九（8分）】36758942131057842169EABGCDF53614312546题图1265432010116618101459