一，单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）

1. 由4个没有区别的点构成的简单无向连通图的个数是(){{ select(1) }}

• 6
• 7
• 8
• 9

2. 如图所示,请问最少要删除这个图的多少条边才能使其不再是一个连通图{{ select(2) }}

• 1
• 2
• 3
• 4

3. 6个顶点的连通图最少有几条边{{ select(3) }}

• 4
• 5
• 6
• 7

4. 无向图中一个顶点的度是指图中{{ select(4) }}

• 与该顶点相邻接的顶点数
• 与该顶点联通的结点数
• 从该顶点出发的边数
• 以该顶点为目的地的边数

5. 设简单无向图G有16条边,且每个顶点的度数都是2,则G有()个顶点{{ select(5) }}

• 10
• 12
• 8
• 16

6. 在一个有向图中,所有顶点的度数之和等于所有边数的()倍{{ select(6) }}

• 0.5
• 2
• 1
• 4

7. 有向图中每个顶点的度数等于该顶点的{{ select(7) }}

• 入度
• 出度
• 入度和出度之和
• 入度和出度之差

8. 假设我们用d={a1,a2,a3,a4,a5},表示无向图G的5个顶点的度数，下面给出的哪个组合是合理的{{ select(8) }}

• {5,4,4,3,1}
• {4,2,2,1,1}
• {3,3,3,2,2}
• {5,4,3,2,1}

9. 无向完全图是指图中每对顶点之间恰好有一条边的简单图.已知无向完全图G有7个顶点,则他共有()条边{{ select(9) }}

• 7
• 21
• 42
• 49

10. 关于拓扑排序,下面说法正确的是{{ select(10) }}

• 所有联通有向图都可以实现拓扑排序
• 对于一个图而言,拓扑排序的结果是唯一的
• 拓扑排序中入度为0的结点总会排在入度大于0的结点的前面
• 拓扑排序结果序列中的第一个结点一定是入度为0的结点

11. 某大学计算机专业的必修课以及先修课的课程设计如下所示请你判断下列课程安排方案哪个是不合理的{{ select(11) }}

    

• 06712345
• 01234675
• 01672345
• 01675234

12. 在一个有向图G中,有7个结点1234567,有9条边,分别是(1,2),(1,3),(1,4),(2,5),(3,5),(3,6),(4,6),(5,7),(6,7),以下哪个有可能是G的拓扑排序序列{{ select(12) }}

• 1346257
• 1326457
• 1345267
• 1253467

13. 如图所示,以0为出发点进行深度优先遍历,遍历序列不可能是{{ select(13) }}

• 0123
• 0132
• 0213
• 0312

14. 在一个无向图G中,有6个结点abcdef,有7条边,分别是(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d),以下那个有可能是G的深度优先搜索序列{{ select(14) }}

• abecdf
• acfebd
• aebcfd
• aedfcb

15. 一个有n个顶点e条边的图采用邻接表储存,使用深度优先搜索对其遍历的时间复杂度为{{ select(15) }}

• O(n​^2​)
• O(e​^2​)
• O(n*e)
• O(n+e)

16. n个结点的完全有向图含有()条边{{ select(16) }}

• n*n
• n*(n+1)
• n*(n-1)
• n/2

17. 以下哪个结构可以用来储存图{{ select(17) }}

• 栈
• 二叉树
• 队列
• 邻接矩阵

18. G是一个非联通无向图(没有重边和自环),共有28条边,则G至少有几个顶点？{{ select(18) }}

• 8
• 9
• 10
• 11

19. 下面哪种图不一定是树{{ select(19) }}

• 没有环的连通图
• 有n个结点，n-1条边的连通图
• 每对结点之间都有路径的图
• 联通，但是删除任意一条边则不联通的图

20. 设G是具有n个结点,m条边的连通图,至少要删除G的()条边才能使得G变成一棵树{{ select(20) }}

• m-n+1
• m-n
• m+n+1
• n-m+1

21. 设G是有6个结点的完全图,最少要从G中删除()条边才能使G变成一棵树{{ select(21) }}

• 6
• 9
• 10
• 15

22. 一个有n个顶点和n条边的无重边无向图一定{{ select(22) }}

• 连通的
• 不连通的
• 无环的
• 有环的

23. 具有6个顶点的无向图，当有（）条边是能确保是一个连通图{{ select(23) }}

• 8
• 9
• 10
• 11

24. 已知无向图G含有16条边，其中度为4的顶点有3个，度为3的顶点有4个，其他顶点的度都小于3，请问图G最少含有几个顶点？{{ select(24) }}

• 10
• 11
• 13
• 15

25. 以下关于图的储存结构的说法中，正确的是{{ select(25) }}

• 一个图的邻接矩阵是唯一的，邻接表是不唯一的
• 一个图的邻接矩阵是唯一的，邻接表也是唯一的
• 一个图的邻接矩阵不唯一，邻接表是唯一的
• 一个图的邻接矩阵不唯一，邻接表也不唯一

26. 无向图G有n个顶点，e条边，它的邻接矩阵有几个0？{{ select(26) }}

• 2
• 2*e
• (n^2)-e
• (n^2)-2*e

27. 如果一个图的邻接矩阵的主对角线全都是0，其余位置全是1，则可以判断该图一定是{{ select(27) }}

• 无向图
• 有向图
• 完全图
• 无权图

28. 用邻接矩阵储存图G，要删除所有从第i个顶点出发的边，应该如何操作?{{ select(28) }}

• 将邻接矩阵的第i行删除
• 将邻接矩阵的第i行全部改写成0
• 将邻接矩阵的第i列删除
• 将邻接矩阵的第i列全部改写成0

29. 用邻接表储存图G，k在邻接表中出现的次数代表{{ select(29) }}

• 顶点k的度
• 顶点k的出度
• 顶点k的入度
• 与顶点k联通的点的个数

30. 如果从无向图的任意一个顶点出发进行一次深度优先搜索就可以访问所有顶点，则该图一定是{{ select(30) }}

• 完全图
• 连通图
• 有回路
• 一棵树