[考研类试卷]计算机专业基础综合数据结构（图）历年真题试卷汇编7及答案与解析.doc

1、计算机专业基础综合数据结构（图）历年真题试卷汇编 7 及答案与解析一、填空题1 构造连通网最小生成树的两个典型算法是_。【北京科技大学 1998 一、5】2 求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树。【南京理工大学 2001 二、6(2 分)】【北京交通大学 2005 二、7(2 分)】3 Prim(普里姆)算法适用于求_的网的最小生成树； Kruskal(克鲁斯卡尔)算法适用于求_的网的最小生成树。【厦门大学 1999 一、4(204)】4 克鲁斯卡尔算法的时间复杂度为_，它对_图较为适合。【中科院计算所 1999 二、3(2 分)】5 下面描述的是一种构造最小生成树算法

2、的基本思想。设要处理的无向图包括 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)算法结束时，相邻矩阵中_的元素指出最小生成树的_。【山东工业大学 1998 二、4(6 分)】6 有一个用于 n 个顶点连通带权无向图的算

3、法描述如下：(1)设集合 T1 与 T2，初始均为空；(2)在连通图上任选一顶点加入 T1；(3)以下步骤重复 n 一 1 次：A. 在 i属于 T1，j 不属于 T1 的边中选最小权的边；B.该边加入 T2。上述算法完成后，T2中共有条边，该算法称 算法，T2 中的边构成图的。【南京理工大学 1999二、7(4 分) 】7 在有向图的邻接矩阵中，若主对角线以下的元素均为零，则该图的拓扑有序序列是_的。【电子科技大学 2005 二、3(1 分)】8 求从某源点到其余各顶点的 Dijkstra 算法在图的顶点数为 10，用邻接矩阵表示图时计算时间约为 10 ms，则在图的顶点数为 40 时，计算

4、时间约为_ms。【南京理工大学 2000 二、3(15 分)】9 求最短路径的 Dijkstra 算法的时间复杂度为_。【哈尔滨工业大学 2001一、5(2 分) 】10 有向图 G=(V，E),其中 V(G)=0，1，2，3，4，5，用三元组表示弧及弧上的权 d。E(G)为 E(G)= ， ， ，)，则从源点 0 到顶点 3 的最短路径长度是_，经过的中间顶点是_。【南京理工大学 1998 三、6(4 分)】11 在拓扑分类中，拓扑序列的最后一个顶点必定是_的顶点。【哈尔滨工业大学 2003 一、6(1 分)】12 设有向图有 n 个顶点和 e 条边，进行拓扑排序时，总的计算时间为_。 【西

5、安电子科技大学 1999 软件一、7(2 分)】【武汉大学 2000 一、7】13 AOV 网中，结点表示(1)，边表示(2) 。AOE 网中，结点表示 (3)，边表示(4)。【北京理工大学 2001 七、3(2 分)】14 在 AOV 网中，存在环意味着(1)，这是(2) 的；对程序的数据流图来说，它表明存在(3)。【厦门大学 1999 一、2(204) 】15 当一个 AOV 网用邻接表表示时，可按下列方法进行拓扑排序。(1)查邻接表中入度为_的顶点，并进栈；(2)若栈不空，则 输出栈顶元素 Vj，并退栈； 查 Vj 的直接后继 Vk，对 Vk 入度处理，处理方法是_，若入度为_，则 Vk

6、 进栈；(3)若栈空时，输出顶点数小于图的顶点数，说明有_，否则拓扑排序完成。【南京理工大学 1996 二、3(6 分)】二、判断题16 任何一个 AOE(Activy On Edge)网中至少有一条关键路径，且是从源点到汇点的最短的一条路径。( ) 【中国海洋大学 2005 二、5(1 分)】（A）正确（B）错误17 在 AOE 网络中，从源点到汇点具有最大长度的路径称为关键路径。完成 AOE所表示的整个工程所需的时间取决于关键路径长度。( )【吉林大学 2007 一、5(1分)】（A）正确（B）错误18 在 AOE 图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。( )【大

7、连海事大学 2001 一、15(1 分) 】（A）正确（B）错误19 在 AOE 图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。( )【大连海事大学 2001 一、16(1 分) 】（A）正确（B）错误20 当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。( )【上海交通大学 1998 一、14(1 分)】（A）正确（B）错误三、综合题20 某网络中的路由器运行 0SPF 路由协议，下表是路由器 R1 维护的主要链路状态信息(LSI)，下图是根据下表及 R1 的接口名构造出来的拓扑网络。请回答下列问题。21 本题中的网络可抽象为数据结构中的哪种逻辑结构?2

8、2 针对题 3 表中的内容，设计合理的链式存储结构，以保存题 3 表中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义，并画出对应题 3 表的链式存储结构示意图(示意图中可仅以 ID 标识结点)。23 按照迪杰斯特拉(Dijkstra) 算法的策略，依次给出 R1 到达题 3 图中子网1921xx 的最短路径及费用。【2014 年全国试题 42(10 分)】23 已知有 5 个顶点的图 G 如下图所示。 请回答下列问题：24 写出图 G 的邻接矩阵 A(行、列下标从 0 开始)。25 求 A2，矩阵 A2 中位于 0 行 3 列元素值的含义是什么?26 若已知具有 n(n2)个顶点

9、的邻接矩阵为 B，则 m(2mn)非零元素的含义是什么?【2015 年全国试题 42(10 分)】计算机专业基础综合数据结构（图）历年真题试卷汇编 7 答案与解析一、填空题1 【正确答案】 普里姆(Ptim)算法和克鲁斯卡尔(Kruskal)算法2 【正确答案】 克鲁斯卡尔3 【正确答案】 边稠密 边稀疏4 【正确答案】 O(eloge)边稀疏5 【正确答案】 (1)(ViVj) 边上的权值 都大得多的数 (2)1 负值 (3) 为负 边6 【正确答案】 n 一 1 普里姆 最小生成树7 【正确答案】 存在，可能不唯一8 【正确答案】 1609 【正确答案】 O(n 2)10 【正确答案】 5

10、0，11 【正确答案】 出度为 012 【正确答案】 O(n+e)13 【正确答案】 (1)活动 (2) 活动间的优先关系 (3) 事件 (4) 活动 边上的权代表活动持续时间14 【正确答案】 (1)某项活动以自己为先决条件 (2)荒谬 (3)死循环15 【正确答案】 (1)零 (2)Vk 入度减 1，零 (3)环二、判断题16 【正确答案】 B17 【正确答案】 A18 【正确答案】 B19 【正确答案】 A20 【正确答案】 B三、综合题21 【正确答案】 本题中的网络可抽象为数据结构中的图结构。22 【正确答案】 链式存储结构的数据类型定义如下： typedef struct(unsi

11、gned int ID； unsigned int IP；LinkNode；Link 的结构 typedef 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*next； HNode； 表头结点 链式存储结构的示意图如下：23 【正确答案】 R1 到达图中子网 1921.x-x 的最短路径及费用如下。24 【正确答案】 (1)邻接矩阵为25 【正确答案】 0 行 3 列的元素的含义是顶点 0 到顶点 3 的最短距离为 2。26 【正确答案】 B m 中非零元素的含义是：假设此顶点位于 i 行 j 列，如果 i=j，则表示 f 顶点到自己的距离为 0；如果 ij，第 i 行第 j 列非零值，结点 V(i)到结点V(j)长度为 m 的路的条数。