数据结构与算法离线作业【2014春】

PAGE1PAGE28浙江大学远程教育学院《数据结构与算法》课程离线作业姓名：学号：7141年级：2014春学习中心：华家池—————————————————————————————一、填空题：【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。【2，1，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构__，链式存储结构___。【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为正整数，试确定下列各程序段中前置以记号@的语句的频度:(1)i=1;k=0;while(i<=n-1){i++;@k+=10*i;//语句的频度是________n-1______________。}(2)k=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)@k++;//语句的频度是____n(n+1)/2__________________。}【7，3，2】线性表(a1，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=___s_____的操作。【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，3】已知L是带表头结点的非空单链表,且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。a.删除P结点的直接前驱结点的语句序列是______1012811414__________________________。b.删除结点P的语句序列是_______10127314______________________。c.删除尾元结点的语句序列是_911314_________________________。(1)P=P->next;(2)P->next=P;(3)P->next=P->next->next;(4)P=P->next->next;(5)while(P!=NULL)P=P->next;(6)while(Q->next!=NULL){P=Q;Q=Q->next};(7)while(P->next!=Q)P=P->next;(8)while(P->next->next!=Q)P=P->next;(9)while(P->next->next!=NULL)P=P->next;(10)Q=P;(11)Q=P->next;(12)P=L;(13)L=L->next;(14)free(Q);【14，3，3】对一个栈，给定输入的顺序是A、B、C，则全部不可能的输出序列有不可能得到的输出序列有CAB。【15，3，3】.在栈顶指针为HS的链栈中，判定栈空的条件是head->next==NULL。【16，3，3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。（每空2分）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，树的度是3，结点g在树的第3层。【21，4，3】从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本的目的是采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。【22，4，3】满三叉树的第i层的结点个数为3i-1，深度为h时该树中共有3h-1结点。【23，4，3】已知一棵完全二叉树有56个叶子结点，从上到下、从左到右对它的结点进行编号，根结点为1号。则该完全二叉树总共结点有___111_____个；有____7___层；第91号结点的双亲结点是___45____号；第63号结点的左孩子结点是________号。【24，4，2】下列表示的图中，共有___5____个是树；有___3____个是二叉树；有__2____个是完全二叉树。【25，4，3】如果某二叉树的后序遍历序列是ABCDEFGHI，中序遍历序列是ACBIDFEHG，则其先序遍历序列的第一个字母是I，最后一个字母是G。【26，4，4】n个结点的二叉排序树的最大深度是n，最小深度为[log2n]+1。【27，4，3】下列二叉树的中序遍历序列是____DBNGOAEC_______;后序遍历序列是_______DNOGBECA_______________________________。【28，5，3】设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个元素的平均比较次数是2。【29，6，3】设无权图G的邻接矩阵为A，若（vi,vj）属于图G的边集合，则对应元素A[i][j]等于1，设无向图G的邻接矩阵为A，若A[i][j]等于0，则A[j][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的简单回路有2条；就连通性而言，该图是强连通图；它的强连通分量有1个；其生成树可能的最大深度是5。【32，10，1】排序过程一般需经过两个基本操作，它们是比较和移动。【33，10，2】在对一组关键字是（54,38,96,45,15,72,60,23,83）的记录进行直接插入排序时，当把第七个记录（关键字是60）插入到有序表时，为寻找插入位置需比较3次。【34，10，4】插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基数排序方法中，不稳定的排序方法有希尔排序、快速排序、堆排序。

二、综合题（选自教材《数据结构》各章习题，采用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-N=N（N-1）次，因此时间复杂度为O(N*N（N-1）)，也就是N的三次方。IfA>B为假，则for语句的外循环2N次，内循环为2*N-N=N次，因此时间复杂度为O（2N*N），也就是N的平方。整段取大的，时间复杂度就是N立方。【2，1，3】测试例1.3中秦九韶算法与直接法的效率差别。令，计算的值。利用clock()函数得到两种算法在同一机器上的运行时间。直接法：0.1μs秦九韶算法：0.04μs【3，1，3】试分析最大子列和算法1.3的空间复杂度。【4，1，3】试给出判断是否为质数的的算法。intsushu(intN){inti;intflag=1;if(N==1)returnfalse;if(N==2)returntrue;for(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;voidswap(int*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++;}else{for(i=k;i<=m;i++){swap(&list[k],&list[i]);perm(list,k+1,m);swap(&list[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=(,,,)，请设计一个算法删除所有值大于min而且小于max的元素。#include<stdio.h>#include<stdlib.h>#include<math.h>typedefintElemType;typedefstructLNode{ElemTypedata;/*数据子域*/structLNode*next;/*指针子域*/}LNode;/*结点结构类型*/LNode*L;/*函数声明*/LNode*creat_L();voiddelete_L(LNode*L,inti);//返回值格式变为空/*建立线性链表*/LNode*creat_L(){LNode*h,*p,*s;ElemTypex;h=(LNode*)malloc(sizeof(LNode));/*分配头结点*/h->next=NULL;p=h;printf("输入一串数字（以-1结束）:\ndata=");scanf("%d",&x);/*输入第一个数据元素*/while(x!=-1)/*输入-1，结束循环*/{s=(LNode*)malloc(sizeof(LNode));/*分配新结点*/s->data=x;s->next=NULL;p->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;p=p->next;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,b;L=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");}【8，3，2】给定一个顺序存储的线性表L=(,,,)，请设计一个算法查找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。#include<iostream>#include<algorithm>usingnamespacestd;#defineMAXN1003intA[MAXN];intdp[MAXN];intmain(){intn,i,j,k;cin>>n;for(i=1;i<=n;i++)cin>>A[i];dp[1]=1;for(i=2;i<=n;i++){dp[i]=1;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）顺序可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？1、2、3、4、5已经在栈中，那最后输出的是由尾到头：5、4、3、2、1。后进先出。【10，3，2】请编写程序将中缀表达式转换为后缀表达式。#include<iostream>#include<stack>#include<string>usingnamespacestd;intprior(charop){if(op=='+'||op=='-')return1;if(op=='*'||op=='/')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为数据域。画出二叉树的逻辑结构。写出该树的前序、中序和后序遍历的序列。前序：ABCEDFHGIJ中序：ECBHFDJIGA后序：ECHFJIGDBA【12，4，4】可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任意4个。【13，4，5】给定关键字序列（11、7、16、4、22、13、5），请回答：（1）画出依次插入到一棵空的二叉排序树后的最终二叉树（6分）；（2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果（4分）；111171642213577111516422133【14，4，6】假设一个文本使用的字符集为{a,b,c,d,e,f,g},字符的哈夫曼编码依次为{0110，10，110，111，00，0111，010}。（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符；egegafbcd0101（2）若这些字符在文本中出现的频率分别为：{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平均查找长度=（1×4+2×2+3×1+4×1）/8=15/8【17，5，4】将关键字序列（7，8，30，11，18，9，14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组。处理冲突采用线性探测法，散列函数为：H（key）=（key×3）modTableSize，要求装入因子为0.7。由装载因子0.7，数据总数7个→存储空间长度为10→P=10所以，构造的散列表为：01234567893071411818.9..H（7）=（7×3）MOD10=1查找成功的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】已知一个无向图的顶点集为{V0，V1，…，V7}，其邻接矩阵如下所示：V001011000V110101000V201000100V310000010V411000010V500100000V600011001V700000001(1)画出该图的图形；223104756(2)给出从V0出发的深度优先遍历序和广度优先遍历序。深度优先序列V0,V1,V2,V5,V4,V6,V3,V7广度优先序列V0V1V3V4V2V6V5V7【19，6，3】已知有向图如右图所示，请给出该图的每个顶点的入度和出度；邻接矩阵；邻接表；逆邻接表；各个强连通分量。各顶点的入度和出度如下：①：3/0②2/2③1/2④1/2⑤2/1⑥2/3邻接矩阵如下：123456100000021001003010001400101151000006110010邻接表如下：逆邻接表有三个强连通分量【20，6，3】试利用Dijkstra算法求下图在从顶点A到其它顶点的最短距离及对应的路径，写出计算过程中各步状态。 终点DistbcdefgSK＝115(a,b)2(a,c)12(a,d){a,c}K＝215(a,b)12(a,d)10(a,c,e)6(a,c,f){a,c,f}K＝315(a,b)11(a,c,f,d)10(a,c,e)16(a,c,f,g){a,c,f,e}K＝415(a,b)11(a,c,f,d)16(a,c,f,g){a,c,f,e,d}K＝515(a,b)14(a,c,f,d,g){a,c,f,e,d,g}K＝615(a,b){a,c,f,e,d,b}【21，6，3】给出如下图所示的具有7个结点的网G。请：画出该网的邻接矩阵；采用Prim算法，从4号结点开始，给出该网的最小生成树（画出Prim算法的执行过程及最小生成树的生成示意图）。00123645164432315725voidprim(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}，请分别用简单选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。简单选择排序：48,25,6,90,17,84,62,48,27,96,49,72,176,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,486,17,17,25,90,84,62,48,27,96,49,72,486,17,17,25,27,84,62,48,90,96,49,72,486,17,17,25,27,84,62,48,90,96,49,72,486,17,17,25,27,48,62,84,90,96,49,72,486,17,17,25,27,48,48,84,90,96,49,72,626,17,17,25,27,48,48,49,90,96,84,72,626,17,17,25,27,48,48,49,62,96,84,72,906,17,17,25,27,48,48,49,62,72,84,96,906,17,17,25,27,48,48,49,62,72,84,90,96不稳定简单插入排序48,25,6,90,17,84,62,48,27,96,49,72,1725,48,6,90,17,84,62,48,27,96,49,72,176，25,48，90,17,84,62,48,27,96,49,72,176，17，25,48，90,84,62,48,27,96,49,72,176，17，25,48，90,84,62,48,27,96,49,72,176，17，25,48，84,90,62,48,27,96,49,72,176，17，25,48，62,84,90,48,27,96,49,72,176，17，25,48，48,62,84,90,27,96,49,72,176，17，25,27,48，48,62,84,90,96,49,72,176，17，25,27,48，48,62,84,90,96,49,72,176，17，25,27,48，48,49,62,84,90,96,72,176，17，25,27,48，48,49,62,72,84,90,96,176，17，,1725,27,48，48,49,62,72,84,90,96稳定。冒泡排序：48,25,6,90,17,84,62,48,27,96,49,72,1725,6,48,17,84,90,48,27,62,49,72,17，966,25,17,48,84,90,27,48,49,62,17，72,966,17,25,48,84,27,48,49,62,17，72,90,966,17,25,48,27,48,49,62,17，72,84,90,966,17,25,27,48,48,49,17，62,72,84,90,966,17,25,27,48,48,17，49,62,72,84,90,966,17,25,27,48,17，48,49,62,72,84,90,966,17,25,27,17，48,48,49,62,72,84,90,966,17,25,17，27,48,48,49,62,72,84,90,966,17,17，25,27,48,48,49,62,72,84,90,96稳定。【23，7，4】给定数组{48,25,6,90,17,84,62,48,27,96,49,72,17}，请分别用堆排序、快速排序和归并排序分别进行排序，写出排序过程中每一步操作后的结果，分析各自比较和交换的次数，以及排序结果是否稳定。堆排序：（差不多乱写了）48,25,6,90,17,84,62,48,27,96,49,72,1748,25,6,90,17,84,62,48,27,17,49,72，9648,25,6,72,17,84,62,48,27,17,49,90，9648,25,6,72,17,49,62,48,27,17,84,90，9648,25,6,17,17,49,62,48,27,72,84,90，9648,25,6,17,17,49,27,48,62,72,84,90，9648,25,6,17,17,48,27,49,62,72,84,90，9627,25,6,17,17,48,48,49,62,72,84,90，9617,25,6,17,27,48,48,49,62,72,84,90，9617,17,6,25,27,48,48,49,62,72,84,90，9617,6,17,25,27,48,48,49,62,72,84,90，966,17,17,25,27,48,48,49,62,72,84,90，96不稳定。快速排序：48,25,6,90,17,84,62,48,