2026年武汉轻工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)_第1页
2026年武汉轻工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)_第2页
2026年武汉轻工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)_第3页
2026年武汉轻工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)_第4页
2026年武汉轻工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)_第5页
已阅读5页,还剩8页未读, 继续免费阅读

下载本文档

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

文档简介

2026年武汉轻工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)一、选择题1、设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为()。A.13B.33C.18D.402、已知广义表LS=((a,b,c),(d,e,f)),用head和tail数取出LS中原子e的运算是()。A.head(tail(LS))B.tail(head(LS))C.head(tail(head(tail(LS))))D.head(tail(tail(head(LS))))3、以下数据结构中,()是非线性数据结构。A.树B.字符串C.队D.栈4、在用邻接表表示图时,拓扑排序算法时间复杂度为()。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时,应执行()。A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中,每一趟排序结束时都至少能够确定一个元素最终位置的方法是()。Ⅰ.简单选择排序Ⅱ.希尔排序Ⅲ.快速排序Ⅳ.堆排Ⅴ.二路归并排序A.仅Ⅰ、Ⅲ、ⅣB.仅Ⅰ、Ⅱ、ⅢC.仅Ⅱ、Ⅲ、ⅣD.仅Ⅲ、Ⅳ、Ⅴ7、下列关于无向连通图特性的叙述中,正确的是()。Ⅰ.所有的顶点的度之和为偶数Ⅱ.边数大于顶点个数减1Ⅲ.至少有一个顶点的度为1A.只有ⅠB.只有ⅡC.Ⅰ和ⅡD.Ⅰ和Ⅲ8、有n(n>0)个分支结点的满二叉树的深度是()。A.n2-1B.log2(n+1)+1C.log2(n+1)D.log2(n-l)9、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历结果为()。A.CBEFDAB.FEDCBAC.CBEDFAD.不定10、在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是()。A.直接插入排序B.起泡排序C.简单选择排序D.快速排序二、填空题11、若用n表示图中顶点数目,则有______条边的无向图成为完全图。12、属于不稳定排序的有______。13、建立索引文件的目的是______。14、应用Prim算法求解连通网络的最小生成树问题。(1)针对如图所示的连通网络,试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(2)下面是Prim算法的实现,中间有5个地方缺失,请阅读程序后将它们补上。15、在基于关键字比较且时间为O(nlog2n)的排序中,若要求排序是稳定的,则可选用______排序;若要求就地排序(及辅助空间为O(1)),则可选用______排序。16、在顺序存储的二叉树中,编号为i和j的两个结点处在同一层的条件是______。17、设有一个10阶对称矩阵A采用压缩存储方式(以行为主序存储:a11=1),则a85的地址为______。18、当两个栈共享一存储区时,栈利用一维数组stack(1,n)表示,两栈顶指针为top[1]与top[2],则当栈1空时,top[1]为______,栈2空时,top[2]为______,栈满时为______。三、判断题19、倒排文件是对次关键字建立索引。()20、倒排序文件的优点是维护简单。()21、循环队列也存在空间溢出问题。()22、广义表(((a,b,c),d,e,f))的长度是4。()23、若从二叉树的任一结点出发,到根的路径上所经过的结点序列按其关键字有序,则该二叉树一定是哈夫曼树。()24、一般来说,若深度为k的n个结点的二叉树只有最小路径长度,那么从根结点到第k-1层具有的最多结点数为2k-1-1,余下的n-2k-1+1个结点在第k层的任一位置上。()25、在任何情况下,归并排序都比简单插入排序快。()26、归并排序辅助存储为O(1)。()27、采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找。()28、若一个有向图的邻接矩阵对角线以下元素均为零,则该图的拓扑有序序列必定存在。()四、简答题29、s是字符数组,s[0]中存放的是该字符串的有效长度,假设s[1..7]中字符串的内容为"abcabaa",说明下列程序的功能及执行结果。30、用一个数组S(设大小为MAX)作为两个堆栈的共享空间。请说明共享方法,栈满/栈空的判断条件,并用C语言或PASCAL语言设计公用的入栈操作push(i,x),其中i为0或1,用于表示栈号,x为入栈值。31、已知图的邻接矩阵为:当用邻接表作为图的存储结构,且邻接点都按序号从大到小排列时,试写出:(1)以顶点V1为出发点的唯一的深度优先遍历序列。当用邻接表作为图的存储结构,且邻接点都按序号从大到小排列时,试写出:(1)以顶点V1为出发点的唯一的深度优先遍历序列。(2)以顶点V1为出发点的唯一的广度优先遍历序列。(3)该图唯一的拓扑有序序列。五、算法设计题32、(1)试分别找出满足下列条件的所有二叉树:(a)前序序列和中序序列相同:(b)前序序列和后序序列相同;(c)中序序列和后序序列相同。(2)已知非空二叉树的结点结构为(lchild,data,rchild),设计算法:从右向左依次将所有叶子的数据值放到向量(假定向量的空间大于叶子的总个数)中。33、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。(1) 下面所示的序列中哪些是合法的?A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIO(2) 通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否则返回false(假定被判定的操作序列已存入一维数组中)。34、令G=(V,E)为一个有向无环图,编写一个给图G中每一个顶点赋以一个整数序号的算法,并满足以下条件:若从顶点i至顶点j有一条弧,则应使i<j。35、设有两个栈S1,S2都采用顺序栈方式,并且共享一个存储区[0..maxsize-1],为了尽量利用空间,减少溢出的可能,可采用栈顶相向,迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。

参考答案一、选择题1、【答案】B2、【答案】C3、【答案】A4、【答案】B5、【答案】D6、【答案】A7、【答案】A8、【答案】C9、【答案】A10、【答案】A二、填空题11、【答案】n(n-1)/212、【答案】希尔排序、简单选择排序、快速排序、堆排序等13、【答案】提高查找速度14、【答案】(1)(0,3,1);(3,5,4);(5,2,2);(3,1,5);(1,4,3)(2)①T[k];toVex=i②min=MaxInt;③mispos=i④exit(0)⑤T[i];fromVex=v【解析】Prim算法的执行类似于寻找图的最短路径的Dijkstra算法。假设N={V,E}是连通图,ET是N上最小生成树边的集合。算法从VT={u0},ET开始,重复执行下述操作:在所有u属于VT,v属于V-VT的边(u,v)属于E中找一条代价最小的边(u0,v0)加入集合ET,同时将v0并入VT,直到VT=V为止。15、【答案】归并;堆16、【答案】++a*b3*4-cd;18【解析】中缀式相当于中序遍历,前缀式相当于前序遍历,后缀式相当于后序遍历。17、【答案】3318、【答案】0;n+1;top[1]+1=top[2]三、判断题19、【答案】√20、【答案】×21、【答案】√22、【答案】×23、【答案】×24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答:本程序的功能是求字符串的nextval函数,程序执行结果是0110132。30、答:两栈共享一向量空间(一维数组),栈底设在数组的两端,两栈顶相邻时为栈满。设共享数组为S[MAX],则一个栈顶指针为一l,另一个栈顶指针为MAX时,栈为空。用C语言写的入栈操作push(i,x)如下:31、答:(1)V1,V4,V9,V10,V7,V6,V8,V3,V2,V5(2)V1,V4,V3,V2,V9,V7,V6,V5,V10,V8(3)V1,V2,V5,V3,V4,V6,V8,V7,V9,V10五、算法设计题32、答:(1)满足条件的二叉树如下:若前序序

温馨提示

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

评论

0/150

提交评论