1、图模拟试卷 3 及答案与解析一、单项选择题1 能在 O(1)时间内访问线性表的第 i 个元素的结构是( )。【电子科技大学 2011一、2(2 分) 】（A）顺序表（B）单链表（C）单向循环链表（D）双向链表2 下面关于线性表的叙述中，错误的是哪一个?( )【北方交通大学 2001 一、14(2分)】（A）线性表采用顺序存储，必须占用一片连续的存储单元（B）线性表采用顺序存储，便于进行插入和删除操作（C）线性表采用链接存储，不必占用一片连续的存储单元（D）线性表采用链接存储，便于插入和删除操作3 线性表是具有 n 个( ) 的有限序列(n0)。【清华大学 1998 一、4(2 分)】（A）表元
2、素（B）字符（C）数据元素（D）数据项（E）信息项4 单链表中，增加一个头结点的目的是( )。 【厦门大学 2003 一、1(2 分)】（A）使单链表至少有一个结点（B）标识表结点中首结点的位置（C）方便运算的实现（D）说明单链表是线性表的链式存储5 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用( ) 存储方式最节省时间。【哈尔滨工业大学 2001 二、1(2 分)】【烟台大学 2007 一、3(2 分) 】（A）顺序表（B）双链表（C）带头结点的双循环链表（D）单循环链表6 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 (
3、 ) 存储方式最节省运算时间。【南开大学 2000 一、3】【华中科技大学2007 一、6(2 分) 】（A）单链表（B）仅有头指针的单循环链表（C）双链表（D）仅有尾指针的单循环链表7 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。【电子科技大学 2013 一、3(2 分)】【江苏大学 2006 一、3(2 分)】（A）单链表（B）单循环链表（C）带尾指针的单循环链表（D）带头结点的双循环链表8 若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用存储结构算法的时间效率最高的是( )。 【北京理工大学 2006 五、5(1分)】（A）
4、单链表（B）给出表尾指针的单循环链表（C）双向链表（D）给出表尾指针的双向循环链表9 对于一个线性表既要求能够进行较快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用( )。 【哈尔滨工业大学 2005 二、2(1 分)】（A）顺序存储方式（B）链式存储方式（C）散列存储方式（D）以上均可以10 在线性表的下列存储结构中，读取元素花费时间最少的是( )。【电子科技大学 2005 一、10(1 分) 】【北京理工大学 2006 五、6(1 分)】（A）顺序表（B）单链表（C）双向链表（D）循环链表11 若线性表最常用的操作是存取第 I 个元素及其前驱和后继元素的值，为节省时间应采
5、用的存储方式( ) 。【北京理工大学 2004 一、3(1 分)】（A）单链表（B）双向链表（C）单循环链表（D）顺序表12 在链式存储结构中，数据之间的关系是通过( )体现的。【北京理工大学 2005一、3 (1 分) 】（A）数据在内存的相对位（B）指示数据元素的指针（C）数据的存储地址（D）指针13 静态链表中指针表示的是( )。 【中南大学 2003 二、2(1 分)】（A）下一元素的地址（B）内存储器的地址（C）下一元素在数组中的位置（D）左链或右链指向的元素的地址14 链表不具有的特点是( )。【电子科技大学 2012 一、3(2 分)】【福州大学 1998一、8(2 分) 】【
6、南京理工大学 2005 一、13(1 分) 】（A）插入、删除不需要移动元素（B）可随机访问任一元素（C）不必事先估计存储空间（D）所需空间与线性长度成正比15 在 n 个结点的线性表的数组实现中，算法的时间复杂性是 O(1)的操作是( )。【哈尔滨工业大学 2003 二、1(1 分)】（A）访问第 i 个结点(1in)和求第 i 个结点的直接前驱(2in)（B）在第 i 个结点后插入一个新结点(1in)（C）删除第 i 个结点(1fn)（D）以上都不对16 (1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第f 个元素的时间与 i 无关。(2)静态链表中能容纳的元素个数的
7、最大数在表定义时就确定了，以后不能增加。 (3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是( ) 。【南京理工大学 2000 一、3(15 分)】（A）(1)，(2)（B） (1)（C） (1)，(2)，(3)（D）(2)17 静态链表与动态链表相比，其缺点是( )。 【北京理工大学 2006 九、5(1 分)】（A）插入、删除时需移动较多数据（B）有可能浪费较多存储空间（C）不能随机存取（D）以上都不是18 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为( )(1in+1)。【北京航空航天大学：1999 一、1(2
8、 分)】（A）O(0)（B） O(1)（C） O(n)（D）O(n 2)19 若长度为 n 的线性表采用顺序存储结构，在其第 i(1in+1)个位置之前插入一个新元素的算法的移动结点的平均次数为( )。 【北京理工大学 2006 五、4(1 分)】（A）n（B） n2（C） (n 一 1)2 （D）(n+1) 220 从一个长度为 n 的顺序表中删除第 i 个元素(1in)时，需向前移动( )个元素。【暨南大学 2010 一、8(2 分)】【烟台大学 2007 一、2(2 分)】【青岛大学 2000 五、1(2 分)】（A）n-i（B） n-i+1（C） n-i-1（D）i二、综合题21 画出
9、下面带权图 G 的所有最小生成树。22 已知存在一个有向图 G，A 和 B 是 G 中的两个结点，试编写一个非递归算法求G 中从 A 到 B 的所有简单路径。假定该有向图使用邻接矩阵的方式存储。23 简述蹦 m 算法和 Kruakal 算法求最小生成树的算法思想，分析它们的时间复杂度及分别适用于什么样的网?23 如要在 n 个大学之间建设通信网络，只需要架设 n 一 1 条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。下左图是 8 个大学的连接型，其边的权值为可架设线路的长度，请回答：24 利用哪种算法，可得到最低经济代价为多少的通信网?25 在右下边的图上画出其连接
10、方式。 25 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“ 畅通工程 ”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接通过道路即可)，并要求增设的道路条数为最少，要解决这个问题，问：26 可用什么数据结构来表示城镇和道路；27 请用伪代码描述效率最高的解法。图模拟试卷 3 答案与解析一、单项选择题1 【正确答案】 A2 【正确答案】 B3 【正确答案】 C4 【正确答案】 C5 【正确答案】 A【试题解析】 顺序表的优点之一是随机存取，即时间复杂度为 O(1)，而插入和删除的时间复杂度都是 O(n)。但是对于在最后
11、插入结点和删除结点的时间复杂度都是 O(1)。6 【正确答案】 D【试题解析】 带有尾指针的单循环链表在最后插入结点和删除第一个元素的时间复杂度是 O(1)。带有头指针的单循环链表要在最后插入结点必须遍历整个链表。7 【正确答案】 D【试题解析】 带有尾指针的单循环链表删除尾结点时要遍历整个链表，时间复杂度是 O(n)。只有用带头结点的双循环链表完成要求的操作最节省时间，时间复杂度是 O(1)。8 【正确答案】 D9 【正确答案】 B【试题解析】 散列存储方式是集合的一种表示方法，元素之间没有“逻辑关系”。B 是正确选择。10 【正确答案】 A11 【正确答案】 D12 【正确答案】 D13
12、【正确答案】 C14 【正确答案】 B15 【正确答案】 A16 【正确答案】 B17 【正确答案】 B【试题解析】 静态链表首先要定义一个一维数组空间，每个数组元素有两个分量，一是数据元素的值，二是指针。指针指向下一个元素在数组中的位置(下标)，插入和删除时只需修改指针，不移动数据。不能随机存取。若定义数组太大，有可能浪费较多存储空间。18 【正确答案】 C19 【正确答案】 B20 【正确答案】 A二、综合题21 【正确答案】 最小生成树如下图所示： 【知识模块】 图22 【正确答案】 深度遍历图，查找简单路径。VN 为结点集合GNN 为邻接矩阵SN为一个辅助用的堆栈visitedN用来表
13、示某个结点是否被访问过，1 为是，0 为否pop(S)，Push(S，vi)分别代表出栈和入栈操作。getTop()用来获得栈顶元素，但不出栈printResuh(S)为打印出结果的操作 AN 为一个辅助用的堆栈，用来遍历图void showAllResuhs(int GNN，int VN ，int A，int B)int i，t；push(S，A)；visitedA=1；A 点标记为已访问for(i=0；i N；i+)if(GAi=0GA 儿 i=INFINITYvisitedi=1)continue；不可达或已被访问的结点则跳过if(i=B)push(S，B)；printResuh(S)；
14、pop(S)；continue；elsevisitedi=1；push(S，vi)；while(AiN)t=AgetTop(S)；if(GgetTop(S)t=0GgetTop(S)t=INFINITYvisitedi=1)不可达或已被访问的结点则跳过AgetTop(S)+；elseif(t=B) 找到通向 B 的简单路径push(S，B)；printResult(S)；pop(S)；AgetTop(S)+；else 继续遍历visitedt=1；push(S，Vt)；AgetTop(S)+；if(AgetTop(S)=N&getTop(S)!=i)getTop(S)的所有路径都遍历过了，退栈
15、AgetTop(S)=0；visitedgetTop(S)=0；pop(S)；AgetTop(S)+； end while end elseAi=0；pop(S)；visitedi=0； end for【知识模块】 图23 【正确答案】 (1)Prim 算法 设图 G=(V，E)，其生成树的顶点集合为 U。 1)v 0 放入 U。 2) 在所有 uU，vV 一 U 的边(u，v) E 中找一条最小权值的边，加入生成树。 3) 把 2)找到的边的 v 加入 U 集合。如果 U 集合已有 n 个元素，则结束，否则继续执行 2)。其算法的时间复杂度为 O(n2)，适合于稠密网。 (2)Kruskal
16、 算法 每次选择 n 一 1 条边，所使用的贪心准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加人已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。Kruskal 算法分 e 步，其中 e 是网络中边的数目。按耗费递增的顺序来考虑这 e 条边，每次考虑一条边。当考虑某条边时，若将其加人已选边的集合中会出现环路，则将其抛弃，否则，将它选入。其时间复杂度是 O(n2)，适合于稀疏网。【知识模块】 图【知识模块】 图24 【正确答案】 Prim 算法，26【知识模块】 图25 【正确答案】 【知识模块】 图【知识模块】 图26 【正确答案】 用图结构表示，其中顶点表示
17、城镇，顶点之间路径表示道路。【知识模块】 图27 【正确答案】 这个应该是特殊(道路权重为 1)的 Prim 算法。采用邻接表结构，顶点结构包括：known 表示时候已经加入， dist 表示到起点的道路条数，path 表示相连的城镇。算法如下：void unweight(Table T)Queue Q；Vertex V， W；Q=CreateQueue(NumVertex)；MakeEmpty(Q) ；Enqueue(S，Q)；s 表示起点，可为任一城镇while(!IsEmpty(Q)V=Dequeue(Q)；TVKnown=True；For each W adajcent to Vif(
18、TWDist=Infinity)TWdist=Tv dist+1；TWpath=v ；Enqueue(W，Q)Dispose Queue(Q)；dfstravrese(G，visit(int v)boolean VisitedMAX；initstack(S)；for(v=0；v=G maxvexnum ；v+)VisitedV=FLASE；for(v=0；v=G maxvexnum ；V+)if(Visitedv=FLASE)push(s，v)；DFS(G，v)；while(!Stackempty(S)pfinff(“d”，v)；DFS(G，w)Visitedw=TRUE；for(firstadjvex(G，w) ；w=0；W=nextadjvex(G，W)VisitedW=TRUE；【知识模块】 图
