滇西应用技术大学《数据结构》2025-2026学年第二学期期末试卷B卷_第1页
滇西应用技术大学《数据结构》2025-2026学年第二学期期末试卷B卷_第2页
滇西应用技术大学《数据结构》2025-2026学年第二学期期末试卷B卷_第3页
滇西应用技术大学《数据结构》2025-2026学年第二学期期末试卷B卷_第4页
滇西应用技术大学《数据结构》2025-2026学年第二学期期末试卷B卷_第5页
已阅读5页,还剩4页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

滇西应用技术大学《数据结构》2025——2026学年第二学期期末试卷(B卷)专业__________________学号__________________姓名__________________题号一二三四五六七八九十成绩复核签字得分登分签字说明:本试卷共分;答题要求:按要求答题考生须知:1.姓名、学号、系、专业、年级、班级必须写在密封线内指定位置。2.答案必须用蓝、黑色钢笔或圆珠笔写在试卷上,字迹要清晰,卷面要整洁,写在草稿纸上的一律无效。第I卷(选择题)评卷人得分一、单项选择题(本大题共10小题,每小题2分,共20分)1.在数据结构中,与所使用的计算机及存储设备无关的是数据的()。A.存储结构B.物理结构C.逻辑结构D.运算的具体实现2.下列程序段的时间复杂度为()。i=1;

while(i<=n)

i=i2;A.O(B.O(C.O(D.O3.在长度为n的顺序表的第i(1≤i≤A.n−B.n−C.i−D.i4.循环队列用数组Q[0..m-1]存放,front指向队头元素,rear指向队尾元素的下一位置,牺牲一个存储单元来区分队空与队满,则队满的判定条件是()。A.front==rearB.(rear+1)%m==frontC.rear==m-1D.front==0&&rear==m-15.元素1、2、3、4依次进栈(进栈与出栈操作可交替进行),则不可能得到的出栈序列是()。A.1,2,3,4B.4,3,2,1C.3,1,4,2D.2,3,4,16.在带头结点的单链表中,p指向某结点,q指向p的后继结点,现要删除q所指结点并释放其空间,正确的操作语句是()。A.p->next=q->next;free(q);B.q->next=p->next;free(q);C.p=q->next;free(q);D.p->next=q;free(q);7.深度为k的二叉树至多含有的结点数为()。A.2kB.2kC.2kD.k8.具有n个顶点的无向完全图的边数为()。A.n(B.n(C.n(D.n9.对含有n个元素的有序顺序表进行折半查找,最坏情况下所需的比较次数为()。A.O(B.O(C.O(D.O10.下列排序算法中,平均时间复杂度为O(nlog2A.直接插入排序B.冒泡排序C.快速排序D.归并排序二、填空题(本大题共10小题,每小题2分,共20分)1.数据的逻辑结构通常分为集合、线性结构、树形结构和________四类。2.顺序表中每个元素占用d个存储单元,首元素a1的存储地址为Loc(a1),则第i个元素3.容量为50的循环队列(数组下标0~49),当前front=20、rear=15,则队列中实际元素的个数为________。4.一棵二叉树中有20个度为2的结点,则度为0的结点(叶子结点)个数为________。5.具有n个结点的二叉树采用二叉链表存储,该二叉链表中空指针域的总数为________。6.无向图G共有16条边,且每个顶点的度数均为4,则G的顶点数为________。7.对n个元素进行快速排序,当初始序列已经有序时,其时间复杂度退化为________。8.哈希函数为H(key)=k9.高度为5的平衡二叉树至少含有的结点数为________。10.具有n个顶点的连通无向图的生成树恰好含有________条边。三、判断题(本大题共10小题,每小题1分,共10分。正确的打"√",错误的打"×")1.数据元素是数据的基本单位,数据项是构成数据元素的不可分割的最小单位。()2.顺序表可以随机存取任意一个元素,而单链表只能顺序存取。()3.栈是一种先进先出(FIFO)的线性表。()4.在完全二叉树中,若某结点没有左孩子,则它必定是叶子结点。()5.哈夫曼树是带权路径长度最小的二叉树,且树中不存在度为1的结点。()6.有向图的邻接矩阵一定是对称矩阵。()7.具有n个顶点的连通无向图,其任何一棵生成树都恰好含有n−1条边。(8.对二叉排序树进行中序遍历,得到的序列一定是递增有序序列。()9.快速排序在任何初始排列下的时间复杂度都为O(nlog10.当待排序序列基本有序时,直接插入排序的时间复杂度接近O(n)四、简答题(本大题共3小题,每小题6分,共18分)1.简述线性表的顺序存储结构与链式存储结构各自的特点,并分别说明两种存储结构适合的应用场合。2.什么是顺序队列的“假溢出”现象?产生假溢出的原因是什么?通常采用什么方法解决该问题?3.简述二叉排序树的定义,并说明对二叉排序树进行中序遍历所得序列的特点以及这一特点对查找操作的意义。五、综合应用题(本大题共2小题,每小题8分,共16分)1.已知字符a、b、c、d、e的使用频率分别为2、3、5、7、11,以这些频率为权值构造哈夫曼树。要求:(1)写出哈夫曼树的构造过程,即依次列出每次合并两个最小权值后所得的权值集合;(4分)(2)约定左分支表示0、右分支表示1,给出一组满足哈夫曼编码规则的字符编码方案;(2分)(3)根据带权路径长度公式W计算该哈夫曼树的带权路径长度WPL,其中wi为第i个叶子结点的权值,li2.设哈希表的表长为11(地址依次为0~10),哈希函数为H依次将关键字序列25、39、6、72、45、87、51存入哈希表,采用线性探测再散列法处理冲突。要求:(1)将每个关键字填入下表中对应的地址单元(空单元留白即可);(5分)地址012345678910关键字(2)在等概率情况下,根据平均查找长度公式A计算查找成功时的平均查找长度ASL,其中Ci为查找第i六、算法设计题(本大题共2小题,每小题8分,共16分)1.已知一个带头结点的单链表L,结点结构由数据域data和指针域next构成。设计一个算法,将链表L就地逆置,即不另外申请新的结点空间,仅通过修改结点中的指针使原来的线性表变为逆序。要求:写出算法的基本思想、完整的C语言算法实现,并分析该算法的

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论