数据结构03-04期末考试A答案

1111121110122222212011211111101020100000nnnnnnnnnnnnnbaaaabbaaabbbaabbbbaC时当时当],][[],][[]][[jiijCjijiCjiA四川大学期末考试题解答(2003-2004学年第二学期)课程名:数据结构(A)计算机科学与技术专业适用人数:学院:专业:教师姓名:姓名:学号:成绩:一.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少个元素?【解答】若设顺序表中已有n=last+1个元素，last是顺序表的数据成员，表明最后表项的位置。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。插入时平均移动元素个数AMN(AveragyMovingNumber)为删除时平均移动元素个数AMN为二.设A和B均为下三角矩阵，每一个都有n行。因此在下三角区域中各有n(n+1)/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。【解答】计算公式2n21)n(n1n1)01)1n(n(1n1in1n1AMNn0i1n0i21n21)n(nn10)12)(n1)((nn11)i(nn1AMN111110111000nnnnaaaaaaA111110111000nnnnbbbbbbB132)16/(1612C三.铁路进行列车调度时,常把站台设计成栈式结构的站台，如右图所示。试问：(1)设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?(2)若进站的六辆列车顺序如上所述,那么是否能够得到435612,325641,154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出进栈或出栈的序列)。【解答】(1)可能的不同出栈序列有种。(2)不能得到435612和154623这样的出栈序列。因为若在4,3,5,6之后再将1,2出栈，则1,2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。35622444411111111332323253253256325643256415344122226111313513541354213542135426四.列出右图所示二叉树的叶结点、分支结点和每个结点的层次。【解答】二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。结点①的层次为0；结点②、③的层次为1；结点④、⑤、⑥的层次为2；结点⑦、⑧的层次为3；结点⑨的层次为4。五.在结点个数为n(n1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？时当时当],1][[],1][[]][[jijiCjiijCjiB【解答】结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。六.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。【解答】具有3个结点的树具有3个结点的二叉树七.写出向堆中加入数据4,2,5,8,3,6,10,14时，每加入一个数据后堆的变化。【解答】以最小堆为例：八.给定一组权值:23,15,66,07,11,45,33,52,39,26,58,试构造一棵具有最小带权外部路径长度的扩充4叉树,要求该4叉树中所有内部结点的度都是4,所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少?【解答】权值个数n=11，扩充4叉树的内结点的度都为4，而外结点的度都为0。设内结点个数为n4，外结点个数为n0，则可证明有关系n0=3*n4+1。由于在本题中n0=11≠3*n4+1，需要补2个权值为0的外结点。此时内结点个数n4=4。仿照霍夫曼树的构造方法来构造扩充4叉树，每次合并4个结点。44444222555228843528345283465283461052834610140070111523263339455258665866821691523261833394552375007011010000000000010010100000010100001010Edge此树的带权路径长度WPL=375+82+169+18=644。画出对其进行折半搜索时的二叉搜索树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。【解答】九.给出右图的邻接矩阵、邻接表和邻接多重表表示。【解答】(1)邻接矩阵50915467701727555389709417050351261276590814457)*44*32*2(1141C141ASL141iisucc155914)*41*(3151C151ASL150i'iunsuccABCDEF①②③④⑤或①②③④⑤①②③④⑤(2)邻接表(3)邻接多重表（十字链表）十..对于如右图所示的有向图，试写出：(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树；【解答】(1)以顶点①为根的深度优先生成树（不唯一）：②③④⑤⑥(2)以顶点②为根的广度优先生成树：0A1B2C3D4E5F10A1B2C3D4E5F324514403101352∧∧∧∧∧∧∧∧∧∧∧∧（出边表）（入边表）0A1B2C3D4E5Fdatafinfoutijilinkjlink01(A,B)03(A,D)12(B,C)14(B,E)25(C,F)31(D,B)34(D,E)54(F,E)∧∧∧∧∧∧∧∧∧∧①②③④⑤④⑤十一.设在4地(A,B,C,D)之间架设有6座桥，如图所示：要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。(1)试就以上图形说明：此问题有解的条件什么？（3分）(2)设图中的顶点数为n，试用C或Pascal描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。（7分）【解答】将下图改为无向图，城市为结点，桥为边：(1)此为欧拉问题。有解的充要条件是每一个结点的度为偶数。（5分）(2)数据结构采用邻接表，每个边结点有3个域，分别记录相关边号、邻接顶点号和链指针。另外，设置一个边的访问标志数组visited[]，当visited[i]==0表示第i条边未访问过，一旦访问了第i条边，即将visited[i]改为1。ABCD①②③④⑤⑥ABCD①②③④⑤⑥ABCD①③②④⑤⑥EdgeNoAdjNolinkstructedgenode{//顶点结点intedgeno;//相关边号intadjvertex;//邻接顶点号edgenode*link;//链接指针};structvertex{//顶点intcity;//顶点数据edgenode*first;//出边表指针};Typedefvertex*nodelist;//邻接表数组下面给出按深度优先搜索方法求解欧拉问题的递归算法。（5分）voiddfs(nodelisteuler,intstart,intn,intvisited[]){couteuler[start].city‘-’;//输出顶点数据edgenode*p=euler[start].first;//找第一条关联的边while(p!=NULL){//有intj=p-edgeno;//边号if(visited[j]==0){//未走过visited[j]=1;//作边访问标记dfs(euler,p-adjvertex,n,visited);//按邻接顶点递归下去}p=p-link;//查下一条关联的边}}主程序（5分）voidmain{①2①2①2①2①2①2①2①2①2①2①2①2∧∧∧∧1A2B3C4Dvisited①②③④⑤⑥nodelistintcount,n,i,j,k;cout“输入顶点数：”;cinn;nodelisteuler=newvertex[n];//创建邻接表数组for(inti=0;in;i++){//输入顶点数据,指针置空cineuler[i].city;euler[i].first=NULL;}cout“输入各条边！”endl;//输入各边数据count=0;//边计数cinijk;//i是边号码，j,k是顶点while(i!=0){//i为0,表示输入结束edgenode*p=newedgenode;//链入第j号链表p-edgeno=i;p-adjvertex=k;p-link=euler[j].first;euler[j].first=p;edgenode*p=newedgenode;//链入第k号链表p-edgeno=i;p-adjvertex=j;p-link=euler[k].first;euler[k].first=p;cinijk;count++;}int*visited=newint[count];//创建访问标志数组for(i=0;icount;i++)visited[i]=0;for(i=0;in;i++){//判断各个顶点的度是否偶数count=0;p=euler[start].first;//找第一条关联的边while(p!=NULL){//有count++;p=p-link;//查下一条关联的边;}//计算该顶点的度if(count%2!=0){cout“顶点的度不为偶数,此题无解！”endl;exit(1);}}dfs(euler,0,n,visited);//从0号顶点开始delete[]visited;}