北京理工大学珠海学院《数据结构》习题集第7章图(第1次更新2012-5-1).doc

第7章 图 选择题 一个有n个顶点的无向图最多有（ ）条边。【＊，★】 A、n B、n(n-1) C、n(n-1)/2 D、2n 具有6个顶点的无向图至少有（ ）条边才能保证是一个连通图。【＊，★】 A、5 B、6 C、7 D、8 具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（ ）。【＊】 A、线性图 B、无向完全图 C、无向图 D、简单图 具有4个顶点的无向完全图有（ ）条边。【＊】 A、6 B、12 C、16 D、20 G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。【＊＊】 A、6 B、7 C、8 D、9 存储稀疏图的数据结构常用的是（ ）。【＊＊】 A、邻接矩阵 B、三元组 C、邻接表 D、十字链表 对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（ ）。【＊】 A、n B、(n-1)2 C、(n+1)2 D、n2 设连通图G的顶点数为n，则G 的生成树的边数为（ ）。【＊】 A、n-1 B、n C、2n D、2n-1 对于一个具有N个顶点和E条边的无向图，若采用邻接表表示，则表头向量的大小为（ （1） ）；所有邻接表中的结点总数是（ （2） ）。【＊，★】 （1）A、N B、N+1 C、N-1 D、N+E （2）A、E/2 B、E C、2E D、N+E 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（ ），所有顶点邻接表的结点总数为（ ）。【＊】 A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e 在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（ ）。【＊，★】 A、顶点v 的度 B、顶点v 的出度 C、顶点v 的入度 D、依附于顶点v 的边数 已知一个图，若从顶点a出发进行深度和广度优先有哪些信誉好的足球投注网站遍历，则可能得到的顶点序列分别为（ ）和（ ）【＊＊，★】 （1） A、abecdf B、acfebd C、acebfd D、acfdeb （2） A、abcedf B、abcefd C、abedfc D、acfdeb 采用邻接表存储的图的深度和广度优先有哪些信誉好的足球投注网站遍历算法类似于二叉树的（ ）和（ ）。【＊＊】 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历 已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先有哪些信誉好的足球投注网站遍历算法，从顶点v1出发，得到的顶点序列分别为（ ）和（ ）。【＊，★】 A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v3,v4,v5,v2 D、v1,v4,v3,v5,v2 已知有8个顶点为A，B，C，D，E，F，G，H的无向图，其邻接矩阵存储结构如下，由此结构，从A点开始深度遍历，得到的顶点序列为（ ）。【＊，★】 A、ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDC E、ABEHFGDC F、ABEHGFCD 已知一个图如下，在该图的最小生成树中各边上权值之和为（ ），在该图的最小生成树中，从v1到v6的路径为（ ）。【＊，★】 A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v6 关键路径是事件结点网络中的（ ）。【＊】 A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最长的回路 D、最短的回路 正确的AOE网必须是（ ），AOE网中某边权值应当是（ ）。【＊，★】 （1）A、完全图 B、哈密尔顿图 C、无环图 D、强连通图 （2）A、实数 B、正整数 C、正数 D、非负数 已知一个图如下，则由该图得到的一种拓扑序列为（ ）。【＊，★】 A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v5 下面结论中正确的是（