等我想的时候我再来添加图片-PTA图的基本概念和存储结构(选择和填空)

落日映苍穹つ 2022-12-23 00:34 7阅读 0赞

> (从网页上扣文字真恶心)  
> (这次题真多)  
> (google输入法真相,好看又好用)  
> (缺点就是 数字和符号有的大有的小??)  
> (可惜google停止了更新)

图的概念与存储结构 题目分析  
1-1  
用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关（F）  
【分析】 所有链表的长度和 与 边数有关

1-2  
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，  
则G一定有2个连通分量（T）  
【分析】连通分量：一个连通图只有一个连通分量，  
两个连通分量说明有两个不连通的子图  
无论 广度优先还是深度优先  
最终实现的功能都是遍历访问一个连通图的所有顶点

1-3  
无向连通图所有顶点的度之和为偶数。（T）  
【分析】任何图的度之和 = 边数 \* 2 所以度之和一定是偶数

1-4  
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。（F）

1-5  
在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。（T）

1-6  
用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。

1-7  
无向连通图至少有一个顶点的度为1。(F)  
\[分析\]回路

1-8  
在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。(T)

1-9  
无向连通图边数一定大于顶点个数减1。  
\[分析\]无向连通图边数最小是 定点数 - 1, 此时是一棵树

2-1  
给定有向图的邻接矩阵如下：

顶点2（编号从0开始）的出度和入度分别是：(D)  
A.3, 1  
B.2, 0  
C.1, 3  
D.0, 2  
\[分析\]出度则查找G\[2\]\[*\] 入度查找G\[*\]\[2\]的个数

2-2  
下列选项中，不是下图深度优先搜索序列的是:©  
A.V1, V3, V2, V5, V4  
B.V1, V2, V5, V4, V3  
C.V1, V2, V3, V4, V5  
D.V1, V5, V4, V3, V2  
\[分析\]深度优先遍历 利用递归的思想

2-3  
下列关于无向连通图特征的叙述中，正确的是：(B)  
1.所有顶点的度之和为偶数  
2.边数大于顶点个数减1  
3.至少有一个顶点的度为1

A.1和3  
B.只有1  
C.只有2  
D.1和2  
\[分析\]1对;2应该是大于等于;3回路不满足

2-4  
下面给出的有向图中，各个顶点的入度和出度分别是：(A)  
A.入度: 0, 2, 3, 1, 2; 出度: 3, 2, 1, 1, 1  
B.入度: 3, 4, 4, 2, 3; 出度: 3, 4, 4, 2, 3  
C.入度: 3, 2, 1, 1, 1; 出度: 0, 2, 3, 1, 2  
D.入度: 0, 1, 2, 1, 1; 出度: 3, 2, 1, 1, 1

2-5  
在图中自a点开始进行广度优先遍历算法可能得到的结果为：(A)  
A.a, b, e, c, d, f  
B.a, e, d, f, c, b  
C.a, e, b, c, f, d  
D.a, c, f, e, b, d  
\[分析\]广度优先遍历的思想是队列,不断入队出队

2-6  
已知一个图的邻接矩阵如下，则从顶点V1出发按广度优先搜索法进行遍历，可能得到的一种顶点序列为：©  
A.V1,V3,V5,V2,V4,V6  
B.V1,V2,V4,V5,V6,V3  
C.V1,V2,V3,V5,V4,V6  
D.V1,V3,V5,V6,V4,V2  
\[分析\]建议把图画出来,此题注意一下,邻接矩阵是对称矩阵,说明边是成对出现的

2-7  
给定一有向图的邻接表如下。从顶点V1出发按广度优先搜索法进行遍历，则得到的一种顶点序列为：(A)  
A.V1,V3,V2,V4,V5  
B.V1,V4,V3,V5,V2  
C.V1,V2,V3,V4,V5  
D.V1,V2,V3,V5,V4  
\[分析\]特别恶心的可能会 根据邻接表 中 临界点的顺序来得到广度优先遍历序列  
本题可能就是,其实我感觉AC都对,但是 答案可能选A

2-8  
若某图的深度优先搜索序列是\{V2, V0, V4, V3, V1\}，则下列哪个图不可能对应该序列？  
\[分析\]挨个选项试试,其中比较特殊的是有个选项是个非连通图  
那么它金光深度优先遍历后的序列只能是一部分

2-9  
下列说法不正确的是：(A)  
A.图的深度遍历不适用于有向图  
B.图的遍历是从给定的源点出发每一个顶点仅被访问一次  
C.遍历的基本算法有两种：深度遍历和广度遍历  
D.图的深度遍历是一个递归过程  
\[分析\]不会

