第5课图

第五课图一、选择题1．图中有关路径的定义是（）。A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是参考答案：A2．设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n2参考答案：B3．一个n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn参考答案：A4．要连通具有n个顶点的有向图，至少需要（）条边。A．n-lB．nC．n+lD．2n参考答案：B5．n个结点的完全有向图含有边的数目（）。A．n*nＢ．n（n+1）C．n／2D．n*（n-1）参考答案：D6．一个有n个结点的图，最少有（）个连通分量。A．0B．1C．n-1D．n参考答案：B7．一个有n个结点的图，最多有（）个连通分量。A．0B．1C．n-1D．n参考答案：D8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为（）。A．5B．6C．8D．9参考答案：A9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（）。A．逆拓扑有序B．拓扑有序C．无序的参考答案：A10．下面结构中最适于表示稀疏无向图的是（）。A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表参考答案：C11．下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图B．无向图C．AOV网D．AOE网参考答案：B12．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（）。A．nijiA1],[B．n1jj,iAC．niijA1],[D．nijiA1],[+n1ji,jA参考答案：B13．下列说法不正确的是（）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．遍历的基本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图D．图的深度遍历是一个递归过程参考答案：C14．无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b参考答案：D15．设图如右所示，，在下面的5个序列中，符合深度优先遍历的序列有（）个。aebdfcacfdebaedfcbaefdcbaefdbcA．5个B．4个C．3个D．2个参考答案：D16．下列方法中可以判断出一个有向图是否有环（回路）的是（）。A．广度优先遍历B．拓扑排序C．求最短路径D．求关键路径参考答案：B17．在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（）。A．O(n)B．O(n+e)C．O(n2)D．O(n3)参考答案：B18．当各边上的权值（）时，BFS算法可用来解决单源最短路径问题。A．均相等B．均互不相等C．不一定相等参考答案：A19．求解最短路径的Floyd算法的时间复杂度为（）。A．O（n）B．O（n+c）C．O（n*n）D．O（n*n*n）参考答案：D20．已知有向图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参考答案：A21．若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列（）。A．存在B．不存在参考答案：A22．一个有向无环图的拓扑排序序列（）是唯一的。A．一定B．不一定参考答案：A23．在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A．O(n)B．O(n+e)C．O(n*n)D．O(n*n*n)参考答案：B24．关键路径是事件结点网络中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路参考答案：A25．下面关于求关键路径的说法不正确的是（）。A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D．关键活动一定位于关键路径上参考答案：C26．下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成参考答案：B27．在一个无向图中，所有顶点的度数之和等于所有边数（）倍。A．1/2B．2C．1D．4参考答案：B28．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A．1/2B．2C．1D．4参考答案：C二、应用题1．（1）如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？参考答案：G1最多n(n-1)/2条边，最少n-1条边。（2）如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？参考答案：G2最多n(n-1)条边，最少n条边。2．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？参考答案：n-1，n3．证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。参考答案：具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。4．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？参考答案：设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方，与图的边数无关。5．请回答下列关于图(Graph)的一些问题：（1）有n个顶点的有向强连通图最多有多少条边?最少有多少条边?（2）表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？参考答案：（1）n(n-1)，n（2）106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律）（3）使用深度优先遍历，按退出DFS过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行DFS(v)未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。6．设有数据逻辑结构为：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）画出这个逻辑结构的图示。（2）相对于关系r，指出所有的开始接点和终端结点。（3）分别对关系r中的开始结点，举出一个拓扑序列的例子。（4）分别画出该逻辑结构的正向邻接表和逆向邻接表。参考答案：（1）略。（2）开始结点：（入度为0）K1，K2，终端结点（出度为0）K6，K7。（3）拓扑序列K1，K2，K3，K4，K5，K6，K8，K9，K7K2，K1，K3，K4，K5，K6，K8，K9，K7规则：开始结点为K1或K2，之后，若遇多个入度为0的顶点，按顶点编号顺序选择。（4）略。7．有向图的邻接表存储如下，要求：（1）画出其邻接矩阵存储；（2）写出图的所有强连通分量；（3）写出顶点a到顶点i的全部简单路径。参考答案：（1）略。（注：邻接矩阵下标按字母升序:abcdefghi）（2）强连通分量：（a），(d)，（h），(b，e，i，f，c，g）（3）顶点a到顶点i的简单路径：（a-b-e-i），（a-c-g-i），（a-c-b-e-i）。8．如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上？参考答案：按各顶点的出度进行排序。n个顶点的有向图，其顶点最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n。之后，进行调整，即若存在弧i，j，而顶点j的出度大于顶点i的出度，则将把j编号在顶点i的编号之前。9．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。参考答案：深度优先遍历序列：125967384；宽度优先遍历序列：123456789。注：（1）邻接表不唯一，这里顶点的邻接点按升序排列；（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一；（3）这里的遍历，均从顶点1开始。10．下面的邻接表表示一个给定的无向图，（1）给出从顶点v1开始，对图G用深度优先搜索法进行遍历时的顶点序列；（2）给出从顶点v1开始，对图G用广度优先搜索法进行遍历时的顶点序列。参考答案：（1）V1V2V4V3V5V6；（2）V1V2V3V4V5V6。11．设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。参考答案：深度优先生成树：广度优先生成树：12．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？参考答案：遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。13．某田径赛中各选手的参赛项目表如下:姓名参赛项ZHAOABEQIANCDSHUNCEFLIDFAZHOUBF设项目A,B,…，F各表示一数据元素，若两项目不能同时举行，则将其连线(约束条件)。（1）根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构；（2）写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列。参考答案：（1）（2）AFEDBC或ABDEFC。14．已知无向图如下所示：（1）给出从V1开始的广度优先搜索序列；（2）画出它的邻接表；（3）画出从123451341241232423455V1开始深度优先搜索生成树。参考答案：设邻接表（略）中顶点的邻接点按顶点编号升序排列（V1编号为1），广度优先搜索序列：V1V2V3V4V5V6V7V8；深度优先搜索序列：V1V2V4V8V5V3V6V7。15．已知某图的邻接表为v1v2v3v4v5v6121124355634（1）写出此邻接表对应的邻接矩阵；（2）写出由v1开始的深度优先遍历的序列；（3）写出由v1开始的深度优先的生成树；（4）写出由v1开始的广度优先遍历的序列；（5）写出由v1开始的广度优先的生成树；（6）写出将无向图的邻接表转换成邻接矩阵的算法。参考答案：（1）略。（2）V1V2V5V3V4V6（3）（4）V1V2V3V4V5V6（5）（6）voidAdjListToAdjMatrix(AdjListgl,AdjMatrixgm)//将图的邻接表表示转换为邻接矩阵表示。{for(i=1;i=n;i++)//设图有n个顶点，邻接矩阵初始化。for(j=1;j=n;j++)gm[i][j]=0;for(i=1;i=n;i++){p=gl[i].firstarc;//取第一个邻接点。while(p!=null){gm[i][p-adjvex]=1;p=p-next;}//下一个邻接点}//for}//算法结束16．考虑右图：（1）从顶点A出发，求它的深度优先生成树；（2）从顶点E出发，求它的广度优先生成树；（3）根据普利姆（Prim）算法，求它的最小生成树。参考答案：设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列（1）ABGFDEC（2）EACFBDG（3）17．在什么情况下，Prim算法