JAV数据库考题适用于大连东软信息学院.docx
- 文档编号:14168357
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:20
- 大小:132.41KB
JAV数据库考题适用于大连东软信息学院.docx
《JAV数据库考题适用于大连东软信息学院.docx》由会员分享,可在线阅读,更多相关《JAV数据库考题适用于大连东软信息学院.docx(20页珍藏版)》请在冰点文库上搜索。
JAV数据库考题适用于大连东软信息学院
5.8习题
5.8.1知识点:
图的基本概念
一、选择题
1①n个顶点的连通图至少有(A)条边。
A.n-1B.n
C.n+1D.0
2①在无向图中定义顶点 vi与vj之间的路径为从vi到达vj的一个(B)。
A.顶点序列B.边序列
C.权值总和D.边的条数
3①具有n个顶点的有向图最多可包含(D)条有向边。
A.n-1B.n
C.n(n-1)/2D.n(n-1)
4①在无向图中定义顶点的度为与它相关联的(B)的数目。
A.顶点B.边
C.权D.权值
5①一个有N个顶点的无向图中,要连通全部顶点至少需要(C)条边。
A.NB.N+1
C.N-1D.N/2
6②含N个顶点的连通图中的任意一条简单路径,其长度不可能超过(C)。
A.1B.N/2
C.N-1D.N
7②设无向图的顶点个数为n,则该图最多有(B)条边。
【清华大学1998】【西安电子科技大1998】【北京航空航天大学1999】
A.n-1B.n(n-1)/2
C.n(n+1)/2D.n(n-1)
8②在一个无向图中,所有顶点的度数之和等于所有边数(B)倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的(C)倍。
【哈尔滨工业大学2001】
A.1/2B.2C.1D.4
二、填空题
1②n(n﹥0)个顶点的无向图中顶点的度的最大值为___n-1_____。
2②n(n﹥0)个顶点的无向图最少有___0_____条边。
3②n(n﹥0)个顶点的连通无向图各顶点的度之和最少为__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 (n≥1) 个顶点的有向强连通图最少有n条边。
(T)4②树中的结点和图中的顶点就是指数据结构中的数据元素。
【青岛大学2001】
(F)5②在n个结点的无向图中,若边数大于n-1,则该图必是连通图。
【中科院软件所1997】
(T)6②强连通图的各顶点间均可达。
【北京邮电大学2000】
(F)7②强连通分量是无向图的极大强连通子图。
【北京邮电大学2002】
(F)8②连通分量指的是有向图中的极大连通子图。
【燕山大学1998】
四、简答题
1③设连通图G如图所示。
(1)如果有关结点,请找出所有关结点。
(2)如果想把该连通图变成重连通图,至少在图中加几条边?
如何加?
图5.591题图
5.8.2知识点:
图的存储
一、选择题
1②在n个顶点的有向无环图的邻接矩阵中至少有(C)个零元素。
A.nB.n(n-1)/2
C.n(n+1)/2D.n(n-1)
2②若采用邻接矩阵法存储一个n个顶点的无向图,则该邻接矩阵是一个(D)。
A.上三角矩阵B.稀疏矩阵
C.对角矩阵D.对称矩阵
3②对于一个有N个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是(D)。
A.NB.(N-1)*(N-1)
C.N-1D.N*N
4③设一个有n个顶点和e条边的有向图采用邻接矩阵表示,要计算某个顶点的出度所耗费的时间是(A)。
A.O(n)B.O(e)C.O(n+e)D.O(
)
5②对于具有e条边的无向图,它的邻接表中有(D)个边结点。
A.e-1B.eC.2(e-1)D.2e
6③下面结构中最适于表示稀疏无向图的是(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.601题图
2③在下图所示的无向图中,试给出:
(1)该图的邻接矩阵
(2)该图的邻接表
(3)该图的多重邻接表
(4)给出每个顶点的度
图5.612题图
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的入度(1 【南京理工大学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】 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 7②下图中给出由7个顶点组成的无向图。 从顶点1出发,对它进行深度优先遍历得到的序列是( (1)C),而进行广度优先遍历得到的顶点序列是( (2)C)。 【中科院软件所1999】 (1): A.1354267B.1347652C.1534276D.1247653E.以上答案均不正确 (2): A.1534267B.1726453C.l354276D.1247653E.以上答案均不正确 图5.627题图 二、填空题 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②图的深度优先搜索(depthfirstsearch)是一种典型的回溯搜索的例子,可以通过递归算法求解。 (T)2①图的广度优先搜索(breadthfirstsearch)算法不是递归算法。 (T)3②对一个连通图进行一次深度优先搜索(depth first search)可以遍访图中的所有顶点。 四、简答题 1③设连通图G如图所示。 试画出该图及其对应的邻接表表示,并给出对它执行从v0开始的深度优先搜索的结果。 图5.631题图 2③首先将如下图所示的无向图给出其存储结构的邻接链表表示,然后写出从顶点v1出发,对图分别进行深度和广度优先遍历的结果。 图5.642题图 3③对下图所示的有向图,从顶点v1出发,分别画出其深度和广度生成树。 图5.653题图 五、算法题 1④使用邻接矩阵,实现图的深度优先遍历算法。 2④使用邻接表,实现图的广度优先遍历算法。 3④假设图采用邻接表存储,分别写出基于DFS和BPS遍历的算法来判别定点i和定点j(i≠j)之间是否有路径。 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.661题图 2④已知世界六大城市为: 北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M),下表给出了这六大城市之间的交通里程(单位: 百公里),试作下面的题目: (1)画出这六大城市的交通网络图; (2)画出该图的邻接表表示法; (3)画出该图按权值递增的顺序来构造的最小(代价)生成树。 表5.12题表 pe n pa L T M Pe 109 82 81 21 124 N 109 58 55 108 32 PA 82 58 3 97 92 L 81 55 3 95 89 T 21 108 97 95 113 M 124 32 92 89 113 3③已知无向图如下所示: (1)给出从V1开始的广度优先搜索序列; (2)画出它的邻接表; (3)画出从V1开始深度优先搜索生成树。 【燕山大学2000】 图5.673题图 五、算法题 1④如下图是一个城市连接图,图中的权值表示两个城市之间的里程(单位: 100km)现要设计一条铁路贯穿所有城市(即从一个任一城市可以到达其他城市),设计一个算法,求出最小代价。 假设每1km的铁路的造价为100万元。 图5.681题图 5.8.5知识点: 图的应用 一、选择题 1②设有向图有n个顶点和e条边,采用邻接表作为其存储表示,在进行拓扑排序时,总的计算时间为(B)。 A.O( )B.O( ) C.O( )D.O( ) 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】 A.G中有弧 C.G中没有弧 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.无向图C.AOV网D.AOE网 二、填空题 1①在AOE网中,从源点到汇点路径上各活动时间总和最长的路径称为___关键路径______。 2①若对一个有向无环图进行拓扑排序,再对排在拓扑有序序列中的所有顶点按其先后次序重新编号,则在相应的邻接矩阵中所有__非零______元素将集中到对角线以上。 3①有向图G可拓扑排序的判别条件是___AOV网有向无环图___。 【长沙铁道学院1998】 4②AOV网中,结点表示___活动______,边表示__优先级关系_______。 AOE网中,结点表示___事件______,边表示____活动_____。 【北京理工大学2001】 5②在AOE网中,从源点到汇点路径上各活动时间总和最长的路径称为____关键路径_____。 【重庆大学2000】 三、判断题 (F)1①对任何用顶点表示活动的网络(AOV网)进行拓扑排序的结果都是唯一的。 (T)2①有回路的有向图不能完成拓扑排序。 (F)3①在AOE网络中一定只有一条关键路径。 (F)4②对一个有向图进行拓扑排序(topologicalsorting),一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。 (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网,从源点到终点的路径最长的路径称作关键路径。 【南京航空航天大学1995】 (T)14②AOE网一定是有向无环图。 【青岛大学2001】 (F)15②在AOE图中,关键路径上某个活动的时间缩短,整个工程的时间也就必定缩短。 【大连海事大学2001】 (T)16②当改变网上某一关键路径上任一关键活动后,必将产生不同的关键路径。 【上海交通大学1998】 四、简答题 1③已知有向图,其边集为{<1,2>,<2,3>,<5,2>,<5,6>,<6,4>,<3,4>},求此图的所有可能的拓扑序列。 若以此顺序输入建立图的邻接表,再在此存储储结构上执行拓扑排序过程,则得到的拓扑序列是哪一种? 2③下表给出了某工程各工序之间的优先关系和各工序所需时间 (1)画出相应的AOE网。 (2)列出各事件的最早发生时间,最迟发生时间。 (3)找出关键路径并指明完成该工程所需最短时间。 表5.22题表 工序代号 A B C D E F G H I J K L M N 所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40 先驱工作 -- -- A,B B C,D B E G,I E I F,I H,J,K L G
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- JAV 数据库 考题 适用于 大连 信息 学院
![提示](https://static.bingdoc.com/images/bang_tan.gif)