第三部分考研真题精选
一、选择题
1．图中有关路径的定义是（）。
A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是
2．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n2
3．一个n个顶点的连通无向图，其边的个数至少为（）。
A．n-1 B．n C．n+1 D．nlogn；
4．要连通具有n个顶点的有向图，至少需要（）条边。
A．n-l B．n C．n+l D．2n
5．n个结点的完全有向图含有边的数目（）。
A．n*n Ｂ．n（n＋１）C．n／2 D．n*（n－l）
6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。
A．0 B．1 C．n-1 D．n
7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。
A．1/2 B．2 C．1 D．4
8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )。
A．5 B．6 C．8 D．9
9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。
A．逆拓扑有序B．拓扑有序C．无序的
10．下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（）。
A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表
11．下列哪一种图的邻接矩阵是对称矩阵？（）
A．有向图B．无向图C．AOV网D．AOE网14．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连，则只要检查（）的第i行第j列的元素是否为零即可。
A．mA B．A C．A m D．Am-1
15. 下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程
16．无向图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,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
19．下面哪一方法可以判断出一个有向图是否有环（回路）：
A．深度优先遍历  B. 拓扑排序  C. 求最短路径  D. 求关键路径
20. 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。
A. O(n)
B. O(n+e)
C. O(n2)
D. O(n3)
21. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（1 ），下面步骤重复n-1次: a：（2 ）；b：（3 ）；最后：（4 ）。
（1）．A．VT，ET为空B．VT为所有顶点，ET为空
C．VT为网中任意一点，ET为空D．VT为空，ET为网中所有边（2）．A. 选i属于VT，j不属于VT，且（i，j）上的权最小
B．选i属于VT，j不属于VT，且（i，j）上的权最大
C．选i不属于VT，j不属于VT，且（i，j）上的权最小
D．选i不属于VT，j不属于VT，且（i，j）上的权最大
（3）．A．顶点i加入VT，（i,j）加入ET    B. 顶点j加入VT，（i,j）加入ET
C. 顶点j加入VT，（i,j）从ET中删去D．顶点i,j加入VT，（i,j）加入ET （4）．A．ET 中为最小生成树B．不在ET中的边构成最小生成树C．ET中有n-1条边时为生成树，否则无解
D．ET中无回路时，为生成树，否则无解
22. (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；
(2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3) ；（图用邻接矩阵表示）
(3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。
上面不正确的是（）。
数据结构与算法考研真题A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3)
23．当各边上的权值( )时，BFS算法可用来解决单源最短路径问题。
A．均相等B．均互不相等C．不一定相等
24. 求解最短路径的Floyd算法的时间复杂度为( )。
A．O（n）  B. O（n+c）  C. O（n*n）  D. O（n*n*n）
25．已知有向图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,V7
C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V7
26．若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列（）。
A．存在B．不存在
27．一个有向无环图的拓扑排序序列（）是唯一的。
A．一定B．不一定
28. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。
A．G中有弧<Vi，Vj> B．G中有一条从Vi到Vj的路径
C．G中没有弧<Vi,Vj> D．G中有一条从Vj到Vi的路径
29. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。
A. O(n)
B. O(n＋e)
C. O(n*n)
D. O(n*n*n)
30. 关键路径是事件结点网络中（）。
A．从源点到汇点的最长路径B．从源点到汇点的最短路径
C．最长回路D．最短回路
31. 下面关于求关键路径的说法不正确的是（）。
A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上
32．下列关于AOE网的叙述中，不正确的是（）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成
D．某些关键活动提前完成，那么整个工程将会提前完成
二、判断题
1.树中的结点和图中的顶点就是指数据结构中的数据元素。（）
2．在n个结点的无向图中，若边数大于n-1，则该图必是连通图。（）
4. 有e条边的无向图，在邻接表中有e个结点。（）
5. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（）
6．强连通图的各顶点间均可达。（）
7．强连通分量是无向图的极大强连通子图。（）
8．连通分量指的是有向图中的极大连通子图。（）
9．邻接多重表是无向图和有向图的链式存储结构。（）
10. 十字链表是无向图的一种存储结构。（）
11. 无向图的邻接矩阵可用一维数组存储。（）
12．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）
13．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（）
14. 有向图的邻接矩阵是对称的。（）
15．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）16. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（）
17. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（）
18．一个有向图的邻接表和逆邻接表中结点的个数可能不等。（）
19．需要借助于一个队列来实现DFS算法。（）
20. 广度遍历生成树描述了从起点到各顶点的最短路径。（）
21．任何无向图都存在生成树。（）
22. 不同的求最小生成树的方法最后得到的生成树是相同的.（）
23．带权无向图的最小生成树必是唯一的。（）
24. 最小代价生成树是唯一的。（）
25．一个网（带权图）都有唯一的最小生成树。（）
26．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）
27．带权的连通无向图的最小（代价）生成树（支撑树）是唯一的。（）
28. 最小生成树的KRUSKAL算法是一种贪心法（GREEDY）。（）
29. 求最小生成树的普里姆(Prim)算法中边上的权可正可负。（）
30．带权的连通无向图的最小代价生成树是唯一的。（）
31. 最小生成树问题是构造连通网的最小代价生成树。（）
32. 在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（）
33. 在用Floyd 算法求解各顶点的最短路径时，每个表示两点间路径的path k-1[I,J]一定是path k [I,J]的子集(k=1,2,3,…,n)。（）
34．拓扑排序算法把一个无向图中的顶点排成一个有序序列。（）
35．拓扑排序算法仅能适用于有向无环图。（）
36. 无环有向图才能进行拓扑排序。（）
37. 有环图也能进行拓扑排序。（）
38．拓扑排序的有向图中，最多存在一条环路。（）
39．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（）
40. 既使有向无环图的拓扑序列唯一，也不能唯一确定该图。（）
41．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）
42．AOV网的含义是以边表示活动的网。（）
43．对一个AOV网，从源点到终点的路径最长的路径称作关键路径。
44. 关键路径是AOE网中从源点到终点的最长路径。（）
45. AOE网一定是有向无环图。（）
46. 在表示某工程的AOE网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。（）
47．在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（）48．在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。（）
49．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。
三、填空题
1.判断一个无向图是一棵树的条件是______。
2．有向图G的强连通分量是指______。
3．一个连通图的______是一个极小连通子图。
4．具有10个顶点的无向图，边的总数最多为______。
5．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。
7．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。
8. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。9．在有n个顶点的有向图中，每个顶点的度最大可达______。
10．设G为具有N个顶点的无向连通图，则G中至少有______条边。
11．n个顶点的连通无向图，其边的条数至少为______。
12．如果含n个顶点的图形形成一个环，则它有______棵生成树。
13．N个顶点的连通图的生成树含有______条边。
14．构造n个结点的强连通图，至少有______条弧。
15．有N个顶点的有向图，至少需要量______条弧才能保证是连通的。
16．右图中的强连通分量的个数为（）个。
17．N个顶点的连通图用邻接矩阵表示时，该矩阵
至少有_______个非零元素。
18．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的______；对于有向图来说等于该顶点的______。
19. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。
20. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。
21. 遍历图的过程实质上是______，breath-first search遍历图的时间复杂度______；depth-first search遍历图的时间复杂度______，两者不同之处在于______，反映在数据结构上的差别是______。
22. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。23. 一无向图G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）}，对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，则采用的遍历方法是______。
24. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。
25．构造连通网最小生成树的两个典型算法是______。
26．求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。
27. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。
28．克鲁斯卡尔算法的时间复杂度为______，它对______图较为适合。
29．对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为______，利用Kruskal算法生成最小代价生成树其时间复杂度为______。
30．下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个节点V1，V2，．．．，Vn，用相邻矩阵A表示，边的权全是正数。请在下列划线处填上正确叙述。（1）．若（Vi，Vj）是边，则A（i，j）的值等于______，若（Vi，Vj）不是边，则A（i，j）的值是一个比任何边的权______，矩阵的对角线元素全为0。
（2）．构造最小生成树过程中，若节点Vi已包括进生成树，就把相邻矩阵的对角线元素A（i，i）置成______，若（Vi，Vj）已包括进生成树，就把矩阵元素A（i，j）置成______。（3）．算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。
31. 有一个用于n个顶点连通带权无向图的算法描述如下：
（1）．设集合T1与T2，初始均为空；
（2）．在连通图上任选一点加入T1；
（3）．以下步骤重复n-1次：
a.在i属于T1，j不属于T1的边中选最小权的边；
b.该边加入T2。
上述算法完成后，T2中共有______条边，该算法称______算法，T2中的边构成图的______。
32. 有向图G可拓扑排序的判别条件是______。
33. Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按______次序依次产生，该算法弧上的权出现______情况时，不能正确产生最短路径。
34. 求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则在图的顶点数为40，计算时间约为______ms。
35．求最短路径的Dijkstra算法的时间复杂度为______。
36.有向图G=(V,E)，其中V(G)={0,1,2,3,4,5}，用<a,b,d>三元组表示弧<a,b>及弧上的权d.E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则从源点0到顶

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。