《2022年数据结构试题A文件 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构试题A文件 .pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、单项选择题（在每小题的4 个备选答案中，选出1 个正确的答案，并将其号码填在题干的括号内。每小题2 分，共 30 分）1 若某线性表中最常用的操作是取第I 个元素和找第I 个元素的前趋元素，则采用（）存储方式最节省时间。A)单链表B)双链表C)单向循环链表D)顺序表2串是任意有限个（）A)符号构成的序列B)符号构成的集合C)字符构成的序列D) 字符构成的集合3设矩阵A 的任一元素)10,1(jiaij满足：)10,1,(;0)10,1 ,(;0jijiajijiaijij现将 A 的所有非 0 元素以行序为主序存放在首地址为2000 的存储区域中， 每个元素占有 4 个单元，则元素A9,5
2、 的首地址为（） 。A)2340 B)2336 C)2164 D)2160 4如果以链表作为栈的存储结构，则退栈操作时（）A)必须判别栈是否满B)对栈不作任何判别C)必须判别栈是否空D) 判别栈元素的类型5设数组 Data0.m 作为循环队列SQ 的存储空间， front 为队头指针， rear 为队尾指针，则执行出队操作的语句为（）A)front=front+1 B)front=(front+1)%m C)rear=(rear+1)%mD)front=(front+1)%(m+1) 6深度为6（根的层次为1）的二叉树至多有（）结点。A)64 B)32 C)31 D)63 7将含 100 个结
3、点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。则编号为49 的结点 X 的双亲的编号为（） 。A)24 B)25 C)23 D) 无法确定8 设有一个无向图G=(V,E)和 G =(V ,E )， 如果 G;G 的生成树，则下面不正确的说法是（） 。A)G 为 G 的子图B) G 为 G 的连通分量C) G 为 G 的极小连通子图且V =V D) G 为G 的一个无环子图9下列序列中，( )是执行第一趟快速排序后得到的序列。(排序的关键字类型是字符串) A)da ，ax，eb，cd，bbffha ，gc B) ge，ax，eb，cd，bb ff da ，ha C
4、)cd，eb， ax，da ff ha ，gc，bb D) ax ，bb，cdda ff eb ，gc，ha 10二分查找要求被查找的表是( )。A) 键值有序的链接表B)链接表但键值不一定有序C)键值有序的顺序表D)顺序表但键值不一定有序11当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为( )。A)n2B)nlog2n c)log2n D)n-1 12堆是一个键值序列(k1，k2， kn)，对 i=1，2，/ 2n，满足 ( )。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -
5、- - - - 第 1 页，共 10 页 - - - - - - - - - A)ki k2ik2i+1B)kik2i+1next=NULL 。2在单链表中，指针p 所指结点为最后一个结点的条件是。3设一个链栈的栈顶指针是ls，栈中结点格式为，栈空的条件是_。如果栈不为空，则退栈操作为p=ls；free(p)。4已知一棵度为3 的树有 2 个度为 1 的结点， 3 个度为 2 的结点， 4 个度为 3 的结点， 则该树中有个叶子结点。5树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和。6n 个顶点的连通图的生成树有条边。7一个有向图G 中若有弧 、和，则在图 G 的拓扑序列中，顶点vi，
6、vj和 vk的相对位置为_ 。8设表中元素的初始状态是按键值递增的，分别用堆排序，快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序 )，_ 最省时间，_ 最费时间。9下面是将键值为x 的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。typedef struct node int key；struct node *left, *right ； void searchinsert( int x; pnode t) /* t 为二叉排序树根节点的指针*/ if （_ ） p= malloc(suze) ；p-key=x; p-left = NULL；p-right=NULL ；t=
7、p； else if(xkey) searchinsert (x, t-left) else _ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - 10.线性表的_ 主要有点是从表中任一结点出发能访问到所有结点。而使用_ ，可根据需要在前后两个方向上方便地进行查找。三、应用题（本题共28 分）1.树的后根遍历方法是：若树非空，则1）依次后根遍历根的各个子树T1，T2， Tm；2）访问根节点。对图1 所示的树，用后根遍历方法进行遍
8、历，请写出遍历所得到的结点访问序列。（4分）图 1 树2.将图 2 的森林转换成二叉树。 （ 4 分）图 2 森林3.图 3 表示一个地区的交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1 条公路， 画出所有可能的方案。（4 分）A B C D E F G H I J K A B C D E F G I J 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - -
9、 图 3 网4已知一个无向图的邻接表如图4 所示。图 4 邻连表1)画出这个图。2)以 v1 为出发点，对图进行广度优先搜索，写出所有可能的访问序列。(本题 4 分，每小题 2 分) 5设 n个元素的有序表为R，K 为一个给定的值，二分查找算法如下：int binswarth(sqlist R ；keytype K) L=1 ； h=n；suc=0；while(L=h) (!suc) mid=(L+h) 2；switch K=Rmid.key：suc=L；break；kRmid.key ：L=mid+1 if(suc) return(mid) else return(0) ； 将上述算法中划线
10、语句改为：Knext=s；2）r=s ；3）r-next=NULL 答案： r-next=s。2. 分析：单链表最后一个结点的指针域为空，所以可用p-next=NULL 作为判断最后一个结点的条件。3. 分析：当栈空时，栈顶指针为空，故判栈空条件为ls=NULL。栈非空时，退栈操作步骤为：1）p=ls ；2）ls=ls-link；3）free(p) 答案： ls=NULL，ls=ls-link。4. 分析：设 n1=2,n2=3,n3=4, 树的总结点数为n=n0+n1+n2+n3。 (1) 树的分支树为n-1=n1+2n2+n3。 (2) (2)-(1)：-1=n2+2n3-n0 名师资料总
11、结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - 有 n0=n2+2n3+1=3+24+1=12 答案： 12。5. 答案：双亲表示法。6. 分析： n 个顶点的连通图，其生成树有且仅有n-1 条边。答案： n-1 。7. 分析：按题意画出图5 所示示意图。 由此知，在拓扑序列中i,j,k的相对位置是i,j,k。图 5 有向图 G 的局部示意图答案： i,j,k。8. 分析：对冒泡排序来讲，由于哨兵的作用，经一趟排序后， 就能判断出当前无
12、序区已经自然有序，终止算法。故它最省时间。对快速排序来讲，由于待排序空间是有序的，每趟排序后， 中间元素的左边总是一个空区域，而右边区域长度仅比上一趟少1。因此当在最坏情况下，占用时间最长。答案：冒泡排序、快速排序。9. 答案： t=NULL,searchinsert(x,t-right)。10. 分析： 线性表的存储方式有多种，其中循环链表的主要优点是从表中任一结点出发，都能访问到所有其它的结点。而如果采用双向链表，则可以按前后两个方向进行查找。答案：循环链表、双向链表。三、应用题1. 答案： EBFGCKHIJDA 。2. 分析：先将每棵树转换成二叉树，然后再将各二叉树的根结点作为兄弟连接
13、在一起。而树转换成二叉树的方法是，先将兄弟结点连在一起，然后除最左边的孩子外，断开其它双亲到孩子的连线。答案：如图6 所示。i k j 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - （a）先将各树转换成二叉树（b）以结点为中心旋转45A B C D E F G I J A B C D E F G I J A B C D E F G I J 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -
14、- - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - （c）将各二叉树组合在一起图 6 森林转换成二叉树3. 分析： 本题实际上是求最小生成树问题。由于图中有两条权值为6 的边，故可以得到两种方案。答案：如图7 所示。图 7 由网络得到的最小生成树4. 答案：（1）如图 8 所示。图 8 图 4 所示邻接表所对应的图（2）v1v2v4v5v3和 v1v4v2v3v5。5分析：经过改动以后，有可能出现死循环，比如当查找的键值k 小于有序表中的最小键值时，就会出现死循环。答案： (1) 算法不能正常运行。(2) 假设有序
15、表的查找序列为(7 ，10， 12，16，24，39，42) ，当待查的键值为k=5 时，出现死循环。6答案： 25 84 2l 47 15 27 68 35 20 第一趟 20 15 21 25 47 27 68 35 84 2 5 3 1 4 18 18 11 11 6 6 5 5 16 16 2 4 3 6 1 5 2 4 3 6 1 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - 第二趟 15 20 21 25 3
16、5 27 47 68 84 第三趟 15 20 21 25 27 35 47 68 84 得到： 15 20 2l 25 27 35 47 68 84 第一趟排序过程中键值的移动情况如图9 所示。图 9 键值移动示意图四、设计题1分析：因为是求前根序列中处于第k 个位置的结点，所以本算法是按前根遍历来实现的。在这当中，访问根结点的操作就是计算器count 加 1，然后判断count 是否等于k，等于 k 就退出并返回指向对应结点的指针，否则继续按前根遍历往下查找。答案： Viod search(bitreptr t；integer k) if(t!=NULL) count+； if(count
17、=k)return(t)； else search(t-lchild, k)； search(t-rehild，k) ； 2分析：判断一个单链表是否递增，只要从起始结点开始，依次向后比较前一个结点的键值是否小于后一个结点的键值。答案：单链表L 的结构如图10 所示。图 10 单链表 L 的结构x 25 84 2l 47 15 27 68 35 20 a1a2anL 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - 参考答案：int isviset(lklist L) /1 分 p=L; /1 分while(p-next!=NULL) /1 分if(p-datanext-data) /1 分p=p-next; /1 分else return(0); /1 分return(1); /1 分 另：整个函数结构1 分。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -