2-81
下列选项中，不是下图深度优先搜索序列的是：
(2分)
A.V1, V5, V4, V3, V2
B.V1, V3, V2, V5, V4
C.V1, V2, V5, V4, V3
D.V1, V2, V3, V4, V5
作者
DS课程组
单位
浙江大学
2-82
若某图的深度优先搜索序列是{V1, V4, V0, V3, V2}，则下列哪个图不可能对应该序列？
(2分)
A.
B.
C.
D.
作者
陈越
单位
浙江大学
2-83
若某图的深度优先搜索序列是{V2, V0, V4, V3, V1}，则下列哪个图不可能对应该序列？
(2分)
A.
B.
C.
D.
作者
陈越
单位
浙江大学
2-84
给定无向带权图如下，以下哪个是从顶点 a 出发深度优先搜索遍历该图的顶点序列（多个顶点可以选择时按字母序）？
(2分)
A.abecdfhg
B.abcdehgf
C.abcdefgh
D.abchgfde
作者
魏宝刚
单位
浙江大学
2-85
对下图从顶点C出发进行深度优先搜索，哪个是错误的搜索序列？
(2分)
A.CBADEFGH
B.CDABEHFG
C.CDAEHGFB
D.CBAEFGHD
作者
魏宝刚
单位
浙江大学
2-86
在图中自a点开始进行广度优先遍历算法可能得到的结果为：
(2分)
A.a, e, d, f, c, b
B.a, c, f, e, b, d
C.a, e, b, c, f, d
D.a, b, e, c, d, f
作者
DS课程组
单位
浙江大学
2-87
在图中自c点开始进行广度优先遍历算法可能得到的结果为：
(2分)
A.c,a,b,e,f,d
B.c,a,f,d,e,b
C.c,f,a,d,e,b
D.c,f,a,b,d,e
作者
DS课程组
单位
浙江大学
2-88
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是：(2分)
A.G肯定不是完全图
B.G中一定有回路
C.G一定不是连通图
D.G有2个连通分量
作者
DS课程组
单位
浙江大学
2-89
给定一有向图的邻接表如下。若从v1开始利用此邻接表做广度优先搜索得到的顶点序列为：{v1, v3, v2, v4, v5}，则该邻接表中顺序填空的结果应为：
(3分)
A.v2, v3, v4
B.v3, v2, v4
C.v3, v4, v2
D.v4, v3, v2
作者
DS课程组
单位
浙江大学
2-90
给定一有向图的邻接表如下。从顶点V1出发按广度优先搜索法进行遍历，则得到的一种顶点序列为：
(2分)
A.V1,V2,V3,V4,V5
B.V1,V2,V3,V5,V4
C.V1,V3,V2,V4,V5
D.V1,V4,V3,V5,V2
作者
DS课程组
单位
浙江大学
2-91
已知一个图的邻接矩阵如下，则从顶点V1出发按广度优先搜索法进行遍历，可能得到的一种顶点序列为：
(2分)
A.V1,V2,V3,V5,V4,V6
B.V1,V2,V4,V5,V6,V3
C.V1,V3,V5,V2,V4,V6
D.V1,V3,V5,V6,V4,V2
作者
DS课程组
单位
浙江大学
2-92
图的广度优先遍历类似于二叉树的：(1分)
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
作者
陈越
单位
浙江大学
2-93
图的广度优先遍历类似于二叉树的：(1分)
A.层次遍历
B.中序遍历
C.后序遍历
D.先序遍历
作者
陈越
单位
浙江大学
2-94
图的广度优先遍历类似于二叉树的：(1分)
A.先序遍历
B.中序遍历
C.层次遍历
D.后序遍历
作者
陈越
单位
浙江大学
2-95
以下算法的功能是（）。
void graph1( adjmatrix GA, int i, int n, int *visited) { int k, j; Queue q; cout<<i<<‘ ‘; visited[i]= 1; InitQueue( q); EnQueue (q, i); while ( !EmptyQueue(q) ) { k= OutQueue (q); for( j=0; j<n; j++) { if ( GA[k][j] != 0 && GA[k][j] != MaxValue && !visited[j] ) { cout<<j<<‘ ‘; visited[j] = 1; EnQueue (q, j); } } } }
(4分)
A.从顶点i出发进行深度优先遍历
B.从顶点i出发进行广度优先遍历
C.输出顶点i的各邻接点
D.输出从顶点i出发到各顶点的路径
作者
严冰
单位
浙江大学
2-96
对下图从顶点C出发进行广度优先搜索，哪个是正确的搜索序列？
(2分)
A.CBDAEFGH
B.CDABEHFG
C.CBAEHGFD
D.CBDAEHFG
作者
魏宝刚
单位
浙江大学
2-97
在一个有权无向图中，如果顶点b到顶点a的最短路径长度是10，顶点c与顶点b之间存在一条长度为3的边。那么下列说法中有几句是正确的？
- c与a的最短路径长度就是13
- c与a的最短路径长度就是7
- c与a的最短路径长度不超过13
- c与a的最短路径不小于7
(3分)
A.1句
B.2句
C.3句
D.4句
作者
DS课程组
单位
浙江大学
2-98
若要求在找到从S到其他顶点最短路的同时，还给出不同的最短路的条数，我们可以将Dijkstra算法略作修改，增加一个count[]数组：count[V]记录S到顶点V的最短路径有多少条。则count[V]应该被初始化为：(3分)
A.对所有顶点都有count[V]=1
B.对所有顶点都有count[V]=0
C.count[S]=1; 对于其他顶点V则令count[V]=0
D.count[S]=0; 对于其他顶点V则令count[V]=1
作者
DS课程组
单位
浙江大学
2-99
我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？(1分)
A.Dijkstra算法
B.Kruskal算法
C.深度优先搜索
D.拓扑排序算法
作者
DS课程组
单位
浙江大学
2-100
数据结构中Dijkstra算法用来解决哪个问题？(1分)
A.关键路径
B.最短路径
C.拓扑排序
D.字符串匹配
作者
DS课程组
单位
浙江大学
2-101
若要求在找到从S到其他顶点最短路的同时，还给出不同的最短路的条数，我们可以将Dijkstra算法略作修改，增加一个count[]数组：count[V]记录S到顶点V的最短路径有多少条。则count[V]应该被初始化为：(3分)
A.count[S]=1; 对于其他顶点V则令count[V]=0
B.count[S]=0; 对于其他顶点V则令count[V]=1
C.对所有顶点都有count[V]=1
D.对所有顶点都有count[V]=0
作者
DS课程组
单位
浙江大学
2-102
使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：
(2分)
A.5, 2, 3, 4, 6
B.5, 2, 3, 6, 4
C.5, 2, 4, 3, 6
D.5, 2, 6, 3, 4
作者
DS课程组
单位
浙江大学
2-103
使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：
(2分)
A.2, 5, 3, 4, 6, 7
B.2, 4, 3, 6, 5, 7
C.2, 3, 4, 5, 6, 7
D.5, 2, 6, 3, 4, 7
作者
陈越
单位
浙江大学
2-104
使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：
(2分)
A.6, 7, 5, 3, 2, 4
B.6, 2, 5, 7, 3, 4
C.2, 3, 4, 5, 6, 7
D.2, 4, 3, 6, 5, 7
作者
陈越
单位
浙江大学
2-105
试利用 Dijkstra 算法求下图中从顶点 A 到其他顶点的最短距离及对应的路径。下列那个序列给出了可能的顶点收集顺序？
(2分)
A.ACFEDBG
B.ACDBFEG
C.ACDGFBE
D.ABCDEFG
作者
魏宝刚
单位
浙江大学
2-106
试利用Floyed算法，求下图所示有向图的各对顶点之间的最短路径。下列选项哪个给出了正确的最短路径长度矩阵和最短路径矩阵？
(2分)
A.
B.
C.
D.
作者
魏宝刚
单位
浙江大学
2-107
任何一个带权无向连通图的最小生成树——(1分)
A.是唯一的
B.是不唯一的
C.有可能不唯一
D.有可能不存在
作者
DS课程组
单位
浙江大学
2-108
给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：
(2分)
A.10
B.11
C.12
D.14
作者
DS课程组
单位
浙江大学
2-109
给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：
(3分)
A.22
B.20
C.15
D.8
作者
陈越
单位
浙江大学
2-110
给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：
(3分)
A.20
B.22
C.8
D.15
作者
陈越
单位
浙江大学
2-111
给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：
(3分)
A.24
B.23
C.18
D.17
作者
陈越
单位
浙江大学
2-112
给定有权无向图如下。关于其最小生成树，下列哪句是对的？
(3分)
A.最小生成树不唯一，其总权重为23
B.最小生成树唯一，其总权重为20
C.边(B, F)一定在树中，树的总权重为23
D.边(H, G)一定在树中，树的总权重为20
作者
陈越
单位
浙江大学
2-113
给定有权无向图如下。关于其最小生成树，下列哪句是对的？
(3分)
A.边(B, A)一定在树中，树的总权重为23
B.边(D, C)一定在树中，树的总权重为20
C.最小生成树不唯一，其总权重为23
D.最小生成树唯一，其总权重为20
作者
陈越
单位
浙江大学
2-114
以下哪个不是给定无向带权图的最小生成树？
(2分)
A.
B.
C.
D.
作者
魏宝刚
单位
浙江大学
2-115
给出如下图所示的具有 7 个结点的网 G，采用Prim算法，从4号结点开始，给出该网的最小生成树。下列哪个选项给出了正确的树结点收集顺序？
(2分)
A.4501362
B.4526301
C.4561023
D.4563201
作者
魏宝刚
单位
浙江大学
2-116
已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是：
(2分)
A.(b,f), (b,d), (a,e), (c,e), (b,e)
B.(b,f), (b,d), (b,e), (a,e), (c,e)
C.(a,e), (b,e), (c,e), (b,d), (b,f)
D.(a,e), (c,e), (b,e), (b,f), (b,d)
作者
考研真题
单位
浙江大学
2-117
下列排序算法中，哪种算法可能出现：在最后一趟开始之前，所有的元素都不在其最终的位置上？（设待排元素个数N>2）(2分)
A.冒泡排序
B.插入排序
C.堆排序
D.快速排序
作者
DS课程组
单位
浙江大学
2-118
若数据元素序列{ 11，12，13，7，8，9，23，4，5 }是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是：(2分)
A.冒泡排序
B.选择排序
C.插入排序
D.归并排序
作者
DS课程组
单位
浙江大学
2-119
对一组数据{ 2，12，16，88，5，10 }进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88 则采用的排序方法可能是：(2分)
A.冒泡排序
B.希尔排序
C.归并排序
D.基数排序
作者
DS课程组
单位
浙江大学
2-120
就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是：(1分)
A.堆排序 < 归并排序 < 快速排序
B.堆排序 > 归并排序 > 快速排序
C.堆排序 < 快速排序 < 归并排序
D.堆排序 > 快速排序 > 归并排序
作者
DS课程组
单位
浙江大学
2-121
下面四种排序算法中，稳定的算法是：(1分)
A.堆排序
B.希尔排序
C.归并排序
D.快速排序
作者
DS课程组
单位
浙江大学
2-122
对于7个数进行冒泡排序，需要进行的比较次数为：(2分)
A.7
B.14
C.21
D.49
作者
DS课程组
单位
浙江大学
2-123
输入105个只有一位数字的整数，可以用O(N)复杂度将其排序的算法是：(1分)
A.快速排序
B.插入排序
C.希尔排序
D.基数排序
作者
DS课程组
单位
浙江大学
2-124
排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置的方法称为：(1分)
A.插入排序
B.选择排序
C.快速排序
D.归并排序
作者
DS课程组
单位
浙江大学
2-125
有组记录的排序码为{ 46，79，56，38，40，84 }，则利用堆排序的方法建立的初始堆为：(2分)
A.79，46，56，38，40，80
B.84，79，56，46，40，38
C.84，56，79，40，46，38
D.84，79，56，38，40，46
作者
DS课程组
单位
浙江大学
2-126{ 12，9，11，8，7，4，5，13，23 }是下列哪种方法第二趟排序后的结果？(2分)
A.归并排序
B.堆排序
C.插入排序
D.基数排序
作者
DS课程组
单位
浙江大学
2-127
对N个记录进行堆排序，需要的额外空间为：(1分)
A.O(1)
B.O(logN)
C.O(N)
D.O(NlogN)
作者
DS课程组
单位
浙江大学
2-128
若数据元素序列{ 19, 21, 7, 14, 5, 27, 1, 10 }是采用下列排序方法之一得到的第一趟排序后的结果，则该排序算法只能是：(2分)
A.快速排序
B.堆排序
C.归并排序
D.选择排序
作者
陈越
单位
浙江大学
2-129
将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下：
第1趟排序后：2, 12, 16, 10, 5, 34, 88
第2趟排序后：2, 5, 10, 12, 16, 34, 88
则可能的排序算法是：(2分)
A.冒泡排序
B.快速排序
C.归并排序
D.插入排序
作者
陈越
单位
浙江大学
2-130
将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下：
第1趟排序后：2, 12, 16, 10, 5, 34, 88
第2趟排序后：2, 5, 10, 12, 16, 34, 88
则可能的排序算法是：(2分)
A.冒泡排序
B.归并排序
C.快速排序
D.插入排序
作者
陈越
单位
浙江大学
