数据结构第六

一、概念题（每空0.5分，共45分）对于集合这逻辑结构来说，其中的数据元素之间也可以有各种各样的非逻辑关系，但任何一对数据元素之间没有关系，即没有关系。查找表按其所包括的运算的不同分为查找表和查找表。查找表中主关键字指的是，次关键字指的是。静态查找表包括、、三种基本运算。动态查找表包括、、、、五种基本运算。假定key为主关键字，若顺序表中第n个元素的键值为K，则顺序查找算法的查找长度为1；若第1个元素的键值为K，则查找长度为；若表中无键值等于K的元素，则查找长度为。二分查找在查找成功时的查找长度不超过，其平均查找长度为，当n较大时约等于。静态查找表的三种不同实现各有优缺点。其中，查找效率最低但限制最少。查找效率最高但限制最强。而查找则介于上述二者之间。二叉搜索树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值于其左孩子（及其子孙）的键值且于其右孩子（及其子孙）的键值。在表示一棵二叉搜索树的二叉链表上，要找键值比某结点X的键值的结点，只需通过结点X的左指针到它的左子树中去找。。中序遍历一棵二叉搜索树所得的结点访问序列是键值的序列。二叉搜索树上的查找长度不仅与有关，也与二叉搜索树的有关。在随机情况下，含有n个结点的二叉搜索树的平均查找长度为，其时间效率很高。折半查找的查找效率与树的形态有关。当二叉搜索树退化为一条单支时，查找算法退化为查找，平均查找长度上升为。有n个结点的AVL树的深度与是同数量级的，因而在它上面进行查找的平均查找长度也与同数量级。平衡二叉搜索树上任一结点的平衡因子只可能是、或。在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数，比较二次查找成功的结点数为，比较五次查找成功的结点数为。总的平均查找长度为。按组织形式的不同，通常有与两类散列表。对闭散列表来说，的方法就是处理冲突的方法。是散列表的一个重要参数，它反映出散列表的装满程度；在散列存储中，该值越大，则。图有、等存储结构，遍历图有、等方法。有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点讷。如果n个顶点的图是一个环，则它有棵生成树。n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为;若采用邻TOC\o"1-5"\h\z接表存储，则空间复杂度为。n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为；若采用邻接表存储时，该算法的时间复杂度为；若是采用广度优先遍历算法的时间复杂度为；同样若用邻接表存储，该算法的时间复杂度为。图的BFS生成树的树高比DFS生成树的树高。用普里姆（Prim）算法求具有n个顶点e条边的图的最小生成树的时间复杂度为；用克鲁斯卡尔（Kruskal）算法的时间复杂度。若要求一个稀疏图G的最小生成树，最好用算法来求解；若要求一个稠密图G的最小生成树，最好用算法来求解。用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是的，否则称为的。按照排序过程涉及的存储设备的不同，排序可分为排序和排序。按排序过程中依据的不同原则对内部排序方法进行分类，主要有：、、、等四类。在排序算法中，分析算法的时间复杂性时，通常以和为标准操作。评价排序的另一个主要标准是执行算法所需要的。常用的插入排序方法有插入排序、插入排序、插入排序和插入排序。直接插入排序是稳定的，它的时间复杂性为，空间复杂度为。对快速排序来讲，其最好情况下的时间复杂度是，其最坏情况下的时间复杂度是直接选择排序是不稳定的，其时间复杂性为。堆排序是不稳定，空间复杂度为。在最坏情况下，其时间复杂性也为。二路归并排序的时间复杂度是。对关键字序列（72，87，61，23，94，16，05，58）进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。初始堆：第1趟：第2趟：第3趟：二、选择题（每空0.5分，共15分）以下说法错误的是（）数字分析法对键值的各位进行分析，选择分布较均匀的若干位组成散列地址。除余法选择一个适当的正整数p,以p除键值以所得的余数作为散列地址。平方取中法以键值平方的中间几位作为散列地址。基数转换法将键值看成另一种进制的数再转换成原来进制的数，然后选择其中几位作为散列地址。随机数法选择一个随机函数random,以键值在该函数下的值作为散列地址。以下说法正确的是（）数字分析法需事先知道所有可能出现的键值及所有键值的每一位上各数字的分布情况，并且键值的位数比散列地址的位数多。除余法要求事先知道全部键值。平方取中法需要事先掌握键值的分布情况。随机数法适用于键值不相等的场合。除余法选择一正整数p，以键值除以p所得的余数作为散列地址。通常选？为（）小于或等于散列表长的素数。接近表长的且不与组成关键字的字符基数直接相关的质数。大于或等于散列表长的素数。接近表长的质数。顺序查找法适合于（）存储结构的查找表。压缩B.散列C.索引D.顺序或链式对采用二分查找法进行查找运算的查找表，要求按（）方式进行存储。顺序存储B.链式存储C.顺序存储且结点按关键字有序D.链式存储且结点按关键字有序TOC\o"1-5"\h\z设顺序表的长为n,则其每个元素的平均查找长度是（）A.nB.（n-1）/2C.n/2D.（n+1）/2设有序表的关键字序列为｛1,4,6,10,18,35,42,53,67,71,78,84,92,99｝，当用二分查找法查找键值为84的结点时，经（）次比较后查找成功。A.2B.3C.4D.12静态查找表与动态查找表两者的根本差别在于（）A.逻辑结构不同B.存储实现不同C.施加的操作不同D.数据元素的类型不同长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的ASL值是（）A.37/12B.62/13C.39/12D.49/13在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（）A.nB.1C.n+1D.n-1二分查找法适用于存储结构为（）的，且按关键字排序的线性表。（）A.顺序存储B.链接存储C.顺序存储或链接存储D.索引存储用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为A.O（n2）B.O（nlogn）C.O（n）D.O（logn）用二分查找法对具有n个结点的线性表查找的时间复杂2性量级为（）A.O（n2）B.O（nlogn）C.O（n）D.O（logn）二叉搜索树的查找和折半查找的时间性能相同。这种2说法（）A.正确B.错误与其他查找方法相比，散列查找法的特点是（）通过关键字比较进行查找通过关键字计算记录存储地址进行查找通过关键字计算记录存储地址，并进行一定的比较进行查找在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（）A.一定都是同义词B.一定都不是同义词C.都相同D.键值不一定有序的顺序表以下说法正确的是（）平衡树一定是丰满树。虽然信息项的序列的顺序不一样，但依次生成的二叉搜索树确是一样的。在二叉搜索树上插入新的结点时，不必移动其他结点，只需改动某个结点的指针，由空变为非空即可。在二叉搜索树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应的指针域置空即可。在一个图中，所有顶点的度数之和等于图的边数白倍。（）A.1/2B.1C.2D.4在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A.1/2B.1C.2D.420.有8个结点的无向图最多有条边。A.14B.28C.56D.11221,有8个结点的无向连通图最少有_条边。A.5B.6C.7D.8

