鲁东大学数据结构期末试卷2023.docx

《鲁东大学数据结构期末试卷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指针同步移动；

13、当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!(LmkListListjntk)(1

14、.inkListPqintcount=0;计数器初值p=q=List-link;P和q指向涟表表头结点的下一个结点While(P!=NULL)(if(countlink;q移到下一个结点p=p-lnk;P移到下一个结点f(countdata):查找成功，输出)五、算法设计题32、答：算法如下：1.inkedListDelete(LinkedListL)1站带头结点的单链表，本算法删除其球小值结点p=L-next;p为工作指针。指向待处理的结点。假定链表非空pre=L;Pre指向加小值结点的前驱q=P；q指向及小值结点，初始假定第一元素结点是好小值结点while(p-next)if(p-next

15、-datadata)pre=jq=p-next;查及小值结点p三-next;指针后移Pre-next=q-next;从链表上删除最小值结点free(q);returnL;释放及小值结点空间结束算法DeIete33、答：算法如下：voidoutput(BSTreebstrintx)从大到小输出二叉排序树bst中所有关键字不小干X的数据元素if(bst)if(bst-data=x)output(bst-rchiId,x);if(bst-data=x)printf(,%4dr,rbst-data);if(bst-data=x)output(bst-lchildzx);/ifyoutput34、答：算

16、法如下：voidCreatOrthList(OrthListg)建t有向图的十字能表存储结构inti,j,v;假定权值为整型scanf(Id,Sn);for(i-0,iheadvex三j;p-tailvex三i;p-weight三v;孤结点中权值域p-headlinkeg(j).firstin;gj.firstin三p;p-tailink=g(i).firstout;g(i.firstout*;scanf(%d%d%d,fcirsj,&v);靠法结束35、答：算法如下:voidSnake-Number(ntAn(n),ntn)将自然数lnn,按“蛇形填入n阶方阵A中i=0;3=0;k=l;while(in&jn)while(i-l)A(i(j)=k+;id-；)if(j0)i6(i-l&jn)A(i)(j)k+;i;j+;if(i0&jn)i三0;elsei=i+2;j三n-l;外层WhiIe/Snake_Numberi,j是矩阵元素的下标，k是:要填入的Fi然数从右上向左下填数副对角线及以上部分的新i,j坐标/副对角线以下的新的i,j坐标从左下向右上