2019
无。
2020
第 8 题
有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。
A. 9
B. 10
C. 11
D. 12
选A。一个无向图的连通性是指图中任意两个顶点都存在一条路径相连。
对于有n个顶点的无向图，其连通性至少需要满足的条件是：当且仅当图中含有n-1条边时，这个图才是连通的。
因此，对于有10个顶点的无向图，至少需要9条边才能确保它是连通图。这是因为当图中只有8条边时，这个图就不是一个连通图。
举个例子，考虑一个有4个顶点的无向图，它只有3条边，所以它不是一个连通图。但是如果我们添加第4条边，这个图就变成了一个连通图。
2021
第 6 题
对于有 n 个顶点、m 条边的无向连通图 (m>n)，需要删掉（ ）条边才能使其成为一棵树。
A. n − 1
B. m − n
C. m − n − 1
D. m − n + 1
选D。树有n - 1条边，把这个图变成树，即变成n - 1条边，需要删掉
m - (n - 1) = m - n + 1条边。
第 14 题
以 a 为起点，对下边的无向图进行深度优先遍历，则 b,c,d,e 四个点中有可能作为最后一个遍历到的点的个数为（ ）。
A. 1
B. 2
C. 3
D. 4
选B。b和e可能为最后一个点。
2022
第 9 题
考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。
A. N − 1
B. N
C. N+1
D. $N^2$
选B。边最少的情况，就是每个顶点只有一条入边和一条出边，连成一个圈，即连通图。
第 10 题
以下对数据结构的表述不恰当的一项为：（ ）。
A. 图的深度优先遍历算法常使用的数据结构为栈。
B. 栈的访问原则后进先出，队列的访问原则是先进先出。
C. 队列常常被用于广度优先搜索算法。
D. 栈与队列存在本质不同，无法用栈实现队列。
选D。虽然本质不同，但是勉强能用，比较麻烦，用两个栈就能实现。
- 入第1个栈，变成倒序。
- 入第2个栈，倒序反过来，就变回原来的顺序。
