第4章图结构测试卷.docVIP

理工大学指挥自动化学院试卷 考试科目： 第4 章 图结构 队别专业： 学 号： 姓 名： 考试日期： 年 月 日 题 号 1 2 3 总 分 得 分 阅 卷 人 【1】在一个无向图中，所有顶点的度数之和等于所有边数的倍。 A．1／2 B．1 C．2 D．4 【2】在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 A．1／2 B．1 C．2 D．4 【3】一个有n个顶点的无向图最多有条边。 A．n B．n(n-1) C．D．2n 【4】具有4个顶点的无向完全图有条边。 A．6 B．12 C．16D．20 【5】具有6个顶点的无向 A．5 B．6 C．7 D．8 【6】在一个具有n个顶点的无向图中，要连通全部顶点至少需要条边。 A．n B．n+1 C．n-1 D．n/2 【7】对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大 A．n B．(n-1)2 C．n-1 D．n2 【8】对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向 ：所有邻接表中的结点总数是② 。 ①A．n B．n+1 C．n-1 D．n+e ②A．e/2 B．e C．2e D．n+e 【9】对某个无向图的邻接矩阵来说，。 A．第i行上的非零元素个数和第i列的非零元素个数一定相等 B．矩阵中的非零元素个数等于图中的边数 C．第i行上，第i列上非零元素总数等于顶点vi的度数 D．矩阵中非全零行的行数等于图中的顶点数 【10】已知一个图如图所示，若从顶点a出发按深度有哪些信誉好的足球投注网站法进行遍历，则 ①A．a，b，e，c，d，f B．a，c，f，e，b，d C．a，e，b，c，f，d D．a，e，d，f，c，b ②A．a，b，c，e，d，f B．a，b，c，e，f，d C．a，e，b，c，f，d D．a，c，f，d，e，b 【11】已知一有向图的邻接表存储结构如图所示。 （1）根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是① 。 A．v1，v2，v3，v5，v4 B．v1，v2，v3，v4，v5 C．v1，v3，v4，v5，v2 D．v1，v4，v3，v5，v2 根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是② 。 A．v1，v2，v3，v4，v5 B．v1，v3，v2，v4，v5 C．v1，v2，v3，v5，v4 D．v1，v4，v3，v5，v2【12】采用邻接表存储的图的深度优先遍历算法类似于二叉树的 。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历 【13】采用邻接表存储的图的广度优先遍历算法类似于二叉树的 。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历【14】一个图中包含k个连通分量，若按深度优先有哪些信誉好的足球投注网站方法访问所有结点，则必须调用次深度优先遍历算法。 A．k B．1 C．k-1 D．k+1 【15】任何一个无向连通图的最小生成树 。 A．有一棵或多棵 B．只有一棵 C．一定有多棵D．可能不存在 【16】以下说法中不正确的是 。 A．无向图中的极大连通子图称为连通分量 B．连通图的广度优先有哪些信誉好的足球投注网站中一般要采用队列来暂存刚访问过的顶点 c．图的深度优先有哪些信誉好的足球投注网站中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先有哪些信誉好的足球投注网站方法 【17】判定一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可 A．求关键路径的方法 B．求最短路径的Dijkstra方法 【18】下面不正确的说法是 。 (1)求从Dijkstra最短路径算法中弧上权值可以为负值。 (2)利用Dijkstra算法求所有不同顶点对的最短路径的算法时间为O(n3)(图用邻接)。 (3)利用Floyd算法求每个不同顶点对的算法中允许弧上的权值为负，但不能有权之 A．(1)、