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

下载本文档

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

文档简介

山东科技大学《数据结构》2025——2026学年第二学期期末试卷(B卷)院(系)_______班级_______学号_______姓名_______题号一二三四五六七总分得分一、单项选择题(本大题共15小题,每小题2分,共30分。在每小题给出的A、B、C、D四个选项中,只有一项符合题目要求,请将所选答案的字母填入题后括号内。)1.在数据结构中,与所使用的计算机无关的是数据的()。A.逻辑结构B.存储结构C.物理结构D.运算的具体实现方式2.在单链表中,指针p指向结点A,指针s指向结点B。若要在结点A之后插入结点B,则正确的操作序列是()。A.s->next=p->next;p->next=s;B.p->next=s;s->next=p->next;C.s->next=p;p->next=s;D.p->next=s;s->next=p;3.设栈S和队列Q的初始状态均为空,元素a、b、c、d、e、f依次通过栈S,每个元素出栈后立即进入队列Q。若出队的顺序为b、d、c、f、e、a,则栈S的容量至少应为()。A.2B.3C.4D.54.循环队列采用数组Q[0..m-1]存放(m为数组长度),front指向队头元素,rear指向队尾元素的下一位置,则队列满的判定条件是()。A.front==rearB.(rear+1)%m==frontC.rear==m-1D.front==0且rear==m-15.已知串S="datastructure"(长度为13),则S的子串总数目(含空串)为()。A.78B.91C.92D.1696.稀疏矩阵常用的两种压缩存储方法是()。A.三元组顺序表和十字链表B.行优先二维数组和列优先二维数组C.邻接矩阵和邻接表D.静态链表和动态链表7.某二叉树共有21个结点,其中度为1的结点有6个,则度为2的结点数为()。A.6B.7C.8D.98.具有n个结点的完全二叉树的深度为()。A.⌊B.⌊C.⌈D.⌈9.无向图G共有16条边,且每个顶点的度数均为4,则图G的顶点数为()。A.6B.7C.8D.1010.已知某二叉树的先序遍历序列为ABDECF,中序遍历序列为DBEAFC,则该二叉树的后序遍历序列为()。A.DEBFCAB.DEBCFAC.DBEFCAD.ADEFBC11.对表长为15的有序表进行二分查找,查找成功时最多需要的比较次数为()。A.3B.4C.5D.1512.对初始序列{45,26,78,12,65,38}进行快速排序,以第一个元素45为基准进行一趟划分后得到的序列为()。A.{38,26,12,45,65,78}B.{12,26,38,45,78,65}C.{26,12,38,45,65,78}D.{38,26,12,45,78,65}13.下列排序算法中,排序过程中关键字的比较次数与初始序列的排列状态无关的是()。A.直接插入排序B.冒泡排序C.快速排序D.简单选择排序14.在含有n个关键字的小根堆(最小堆)中,关键字最小的记录()。A.一定位于堆顶B.位于堆顶或堆的最后一层C.可以位于堆中的任意位置D.一定是叶子结点15.对有向图进行拓扑排序时,若输出部分顶点后不存在入度为0的顶点且仍有顶点未输出,则说明()。A.该图一定是强连通图B.该图一定是完全图C.该图中存在回路D.该图中所有顶点的度数均为偶数二、判断题(本大题共10小题,每小题1分,共10分。正确的在括号内画"√",错误的画"×"。)1.数据的逻辑结构独立于数据的存储结构,是数据元素之间逻辑关系的描述。()2.在长度为n的顺序表中按序号访问任意一个元素的时间复杂度为O(1),而在单链表中相应操作的时间复杂度为O(n)。()3.空串与空格串是相同的概念。()4.循环队列采用牺牲一个存储单元的方法区分队空与队满时,若数组长度为m,则队列中最多能存储m个元素。()5.完全二叉树中,若某结点没有左孩子,则它一定是叶子结点。()6.哈夫曼树是带权路径长度最小的二叉树,且权值越大的结点离根越近。()7.无向图的邻接矩阵一定是对称矩阵。()8.具有n个顶点的强连通有向图,其弧数至少为n。()9.任何一个AOV网的拓扑排序序列一定是唯一的。()10.快速排序在初始序列基本有序(正序)时排序性能最差。()三、填空题(本大题共10小题,每空2分,共20分。请将正确答案填写在横线上。)1.数据的逻辑结构通常分为集合、线性结构、树形结构与________四大类。2.在长度为n的顺序表的第i(1≤3.设二维数组A[0..8][0..9]按行优先方式存储,每个元素占4个存储单元,若LOC4.高度为5的完全二叉树至少有________个结点。5.具有n个顶点的无向完全图共有________条边。6.具有n个叶子结点的哈夫曼树共有________个结点。7.使用Dijkstra算法求单源最短路径时,要求图中边的权值不能为________。8.在有序表{2,5,8,12,16,23,38,45,56,70,88}中二分查找关键字12,依次与之比较的元素为________。9.快速排序的平均时间复杂度为________。10.对含有n个元素的序列建立初始堆的时间复杂度为________。四、简答题(本大题共4小题,每小题5分,共20分。)1.简述栈和队列这两种操作受限的线性表各自的运算特性,并各举出一个实际应用例子。2.简述线性表的顺序存储结构与链式存储结构各自的优点和缺点,并说明它们各自适用的场合。3.什么是哈希(散列)查找?简述线性探测再散列法与链地址法处理冲突的基本思想,并指出线性探测再散列法的主要缺点。4.什么是稳定的排序?分别举出一个稳定的排序算法和一个不稳定的排序算法;写出快速排序在平均情况和最坏情况下的时间复杂度,并说明最坏情况发生的条件。五、综合应用题(本大题共2小题,每小题10分,共20分。要求写出必要的分析过程和计算步骤。)1.已知某通信系统中使用6个字符,各字符的使用频率如下表所示:字符abcdef使用频率512820315以使用频率为权值构造哈夫曼树,并回答下列问题:(1)写出构造哈夫曼树的合并过程,即每次从当前森林中选取的两个最小权值及合并后得到的新权值(共需5次合并,权值相同时任选其一);(2)利用公式WPL=i=16w(3)规定哈夫曼树左分支表示0、右分支表示1,给出每个字符的哈夫曼编码。2.设

温馨提示

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

评论

0/150

提交评论