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