JAVA数据库考题适用于大连东软信息学院.docx

5.8习题5.8.1知识点：图的基本概念一、选择题1 n个顶点的连通图至少有（ A ）条边。An-1 Bn Cn+1 D0 2 在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个（ B ）。A顶点序列B边序列C权值总和D边的条数3 具有n个顶点的有向图最多可包含（ D ）条有向边。An-1 B nCn（n-1）/2 D n（n-1）4 在无向图中定义顶点的度为与它相关联的（ B ）的数目。A顶点B边C权D权值5 一个有N个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。ANBN1CN1DN/2 6 含N个顶点的连通图中的任意一条简单路径，其长度不可能超过（ C ）。A1BN/2CN1DN 7 设无向图的顶点个数为n，则该图最多有（ B ）条边。【清华大学 1998】【西安电子科技大 1998】【北京航空航天大学 1999】An-1 B n（n-1）/2Cn（n+1）/2 Dn（n-1） 8 在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C ）倍。【哈尔滨工业大学 2001】A1/2 B2 C1 D4二、填空题1 n（n0）个顶点的无向图中顶点的度的最大值为_n-1_。2 n（n0）个顶点的无向图最少有_0_条边。3 n（n0）个顶点的连通无向图各顶点的度之和最少为_2(n-1)_。4 具有n个顶点的无向完全图，边的总数为_n(n-1)/2_条；而具有n个顶点的有向完全图边的总数为_n(n-1)_条。5 在有n个顶点的有向图中，每个顶点的度最大可达_2(n-1)_。6 在有n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_n_条弧。【合肥工业大学 2000】7 n个顶点的连通无向图，其边的条数至少为_n-1_。【哈尔滨工业大学 2000】8 N个顶点的连通图的生成树含有_n-1_条边。【中山大学 1998】9 一个连通图的_生成树_是一个极小连通子图。【重庆大学 2000】三、判断题（ T）1 如果无向图中各个顶点的度都大于2，则该图中必有回路。（ F ）2 一个图的子图可以是空图，顶点个数为0。（ T ）3 有n（n1）个顶点的有向强连通图最少有n条边。（ T ）4 树中的结点和图中的顶点就是指数据结构中的数据元素。【青岛大学 2001】（ F ）5 在n 个结点的无向图中，若边数大于n-1，则该图必是连通图。【中科院软件所1997】（ T）6 强连通图的各顶点间均可达。【北京邮电大学 2000】（ F）7 强连通分量是无向图的极大强连通子图。【北京邮电大学 2002】（ F）8 连通分量指的是有向图中的极大连通子图。【燕山大学 1998】四、简答题1 设连通图G如图所示。（1）如果有关结点，请找出所有关结点。（2）如果想把该连通图变成重连通图，至少在图中加几条边？如何加？图5.59 1题图5.8.2知识点：图的存储一、选择题1 在n个顶点的有向无环图的邻接矩阵中至少有（C ）个零元素。An Bn（n-1）/2 Cn（n+1）/2 Dn（n-1） 2 若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。A上三角矩阵B稀疏矩阵C对角矩阵D对称矩阵3 对于一个有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ D ）。ANB（N1）*（N1）CN1DN*N 4 设一个有n个顶点和e条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是（ A ）。AO（n） BO（e） CO（n+e） DO（） 5 对于具有e条边的无向图，它的邻接表中有（ D ）个边结点。Ae-1 Be C2（e-1） D2e6 下面结构中最适于表示稀疏无向图的是（ E ），适于表示稀疏有向图的是（ D ）。【北京工业大学 2001】A邻接矩阵 B逆邻接表 C邻接多重表 D十字链表 E邻接表二、填空题1 用邻接矩阵存储图，占用存储空间数与图中顶点个数_n有_关，与边数_无_关。2 邻接表和十字链表适合于存储_有向_图，邻接多重表适合于存储_无向_图。3 在有向图的邻接矩阵表示中，计算第I 个顶点入度的方法是_第i列非零元素个数_。【青岛大学 2002】4 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_度_；对于有向图来说等于该顶点的_出度_。【燕山大学 2001】5 对于一个具有n 个顶点e 条边的无向图的邻接表的表示，则表头向量大小为_n_，邻接表的边结点个数为_2e_。【青岛大学 2002】三、判断题（T）1 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。（ T ）2 存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。（ T ）3 邻接矩阵只适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。（ F ）4 邻接多重表是无向图和有向图的链式存储结构。【南京航空航天大学 1995】（ F ）5 十字链表是无向图的一种存储结构。【青岛大学 2001】（ T ）6 无向图的邻接矩阵可用一维数组存储。【青岛大学 2000】（ T ）7 有n 个顶点的无向图， 采用邻接矩阵表示， 图中的边数等于邻接矩阵中非零元素之和的一半。 【北京邮电大学 1998】（ F ）8 有向图的邻接矩阵是对称的。【青岛大学 2001】（ F ）9 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。【东南大学 2001】【哈尔滨工业大学 1999】（ F ）10 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。【上海海运学院1998】（ F ）11 一个有向图的邻接表和逆邻接表中结点的个数可能不等。【上海交通大学 1998】四、简答题1 在下图所示的有向图中，试给出： （1）每一个顶点的入度和出度；（2）邻接矩阵；（3）邻接表、逆邻接表；（4）强连通分量。图5.60 1题图2 在下图所示的无向图中，试给出：（1）该图的邻接矩阵（2）该图的邻接表（3）该图的多重邻接表（4）给出每个顶点的度图5.61 2题图3 已知无向图G，V（G）=1，2，3，4，E（G）=（1，2），（1，3），（2，3），（2，4），（3，4）试画出G 的邻接多重链表，并说明，若已知点i，如何根据邻接多重链表找到与i 相邻的点j？【东南大学1998】五、算法题1 设有向图用邻接表表示，图有n 个顶点，表示为1 至n，试写一个算法求顶点k 的入度（1kn）。【南京理工大学 1997】2 一个无向连通图的存储结构以邻接表的形式给定，设计算法删除该图中的一条边（i，j）。【北京工业大学 1996】5.8.3知识点：图的遍历一、选择题1 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是（B ）。A栈B队列 C二叉树D树2 一个连通图的生成树是包含图中所有顶点的一个（ C ）子图。A极小B连通 C极小连通D无环3 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（C ）。A前序遍历B中序遍历 C后序遍历D层次遍历4 对于有向图，其邻接矩阵表示比邻接表表示更易于（A ）。A求一个顶点的度B求一个顶点的邻接点C进行图的深度优先遍历D进行图的广度优先遍历5 下列说法不正确的是（ C ）。【青岛大学 2002】A图的遍历是从给定的源点出发每一个顶点仅被访问一次 B遍历的基本算法有两种：深度遍历和广度遍历 C图的深度遍历不适用于有向图D图的深度遍历是一个递归过程6 无向图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），对该图进行深度优先遍历，得到的顶点序列正确的是（ D ）。【南京理工大学 2001】Aa，b，e，c，d，f Ba，c，f，e，b，d Ca，e，b，c，f，d Da，e，d，f，c，b7 下图中给出由7 个顶点组成的无向图。从顶点1 出发，对它进行深度优先遍历得到的序列是（ （1）C ），而进行广度优先遍历得到的顶点序列是（ （2）C ）。【中科院软件所 1999】（1）：A1354267 B1347652 C1534276 D1247653 E以上答案均不正确（2）：A1534267 B1726453 Cl354276 D1247653 E以上答案均不正确图5.62 7题图二、填空题1 深度优先生成树的高度比广度优先生成树的高度_高_。2 遍历图的基本方法有_深度_优先搜索和_广度_优先搜索两种。3 已知一无向图G=（V，E），其中V=a，b，c，d，e ， E=（a，b），（a，d），（a，c），（d，c），（b，e）。现用某一种图遍历方法从顶点a 开始遍历图，得到的序列为abecd，则采用的是_深度_遍历方法。【南京理工大学 1996】4 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列_存放被访问的结点以实现遍历。【南京理工大学 1999】三、判断题（T ）1 图的深度优先搜索（depth first search）是一种典型的回溯搜索的例子，可以通过递归算法求解。（ T ）2 图的广度优先搜索（breadth first search）算法不是递归算法。（ T ）3 对一个连通图进行一次深度优先搜索（depthfirstsearch）可以遍访图中的所有顶点。四、简答题1 设连通图G如图所示。试画出该图及其对应的邻接表表示，并给出对它执行从v0开始的深度优先搜索的结果。 图5.63 1题图2 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出从顶点v1出发，对图分别进行深度和广度优先遍历的结果。图5.64 2题图3 对下图所示的有向图，从顶点v1出发，分别画出其深度和广度生成树。图5.65 3题图五、算法题1 使用邻接矩阵，实现图的深度优先遍历算法。2 使用邻接表，实现图的广度优先遍历算法。3 假设图采用邻接表存储，分别写出基于DFS和BPS遍历的算法来判别定点i和定点j（ij）之间是否有路径。5.8.4知识点：最小生成树一、选择题1 在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（ D ）辅助结构，判断一条边的两个端点是否在同一个连通分量上。A位向量B堆 C并查集D生成树顶点集合2 任何一个带权的无向连通图的最小生成树（ B ）。A只有一棵B有一棵或多棵 C一定有多棵D可能不存在3 一个无向连通图的生成树是含有该连通图的全部顶点的（ A ）。A极小连通子图B极小子图 C极大连通子图D极大子图4 对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个（ C ）。A由n-1条权值最小的边构成的子图B由n-1条权值之和最小的边构成的子图C由n-1条权值之和最小的边构成的连通子图D由n顶点构成的边的权值之和最小的连通子图5 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（B ）。【合肥工业大学 2001】A. O（） B. O（） C. O（） D. O（）二、填空题1 101个顶点的连通网络N有100条边，其中权值为1，2，3，4，5，6，7，8，9，10的边各10条，则网络N的最小生成树各边的权值之和为_550_。2 在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个_边_上，才有可能加入到生成树中。3 构造连通网络最小生成树的两个典型算法是_prim_和_kruskal_。4 Prim（普里姆）算法适用于求_稠密_的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求_稀疏_的网的最小生成树。【厦门大学 1999】5 对于含N 个顶点E 条边的无向连通图，利用Prim 算法生成最小代价生成树其时间复杂度为_O(n2)_，利用Kruskal 算法生成最小代价生成树其时间复杂度为_O(eloge)_。【长沙铁道学院 1998】三、判断题（ F ）1 最小生成树是指边数最少的生成树。（ F ）2 从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树。（ F ）3 只要无向网中没有权值相同的边，其最小生成树就是唯一的。（ F ）4 只要无向网中有权值相同的边，其最小生成树就不可能是唯一的。（ F ）5 需要借助于一个队列来实现DFS 算法。【南京航空航天大学 1996】（ F ） 6 广度遍历生成树描述了从起点到各顶点的最短路径。【合肥工业大学 2001】（ F ）7 任何无向图都存在生成树。【北京邮电大学 2000】（ F ）8 不同的求最小生成树的方法最后得到的生成树是相同的。【南京理工大学 1998】（ F ）9 带权无向图的最小生成树必是唯一的。【南京航空航天大学 1996】（ T ）10 最小生成树的KRUSKAL 算法是一种贪心法（GREEDY）。【华南理工大学 2002】（ T ）11 求最小生成树的普里姆（Prim）算法中边上的权可正可负。【南京理工大学 1998】（ T ）12 最小生成树问题是构造连通网的最小代价生成树。【青岛大学 2001】（ T ）13 在图G 的最小生成树G1 中，可能会有某条边的权值超过未选边的权值。【合肥工业大学 2000】四、简答题1 对下图所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。图5.66 1题图2 已知世界六大城市为:北京（Pe）、纽约（N）、巴黎（Pa）、伦敦（L）、东京（T）、墨西哥（M），下表给出了这六大城市之间的交通里程（单位:百公里），试作下面的题目：（1）画出这六大城市的交通网络图;（2）画出该图的邻接表表示法;（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。 表5.1 2题表penpaLTMPe109828121124N109585510832PA825839792L815539589T211089795113M1243292891133 已知无向图如下所示：（1）给出从V1 开始的广度优先搜索序列；（2）画出它的邻接表；（3）画出从V1 开始深度优先搜索生成树。【燕山大学 2000】图5.67 3题图五、算法题1 如下图是一个城市连接图，图中的权值表示两个城市之间的里程（单位：100km）现要设计一条铁路贯穿所有城市（即从一个任一城市可以到达其他城市），设计一个算法，求出最小代价。假设每1km的铁路的造价为100万元。图5.68 1题图5.8.5知识点：图的应用一、选择题1 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ B ）。AO（） B O（） CO（） DO（） 2 图中有关路径的定义是（ A ）。A由顶点和相邻顶点序偶构成的边所形成的序列B由不同顶点所形成的序列C由不同边所形成的序列D上述定义都不是3 以下说法正确的是（ A ）。A连通图的生成树是该连通图的一个极小连通子图B无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的C任何一个有向图，其全部顶点可以排成一个拓扑序列D有回路的图不能进行拓扑排序4 关键路径是事件顶点网络中（ A ）。A从源点到汇点的最长路径B从源点到汇点的最短路径C最长的回路D最短的回路5 下面哪一方法可以判断出一个有向图是否有环（回路）（ B ）。A深度优先遍历B拓扑排序 C求最短路径D求关键路径6 一个有向无环图的拓扑排序序列（ B ）是唯一的。【北京邮电大学 2001】A一定 B不一定7 在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是（D ）。【南京理工大学 2000】AG 中有弧 BG 中有一条从Vi 到Vj 的路径CG 中没有弧 DG 中有一条从Vj 到Vi 的路径8 在用邻接表表示图时，拓扑排序算法时间复杂度为（ B ）。【合肥工业大学 2000】【南京理工大学 2001】【青岛大学 2002】A. O（） B. O（） C. O（） D. O（）9 下面关于求关键路径的说法不正确的是（ A）。【南京理工大学 1998】A求关键路径是以拓扑排序为基础的B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D关键活动一定位于关键路径上10 下列关于AOE 网的叙述中，不正确的是（D）。【北方交通大学 1999】【北京工业大学 1999】A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成11 下列哪一种图的邻接矩阵是对称矩阵？（ B）【北方交通大学 2001】A有向图 B无向图 CAOV 网 DAOE 网二、填空题1 在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为_关键路径_。2 若对一个有向无环图进行拓扑排序，再对排在拓扑有序序列中的所有顶点按其先后次序重新编号，则在相应的邻接矩阵中所有_非零_元素将集中到对角线以上。3 有向图G 可拓扑排序的判别条件是_AOV网 有向无环图_。【长沙铁道学院 1998】4 AOV网中，结点表示_活动_，边表示_优先级关系_。AOE网中，结点表示_事件_，边表示_活动_。【北京理工大学 2001】5 在AOE 网中，从源点到汇点路径上各活动时间总和最长的路径称为_关键路径_。【重庆大学2000】三、判断题（ F ）1 对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。（ T ）2 有回路的有向图不能完成拓扑排序。（ F ）3 在AOE网络中一定只有一条关键路径。（ F ）4 对一个有向图进行拓扑排序（topological sorting），一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。（ T ）5 对于一个边上权值任意的带权有向图，使用Dijkstra算法可以求一个顶点到其它各个顶点的最短路径。（ F ）6 拓扑排序算法把一个无向图中的顶点排成一个有序序列。【南京航空航天大学1995】（ T ）7 拓扑排序算法仅能适用于有向无环图。【南京航空航天大学 1997】（ F ）8 拓扑排序的有向图中，最多存在一条环路。【大连海事大学 2001】（ F ）9 任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。【上海交通大学1998】（ F ）10 即使有向无环图的拓扑序列唯一，也不能唯一确定该图。【合肥工业大学 2001】（ T ）11 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。【中科院软件所 1997】（F ）12 AOV 网的含义是以边表示活动的网。【南京航空航天大学 1995】（ F ）13 对一个AOV 网，从源点到终点的路径最长的路径称作关键路径。【南