有8个结点的有向完全图有条边。D.112TOC\o"1-5"\h\zA.14B.28C.56用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。D.112A.栈B.队列C.树D.图用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。A.栈B.队列C.树D.图任何一个无向连通图的最小生成树A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在TOC\o"1-5"\h\z以下不稳定的排序方法是()A.直接插入排序B.冒泡排序C.直接选择排序D.二路归并排序在文件局部有序或文件长度较小的情况下，最佳的排序方法是()A.直接插入排序B.冒泡排序C.直接选择排序D.归并排序快速排序在最坏的情况下的时间复杂度是()A.O(log2n)B.O(nlog2n)C.O(n2)D.0(n3)三、综合题(每题2分，共30分)对长度为20的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均查找长度。2,给定有序表D={006,087,155,188,220,465,505,508,511,586,656,670,700,766,897,908}，用二分查找法在D中查找586，试用图示法表示出查找过程。给定表(19，14，22，01，66，21，83，27，56，13，10)。试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成之后的二叉排序树。按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。给定表(Jan,Feb,Mar,Apr,May,Jun,Jun,Aug,Sep,0ct,Nov,Dec).设取散列函数H(x)=|_i/2_|,其中i为键值中第一个字母在英语字母表中的序号，要求：画出相应的开散列表；（2）画出闭散列表（以线性探测法处理）；（3）分别求这两个散列表在等概率情况下查找成功与不成功时的平均查找长度。（1）（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表。顶点123456入度出度—5,已知如图所示的有向图，请给出该图的:请对下图的无向带权图：（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。8.试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各第9题图第8题图9,给定下列网G:1）试着找出网G的最小生成树，画出其逻辑结构图；2）用两种不同的表示法画出网G的存储结构图；3）用C++语言定义其中一种表示法（存储结构）的数据类型。已知一具有n个顶点的有向图G=（V,E）采用邻接表存储方法，请写一算法，检查任意给定序列v1,v2,…,vn（vi£V,1WiWn）是否为该有向图的一个拓扑序列。若是，算法给出信息1，否则，给出信息0。对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。12.写出非递归调用的快速排序算法。13.Obtainthelinked-adjacency-listrepresentationsofthenetworksthatcorrespondtothecost-adjacencymatricesasbelow.14.Forthegraphasbelow,dothefollowing:Obtainabreadth-firstspanningtreeObtainabreadth-firstspanningtreestartingatvertex1;startingatvertex3;108888280388388027488608588850above,dothefollowing:Obtainadepth-firstspanningtreestartingObtainadepth-firstspanningtreestartingatvertex1;atvertex3;参考答案一、概念题(每空0.5分，共45分)逻辑关联静态动态能唯一标识数据元素的数据项不能唯一标识数据元素的数据项建表查找读表元素查找读表元素插入新元素删除初始化nn+1hogn」+1〃*log(n+1)-1log(n+1)-1.2n22顺序查找二分(折半)查找分块查找大小小递增有序节点个数生成过程(形态)O(log2n)顺序°(n+1)/2lognlogn02+1-211293.92(提示：二分查找过程可以与一棵有序二叉树相对应，那么第一层上1个结点，第二层上2个结点，第三层上4个结点，第四层上8个结点，第5层上9个结点。平均查找长度ASL=(1*1+2*2+3*4+4*8+5*9)/24=3.92)开散列闭散列构造后继散列地址序列装填因子存取元素时发生冲突的可能性就越大邻接矩阵邻接表深度优先遍历广度优先遍历出度nO(n2)O(n+e)O(n2)O(n+e)O(n2)O(n+e)小或相等O(n2)O(elog2e)克鲁斯卡尔(Kruskal)算法普里姆(Prim)算法递增20稳定不稳定内部外部插入排序、交换排序、选择排序、归并排序键值比较、记录移动、附加空间直接、折半、表、希尔O(n2)O(1)O(nlog2n)、O(n2)O(n2)O(1)O(nlog2n)O(log2n)(9487615872160523)(8772615823160594)(7258610523168794)(6158160523728794)二、选择题A2.A3.A4.A12.C13.D14.21.C22.C23.B24.D5.C6.D7.B15.C16.D17.A25.D26.C8.C9.B10.CC18.C19.B20.BC30.CC27.A28.C29.成功平均查找长度为：(1+2*2+3*4+4*8+5*5)/20=74/20=3.7三、综合题（每题2分，共30分）1.判定树如下图所示：2.010203006087155flow006087155040506188220465188220465070809101112505508511586656670fmid③006087155188220465505508511586656670fflowmid505508511586656670ffflowmidhig（成功）1370070070014766fhig766fhig7661589789789716908908908(2)AVL树略，成功平均查找长度为：ASL=(1+2*2+3*4+4*4)/11=33/11=3.4.⑴略012345678910111213AprIAugDecIFebITanIMarIMayITunTulISepIOctINov（3）开散列表上查找成功的平均查找长度：ASL=（1+2+1+1+1+2+3+1+2+1+2+1）/12=18/12=1.5开散列表上查找不成功的平均查找长度：ASL=（3+1+2+2+1+4+3+3+1+2+1+1+1+1）/14=26/14^2闭散列表上查找成功的平均查找长度：ASL=（1+2+1+1+1+1+2+4+5+2+5+6）/12=31/12^2.6闭散列表上查找不成功的平均查找长度：ASL=（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14=60/14^45.'00000%'00000%10G]Q■0：0I000I：CQ101t1G000DJ10Q1Cl新搓逅阵（3）邹揍麦6.（1）设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!邻接矩阵为：04388888405598883500438888840559888350588858550765489870388888630288885820688548860(2)ab""邻接表为:—►Etiddie9cfa3fdfb5fefb9fffd6fgfd5fhfc5fb5ffd5ffh5Ac5e7f6fg5一h4ad7ff3人e3fg2人f2fh6人d4fg6人深度优先生成树广度优先生成树8.最短路径为：（a,c,f,e,d,g,b）终点bcdef（■终点集）K=115（.L）1215(aTb)12<a,d》10(a-:-K=315db)[a*cf)1U16〔a.ELg){a..-}K=415(atb)6唱,顷16+e«d}K=51514Ca+c^radig)国AJ心K—639.（1）.最小生成树可直接画出，如图所示。（2）.可用邻接矩阵和邻接表来描述01288488120208898820015881288150881048880688988608881210880邻接表为:afb12fe4bfa12fc20cfb20fd15dfc15fg10efa4fb8ffb9fe6gfc12fd10（3）略，参考教材。f910.在邻接表的表头中增加一个入度域in，数据结构修改如下:typedefstructvexnode(VertexTypevertex;intin;/*增加一个入度域*/ArcNodeTp*firstarc;}AdjList[vnum];typedefstructgraph(AdjListadjlist;intvexnum,arcnum;}GraphTp;拓扑排序算法如下：Top_Sort(GraphTpg)(LstackTp*S;ArcNodeTp*p;intm,I,v;InitStack(S);for(I=0;I<g.vexnum;I++)if(g.adjlist[I].in==0)push(S,&v)m=0;while(!EmptyStack(S)){Pop(S,&v);printf("％d'',v);m++;p=g.adjlist[I].firstarc;while(p!=NULL){(g.adjlist[p->adjvex].in)--;/*建立入度为0的顶点栈S*//*if(w的入度==0)*//*w入S栈*//*S出栈->v*//*输出v*//*p=图g中顶点v的第一个邻接点*//*p存在*//*p的入度--*/if(g.adjlist[p->adjvex].in==0)Push(S,p->adjvex);p=p->nextarc;}}if(m<g.vexnum)return0;elsereturn1;/*if（p的入度==0）*//*p入S栈*//*p=图g中顶点v的下一个邻接点*//*图含有环*//*拓扑排序完成*/}（注：这是C版的，C++版的可以自己仿照写出。）11.1.①直接插入排序序号123456789101112]]]]]]]]]]55555555551111111111[111111111566666666666xc9899999999]]]]]]]]]]55555555551111111111[111111111566666666666xc9899999999.40371^9889999999的333333364393[9887777777555555643935[9887666666696969696966439399999[99887653335354433313333[3888666484848443337778[8888655531313333370001[88665444333300099986644433303300486443003333333384411111111123456789序号123456789101112关键字834063138435965739796115i=113[4063838435965739796115]i=21315[63838435965739796140]i=3131535[838463965739796140]i=413153539[8463965783796140]i=51315353940[63965783796184]i=6131535394057[966383796184]i=713153539405761[6383799684]i=813