《鲁东大学数据结构期末试卷2023.docx》由会员分享,可在线阅读,更多相关《鲁东大学数据结构期末试卷2023.docx(12页珍藏版)》请在优知文库上搜索。
1、2023年鲁东大学软件工程专业数据结构与算法科目期末试卷A(有答案)一、选择题1、若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是()。A.快速排序B.堆排序C.归并排序D.直接插入排序2、下列说法不正确的是()。A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种:深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程3、计算机算法指的是解决问题的步骤序列,它必须具备()三个特性。A.可执行性、可移植性、可扩充性B,可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、动态存储管
2、理系统中,通常可有()种不同的分配策略。A.lB.2C3D.45、已知串S=aaab,其next数组值为()。A.0123B.1123C.1231D.12116、下列关于无向连通图特性的叙述中,正确的是(constintMaxIntINT-MAX;constintn三6;tyedefintAdjMatrix(n)(n;typedefstructintfromVex,toVex;intweight;TreeEdgeNode;typedefTreeEdgeNodeMST(n-1;/INT_MAX 的值在limits -h 中图的顶点数,应由用户定义用二维数组作为邻接矩阵&示生成蝴的边结点边的起点与
3、终点边上的权值最小生成树定义voidPrimMSTCAdjMatrixG,MSTT,intrt)/从顶点rt出发构造图G的最小生成树T,rt成为椅的根结点TreeEdgeNodee;intirk*Ormin,minposrv;if(i!-rt)T(k.fromVex-rt;for(k0;kn-1;k+)for (ik;in-l;i+)if(T(i).weightmin)minT(i).weight; :Tfk+1 .WeiQhfGfrt Mi: )依次求MST的候选边遍历当前候选边臬合 选具有最小权值的候选边if(mins MaxInt)图不连通,出错处理for(i-0;in;i+)初始化最小
4、生成阿TcerrGraphisdisconnectedIendl;e三T(minpos);T(minpos=T(k);Tkae;V=Tlk).toVex;for(i=k+l;in-l;i+)修改候选边臬合if(Gv(T(iJ.toVex)=0)I(2)ifr=p-lchild;p-lchild三p-rchild;p-rchild=r;stack(4)l=plchild?stack(+tpJ=p-rchild;)1)三、判断题19、直接访问文件也能顺序访问,只是一般效率不高。()20、倒排文件的目的是为了多关键字查找。()21、串是一种数据对象和操作都特殊的线性表。()22、稀疏矩阵压缩存储后,
5、必会失去随机存取功能。()23、若从二叉树的任一结点出发,到根的路径上所经过的结点序列按其关键字有序,则该二叉树一定是哈夫曼树。()24、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。(25、为了很方便地Jffi入和删除数据,可以使用双向链表存放数据。()26、在任何情况下,归并排序都比简单插入排序快。()27、B-树中所有结点的平衡因子都为零。()28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。()四、简答题29、设有n个元素采用起泡排序法进行排序,通常需要进行多少趟排序?对于第J趟起泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件,有可能使起泡趟数可以减少并且
6、能完成排序。30、给出一组关键字:29,18,25,47,58,12,51,10,分别写出按下列各种排序方法进行排序时的变化过程:(1)归并排序,每归并一次书写一个次序。2)快速排序,每划分一次书写一个次序。(3)堆排序,先建成一个堆,然后每从堆顶取下一个元素后,将堆调整一次。31、已知一个带有表头结点的单链表,结点结构为datalink假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:(1)描述算法的基本设计思想。(2)描述算法的详细实
7、现步骤。(3)根据设计思想和实现步骤,采用程序设计语言描述算法(使用C或C+或JAVA语言实现),关键之处请给出简要注释。五、算法设计题32、试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法delete(LinkIiSt&L)。33、编写递归算法,从大到小输出给定二叉排序树中所有关蹦字不小于X的数据元素。要求你的算法的时间复杂度为。(Iog2(x+m),其中,2为排序树中所含结点数,m为输出的关键字个数。34、给出以十字链表作存储结构,建立图的算法,输入(i,j,v),其中i,j为顶点号,V为权值。参考答案一、选择题1、【答案】C2、【答案】C3、【答案】B4、【答案】C5、【答
8、案】A6、【答案】A7、【答案】A8、【答案】C9、【答案】B10、【答案】C二、填空题11、【答案】2(N-1)12、【答案】480+8=488;480-32=44813、【答案】O(I);O(n)14、【答案】2;4;3【解析】二分法查找元素次数列表下标1234567891011数值121824354750628390115134次数34234134234查找100是找到115就停止了。15、【答案】(1)(0,3,1);(3,5,4);(5,2,2);(3,1,5);(1,4,3)(2)Tk;toVex=imin=MaxInt;mispos=iexit(0)Ti;fromVex=v【解析
9、】Prirn算法的执行类似于寻找图的最短路径的DijkStra算法。假设N=V,E是连通图,ET是N上最小生成树边的集合。算法从V=u0,ET开始,重复执行下述操作:在所有U属于V,V属于V-Vt的边(u,V)属于E中找一条代价最小的边(uo,V0)加入集合Et,同时将VO并入Vt,直到VT=V为止。16、【答案】FEGHDCB;BEF【解析】树的前序序列对应二叉树的前序序列,该二叉树转换成森林时含三棵树,其第一棵树的前序是BEF。17、【答案】+a*b3*4-cd:18【解析】中缀式相当于中序遍历,前缀式相当于前序遍历,后缀式相当于后序遍历。18、【答案】stacktp=t;p=stackt
10、p-;p;+tp【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈,然后判断栈是否为空,如果不为空,则取栈顶元素,交换取出结点的左右指针。并将左右指针分别进栈,重复这一操作。完成二叉树左右孩子的交换。三、判断题19、【答案】X20、【答案】21、【答案】22、【答案】23、【答案】24、【答案】25、【答案】26、【答案】X27、【答案】28、【答案】X四、简答题29、答:n个元素采用起泡排序法进行排序,通常需要进行n-1趟排序。第j趟起泡排序要进行n-j次比较。在一趟排序中,若没有记录交换,则表示排序完成。因而,可通过设标记来控制排序结束,下面语句段说明了标记flag的使
11、用。intj*l,flag三l;/flag用作控制标记while(jn&flag)j是起泡排序连乳酸多n-1凿flag三O;设标记,若本趟不发生交换,本Ifi起泡排序后,算法结束for(i=ljiri+l)(flag三l;发生/交换,还要进行卜遛30、答:(1)2一路归并第一趟:18,29,25,47,12,58,10,51。第二趟:18,25,29,47,10,12,51,58。第三趟:10,12,18,25,29,47,51,58。(2)快速排序第一趟:10,18,25,12,29,58,51,47。第二趟:10,18,25,12,29,47,51,88。第三趟:10,12,18,25,2
12、9,47,51,88。(3)堆排序建大堆:58,47,51,29,18,12,25,10。51,47,25,29,18,12,10,58。47,29,25,10,18,12,51,58。29,18,25,10,12,47,51,58。25,18,18,12,10,29,47,51,58。10,12,25,29,47,51,58。12,10,18,25,29,47,51,58。10,12, 18, 25, 29, 47,51, 58。31、答:(1)算法的基本设计思想定义两个指针变量P和q,初始时均指向头结点的下一个结点。P指针沿链表移动;当P指针移动到第k个结点时,q指针开始与P指针同步移动;当P指针移动到链表最后一个结点时,因为P和q相隔k,故q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。(2)算法的详细实现步骤CoUnt=0,P和q指向链表表头结点的下一个结点。若P为空,转。若CoUnt等于k,则q指向下一个结点;否则,CoUnt=CoIInt+1。P指向下一个结点,转步骤。若coUnt等于k,则查找成功,输出该结点的data域的值,返回L否则,查找失败,返回0。算法结束。(3)算法实现typedefstructLNodeintdata;数据域structLNode*link;指针域*LinkList;intSearchN!(Lmk