2023学年第一学期数据结构试题(A卷).docx

上传人:王** 文档编号:867733 上传时间:2024-02-08 格式:DOCX 页数:8 大小:196.10KB
下载 相关 举报
2023学年第一学期数据结构试题(A卷).docx_第1页
第1页 / 共8页
2023学年第一学期数据结构试题(A卷).docx_第2页
第2页 / 共8页
2023学年第一学期数据结构试题(A卷).docx_第3页
第3页 / 共8页
2023学年第一学期数据结构试题(A卷).docx_第4页
第4页 / 共8页
2023学年第一学期数据结构试题(A卷).docx_第5页
第5页 / 共8页
2023学年第一学期数据结构试题(A卷).docx_第6页
第6页 / 共8页
2023学年第一学期数据结构试题(A卷).docx_第7页
第7页 / 共8页
2023学年第一学期数据结构试题(A卷).docx_第8页
第8页 / 共8页
亲,该文档总共8页,全部预览完了,如果喜欢就下载吧!
资源描述

《2023学年第一学期数据结构试题(A卷).docx》由会员分享,可在线阅读,更多相关《2023学年第一学期数据结构试题(A卷).docx(8页珍藏版)》请在优知文库上搜索。

1、20232023学年第一学期数据构造期末考试试题考试时间100分钟考试方式闭卷笔试一、单项选择题:(每题2分,共40分)在每题给出的四个选项中,请选出一项最符合题目要求的。)两大类。B.挨次构造、链式构造D.根本构造、构造构造1 .从规律上可以把数据构造分为(A.动态构造、静态构造C.线性构造、非线性构造2 .以下术语中,()与数据的存储构造无关。A.栈B.哈希表 C.线索树D.双向链表3,下面的程序段的时间简单度为()。for(i=l;i=n;i+)for(j=l;j=n;j+)x=x+l;A.0(log2n)B.0(2n)C.0(n)D.0(112)4 .假设长度为n的线性表承受挨次存储构

2、造,在其第i(l:i=n+l)个位置插入一个元素的算法的时间简单度为()OA.0(0)B.0(l)C.0(n)D.0(n2)5 .为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑构造应当是()OA.栈B.队列C.树D.图6 .假设元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进展。但不允许连续三次进展退栈工作,则不行能得到的出栈序列是()。A.dcebfaB.cbdaefC.bcaefdD.afedcb7 .假设对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角

3、线上全部元素)依次存放于一维数组Bl.(n(n+l)2中,则在B中确定A矩阵中的元素aij(ij)的位置k的关系为()。A.i*(i-l)2+jB.j*(j-l)2+IC.i*(i+l)2+jD.j*(j+l)2+i8 .在一棵度为4的树T中,假设有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则数T的叶节点个数是(A.41B.82C.113I).1229 .给定二叉树以下图所示。设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。假设遍历后的结点序列为(3,L7,5,6,2,4),则其遍历方式是()。A. LRNB. NRLC. RLND. RNL

4、10 .将森林转换为对应的二叉树,假设在二叉树中,结点u是结点V的父结点的父结点,则在原来的森林中,u和V可能具有的关系是()。I.父子关系II.兄弟关系11Iu的父结点与V的父结点是兄弟关系A.只有IIB.I和11CJ和InD.I、II和HI11.以下编码中,(. (00, 01, 10, 11))不是前缀码。B. 0, 10,110, 111)C. (0, 1, 00, 11)D. (1, 01,000, 001)12 .在以下图所示的平衡二叉树中插入关键字48后得到一棵平衡二叉树,在平衡二叉树中,关键字37所在结点的左、右子结点保存的关键字分别是()。A. 13, 48B. 24, 48

5、C. 24, 53D. 24, 9013 .假设无向图G=(V.E)中含7个顶点,则保证图G在任何状况下都是连通的,则需要的边数最少是(.6B.15C.16D.2114.已知有向图G=(V,E),其中V=V,V2,V3,VV$,丫6,V7,E=,图G的拓扑序列是()。AV1,V3,V4,V6,V2,V5,V7B,V1,V3,V2,V6,V4,V5,V7c.V1,v3,v4,V5,V2,V6,V7D.V1,v2,V5,V3,V4,V6,V715.关键字序列(3, 5, 9, 18, 37, 66, 给定值与关键字比较的次数分别为(98, 102),用折半查找法查找66与67,需要将A.6, 7B

6、.2, 3)oC.2, 4D.3, 416 .以下表达中,不符合m阶B树定义要求的是(A.根结点最多有m棵子树C.各结点内关键字均升序或降序排列B.全部叶结点都在同一层上D.叶结点之间通过指针链接17 .对一组数据2, 12,第一趟 其次趟 第三趟(2, 12, 16, (2, 12, 5, (2, 5, 10,16,5,10,12,88,10,16,16,5, 10)88)88)88)进展排序,假设前三趟排序结果如下:则承受的排序方法可能是()。.起泡排序B.希尔排序C.归并排序D.基数排序18.以下关键字序列中,()是堆。. (75, 65,30, 15, 25, 45,20, 10)C.

7、 (75,45,65,10, 25,30,20,15)B. (75,65, 45, 10, 30, 25, 20, 15)D. (75,45, 65, 30,15,25, 20,10)19.对关键字序列(05, 46, 13, 55,94,17, 42)进展基数排序,一趟排序后的结果是(20.)oA. (05, 46, 13,C. (42, 13, 94,55,05,94,55,17, 42)46, 17)B. (05, 13, 17,D. (05, 13, 46,42,55,46, 55, 94)17, 42, 94)以下排序方法中, A.折半插入排序)B.是稳定的排序方法。直接选择排序 C