2-10  
在一个有向图中，所有顶点的入度与出度之和等于所有边之和的多少倍？(A)  
A.2  
B.1/2  
C.1  
D.4

2-11  
若无向图G =（V，E）中含7个顶点，  
要保证图G在任何情况下都是连通的，则需要的边数最少是：  
A.15  
B.6  
C.21  
D.16  
\[分析\]无向图保证连通性, 边树 = n \* (n - 1) / 2

2-12  
如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是：(B)  
A.完全图  
B.连通图  
C.一棵树  
D.有回路的图

2-13  
已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是：(D)  
A.10  
B.15  
C.13  
D.11  
\[分析\]假设其余定点都是度为2的点,16 \* 2 = 4 \* 3 +　３　＊　４　＋ 2 \* x

2-14  
在图中自a点开始进行深度优先遍历算法可能得到的结果为：(D)  
A.a, e, b, c, f, d  
B.a, c, f, e, b, d  
C.a, b, e, c, d, f  
D.a, e, d, f, c, b

2-15  
已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为：©  
A.V1,V2,V3,V4,V5,V6  
B.V1,V3,V5,V2,V4,V6  
C.V1,V2,V4,V5,V6,V3  
D.V1,V3,V5,V6,V4,V2

2-16  
对于一个具有N个顶点的无向图，要连通所有顶点至少需要多少条边？©  
A.N  
B.N/2  
C.N−1  
D.N+1  
\[分析\]树

2-17  
若一个有向图用邻接矩阵表示，则第i个结点的入度就是：  
(1分)(A)  
A.第i列的非零元素个数  
B.第i行的元素个数  
C.第i列的零元素个数  
D.第i行的非零元素个数  
\[分析\]G\[\*\]\[i\]表示 指向i的有向边, 这种边的个数就是i节点的入度个数

2-18  
给定一个有向图的邻接表如下图，则该图有\_\_个强连通分量。(A)  
A.3 \{ \{2\}, \{4\}, \{0, 1, 3, 5\}\}  
B.4 \{ \{0, 1, 5\}, \{2\}, \{3\}, \{4\}\}  
C.1 \{0, 1, 2, 3, 4, 5\}  
D.1 \{0, 5, 1, 3\}  
\[分析\]有向图的强连通分量:在有向图中,任意两点u,v都存在u到v的有向路径  
判断是否是强连通分量的方法是从起点找一条路径,若能找到回路,  
则路径上的点都属于一个强连通分量

2-19  
关于图的邻接矩阵，下列哪个结论是正确的？(B)  
A.无向图的邻接矩阵可以是不对称的，也可以是对称的  
B.有向图的邻接矩阵可以是对称的，也可以是不对称的  
C.有向图的邻接矩阵总是不对称的  
D.无向图的邻接矩阵总是不对称的  
\[分析\]无向图的邻接矩阵一定是 对称的,有向图不一定

2-20  
图的广度优先遍历类似于二叉树的：(B)  
A.后序遍历  
B.层次遍历  
C.先序遍历  
D.中序遍历

2-21  
给定无向图G，从V0出发进行深度优先遍历访问的边集合为： \{(V0,V1), (V0,V4),  
(V1,V2), (V1,V3), (V4,V5), (V5,V6)\}。则下面哪条边不可能出现在G中？  
A.(V4,V6)  
B.(V1,V5)  
C.(V0,V6)  
D.(V0,V2)  
\[分析\]无向图,加上试试

2-22  
图的深度优先遍历类似于二叉树的：©  
A.中序遍历  
B.层次遍历  
C.后序遍历  
D.先序遍历  
\[分析\]画个树,肯定先访问根节点吧,所以就是先序遍历

2-23  
若某图的深度优先搜索序列是\{V1, V4, V0, V3, V2\}，则下列哪个图不可能对应该序列？(A)

2-24  
对于有向图，其邻接矩阵表示比邻接表表示更易于：(D)  
A.进行图的深度优先遍历  
B.进行图的广度优先遍历  
C.求一个顶点的出边邻接点  
D.求一个顶点的入度  
\[分析\]我只会D,其余的不懂

2-25  
设无向图的顶点个数为N，则该图最多有多少条边？(A)  
A.N(N+1)/2  
B.N^2  
C.N(N−1)/2  
D.N−1

2-26  
如果G是一个有28条边的非连通无向图，那么该图顶点个数最少为多  
少？©  
A.9  
B.7  
C.8  
D.10  
\[分析\]28条边最少由8个节点组成,要保证联通,再加一个节点即可  
具体怎么分析我也不太清楚

