1、计算机专业基础综合数据结构（图）历年真题试卷汇编 9及答案解析(总分：62.00，做题时间：90 分钟)一、单项选择题(总题数：20，分数：42.00)1.若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为( )。【中国科学技术大学 1997一、3(1 分)2004】（分数：2.00）A.对称矩阵B.稀疏矩阵C.三角矩阵D.一般矩阵2.采用邻接表存储的图的深度优先遍历算法类似于树的( )，而其广度优先遍历算法类似于树的( )。【北京交通大学 2007】（分数：2.00）A.中序遍B.先序遍历C.后序遍D.按层次遍历3.执行( )操作时，需要使用队列作辅助存储空间。【华中科技大学 2006一、
2、1(2 分)】（分数：2.00）A.查找哈希(Hash)表B.广度优先搜索图C.先序(根)遍历二叉树D.深度优先搜索图4.图的 BFS生成树的树高比：DFS 生成树的树高( )。【青岛大学 2004一、8(3 分)】（分数：2.00）A.小或相等B.小C.大或相等D.大5.无向图 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)，对该图进行深度优先遍历，得到的顶点序列正确的是( )。【南京理工大学 2001一、14(15分)】（分数：2.00）A.a，b，e，c，d,fB.a，c，f,e ，b，dC.a，e
3、，b，c,f,dD.a，e，d,f, c，b6.设图如下所示，在下面的 5个序列中，符合深度优先遍历的序列有多少? ( )。【南京理工大学 2000一、20(15 分)】 （分数：2.00）A.5个B.4个C.3个D.2个下图中给出由 7个顶点组成的无向图。从顶点 1出发，对它进行深度优先遍历得到的序列是()，而进行广度优先遍历得到的顶点序列是()。【中科院软件所 1999六、2(1)(2 分)】 （分数：4.00）A.1354267B.1347652C.1534276D.1247653E.以上答案均不正确A.1 534267B.1 726453C.1 354276D.1 247653E.以上
4、答案均不正确7.下面哪一方法可以判断出一个有向图是否有环(回路)?( )【东北大学 2000 42(4 分)】（分数：2.00）A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径8.判断有向图是否有回路，除了可以用拓扑排序外，还可以用( )。【南京理工大学 2004一、7(1 分)】（分数：2.00）A.求关键路径的方法B.广度优先遍历算法C.求最短路径的算法D.深度优先遍历算法9.在图采用邻接表存储时，求最小生成树的 Prim算法的时间复杂度为( )。【合肥工业大学 2001一、2(2分)】（分数：2.00）A.O(n)B.O(n+e)C.O(n 2 )D.O(n 2 )10.在求边稠
5、密的图的最小代价生成树时，采用( )算法较合适。【上海交通大学 2005四、7(2 分)】（分数：2.00）A.普里姆(Prim)B.克鲁斯卡尔(Kruskal)C.迪杰斯特拉(Dijkstra)D.其他11.在具有 n个顶点的图 G中，若最小生成树不唯一，则( )。【电子科技大学 2008一、2(1 分)】（分数：2.00）A.G的边数一定大于 n-1B.G的权值最小的边一定有多条C.G的最小生成树的代价不一定相等D.上述选项都不对12.(1)求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra)最短路径算法中弧上权不能为负的原因是在实际应用中无意义； (2)利用 Dijkztra求每一对
6、不同顶点之间的最短路径的算法时间是 O(n 3 )(图用邻接矩阵表示)； (3)Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正确的是( )。【南京理工大学 2000一、21(15 分)】（分数：2.00）A.(1)，(2)，(3)B.(1)C.(1)，(3)D.(2)，(3)13.当各边上的权值( )时，BFS 算法可用来解决单源最短路径问题。【中科院计算所 2000一、3(2 分)】（分数：2.00）A.均相等B.均互不相等C.不一定相等14.求解最短路径的 Floyd算法的时间复杂度为( )。【合肥工业大学 1999一、2(2 分)】【中南大学 20
7、05一、8(2 分)】（分数：2.00）A.O(n)B.O(n+e)C.O(n * n)D.O(n * n * n)15.已知有向图 G=(V,E)，其中 V=V 1 ，V 2 ，V 3 ，V 4 ，V 5 ，V 6 ，V 7 ，庐 1，V 2，1，V 3，1，V 4，2，V 5，3，V 5，3，V 6，4，V 6，5，V 7，6，V 7，G 的拓扑序列是( )。【北京航空航天大学 2000一、7(2 分)】（分数：2.00）A.V 1 ，V 3 ，V 4 ，V 6 ，V 2 ，V 5 ，V 7B.V 1 ，V 3 ，V 3 ，V 6 ，V 4 ，V 5 ，V 7C.V 1 ，V 3 ，V 4
8、 ，V 5 ，V 2 ，V 6 ，V 7D.V 1 ，V 2 ，V 5 ，V 3 ，V 4 ，V 6 ，V 716.若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )。【中科院计算所 1998二、6(2 分)】【中国科技大学 1998二、6(2 分)】（分数：2.00）A.存在B.不存在17.一个有向无环图的拓扑排序序列( )是唯一的。【北京邮电大学 2001一、3(2 分)】（分数：2.00）A.一定B.不一定18.在有向图 G的拓扑序列中，若顶点所在顶点 V j 之前，则下列情形不可能出现的是( )。【南京理工大学 2000一、9(15 分)】【江苏大学 200
9、6一、1(2 分)】（分数：2.00）A.G中有弧 jB.G中有一条从 V i 到 V j 的路径C.G中没有弧 i，V jD.G中有一条从 V j 到 V j 的路径19.在用邻接表表示图时，拓扑排序算法时间复杂度为( )。【合肥工业大学 2000一、2(2 分)】【南京理工大学 2001一、9(15 分)】【青岛大学 2002二、3(2 分)】（分数：2.00）A.O(n)B.D(n+e)C.O(n * n)D.D(n * n * n)二、判断题(总题数：10，分数：20.00)20.最小代价生成树是唯一的。( )【山东大学 2001一、5(1 分)】（分数：2.00）A.正确B.错误21
10、.一个网(带权图)都有唯一的最小生成树。( )【大连海事大学 2001一、14(1 分)】（分数：2.00）A.正确B.错误22.连通图上各边权值均不相同，则该图的最小生成树是唯一的。( )【哈尔滨工大 2000三、3(1 分)】【烟台大学 2007二、12(1 分)】【中国海大 2007二、10(1 分)】（分数：2.00）A.正确B.错误23.无向连通图的最小生成树是唯一的。( )【上海海事大学 2005一、7(2 分)】（分数：2.00）A.正确B.错误24.图的最小支撑树是唯一的。( ) 【吉林大学 2007一、6(1 分)】（分数：2.00）A.正确B.错误25.带权的连通无向图的最
11、小代价生成树是唯一的。( )【东南大学 2001一、5(1 分)】（分数：2.00）A.正确B.错误26.若连通图上各边的权值均不相同，则该图的最小生成树是唯一的。( )【同济大学 2004】（分数：2.00）A.正确B.错误27.在图 G的最小生成树 G1中，可能会有某条边的权值超过未选边的权值。( )【合肥工业大学 2000二、7(1分)】（分数：2.00）A.正确B.错误28.所谓赋权无向图 G的最小生成树 T，就是将 G中各结点间的最短路径作为边而构造出的 G的子图。( )【上海交通大学 1994一、5(2 分)】（分数：2.00）A.正确B.错误29.最小生成树的 Kruskal算法
12、是一种贪心法。( )【华南理工大学 2002一、6(1 分)】【烟台大学 2007二、10(1 分)】（分数：2.00）A.正确B.错误计算机专业基础综合数据结构（图）历年真题试卷汇编 9答案解析(总分：62.00，做题时间：90 分钟)一、单项选择题(总题数：20，分数：42.00)1.若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为( )。【中国科学技术大学 1997一、3(1 分)2004】（分数：2.00）A.对称矩阵B.稀疏矩阵C.三角矩阵D.一般矩阵 解析：解析：若是下三角矩阵，说明编号大的顶点是弧尾，编号小的顶点是弧头，不会出现编号小的顶点指向编号大的顶点的现象。上三角矩阵恰
13、恰相反。这两种情况说明该有向图可以拓扑排序，但是具有拓扑排序序列的有向图的邻接矩阵不一定是三角矩阵。有向无环图具有拓扑排序序列，其邻接矩阵没有明显特征。2.采用邻接表存储的图的深度优先遍历算法类似于树的( )，而其广度优先遍历算法类似于树的( )。【北京交通大学 2007】（分数：2.00）A.中序遍B.先序遍历 C.后序遍D.按层次遍历 解析：3.执行( )操作时，需要使用队列作辅助存储空间。【华中科技大学 2006一、1(2 分)】（分数：2.00）A.查找哈希(Hash)表B.广度优先搜索图 C.先序(根)遍历二叉树D.深度优先搜索图解析：4.图的 BFS生成树的树高比：DFS 生成树的
14、树高( )。【青岛大学 2004一、8(3 分)】（分数：2.00）A.小或相等 B.小C.大或相等D.大解析：5.无向图 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)，对该图进行深度优先遍历，得到的顶点序列正确的是( )。【南京理工大学 2001一、14(15分)】（分数：2.00）A.a，b，e，c，d,fB.a，c，f,e ，b，dC.a，e，b，c,f,dD.a，e，d,f, c，b 解析：6.设图如下所示，在下面的 5个序列中，符合深度优先遍历的序列有多少? ( )。【南京理工大学 2000一
15、、20(15 分)】 （分数：2.00）A.5个B.4个C.3个D.2个 解析：解析：第一个和第四个序列符合深度优先遍历。下图中给出由 7个顶点组成的无向图。从顶点 1出发，对它进行深度优先遍历得到的序列是()，而进行广度优先遍历得到的顶点序列是()。【中科院软件所 1999六、2(1)(2 分)】 （分数：4.00）A.1354267B.1347652C.1534276 D.1247653E.以上答案均不正确解析：A.1 534267B.1 726453C.1 354276 D.1 247653E.以上答案均不正确解析：7.下面哪一方法可以判断出一个有向图是否有环(回路)?( )【东北大学
16、2000 42(4 分)】（分数：2.00）A.深度优先遍历 B.拓扑排序 C.求最短路径D.求关键路径解析：8.判断有向图是否有回路，除了可以用拓扑排序外，还可以用( )。【南京理工大学 2004一、7(1 分)】（分数：2.00）A.求关键路径的方法B.广度优先遍历算法C.求最短路径的算法D.深度优先遍历算法 解析：9.在图采用邻接表存储时，求最小生成树的 Prim算法的时间复杂度为( )。【合肥工业大学 2001一、2(2分)】（分数：2.00）A.O(n)B.O(n+e) C.O(n 2 )D.O(n 2 )解析：10.在求边稠密的图的最小代价生成树时，采用( )算法较合适。【上海交通
17、大学 2005四、7(2 分)】（分数：2.00）A.普里姆(Prim) B.克鲁斯卡尔(Kruskal)C.迪杰斯特拉(Dijkstra)D.其他解析：11.在具有 n个顶点的图 G中，若最小生成树不唯一，则( )。【电子科技大学 2008一、2(1 分)】（分数：2.00）A.G的边数一定大于 n-1 B.G的权值最小的边一定有多条C.G的最小生成树的代价不一定相等D.上述选项都不对解析：解析：生成树有 n个顶点和 n1条边。最小生成树是权值之和最小的那棵生成树。若最小生成树不唯一，一定是有权值相等的边，但未必是权值最小的边相等。最小生成树的代价一定相等。当然，G 的边数一定大于 n1，否
18、则，就只有一棵生成树了。12.(1)求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra)最短路径算法中弧上权不能为负的原因是在实际应用中无意义； (2)利用 Dijkztra求每一对不同顶点之间的最短路径的算法时间是 O(n 3 )(图用邻接矩阵表示)； (3)Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正确的是( )。【南京理工大学 2000一、21(15 分)】（分数：2.00）A.(1)，(2)，(3)B.(1)C.(1)，(3) D.(2)，(3)解析：13.当各边上的权值( )时，BFS 算法可用来解决单源最短路径问题。【中科院计算所 20
19、00一、3(2 分)】（分数：2.00）A.均相等 B.均互不相等C.不一定相等解析：14.求解最短路径的 Floyd算法的时间复杂度为( )。【合肥工业大学 1999一、2(2 分)】【中南大学 2005一、8(2 分)】（分数：2.00）A.O(n)B.O(n+e)C.O(n * n)D.O(n * n * n) 解析：15.已知有向图 G=(V,E)，其中 V=V 1 ，V 2 ，V 3 ，V 4 ，V 5 ，V 6 ，V 7 ，庐 1，V 2，1，V 3，1，V 4，2，V 5，3，V 5，3，V 6，4，V 6，5，V 7，6，V 7，G 的拓扑序列是( )。【北京航空航天大学 20
20、00一、7(2 分)】（分数：2.00）A.V 1 ，V 3 ，V 4 ，V 6 ，V 2 ，V 5 ，V 7 B.V 1 ，V 3 ，V 3 ，V 6 ，V 4 ，V 5 ，V 7C.V 1 ，V 3 ，V 4 ，V 5 ，V 2 ，V 6 ，V 7D.V 1 ，V 2 ，V 5 ，V 3 ，V 4 ，V 6 ，V 7解析：16.若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )。【中科院计算所 1998二、6(2 分)】【中国科技大学 1998二、6(2 分)】（分数：2.00）A.存在 B.不存在解析：17.一个有向无环图的拓扑排序序列( )是唯一的。【北京邮
21、电大学 2001一、3(2 分)】（分数：2.00）A.一定B.不一定 解析：18.在有向图 G的拓扑序列中，若顶点所在顶点 V j 之前，则下列情形不可能出现的是( )。【南京理工大学 2000一、9(15 分)】【江苏大学 2006一、1(2 分)】（分数：2.00）A.G中有弧 jB.G中有一条从 V i 到 V j 的路径C.G中没有弧 i，V jD.G中有一条从 V j 到 V j 的路径 解析：解析：若有向图 G的拓扑序列中，顶点 Vi在顶点 Vj之前，不可能出现有一条从 Vj到 Vi的路径。因为若是有这样一条路径，说明图中存在回路，不可能拓扑排序成功。A、B 和 C都可能存在，即
22、本题选择 D。19.在用邻接表表示图时，拓扑排序算法时间复杂度为( )。【合肥工业大学 2000一、2(2 分)】【南京理工大学 2001一、9(15 分)】【青岛大学 2002二、3(2 分)】（分数：2.00）A.O(n)B.D(n+e) C.O(n * n)D.D(n * n * n)解析：二、判断题(总题数：10，分数：20.00)20.最小代价生成树是唯一的。( )【山东大学 2001一、5(1 分)】（分数：2.00）A.正确B.错误 解析：21.一个网(带权图)都有唯一的最小生成树。( )【大连海事大学 2001一、14(1 分)】（分数：2.00）A.正确B.错误 解析：22.
23、连通图上各边权值均不相同，则该图的最小生成树是唯一的。( )【哈尔滨工大 2000三、3(1 分)】【烟台大学 2007二、12(1 分)】【中国海大 2007二、10(1 分)】（分数：2.00）A.正确 B.错误解析：23.无向连通图的最小生成树是唯一的。( )【上海海事大学 2005一、7(2 分)】（分数：2.00）A.正确B.错误 解析：24.图的最小支撑树是唯一的。( ) 【吉林大学 2007一、6(1 分)】（分数：2.00）A.正确B.错误 解析：25.带权的连通无向图的最小代价生成树是唯一的。( )【东南大学 2001一、5(1 分)】（分数：2.00）A.正确B.错误 解析
24、：26.若连通图上各边的权值均不相同，则该图的最小生成树是唯一的。( )【同济大学 2004】（分数：2.00）A.正确 B.错误解析：27.在图 G的最小生成树 G1中，可能会有某条边的权值超过未选边的权值。( )【合肥工业大学 2000二、7(1分)】（分数：2.00）A.正确 B.错误解析：28.所谓赋权无向图 G的最小生成树 T，就是将 G中各结点间的最短路径作为边而构造出的 G的子图。( )【上海交通大学 1994一、5(2 分)】（分数：2.00）A.正确B.错误 解析：29.最小生成树的 Kruskal算法是一种贪心法。( )【华南理工大学 2002一、6(1 分)】【烟台大学 2007二、10(1 分)】（分数：2.00）A.正确 B.错误解析：
