版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
防灾科技学院《数据结构》2025——2026学年第二学期期末试卷(B卷)课程名称:________________授课教师:________________
考试时间:120分钟满分:100分考试形式:闭卷□开卷□注意事项:所有答案一律写在答题纸上,写在试卷上无效。答题字迹清晰,不得使用涂改液、修正带。严禁携带手机、智能手表等电子设备进入考场。本试卷共_____页。一、单项选择题(每小题2分,共20分)1.下列关于数据结构基本概念的叙述中,正确的是()。A.数据元素是数据的最小单位B.数据的逻辑结构独立于其存储结构C.数据的存储结构是描述数据元素之间逻辑关系的结构D.栈和队列都是典型的非线性结构2.某算法中基本操作的重复执行次数为T(n)A.OB.OC.OD.O3.设入栈序列为1、2、3、4,四个元素依次入栈且可在入栈过程中随时出栈,则下列出栈序列中不可能得到的是()。A.1、2、3、4B.4、3、2、1C.1、3、2、4D.3、1、2、44.设循环队列的存储空间容量为m,队头指针为front,队尾指针为rear(rear指向队尾元素的后一个位置),采用牺牲一个存储单元的方法区分队空与队满,则队列为满的判定条件是()。A.rear==frontB.(rear+1)modm==frontC.front==0D.rear==m-15.已知一棵二叉树有20个叶子结点、10个度为1的结点,则该二叉树的结点总数为()。A.39B.40C.49D.506.由n个权值构造一棵哈夫曼树,则该哈夫曼树的结点总数为()。A.nB.nC.2D.27.具有n个顶点、e条边的无向图采用邻接表存储,则其邻接表中边结点的总数为()。A.nB.eC.2D.e8.下列排序方法中,其关键字比较次数与待排序序列的初始排列状态无关的是()。A.快速排序B.直接插入排序C.冒泡排序D.简单选择排序9.对有序表{2,5,8,11,15,19,23,27,31,36}进行折半查找(元素按升序排列,查找下标从1开始),查找元素27时依次与之比较的元素是()。A.15、27B.19、27C.15、23、27D.19、23、2710.采用链地址法处理冲突构造散列表,若某散列地址对应的单链表中已存入4个元素,则在等概率情况下查找该单链表中元素的平均比较次数为()。A.2B.2.5C.4D.5二、判断题(每小题1分,共10分。正确的打"√",错误的打"×")1.数据项是数据的最小单位,是数据中不可分割的最小组成部分。2.线性表采用链式存储结构时,可以实现对任一元素的随机访问。3.队列是一种操作受限的线性表,只允许在队头进行插入操作、在队尾进行删除操作。4.稀疏矩阵采用三元组表表示时,三元组表中元素的个数等于矩阵中非零元素的个数。5.深度为k的二叉树最多有2k−6.任何有向图的邻接矩阵都是不对称的。7.对同一张图进行遍历,采用邻接矩阵存储时遍历算法的时间复杂度为O(n2)8.拓扑排序只适用于有向无环图。9.平衡二叉树中任一结点的左、右子树高度之差的绝对值不超过1。10.快速排序在任何情况下的时间复杂度都是O(三、填空题(每小题2分,共20分)1.算法具有五个重要特性:有穷性、确定性、________、输入和输出。2.在长度为n的顺序表中删除第i(1≤3.设有元素a、b、c依次入栈(可在入栈过程中随时出栈),则可能得到的出栈序列共有________种。4.高度为h的完全二叉树最少有________个结点。5.已知一棵完全二叉树共有100个结点,则该二叉树的叶子结点个数为________。6.具有6个顶点的无向完全图共有________条边。7.对一棵二叉排序树进行________遍历,可以得到一个关键字递增有序的序列。8.散列表的装填因子α等于表中已存入的记录数与散列表长度之比,装填因子越________,发生冲突的可能性越大。9.对含有n个元素的无序序列建立初始大根堆,其时间复杂度为________。10.在长度为n的顺序表上进行顺序查找,等概率条件下查找成功的平均查找长度为________。四、简答题(每小题6分,共24分)1.什么是数据的逻辑结构?什么是数据的存储结构?二者有什么区别与联系?请写出四种基本的逻辑结构,并指出线性表常用的两种存储结构及其各自的主要特点。2.什么是队列的“假溢出”现象?循环队列是如何解决“假溢出”问题的?若采用“牺牲一个存储单元”的方法,应如何判定循环队列的“队空”与“队满”?3.什么是二叉排序树?简述在二叉排序树中查找关键字为key的结点的过程。从二叉排序树中删除一个结点时,通常分为哪三种情况?请分别简述相应的处理方法。4.简述图的深度优先搜索(DFS)与广度优先搜索(BFS)的基本思想,并分别说明这两种遍历算法各借助哪种辅助数据结构实现;当图采用邻接表存储时,写出两种遍历算法的时间复杂度。五、综合应用题(共26分)1.(8分)已知一组权值集合为{2,4,5,7,9,13},以这些权值作为叶结点权值构造哈夫曼树。(1)写出构造该哈夫曼树的逐步过程(依次说明每一步选取的两棵树的根结点权值及合并所得新结点的权值);(4分)(2)计算该哈夫曼树的带权路径长度WPL;(2分)(3)约定构造过程中每次合并时权值较小者作为左孩子,左分支标记为0、右分支标记为1,写出权值为13的叶结点的哈夫曼编码。(2分)2.(9分)已知一棵二叉树的先序遍历序列为A,B,D,E,C,F,G,中序遍历序列为D,B,E,A,C,G,F。(1)由上述两个序列唯一确定该二叉树,写出该二叉树的后序遍历序列,并给出简要推导过程;(6分)(2)用文字逐层描述该二叉树各结点之间的孩子关系,即说明根结点是谁,以及每个非叶结点的左孩子和右孩子分别是谁。(3分)3.(9分)设散列表长度为13(地址为0~12),散列函数为H依次将关键字序列{23,34,14,38,46,16,68,15,7,31,26}存入散列表,并采用线性探测再散列法处理冲突。(1)将各关键字填入下表对应的地址位置(未存入关键
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年保温袋行业洞察报告及未来五至十年发展趋势报告
- 2026年数字出版行业投资规划建议报告及未来五至十年存量博弈与增量突破
- 2026年滴滴talentq测试题及答案
- 为老年人进行口腔护理培训
- 2型糖尿病性远端对称性周围神经病的护理
- 驾驶证科目二场地驾驶技巧及模拟试题及答案
- 2026年北京市教师资格证科目二备考练习题及答案
- 建筑施工图识读与绘制技能考核模拟试卷及答案
- 航空器液压系统维修技能模拟试卷及答案
- 2026年心理移民心理测评题库及参考答案
- 农村污水处理工程施工组织设计
- 雨课堂学堂在线学堂云《信息检索与科技写作( 理大)》单元测试考核答案
- 概念验证中心运营细则
- 期末考试质量分析报告写作模板
- 银行绿色信贷宣传课件
- 大学版画教学课件
- 食品生物技术专业教学标准(高等职业教育专科)2025修订
- 住院患者沐浴管理制度
- T/CADBM 51-2021室内装饰用竹木纤维集成墙板应用技术规程
- 妊娠合并下肢静脉血栓护理
- PowerSurfacing-威力曲面-中文教程
评论
0/150
提交评论