2-27  
下面关于图的存储的叙述中，哪一个是正确的？(A)  
A.用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，  
而与边数无关  
B.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，  
而与边数无关  
C.用邻接表法存储图，占用的存储空间数只与图中边数有关，  
而与结点个数无关  
D.用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，  
而与结点个数无关

2-28  
给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：()  
A.V1,V2,V3,V4,V7,V6,V5  
B.V1,V5,V6,V4,V7,V2,V3  
C.V1,V5,V4,V7,V6,V2,V3  
D.V1,V5,V4,V7,V6,V3,V2  
\[分析\]我觉得ABCD都挺对的呀  
难道是根据原邻接表的顺序遍历?

2-29  
对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是：(B)  
A.N  
B.N^2  
C.(N−1)^2  
D.N−1

2-30  
给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：  
A.V1,V4,V3,V5,V2  
B.V1,V2,V3,V5,V4  
C.V1,V2,V4,V5,V3  
D.V1,V3,V4,V5,V2  
\[分析\]我觉得ABCD都挺对的呀

2-31  
如果G是一个有36条边的非连通无向图，  
那么该图顶点个数最少为多少？(A)  
A.10  
B.8  
C.9  
D.7  
\[分析\]36条边最少由9个点构成,为了构成非联通图所以需要10个点

2-32  
下面给出的有向图中，有\_\_个强连通分量。©  
A.1 (\{1,2,3,4\})  
B.5 (\{0\}, \{1\}, \{2\}, \{3\}, \{4\})  
C.2 (\{1,2,3,4\}, \{0\})  
D.1 (\{0,1,2,3,4\})  
\[分析\]求回路的个数,并根据回路组成集合

2-33  
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是：(D)  
A.G肯定不是完全图  
B.G有2个连通分量  
C.G一定不是连通图  
D.G中一定有回路  
\[分析\]D没有回路,但是非联通的图也可以满足条件

2-34  
设N个顶点E条边的图用邻接表存储，  
则求每个顶点入度的时间复杂度为：(B)  
A.O(N)  
B.O(N×E)  
C.O(N+E)  
D.O(N^2)  
\[分析\]求一个点的入度,需要访问所有的边,  
一个点的时间复杂度是O(E),N个点就是O(N\*E)

2-35  
具有N（N>0）个顶点的无向图至多有多少个连通分量？(B)  
A.0  
B.N  
C.N−1  
D.1  
\[分析\]没有边

2-36  
在任一有向图中，所有顶点的入度之和与所有顶点的出度之和  
的关系是：(B)  
A.不确定  
B.相等  
C.小于等于  
D.大于等于  
\[分析\]一条有向边可以产生一个出度,一个入度

2-37

在图中自c点开始进行广度优先遍历算法可能得到的结果为：©  
A.c,a,f,d,e,b  
B.c,a,b,e,f,d  
C.c,f,a,d,e,b  
D.c,f,a,b,d,e  
\[分析\]广度优先遍历需要注意一点,比如push进c,f,a之后  
下一个从队列取出的应该是f,而不是a

在N个顶点的无向图中，所有顶点的度之和不会超过顶点数的多少倍？(B)  
A.(N−1)/2  
B.N−1  
C.1  
D.2  
\[分析\]不会超过,所以求最大,顶点数一定,所以求度之和的最大值  
即边数的最大值,注意边数的最大值是n\*(n-1)/2  
度之和最大值是n\*(n-1), 所以倍数是(n-1)

2-39  
一个有N个顶点的强连通图至少有多少条边？(B)  
A.N(N−1)  
B.N  
C.N−1  
D.N+1  
\[分析\]强连通图 属于 有向图,无向图中不存在 强连通图  
N个点,N条边首尾相连就行, 不能再少

2-40  
给定一有向图的邻接表如下。若从v1开始利用此邻接表做广度优先搜索得到的  
顶点序列为：\{v1, v3, v2, v4, v5\}，  
则该邻接表中顺序填空的结果应为：(A)  
A.v3, v2, v4  
B.v3, v4, v2  
C.v2, v3, v4  
D.v4, v3, v2  
\[分析\]注意是利用此邻接表做BFS,要利用了邻接表中同一层节点的顺序

2-41

若无向图G =（V，E）中含10个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是：(Ｃ)  
A.9  
B.37  
C.45  
D.36  
\[分析\]10 ＊　（　９　）　／　２

２－４２  
在一个无向图中，所有顶点的度数之和等于所有边数的多少倍？（C）  
A.1  
B.1/2  
C.2  
D.4