2023学年第一学期数据结构试题(A卷).docx
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的线性表承受挨次存储构造，在其第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以行序为主序方式将其下三角形的元素(包括主对角线上全部元素)依次存放于一维数组Bl.(n(n+l)2中，则在B中确定A矩阵中的元素aij(i<j)的位置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. RNL10 .将森林转换为对应的二叉树，假设在二叉树中，结点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, 48C. 24, 53D. 24, 9013 .假设无向图G=(V.E)中含7个顶点，则保证图G在任何状况下都是连通的，则需要的边数最少是(.6B.15C.16D.2114.已知有向图G=(V,E),其中V=V,V2,V3,VV$,丫6,V7,E=<VrV2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6，匕>,图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.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. (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.希尔排序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,哈希函数为：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语言实现)，关键之处请给出简要注释。5 .用一个带有表头结点的循环链表表示队列，结点构造为Ida'IlInkL假设该循环链表只设一个尾指针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. 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,V5VjV3V4V2V5SIV1,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)算法的根本设计思想：顺次比较a,b两个数组的元素，将较小的一个存放到C数组中去，并取下一个元素；当一个数组搜寻到终点的时候，将另一个数组的剩余元素依次存放到C数组中。(2)算法的具体实现步骤：用i,j分别表示a,b数组的当前比较元素的下标，初值分别为0；用k表示结果数组c的待用单元的下标，初值为Oo 当i<m且j<n时，比较ai与bj,比较小的元素存放的C数组中，且下标自加1,c数组下标自加1,重复； 当i<m时，将a数组的剩余元素依次存放到C数组中；当j<n时，将b数组的剩余元素依次存放到C数组中。(3)算法的C语言描述：voidMerge(inta,intb,intc,intm,intn)/函数首部(inti,j,k；if( ai<bj)( else ck=bj+；for(i=0,j=0,k=0；i<m&&j<n；+k)当a,b中均有元素的时ck=ai+;ai存放到ck中，取a的下一个元素;bj存放到ck中，取b的下一个元素当b中没有元素时当a中没有元素时while(i<m)ck÷+=ai+：while(j<n)ck+=bj+；5. (1)算法的根本设计思想：用尾指针标识的带头结点的循环链表表示队列，初始化即生成一个头结点，头结点的指针域指向自身，形成循环链表。入队列，给元素安排结点空间，并将结点插到链表
