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

《鲁东大学数据结构期末试卷2023.docx》由会员分享，可在线阅读，更多相关《鲁东大学数据结构期末试卷2023.docx（15页珍藏版）》请在第一文库网上搜索。

1、2023年鲁东大学软件工程专业数据结构与算法科目期末试卷A（有答案）一、选择题1、若需在O（n1og2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序C.归并排序D.直接插入排序2、下列说法不正确的是（）。A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、动态存储管

2、理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.45、已知串S=aaab,其next数组值为（）。A.0123B.1123C.1231D.12116、下列关于无向连通图特性的叙述中，正确的是（I.所有的顶点的度之和为偶数.边数大于顶点个数减1I至少有一个顶点的度为1A.只有IB.只有C.I和D.I和In7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是()。I.简单选择排序.希尔排序in.快速排序IV.堆排V.二路归并排序A.仅工、田、IVB.仅工、n、HIC.仅H、m、IVD.仅HI、IV

3、、V8、有n(n0)个分支结点的满二叉树的深度是()。A.2-1B.I0g2(n+1)+1C.I0g2(n+1)D.I0g2(n-1)9、有关二叉树下列说法正确的是()。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为I,则应作()型调整以使其平衡A.11B.1RCR1D.RR二、填空题11、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有个非零元素。12、起始地址为480,大小为8的块，其伙伴块的起始地址是；

4、若块大小为32,则其伙伴块的起始地址为。13、对于一个具有n个结点的单链表，在已知的结点半P后插入一个新结点的时间复杂度为，在给定值为X的结点后插入一个新结点的时间复杂度为o14、已知有序表为(12,18,24,35,47,50,62,83,90,115,134)当用二分法查找90时，需次查找成功，查找47时成功，查找IOO时，需次才能确定不成功。15、应用Prim算法求解连通网络的最小生成树问题。(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值)，y6X(2)下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

5、INT_MAX的值在中图的顶点效，应由用户定义用维数组作为邻接矩阵去示生成树的边结点边的起点与终点边1的权值最小生成树定义if(i!rt)T(k.fromVex=rt;for(k0;kn-1;k*+)for(i=k;in-1;i+)if(Ti.weightmin)min=T(i).weight;：T1ki）.weightGrti;/依次求MST的候选边遍历当前候选边集合选具有最小权值的候选边；）if(min=MaxInt)图不连通，出错处理constintMaxInt=INT_MAX;constintn6;typedefintAdjMatrixJnJ(n;typedefstructintfro

6、mVex,toVex;intweight;TreeEdgeNode;typedefTreeEdgeNodeMSTn-1;voidPrimMST(AdjMatrixG,MSTT,intrt)从顶点rt出发构造图G的最小生成树T,rt成为树的根结点TreeEdgeNodee;inti,k0fminrminosfv;for(i-0;in;i+)初始化最小生成树TcerrwGraphisdisconnected!wend1;e=T(minpos);Tminpos)=T(k;T(k)=e;v=T(k).toVex;for(i=k1;in-1;i+)修改候选边集合if(Gv(Ti).toVex)=0）-1

7、2）_ifr=-1chi1d;p-1chi1d=p-rchi1d;p-rchi1dr;stack（4）1p-1chi1d;stack+tpp-rchi1d;）1三、判断题19、直接访问文件也能顺序访问，只是一般效率不高。（）20、倒排文件的目的是为了多关键字查找。（）21、串是一种数据对象和操作都特殊的线性表。（）22、稀疏矩阵压缩存储后，必会失去随机存取功能。（）23、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（）24、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）25、为了很方便地插入和删除数据，可以使用双向链表存放数据。（

8、）26、在任何情况下，归并排序都比简单插入排序快。（）27、B-树中所有结点的平衡因子都为零。（）28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（）四、简答题29、设有n个元素采用起泡排序法进行排序，通常需要进行多少趟排序？对于第J趟起泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。30、给出一组关键字：29,18,25,47,58,12,51,10,分别写出按下列各种排序方法进行排序时的变化过程：（1）归并排序，每归并一次书写一个次序。（2）快速排序，每划分一次书写一个次序。（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素

9、后，将堆调整一次。31、已知一个带有表头结点的单链表，结点结构为data1ink假设该链表只给出了头指针Iisto在不改变链表的前提下，请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1否则，只返回0。要求：(1)描述算法的基本设计思想。(2)描述算法的详细实现步骤。(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或C+或JAVA语言实现)，关键之处请给出简要注释。五、算法设计题32、试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法de1ete(1ink1ist&1)。33、编写递归算法，

10、从大到小输出给定二叉排序树中所有关蹦字不小于X的数据元素。要求你的算法的时间复杂度为。(og2(x+m)，其中，2为排序树中所含结点数，m为输出的关键字个数。34、给出以十字链表作存储结构，建立图的算法，输入(i,j,v),其中i,j为顶点号，V为权值。参考答案一、选择题1、【答案】C2、【答案】C3、【答案】B4、【答案】C5、【答案】A6、【答案】A7、【答案】A8、【答案】C9、【答案】B10、【答案】C二、填空题11、【答案】2(N-1)12、【答案】480+8=488；480-32=44813、【答案】O(1)；O(n)14、【答案】2；4；3【解析】二分法查找元素次数列表下标123

11、4567891011数值121824354750628390115134次数34234134234查找IOO是找到115就停止了。15、【答案】(1)(0,3,1)；(3,5,4)；(5,2,2)；(3,1,5)；(1,4,3)(2)Tk；toVex=i(2)min=MaxInt;mispos=i函tTi；fromVex=v【解析】Prim算法的执行类似于寻找图的最短路径的DijkStra算法。假设N=V,E是连通图，ET是N上最小生成树边的集合。算法从V=u,ET开始，重复执行下述操作:在所有U属于V,V属于V-VT的边(u,V)属于E中找一条代价最小的边(Uo,V0)加入集合Et,同时将V

12、o并入Vt,直到VT=V为止。16、【答案】FEGHDCB；BEF【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEFo17、【答案】+a*b3*4-cch18【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。18【答案】stacktp=t;p=stacktp-;p；+tp【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。三、判断题19、【答案】20、【答案】21、【答案】22、【答案】23、【答案】X24、【答案】25、【答案】26、【答案】27、【答案】28、【答案】四、简答题29、答：n个元素采用起泡排序法进行排序，通常需要进行ri-1趟排序。第j趟起泡排序要进行n-j次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排序结束，下面语句段说明了标记f1ag的使用。intj1zf1ag=1;/f1ag用作控制标记whi1e(jn&f1ag)提起泡推序趟数，最多n-1趟f1ag=O;设标记，苕本趟不发生交换,本IS起泡排序后,算法结束for(i=1;ii+1)f1ag1;riri+