2016浙大数据结构与算法离线作业

浙江大学远程教育学院《数据结构与算法》课程离线作业姓名：学号：年级：2016春学习中心：一、填空题：(【序号，章，节】。。。。。。)[1,1,2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。[2,1,2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。[3,1,2]存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构，链式存储结gj_o[4,1,3】度量算法效率可通过时间复杂度来进行。[5,1,3]设n为正整数，下面程序段中前置以记号颔语句的频度是n(n+1)/2。for(i=0;i<n;i++){for(j=0;j<n;j++)if(i+j==n-1)@a[i][j]=0;}[6,1,3】设n为正整数，试确定下列各程序段中前置以记号@勺语句的频度：i=1;k=0;while(i<=n-1){i++;@k+=10*i;//语句的频度是n-1。}⑵k=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)@k++;//语句的频度是n(n+1)/2。[7,3,2】线性表（ai,a2,…，an）有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：顺序存储密度较大;顺序存储利用率较高;顺序可以随机存取;链式不可以随机存取;链式插入和删除操作比较方便。[8,3,2】从一个长度为n的顺序表中删除第i个元素（1<i<n）时，需向前移动n-i个元素[9,3,2】带头结点的单链表Head为空的条件是Head->next=NULL。[10,3,2】在一个单链表中p所指结点（p所指不是最后结点）之后插入一个由指针s所指结点，应执行s->next=p->next;和p->next=二的操作。[11,3,2】在一个单链表中删除p所指结点时，应执行以下操作：q=p->next;p->data=p->next->data;p->next=p->next->next;free(q);[12,3,2】带头结点的单循环链表Head的判空条件是Head->next==Head；不带头结点的单循环链表的判空条件是Head==NULL[13,3,2】已知L是带表头结点的非空单链表，且P结点既然不首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P结点的直接前驱结点的语句序列是1012811414。b.删除结点P的语句序列是10127314qc.删除尾元结点的语句序列是911314。P=P->next;P->next=P;P->next=P->next->next;P=P->next->next;while(P!=NULL)P=P->next;while(Q->next!=NULL){P=Q;Q=Q->next};while(P->next!=Q)P=P->next;while(P->next->next!=Q)P=P->next;while(P->next->next!=NULL)P=P->next;Q=P;Q=P->next;P=L;L=L->next;free(Q);[14,3,3】对一个栈，给定输入的顺序是A、B、C,则全部不可能的输出序列有CAB[15,3,3】.在栈顶指针为HS的链栈中，判定栈空的条件是head->next==NULL[16,3,3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。voidconversion10_16(){InitStack(&s);scanf("％d,&N);while(N){Push(s,N%16);N=N/16;}while(!StackEmpty(s)){Pop(s,e);if(e<=9)printf("%d,e);elseprintf("%C,e-10+'A);}}/*conversion*/[17,3,4]若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是2和4。[18,3,4】堆栈和队列都是线性表，堆栈是后进先出的线性表，而队列是先进先出的线性表。[19,3,4]若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是2和4。[20,4,2】已知一棵树边的集合是{<a,d>,<d,c>,<d,j>,<e,a>,<f,g>,<d,b>,<g,h>,<g,i>,<e,f>}。那么根结点是e,结点b的双亲是d,结点a的子孙有bcdj,树的深度是4树的度是工,结点g在树的第3层。[21,4,3]从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。[22,4,3】满三叉树的第i层的结点个数为,深度为h时该树中共有3h-1结点[23,4,3】已知一棵完全二叉树有56个叶子结点，从上到下、从左到右对它的结点进行编号，根结点

为1号。则该完全二叉树总共结点有111个；有上层；第91号结点的双亲结点是45号；第63号结点的左孩子结点是32号。[24,4,3】下列表示的图中，共有5个是树；有3个是二叉树；有2个是完全二叉树。[25,4,4】[25,4,4】n个结点的二叉排序树的最大深度是n,最小深度为[log2n]+1[26,4,3】如果某二叉树的后序遍历序列是列的第一个字母是[26,4,3】如果某二叉树的后序遍历序列是列的第一个字母是I,最后一个字母是ABCDEFGHI中序遍历序列是ACBIDFEHG则其先序遍历序[27,4,3】下列二叉树的中序遍历序列是[27,4,3】下列二叉树的中序遍历序列是DBNGOAEC;后序遍历序列是DNIGBECA。[28,5,4]设HASH表的大小为n(n=10),HASH函数为h(x)=x%7,如果二次探测再散列方法Hi=(H(key)+di)mod10(di=12,22,32，…,)解决冲突，在HASH!中依次插入关键字{1,14,55,20,84,27}以后，关键字1、20和27所在地址的下标分别是1、7和5。插入上述6个元素的平均比较次数是2o[29,6,3]设无权图G的邻接矩阵为A,若(vi,vj)属于图G的边集合，则对应元素A[i][j]等于122、设无向图G的邻接矩阵为A,若A[i][j]等于0,则A皿i]等于0。[30,6,3]若一个图用邻接矩阵表示，则删除从第i个顶点出发的所有边的方法是矩阵第i行全部置为零。[31,6,2】设一个图G={V,{A}},V={a,b,c,d,e,f},A={<a,b>,<b,e>,<a,e>,<c,a>,<e,d>,<d,f>,<f,c>}。那么顶点e的入度是2；出度是1；通过顶点f的简单回路有二条；就连通性而言，该图是强连通图；它的强连通分量有J个；其生成树可能的最大深度是5。[32,7,1】排序过程一般需经过两个基本操作，它们是比较和移动。[33,7,2】在对一组关键字是(54,38,96,45,15,72,60,23,83)的记录进行直接插入排序时，当把第七个记录(关键字是60)插入到有序表时，为寻找插入位置需比较/次。[34,7,4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有希尔排序、快速排序、堆排序。二、综合题(选自教材《数据2^构》各章习题，采用word文件格式上传)[1,1,3】试分析下面一段代码的时间复杂度：if(A>B){for(i=0;i<N;i++)for(j=N*N;j>i;j--)A+=B;}else{for(i=0;i<N*2;i++)for(j=N*2;j>i;j--)A+=B;}答：ifA>B为真，则for语句的外循环N次，内循环为N(N-1)次，因此时间复杂度为O(N*N(N-1)),也就是N的三次方。ifA>B为假，则for语句的外循环2N次，内循环为N次，因此时间复杂度为O2N*N),也就是N的平方。整段取最大的，时间复杂度就是N立方。.100i[2,1,3】测试例1.3中秦九韶算法与直接法的效率差别。令f(X)1i〔Xi/i,计算f(1.1)的值。利用clock()函数得到两种算法在同一机器上的运行时间。答：直接法：0.1心s秦九韶算法：0.04心s[3,1,3】试分析最大子列和算法1.3的空间复杂度。答：算法1.3的基本思路是将原问题拆分成若干小型问题，分别解决后再将结果合而治之，用递归方法实现。算法1.3的负责度分析略有难度：若记整体时间复杂度为T(N),则函数DivideAndConquer中通过递归实现“分”的复杂度为2T(N/2),因为我们解决了2个长度减半的字问题。求跨分界线的最大子列和时，有两个简单的for循环，所用步骤一共不超过N,所以可以在O(N)时间完成。其他步骤都只需常熟0(1)时间。综上分析则有递推式:T(1)=0(1);T(N)=2T(N/2)+O(N)=2[2T((N/2)/2+O(N/2)]+O(N)=22T(N/22)+2O(N)=…=2KT(N/2k)+kO(N)当不断对分直到N/2k=1,即2k=此寸，就得到T(N)=NT(1)+logN*O(N)=O(NlogN)。此算法比算法1.2又快了一些，当N=104时，效果会非常明显。但是这仍然不是最快的算法。[4,1,3】试给出判断N是否为质数的O(JN)的算法。答：intsushu(intN){inti;intflag=1;if(N==1)returnfalse;//1既不是合数也不是质数if(N==2)returntruefor(i=2;i<=sqrt(N);i++){if(N%i==0){flag=0；break;}returnflag;)[5,2,2】请编写程序，输入整数n和a,输出S=a+aa+aaa+・・+aa…a(n个a)的结果。答：#include"stdio.h"intmain(){inta,b,n,i,s=0;scanf("%d%d",&a,&n);b=a;for(i=1;i<=n;i++){s+=a;a=a*10+b;)printf("%d'n",s);)[6,2,3】请编写递归函数，输出123..n的全排列(n小于10),并观察n逐步增大时程序的运行时间答：#include<stdio.h>#defineN8intn=0;voids*a,int*b)(intm;m=*a;*a=*b;*b=m;)voidperm(intlist[],intk,intm)(inti;if(k>m)(for(i=0;i<=m;i++)printf("%d",list[i]);printf("\n");n++;)elsefor(i=k;i<=m;i++)(s[k],&list[i]);perm(list,k+1,m);sist[k],&list[i]);}}}intmain()(intlist[N];intnum,i=0;printf("Pleaseinputanum:");scanf("%d",&num);while(num!=0)(list[i]=num%10;num=num/10;i++;perm(list,0,i-1);printf("total:%d\n",n);return0;)[7,3,2]给定一个顺序存储的线性表L而且小于max的元素。答：#include<stdio.h>#include<stdlib.h>#include<math.h>typedefintElemType;typedefstructLNode(a1，a2,,an),请设计一个算法删除所有值大于min{ElemTypedata;/*structLNode*next;/*)LNode;/*LNode*L;/*数据子域*/指针子域*/结点结构类型*/函数声明*/LNode*creat_L();返回值格式变为空返回值格式变为空voiddelete_L(LNode*L,inti);//*/*//*建立线T链表*/LNode*creat_L()(LNode*h,*p,*s;ElemTypex;h=(LNode*)malloc(sizeof(LNode));h->next=NULL;p=h;printf("输入一串数字(以-1结束)scanf("%d",&x);/*while(x!=-1)/*(s=(LNode*)malloc(sizeof(LNode));

/*分配头结点*/:\ndata=");输入第一个数据元素输入-1,结束循环*//*分配新结点*/s->data=x;s->next=NULLp->next=s;p=s;printf("data=");输入下一个数据*/scanf("%d",&x);输入下一个数据*/}return(h);}/*creat_L*/

/*输出单链表中的数据元素*/voidout_L(LNode*L)(LNode*p;p=L->next;printf("\n数据是:");while(p!=NULL)(printf("%5d",p->data);p=p->next;}}/*out_link*//*删除大于x小于y的值*/voiddelete_L(LNode*L,inta,intb)(LNode*p,*q;p=L;q=p;链表为空");链表为空");if(p==NULL)printf("ERROR:while(p!=NULL)(if((p->data>a)&&(p->data<b))(q->next=p->next;free(p);p=q->next;}else(q=p;p=p->next;}}}/*delete_L*/voidmain()(inta,bL=creat_L();out_L(L);printf("\n\n请输入你要删除的元素的范围min和max:\n");scanf("%d%d",&a,&b);delete_L(L,a,b);out_L(L);printf("\n");}/*main*/[8,3,2]给定一个顺序存储的线性表l=(a1,a2,,an),请设计一个算法查找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。答：#include<iostream>#include〈algorithm〉usingnamespacestd;#defineMAXN1003intA[MAXN];intdp[MAXN];//动态规划思想O(n〃2)intmain()(intn,i,j,k;cin>>n;for(i=1;i<=n;i++)cin>>A[i];dp[1]=1；//有n个阶段for(i=2;i<=n;i++)(dp[i]=1；//每个阶段只有1个状态//每个状态有i种决策，以得出以元素i结尾的最长递归子序列的长度for(j=i-1;j>=0;j--)(if(A[i]>A[j])dp[i]=max(dp[i],dp[j]+1);}}intmaximum=dp[1];for(i=2;i<=n;i++)maximum=max(maximum,dp[i]);cout<<maximum;}[9,3,3】如果有1、2、3、4、5按顺序入栈，不同的堆栈操作(pop,push)顺序可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？答:共有34种不同的输出序列TOC\o"1-5"\h\z12345123541243512543132451325414325154322134521435215432314523154234152345123541243152435124531254313214532154324153245132541342153425134521354214321543251435214532154321[10,3,2】请编写程序将中缀表达式转换为后缀表达式。答：#include<iostream>#include<stack>#include<string>usingnamespacestd;intprior(charop){if(op=='+'||op=='-')return1;if(op=='*'110P=='/')return2;return0;stringmiddletolast(stringmiddle)(stack<char>op;stringans;for(inti=0;i<middle.size();i++)(charc=middle[i];if(c>='0'&&c<='9')(ans.append(1,c);)else(if(c=='(')op.push('(');else(if(c==')')while(op.top()!="(')(ans.append(1,op.top());op.pop();)op.pop();)else(if(op.empty())(op.push(c);)else(if(prior(c)>prior(op.top()))op.push(c);else(while(!op.empty()&&prior(c)<=prior(op.top()))ans.append(1,op.top());op.pop();)op.push(c);))))))while(!op.empty())(ans.append(1,op.top());op.pop();)returnans;)intmain()(stringmdata,res;cin>>mdata;res=middletolast(mdata);for(inti=0;i<res.size();i++)(if(i==0)cout<<res[i];elsecout<<''<<res[i];}cout<<endl;return0;}[11,4,3】设二叉树的存储结构如下:12345678910Lchild00237580101dataJHFDBACEGIRchild0009400000其中根结点的指针值为6,Lchild,Rchild分别为结点的左、右孩子指针域，data为数据域画出二叉树的逻辑结构。答：21B写出该树的前序、中序和后序遍历的序歹上答:前序序歹U:ABCEDFHGI中序序列：ECBHFDJIGA后序序列：ECHFJIGDBA[12,4,4】可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任意可以生成如上二叉排序树的关键字的初始排列有30种可以生成如上二叉排序树的关键字的初始排列有30种任写4个序列如下:(5,7,6,4,2,1,3)TOC\o"1-5"\h\z(5,7,6,4,2,3,1)(5,4,2,3,7,6,1)(5,4,2,1,7,6,3)[13,4,5]给定关键字序列(11、7、16、4、22、13、5),请回答:6分)；画出依次插入到一棵空的二叉排序树后的最终二叉树(6分)；答:答:4分)；{a,b,c,d,e,f,g),110,111,00,0111,010}字符的哈夫曼编码依次为4分)；{a,b,c,d,e,f,g),110,111,00,0111,010}字符的哈夫曼编码依次为{0110,10,(2)画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符;答:若这些字符在文本中出现的频率分别为:{3,35,13,15,20,5,9},求该哈夫曼树的带权路径长度。答：WPL=4*(3+5)+3*(9+13+15)+2*(20+35)=253[15,5,3】用公式5.6计算一下你的身份证号码的散列值是多少。答：924300[16,5,4】设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为：H(key)=key%17,采用平方探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表。答：首先将各个数除以17取余数：(6,2,7,1,2,7,7,6)可见20,85与46冲突，58与71冲突。将7+1再对13取余，直到无冲突，类似的6+1对13取余，最后可得H(71)=6;H(28)=2;H(46)=7;H(14)=1;H(2)=3;H(20)=8;H(85)=9;H(58)=10;哈希表存储结构：012345678910142827146208558平均查找长度=(1X4+2X2+3X1+4X1)/8=15/8[17,5,4】将关键字序列(7,8,30,11,18,9,14)散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组。处理冲突采用线性探测法，散列函数为：H(key)=(keyX3)modTableSize,要求装入因子为0.7。答:(1)由装载因子0.7,数据总数7个一存储空间长度为10-P=10所以，构造的散列表为：H(7)=(7X3)MOD10=101234567893071411818.9..(2)查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.2[18,6,3】已知一个无向图的顶点集为{V。，Vi,…，V7},其邻接矩阵如下所示:V)/1011000TOC\o"1-5"\h\zV01000100M10000010M11000010(1)画出该图的图形;答：(2)给出从V0出发的深度优先遍历序和广度优先遍历序。答：深度优先序歹UV0,V1,V2,V5,V4,V6,V3,V7广度优先序歹UV0V1V3V4V2V6V5V7[19,6,3】已知有向图如右图所示，请给出该图的每个顶点的入度和出度；邻接矩阵；邻接表；逆邻接表；各个强连通分量。答：(1)各顶点的入度和出度如下：①：3/0②2/2③1/2④1/2⑤2/1⑥2/3(2)邻接矩阵如下:123456101000002100100300001

4001011511000006110010(3)123456(4)123456(5)①【20,邻接表如下:逆邻接表如下:邻接表如下:逆邻接表如下:有三个强连通分量6,3】试利用Dijkstra算法求下图在从顶点A到其它顶点的最短距离及对应的路径，写出计算过程中各步状态答：1c:22c:2f:63程中各步状态答：1c:22c:2f:63c:2f:6e:104c:2f:6e:10d:115c:2f:6e:10d:11g:146c:2f:6e:10d:11g:14b:15[21,6,3]给出如下图所示的具有7个结点的网G。请:画出该网的邻接矩阵；采用Prim算法，从4号结点开始，给出该网的最小生成树小生成树的生成示意图)。(画出Prim算法的执行过程及最存入前驱结点数组//初始起点的数组voidprim(MGraphg,intv0,int&sum){intlowcost[MAXSIZE],vset[MAXSIZE];intv,pre[MAXSIZE];//pre口inti,j,k,min;v=v0;for(i=1;i<=g.n;i++){lowcost[i]=g.edges[v0][i];//lowcost[]pre[i]=v0;vset[i]=0;vset[v0]=1;sum=0;for(i=1;imin=INF;for(j=1;j<=g.n;j++){if(vset[j]==0&&lowcost[j]min=lowcost[j];k=j;}}vset[k]=1;//将此结点并入到所够造的生成树中v=k;if(min!=INF){printf("边的起点为：％d终点为：％d权值为％d\n",pre[v],v,min);sum+=min;}else{break;}for(j=1;j<=g.n;j++){//并入新结点后修改剩下的结点到生成树的权值if(vset[j]==0&&g.edges[v][j]lowcost[j]=g.edges[v][j];pre[j]=v;//并记其下全趋结点}}}}[22,7,4]给定数组{48,25,6,90,17,84,62,48,27,96,49,72,17},请分别用简单选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。答：简单选择排序：6,25,48,90,17,84,62,48,27,96,49,72,176,17,48,90,25,84,62,48,27,96,49,72,176,17,17,90,25,84,62,48,27,96,49,72,48

6,17,17,25,9084,62,48,27,96,49,72,486,17,17,25,27,84,62,48,9096,49,72,486,17,17,25,27,48628490964972486171725274848849096497262TOC\o"1-5"\h\z61717252748484990968472626171725274848496296847290617172527484849627284969061717252748484962728496906171725274848496272849096直接插入排序62548901784624827966254890176254890178462482796625489017846248279662548179084624827966172548908462482796617254884906248279661725486284904827966172548486284902796617252748486284909661725274848628490964972174972497217497217497217497217497217497217