专升本《数据结构》主观题常见题型及答案总结：.docx

专升本数据结构主观题常见题型及答案总结:专升本数据结构主观题常见题型及答案总结：一、名词解释1、队列：是一种先进先出的线性表,它只允许在表的一段进行插入,而另一端删除元素,允许插入的一端叫做队尾,允许删除的一端称为队首。2、满二叉树：是一棵深度为k的,且有（2八k）-l个结点的二叉树。3、折半查找：取表的中间位置的记录关键字和所给关键字进行比较。4、关键字：是数据元素中某个数据项的值,用它可以识别一个或一组数据元素。5、循环链表：是另一种形式的链式存储结构,它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。6、分块查找：先确定待查记录所在的块（子表）,然后在块中顺序查找。7、动态查找表:在查找过程中同时插入查找不存在的数据元素,或者从查找表中删除已存在的某个数据元素。8、双向链表：采用链式存储结构的线性表,每个结点除一个数据域外,还有两个指针域,其一指向直接前驱,另一指向直接后继。9、循环队列：循环队列是将队列的数据区看成头尾相接的循环结构。10、二叉树:是一种树型的结构，它的特点是每个结点之多有两棵子树，且有左右之分，不可任意颠倒。11、顺序存储：用一组地址连续的存储单元依次存放线性表的元素。12、有向完全图：有n（n-l）条边的有向图称为有向完全图（图中每个顶点和其余n-l个顶点都有弧相连）。13、查找表:是由同一类型的数据元素或记录构成的集合。14、排序:就是按关键字值的递增或递减的次序，把文件中的各记录一次排列起来，可使一个无序文件变成有序文件的一种操作。二、简答题1.二分查找法的基本思想。折半（二分）查找的基本思路:先取表的中间位置的记录关键字和所给关键字进行比较,若相等,则查找成功,如果给定关键字比该记录的关键字小,则说明所要查找的记录只可能在表的前半部分,反之,则在后半部分,重复步骤,每一次比较就可以将查找范围缩小一半,直到找到给定的关键字的记录,查找成功,找不到为查找失败.2、简述深度优先遍历的方法。假设初始状态是图中所有顶点均未被访问过,则深度优先搜索可从某个顶点V出发，首先访问此顶点（称此顶点为初始点），然后依次从V的任一个未被访问的邻接点出发进行深度优先搜索遍历,直到图中所有与V有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为初始点，重复上述步骤，直到图中所有顶点都被访问过为止。3、简述顺序表和链表各自的缺点。顺序表：1）结点中只存放数据元素本身的信息,无附加内容。2 ）可直接存取数据元素。3 ）存取操作速度较快。4 ）插入.删除数据元素时,由于需要保持数据元素之间的逻辑关系,必须大量移动元素,因此实现起来较慢。5 ）顺序存储是一种静态结构,存储密度大,空间利用率低,预分配空间大小难以确定。链表：1 ）.结点中除存放数据元素本身的信息外,还需存放附加的指针。2 ）.不能直接存取数据元素,需顺链查找,存取速度较慢。3 ）.插入.删除元素时不必移动其他元素,速度较快。4）犍式存储是一种动态存储结构,空间利用率高,存储密度小,不存在预分配空间问题。4、简述线性结构的特点。线性结构的特点是：除第一个元素和最后一个元素外，每个数据元素都有唯一的前驱和唯一的后继，第一个元素没有前驱，最后一个元素没有后继，关系是一对一的。5、树和二叉树之间的区别。二叉树的一个结点至多有2个子树，树则不然。二叉树的一个结点的子树有左右之分，而树则没有此要求。6、简述图的广度优先搜索遍历的方法。1 ).从图中某个顶点VO出发，首先访问VO,依次访问VO的各个未被访问的邻接点。2 ).分别从这些邻接点(端结点)出发,依次访问各个未被访问的邻接点，访问时应保证：如果Vi和Vk为当前结点，且Vi在Vk之前被访问，则Vi的所有未被访问的邻接点应在Vk的所有未被访问的邻接点之前访问。3 ),重复步骤2,直到所有结点均没有未被访问的邻接点。4 ).若此时还有顶点未被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止。7、什么叫遍历二叉树？写出对下图所示二叉树进行先序、中序、后序遍历结点序列。二叉树遍历是指按照一定次序访问树中所有结点，并且每个结点仅被访问一次的过程。巴先序遍历序列：中序遍历序列：后序遍历序列：三、论述题1.试表述各种内部排序方法并论述如何选择。(1)若n(待排序的记录数目)较小，可采用直接插入排序或直接选择排序；(2)若记录的初始状态已经按关键字基本有序，则选用直接插入排序或冒泡排序法。(3)若n较大，则采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。但快速排序、堆排序都是不稳定排序,若要求稳定排序,则可选用归并J序。(4)基数排序可在0(dxn)时间内完成对n个记录的排序，d是指逻辑关键字的个数，一般远小于no(5)当记录本身的信息量很大时，为避免大量时间用在移动数据上，可用链表作为存储结构，插入排序和归并排序都容易在链表上实现，但有的排序方法，如快速排序和堆排序在链表上很难实现。2、折半查找法的基本思想。折半(二分)查找的基本思路:先取表的中间位置的记录关键字和所给关键字进行比较,若相等,则查找成功,如果给定关键字比该记录的关键字小,则说明所要查找的记录只可能在表的前半部分,反之很U在后半部分,重复步骤,每一次比较就可以将查找范围缩小一半,直到找到给定的关键字的记录,查找成功,找不到为查找失败。四、解答题己HlW>WFWrMbW8件序H为，6Gl.匕出演F附*恁Ilmtw/trfim<naom-j.>.4.e.,«如&食irm三fttt*KlK掰K长年FW%>7NZ盒等%Mm值黛会府tB*M一金AKWttKtE0*B>A*343“*SfaFnffl哈A9"“«i6ooeu<>ot.t.ih/O1.3、设待排序的表有10个元素，其关键字分别为(9,8,7,6,5,4,3,2,1,0)°说明采用直接插入排序方法进行排序的过程。4、已知一组关键字为25,18,46,2,53,39,32,4,74,67,60,llo按表中的元素顺序依次插入到一棵初始为空的二叉排序树中，画出该二叉排序树。求在等概率的情况下查找成功的平均查找长度和查找不成功的平均查找长度。t4>K:»,，叽32.X.4».Stt.K.MN.W二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质（BST性质）的二叉树:若它的左子树非空，则左子树上所有结点值（指关键字值）均小于根结点值；若它的右子树非空，则右子树上所有结点值均大于根结点值；左、右子树本身又各是一棵二叉排序树。注意：二叉排序树中没有相同关键字的结点。5、W=0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11)建立一颗哈夫曼树。构造哈夫曼树的过程：（1）给定的n个权值W1,W2,，Wn构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F=T1,T2,，Tn。（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和。（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中。（4）重复（2）、（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。哈夫曼树的特点：nl=O:因为每次两棵树合并。n=n+nl+n2=0+n2=2n0-l06、设待排序的表有10个记录，其关键字分别为(6,8,7,9,0,1,3,2,4,5)°说明采用快速排序方法进行排序的过程。快速排序算法是基于分治策略的另一个排序算法。该方法的基本思想是：1 .先从数列中取出一个数作为基准数，记为Xo,*¼<MA一4OUV4><*t，2 .分区过程，将不小于X的数全放到它的右边，不大于X的数全放到它的左边。(这样key的位置左边的没有大于key的，右边的没有小于key的，只需对左右区间排序即可)3.再对左右区间重复第二步，直到各区间只有一个数。7、设下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小。各H,Ftl西的代价121316，U*1*2>12341>448*12¼417*12*22UkJMq7CG*aeiN*0B164112OIlB51629。12MfJIDlW>4HlJJ<J1Pr<1.MM.A/hMJIJPWWd<UIKAOr.Rlft)uKrwknlBrAMmiII<yj½V.望蛤恬内吐电的1+*1ilV>利用/，,接队11hiMM算的ift的小，底附为,NO.Ih，*».11.0.(2.5.T.4).利司身卡。尔小伪小，罐MM1(010.-1I'I.5.OCb$).普里姆(Prim)算法是一种构造性算法，用于构造最小生成树。过程如下：(1)初始化U=voV到其他顶点的所有边为候选边；(2)重复以下步骤n-1次，使得其他n-1个顶点被加入到U中：从候选边中挑选权值最小的边输出，设该边在V-U中的顶点是k,将k加入U中；考察当前V-U中的所有顶点j,修改候选边：若(j,k)的权值小于原来和顶点k关联的候选边，则用(k,j)取代后者作为候选边。克鲁斯卡尔(Kruskal)算法过程：(1)置U的初值等于V(即包含有G中的全部顶点)，TE的初值为空集(即图T中每一个顶点都构成一个连通分量)。(2)将图G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路，则加入TE;否则舍弃，直到TE中包含(n-l)条边为止。克鲁斯卡尔算法求解最小生成树的过程»K.I1.DtiteMro<I>A三4M.>>-D.1.务2，一/«0.Sl-Ir.O.O.Il.：九IhMK方hF忡£*4m(0<八I.4.31.=1TOlSz60.I.0.I.1).临样KIt的3UiV；o.I.忆M集IKNOMAtKrH”二度.血抄'EdU4.2.Ifj.尸一.3卜00.I.0.1.>J.eUWJBMK*的1在2.44，、0I.1.力.M9H<>2MtJ)r)MM114tK<.d<oM(kI.4.2«I.19，,fvMK<Sk0.O.I.I.盟地朴德dWlC4«5)Vtt.I.3.2.4.H<*UfU/八，的用I薛冷K«，df(S卜MI.4.2«K.IQ：,i0.5卜IM0.I.CI.)：.W也也长嚏<，>»I.J.工4力旧墟.y，卜ft.4.，.X.1<1；.1叫。.»帙处怙累扪FJMOMlnI<Mft1«14Ml4JM946Jl2u÷7t美174W435494*JlW77Kr>24*12.r/l>"lXOoKtrNIK.弊神为。，I双0角2时置付恍度为:！施朴为:U.1.2MOR311MIK3.黑技为。.，AloiIl的*踣胃恨&箫护内他1.1MOKSflJf幡Kit为JaMiQ.J1B8、假设哈希表长度m=13,采用除留余数法哈希函数建立如下关键字集合的哈希表(16,74,60,43,54,90,46,31,29,88,77),共11个关键字。解：n=ll,m=13,设计除留余数法的哈希函数为：h(k)=kmodPP应为小于等于m的素数，设p=13o对于上题采用线性探查法解决冲突。KMT:1674M4JM46Ji29MT7*曰334MXI)"A44j=(4iIt11l)¼U=S'>*tO将”It，)仍"交>Uk式.7”“IMIlI：4Jt<tff:U74OMW¼312tWT!b(0HOIl314MU24J31上4M14*1M*Wm1377片<<84><iKJMtAA¼l<HAi<<tH>1.HXAS1.”.Il2III*I4*HI1*II-IJM对十H面构0粕哈不成功金NAS1.计算W<*Mf<f.M4t*M.京局二"叔J,IKY1.一时于W*的良S呛*不成功金RAS1.HM*，1，熏，'11ljrrM1«4JJt4*74Mi9金次ftIIi,?931IJ-t<*WT<t.(»$*"1/ee"7÷4M*331+3=4,92Ata2.CMnMjijtur.t139、设待排序的表有10个记录，其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用堆排序方法进行排序的过程。M44H：.,7,9,%vJr2t*g42一，E全二义也调负完毕.人为一个大版堆9876SI324010、将整数序列(4,5,7,2,1,3,6)中的元素依次插入到一棵空的二叉排序树中，试构造相应的二叉排序树，要求用图形给出构造过程。图：构造二叉排序树过程4«IifrHfjatrt7<.xir三r*zwwri.hwUF"(I)d二|为11cW:2)M¾三*fcrtrttJ11fjMU<.4A号1.>S0t43>Mj，均鲁¾Kf.V«(I3二Kfty网妁J序台历序It为4OWXM.1!中午心方“”为WTfnmIm司机劭咛亨-七町XWd柯iMKADF/JbAAW1.懵95一粗二乂林序树<2)AS1.<l<1>2-2M*>2*4*P5yO-3(3)/I.V.«-<6-JU-4*25)H-JMK-HV45.，.162面元丽<3THH*111ch7“制搂的"HlXH,4UIM出帕出UN林人35UtW»8XHdf?ip<.n.i«.*.j.M.n.,.<.11).M,e曲*也小尸5，1九茶四开JOtit汪的林忤拓的注止冲突H在O-IUfteElMfa0支ITFf*l>鲁上,fWntfct.Wt依1.MJltiN传住WB卜Idki的计公大，,<4"M*r)4,r4F*6rI*2,HWAKtttdMiitVlJlffteF.Mrr*sw.Mr%>.2>rD*s>>u61MH4%I>I,M4KI)、忤2%Ii空Jr-标.MMK6">%"TItWnMMigiW-rrz%>(«.2EI>9-2fM*>.wpnw3(仍冷卖AinwHhH1-4MMr!>>(*«*-cw"l>%lZWfW>MeKM,*SAiiiriixoii<t>>-WS11-IO<.*t.MIE心11%IAll，nX).MIW-IlMb%-:A(77VrT%lP121”臾).Arrr口T,N1AI3l.m.I2J1.49i7«lIl12Ml*)43jl“_广州kftt:哈希冲突解决方法：开放定址法：冲突时找一个新的空闲的哈希地址。(1)线性探查法线性探查法的数学递推描述公式为：d=h(k)di=(di-l+l)modm(lim-l)非同义词冲突：哈希函数值不相同的两个记录争夺同一个后继哈希地址堆积(或聚集)现象。(2)平方探查法平方探查法的数学描述公式为：d=h(k)di=(d±i2)modm(lim-l)查找的位置依次为：dO、d+lsd-lxd+4、d-4、平方探查法是一种较好的处理冲突的方法，可以避免出现堆积现象。它的缺点是不能探查到哈希表上的所有单元，但至少能探查到一半单元。