1、计算机专业基础综合数据结构（图）历年真题试卷汇编 5及答案解析(总分：52.00，做题时间：90 分钟)一、填空题(总题数：15，分数：30.00)1.构造连通网最小生成树的两个典型算法是_。【北京科技大学 1998一、5】（分数：2.00）_2.求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树。【南京理工大学 2001二、6(2 分)】【北京交通大学 2005二、7(2 分)】（分数：2.00）_3.Prim(普里姆)算法适用于求_的网的最小生成树；Kruskal(克鲁斯卡尔)算法适用于求_的网的最小生成树。【厦门大学 1999一、4(204)】（分数：2.00）_4.克鲁斯卡尔
2、算法的时间复杂度为_，它对_图较为适合。【中科院计算所 1999二、3(2分)】（分数：2.00）_5.下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括 n个顶点V1，V2，Vn，用相邻矩阵 A表示，边的权全是正数。请在下列画线处填上正确叙述。(1)若(Vi，Vj)是边，则 A(i，j)的值等于_，若(Vi，Vj)不是边，则 A(i，j)的值是一个比任何边的权_，矩阵的对角线元素全为 0。(2)构造最小生成树过程中，若顶点 Vi已包括进生成树，就把相邻矩阵的对角线元素 A(i，i)置成_，若(Vi，Vj)已包括进生成树，就把矩阵元素 A(i，j)置成_。(3)算法结束时，相邻
3、矩阵中_的元素指出最小生成树的_。【山东工业大学 1998二、4(6 分)】（分数：2.00）_6.有一个用于 n个顶点连通带权无向图的算法描述如下：(1)设集合 T1与 T2，初始均为空；(2)在连通图上任选一顶点加入 T1；(3)以下步骤重复 n一 1次：A.在 i属于 T1，j 不属于 T1的边中选最小权的边；B.该边加入 T2。上述算法完成后，T2 中共有条边，该算法称算法，T2 中的边构成图的。【南京理工大学 1999二、7(4 分)】（分数：2.00）_7.在有向图的邻接矩阵中，若主对角线以下的元素均为零，则该图的拓扑有序序列是_的。【电子科技大学 2005二、3(1 分)】（分数
4、：2.00）_8.求从某源点到其余各顶点的 Dijkstra算法在图的顶点数为 10，用邻接矩阵表示图时计算时间约为 10 ms，则在图的顶点数为 40时，计算时间约为_ms。【南京理工大学 2000二、3(15 分)】（分数：2.00）_9.求最短路径的 Dijkstra算法的时间复杂度为_。【哈尔滨工业大学 2001一、5(2 分)】（分数：2.00）_10.有向图 G=(V，E),其中 V(G)=0，1，2，3，4，5，用三元组表示弧及弧上的权 d。E(G)为 E(G)=，)，则从源点 0到顶点 3的最短路径长度是_，经过的中间顶点是_。【南京理工大学 1998三、6(4 分)】（分数：
5、2.00）_11.在拓扑分类中，拓扑序列的最后一个顶点必定是_的顶点。【哈尔滨工业大学 2003一、6(1分)】（分数：2.00）_12.设有向图有 n个顶点和 e条边，进行拓扑排序时，总的计算时间为_。 【西安电子科技大学1999软件一、7(2 分)】【武汉大学 2000一、7】（分数：2.00）_13.AOV网中，结点表示(1)，边表示(2)。AOE 网中，结点表示(3)，边表示(4)。【北京理工大学 2001七、3(2分)】（分数：2.00）_14.在 AOV网中，存在环意味着(1)，这是(2)的；对程序的数据流图来说，它表明存在(3)。【厦门大学1999一、2(204)】（分数：2.0
6、0）_15.当一个 AOV网用邻接表表示时，可按下列方法进行拓扑排序。(1)查邻接表中入度为_的顶点，并进栈；(2)若栈不空，则输出栈顶元素 Vj，并退栈；查 Vj的直接后继 Vk，对 Vk入度处理，处理方法是_，若入度为_，则 Vk进栈；(3)若栈空时，输出顶点数小于图的顶点数，说明有_，否则拓扑排序完成。【南京理工大学 1996二、3(6 分)】（分数：2.00）_二、判断题(总题数：5，分数：10.00)16.任何一个 AOE(Activy On Edge)网中至少有一条关键路径，且是从源点到汇点的最短的一条路径。( )【中国海洋大学 2005二、5(1 分)】（分数：2.00）A.正确
7、B.错误17.在 AOE网络中，从源点到汇点具有最大长度的路径称为关键路径。完成 AOE所表示的整个工程所需的时间取决于关键路径长度。( )【吉林大学 2007一、5(1 分)】（分数：2.00）A.正确B.错误18.在 AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。( )【大连海事大学2001一、15(1 分)】（分数：2.00）A.正确B.错误19.在 AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。( )【大连海事大学 2001一、16(1 分)】（分数：2.00）A.正确B.错误20.当改变网上某一关键路径上任一关键活动后，必将产生不同
8、的关键路径。( )【上海交通大学 1998一、14(1分)】（分数：2.00）A.正确B.错误三、综合题(总题数：2，分数：12.00)某网络中的路由器运行 0SPF路由协议，下表是路由器 R1维护的主要链路状态信息(LSI)，下图是根据下表及 R1的接口名构造出来的拓扑网络。 请回答下列问题。 （分数：6.00）(1).本题中的网络可抽象为数据结构中的哪种逻辑结构?（分数：2.00）_(2).针对题 3表中的内容，设计合理的链式存储结构，以保存题 3表中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义，并画出对应题 3表的链式存储结构示意图(示意图中可仅以 ID标识结点)。（分数
9、：2.00）_(3).按照迪杰斯特拉(Dijkstra)算法的策略，依次给出 R1到达题 3图中子网 1921xx 的最短路径及费用。【2014 年全国试题 42(10分)】（分数：2.00）_已知有 5个顶点的图 G如下图所示。 （分数：6.00）(1).写出图 G的邻接矩阵 A(行、列下标从 0开始)。（分数：2.00）_(2).求 A 2 ，矩阵 A 2 中位于 0行 3列元素值的含义是什么?（分数：2.00）_(3).若已知具有 n(n2)个顶点的邻接矩阵为 B，则 m (2mn)非零元素的含义是什么?【2015 年全国试题 42(10分)】（分数：2.00）_计算机专业基础综合数据结
10、构（图）历年真题试卷汇编 5答案解析(总分：52.00，做题时间：90 分钟)一、填空题(总题数：15，分数：30.00)1.构造连通网最小生成树的两个典型算法是_。【北京科技大学 1998一、5】（分数：2.00）_正确答案：(正确答案：普里姆(Ptim)算法和克鲁斯卡尔(Kruskal)算法)解析：2.求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树。【南京理工大学 2001二、6(2 分)】【北京交通大学 2005二、7(2 分)】（分数：2.00）_正确答案：(正确答案：克鲁斯卡尔)解析：3.Prim(普里姆)算法适用于求_的网的最小生成树；Kruskal(克鲁斯卡尔)算法
11、适用于求_的网的最小生成树。【厦门大学 1999一、4(204)】（分数：2.00）_正确答案：(正确答案：边稠密 边稀疏)解析：4.克鲁斯卡尔算法的时间复杂度为_，它对_图较为适合。【中科院计算所 1999二、3(2分)】（分数：2.00）_正确答案：(正确答案：O(eloge)边稀疏)解析：5.下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括 n个顶点V1，V2，Vn，用相邻矩阵 A表示，边的权全是正数。请在下列画线处填上正确叙述。(1)若(Vi，Vj)是边，则 A(i，j)的值等于_，若(Vi，Vj)不是边，则 A(i，j)的值是一个比任何边的权_，矩阵的对角线元素全为
12、 0。(2)构造最小生成树过程中，若顶点 Vi已包括进生成树，就把相邻矩阵的对角线元素 A(i，i)置成_，若(Vi，Vj)已包括进生成树，就把矩阵元素 A(i，j)置成_。(3)算法结束时，相邻矩阵中_的元素指出最小生成树的_。【山东工业大学 1998二、4(6 分)】（分数：2.00）_正确答案：(正确答案：(1)(ViVj)边上的权值 都大得多的数 (2)1 负值 (3)为负 边)解析：6.有一个用于 n个顶点连通带权无向图的算法描述如下：(1)设集合 T1与 T2，初始均为空；(2)在连通图上任选一顶点加入 T1；(3)以下步骤重复 n一 1次：A.在 i属于 T1，j 不属于 T1的
13、边中选最小权的边；B.该边加入 T2。上述算法完成后，T2 中共有条边，该算法称算法，T2 中的边构成图的。【南京理工大学 1999二、7(4 分)】（分数：2.00）_正确答案：(正确答案：n 一 1 普里姆 最小生成树)解析：7.在有向图的邻接矩阵中，若主对角线以下的元素均为零，则该图的拓扑有序序列是_的。【电子科技大学 2005二、3(1 分)】（分数：2.00）_正确答案：(正确答案：存在，可能不唯一)解析：8.求从某源点到其余各顶点的 Dijkstra算法在图的顶点数为 10，用邻接矩阵表示图时计算时间约为 10 ms，则在图的顶点数为 40时，计算时间约为_ms。【南京理工大学 2
14、000二、3(15 分)】（分数：2.00）_正确答案：(正确答案：160)解析：9.求最短路径的 Dijkstra算法的时间复杂度为_。【哈尔滨工业大学 2001一、5(2 分)】（分数：2.00）_正确答案：(正确答案：O(n 2 )解析：10.有向图 G=(V，E),其中 V(G)=0，1，2，3，4，5，用三元组表示弧及弧上的权 d。E(G)为 E(G)=，)，则从源点 0到顶点 3的最短路径长度是_，经过的中间顶点是_。【南京理工大学 1998三、6(4 分)】（分数：2.00）_正确答案：(正确答案：50，)解析：11.在拓扑分类中，拓扑序列的最后一个顶点必定是_的顶点。【哈尔滨工
15、业大学 2003一、6(1分)】（分数：2.00）_正确答案：(正确答案：出度为 0)解析：12.设有向图有 n个顶点和 e条边，进行拓扑排序时，总的计算时间为_。 【西安电子科技大学1999软件一、7(2 分)】【武汉大学 2000一、7】（分数：2.00）_正确答案：(正确答案：O(n+e)解析：13.AOV网中，结点表示(1)，边表示(2)。AOE 网中，结点表示(3)，边表示(4)。【北京理工大学 2001七、3(2分)】（分数：2.00）_正确答案：(正确答案：(1)活动 (2)活动间的优先关系 (3)事件 (4)活动 边上的权代表活动持续时间)解析：14.在 AOV网中，存在环意味
16、着(1)，这是(2)的；对程序的数据流图来说，它表明存在(3)。【厦门大学1999一、2(204)】（分数：2.00）_正确答案：(正确答案：(1)某项活动以自己为先决条件 (2)荒谬 (3)死循环)解析：15.当一个 AOV网用邻接表表示时，可按下列方法进行拓扑排序。(1)查邻接表中入度为_的顶点，并进栈；(2)若栈不空，则输出栈顶元素 Vj，并退栈；查 Vj的直接后继 Vk，对 Vk入度处理，处理方法是_，若入度为_，则 Vk进栈；(3)若栈空时，输出顶点数小于图的顶点数，说明有_，否则拓扑排序完成。【南京理工大学 1996二、3(6 分)】（分数：2.00）_正确答案：(正确答案：(1)
17、零 (2)Vk 入度减 1，零 (3)环)解析：二、判断题(总题数：5，分数：10.00)16.任何一个 AOE(Activy On Edge)网中至少有一条关键路径，且是从源点到汇点的最短的一条路径。( )【中国海洋大学 2005二、5(1 分)】（分数：2.00）A.正确B.错误 解析：17.在 AOE网络中，从源点到汇点具有最大长度的路径称为关键路径。完成 AOE所表示的整个工程所需的时间取决于关键路径长度。( )【吉林大学 2007一、5(1 分)】（分数：2.00）A.正确 B.错误解析：18.在 AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。( )【大连海事
18、大学2001一、15(1 分)】（分数：2.00）A.正确B.错误 解析：19.在 AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。( )【大连海事大学 2001一、16(1 分)】（分数：2.00）A.正确 B.错误解析：20.当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。( )【上海交通大学 1998一、14(1分)】（分数：2.00）A.正确B.错误 解析：三、综合题(总题数：2，分数：12.00)某网络中的路由器运行 0SPF路由协议，下表是路由器 R1维护的主要链路状态信息(LSI)，下图是根据下表及 R1的接口名构造出来的拓扑网络。 请回
19、答下列问题。 （分数：6.00）(1).本题中的网络可抽象为数据结构中的哪种逻辑结构?（分数：2.00）_正确答案：(正确答案：本题中的网络可抽象为数据结构中的图结构。)解析：(2).针对题 3表中的内容，设计合理的链式存储结构，以保存题 3表中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义，并画出对应题 3表的链式存储结构示意图(示意图中可仅以 ID标识结点)。（分数：2.00）_正确答案：(正确答案：链式存储结构的数据类型定义如下： typedef struct(unsigned int ID；unsigned int IP；LinkNode；Link 的结构 typedef
20、 struct unsigned int Prefix；unsigned int Mark；LinkNode； Net 的结构 typedef struct Node int flag； flag=l 表示 Link；flag=2 表示 Net union(LinkNode Lnode；NetNode Nnode；LinkORNet； unsigned int Metric； struct Node*next； ArcNode； 弧结点 typedef struct HNode uns igned int RouterID； ArcNode*LN_1 ink； struct HNode*nex
21、t； HNode； 表头结点 链式存储结构的示意图如下： )解析：(3).按照迪杰斯特拉(Dijkstra)算法的策略，依次给出 R1到达题 3图中子网 1921xx 的最短路径及费用。【2014 年全国试题 42(10分)】（分数：2.00）_正确答案：(正确答案：R1 到达图中子网 1921.x-x 的最短路径及费用如下。 )解析：已知有 5个顶点的图 G如下图所示。 （分数：6.00）(1).写出图 G的邻接矩阵 A(行、列下标从 0开始)。（分数：2.00）_正确答案：(正确答案：(1)邻接矩阵为 )解析：(2).求 A 2 ，矩阵 A 2 中位于 0行 3列元素值的含义是什么?（分数：2.00）_正确答案：(正确答案： )解析：(3).若已知具有 n(n2)个顶点的邻接矩阵为 B，则 m (2mn)非零元素的含义是什么?【2015 年全国试题 42(10分)】（分数：2.00）_正确答案：(正确答案：B m 中非零元素的含义是：假设此顶点位于 i行 j列，如果 i=j，则表示 f顶点到自己的距离为 0；如果 ij，第 i行第 j列非零值，结点 V(i)到结点 V(j)长度为 m的路的条数。)解析：