8、.希尔排序D.快速排序二、综合应用题:(13题各10分,4、5题各15分,共60分)01 .一棵二叉排序树的构造如以下图所示,9个结点的值分别为(1,2,3,4,5,6,7,8,9)。请在图中标出各结点的值。2 .设无向图G=(V,E),其中V=(l,2,3,4,5),E=(1,2,4),(2,5,5),(1,3,2),(2,4,4),(3,4,1),(4,5,3),(1,5,8),每条边由一个三元组表示,三元组中前两个元素为与该边关联的顶点,第三个元素为该边的权。请写出图G中从顶点1到其余各点的了短路径的求解过程。要求列出最短路径上的顶点,并计算路径长度。3 .设哈希表的地址范围为09,哈希

9、函数为:H(Key)=KeyMOD7,用线性探测法再散列法处理冲突,依据关键字序列(16,8,15,32,24,30)哈希造表,试答更以下问题:(1)画出哈希表的示意图;(2)假设查找关键字24,需要依次与哪些关键字进展比较?(3)假定每个关键字的查找概率相等,求查找成功时的平均查找长度。地址下标0123456789关键字4 .两个升序序列长度分别为m与n,分别存放在数组a与b中。编写将两个数组的元素归并成一个非递减的序列并存放到数组C中的算法。要求:(1)描述算法的根本设计思想;(2)描述算法的具体实现步骤;(3)依据设计思想和实现步骤,承受程序设计语言描述算法(使用C或C+或JAVA语言实

10、现),关键之处请给出简要注释。5 .用一个带有表头结点的循环链表表示队列,结点构造为IdaIlInkL假设该循环链表只设一个尾指针rear指向队尾元素结点(留意不设头指针)。编写相应的初始化队列、入队列和出队列算法。要求:(1)描述算法的根本设计思想;(2)描述算法的具体实现步骤;(3)依据设计思想和实现步骤,承受程序设计语言描述算法(使用C或C+或JAVA语言实现),关键之处请给出简要注释。20232023学年第一学期数据构造期末考试参考答案一、单项选择题:(每题2分,共40分)1. C 2. 3. D4. C 5. B 6. D 7. B 8. B 9. D 10. B11. C 12.

11、C13. A14. A 15. B 16.1)17. A 18. D 19. C 20. A二综合应用题:(13题各10分,4、5题各15分,共60分)。V5,则邻接矩阵为:1.842OO8:4OOOO452OOOO1OOOO41OO3185OO3ooJ2.假设顶点数组为VI,V2,V3,V4,从Vl点到各终点的距离值和最短路径的求解过程如下表:顶点i=li=2i=3i=4i=5VlOOOOOOOOOO无V24(VI,V2)4V1,V24V1,V2V32(VI,V3?V4OO3(VI,V3,V4)V58V1,V58V1,V56V1,V3,V4,V56V1,V3,V4,V5VjV3V4V2V5S

12、IV1,V3IV1,V3,V4V1,V2,V3,V4V1,V2,V3,V4,V5以Vl为起点到顶点V2最短路径长度为4,路径为V1,V2;以Vl为起点到顶点V3最短路径长度为2,路径为V1,V3;以VI为起点到顶点V4最短路径长度为3,路径为V1,V3,V4;以Vl为起点到顶点V5最短路径长度为6,路径为V1,V3,V4,V5。3. (1)哈希表的示意图:地址下标0123456789关键字81615322430(2)假设查找关键字24,需要依次与15,32,24等3个元素比较。(3)查找成功时的平均查找长度:ASL=(1+1+3+1+3+5)/6=73o4. (1)算法的根本设计思想:顺次比较

13、a,b两个数组的元素,将较小的一个存放到C数组中去,并取下一个元素;当一个数组搜寻到终点的时候,将另一个数组的剩余元素依次存放到C数组中。(2)算法的具体实现步骤:用i,j分别表示a,b数组的当前比较元素的下标,初值分别为0;用k表示结果数组c的待用单元的下标,初值为Oo 当im且jn时,比较ai与bj,比较小的元素存放的C数组中,且下标自加1,c数组下标自加1,重复; 当im时,将a数组的剩余元素依次存放到C数组中;当jn时,将b数组的剩余元素依次存放到C数组中。(3)算法的C语言描述:voidMerge(inta,intb,intc,intm,intn)/函数首部(inti,j,k;if( aibj)( else ck=bj+;for(i=0,j=0,k=0;im&jn;+k)当a,b中均有元素的时ck=ai+;ai存放到ck中,取a的下一个元素;bj存放到ck中,取b的下一个元素当b中没有元素时当a中没有元素时while(im)ck+=ai+:while(jn)ck+=bj+;5. (1)算法的根本设计思想:用尾指针标识的带头结点的循环链表表示队列,初始化即生成一个头结点,头结点的指针域指向自身,形成循环链表。入队列,给元素安排结点空间,并将结点插到链表

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 高等教育 > 习题/试题

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!