北邮算法与数据结构习题参考答案

北邮算法与数据结构习题参考答案PAGE1.作业参考答案一、（带头结点）多项式乘法C=A×B：voidPolyAdd(list&C,listR)//R为单个结点{p=C;while((！p->next)&&(p->next->exp>R->exp))p=p->next;if((p->next)||(p->next->exp<R->exp)){R->next=p->next;p->next=R;}else{p->next->inf+=R->inf;deleteR;if(!p->next->inf){R=p->next;p->next=R->next;deleteR;}}}voidPolyMul(listA,listB,list&C){C=newstructnode;C->next=NULL;q=B->next;While(q){p=A->next;while(p){r=newstructnode;r->exp=p->exp+q->exp;r->inf=p->inf*q->inf;PolyAdd(C,r);p=p->next;}q=q->next;}}二、梵塔的移动次数：已知移动次数迭代公式为：M(n)=2M(n-1)+1初值为：M(0)=0则：M(n)=2(2M(n-2)+1)+1=4M(n-2)+3=8M(n-3)+7=2iM(n-i)+2i–1若n=i,则M(n-n)=0,故：M(n)=2nM(n-n)+2n–1北邮算法与数据结构习题参考答案全文共15页，当前为第1页。=2n–北邮算法与数据结构习题参考答案全文共15页，当前为第1页。所以，梵塔的移动次数为2n–1次。三、简化的背包问题：voidPack(intm,inti,intt)//初始值为:11t{for(k=i;k<=n;k++){solution[m]=weight[k];if(t==weight[k]){for(j=1;j<=m;j++)cout<<solution[j];cout<<endl;}elseif(t>weight[k])Pack(m+1,k+1,t-weight[k]);}}四、判断括号是否配对：intCorrect(strings){Inistack(Q);for(i=0;s[i]==‘=’;i++)//表达式以‘=’结束{switch(s[i]){case‘(’:case‘[’:case‘{’:Push(Q,s[i]);break;case‘)’:case‘]’:case‘}’:if(Empty(Q))return0;t=Pop(Q);if(!Matching(t,s[i]))return0;}}if(!Empty(Q))return0;return1;}北邮算法与数据结构习题参考答案全文共15页，当前为第2页。五、堆栈可能的输出：北邮算法与数据结构习题参考答案全文共15页，当前为第2页。124313241342142314322143231423412413243131243142321432413412342141324213423143124321六、用两个堆栈实现一个队列：intFullQ(){if(Full(S1)&&!Empty(S2))return1;return0;}intEmptyQ(){if(Empty(S1)&&Empty(S2))return1;return0;}voidEnqueue(elemtypex){if(Full(S1))if(Empty(S2))while(!Empty(S1))Push(S2,Pop(S1));if(!Full(S1))Push(S1,x);}elemtypeDequeue(){if(Empty(S2))while(!Empty(S1))Push(S2,Pop(S1));if(!Empty(S2))returnPop(S2);}七、生成新串与字符第一次出现位置：intIndex(stringS,stringT){for(i=1;i+Len(T)-1<=Len(S);i++)ifEqual(Sub(S,I,Len(T)),T)returni;return0;}voidCreatNewStr(stringS,stringT,stringR,arrantP){R=“”;j=0;for(i=1;i<=Len(S);i++)北邮算法与数据结构习题参考答案全文共15页，当前为第3页。{北邮算法与数据结构习题参考答案全文共15页，当前为第3页。ch=Sub(S,i,1);if(!Index(T,ch)&&!Index(R,ch)){R=Concat(R,ch);P[j++]=i;}}}八、块链字符串插入：{为避免字符串内部块间大量的数据移动，最好的方法是定义两种字符串中不出现的字符作为空标记和串结束标记，如‘#’和‘$’；也可只使用空标记，串结束以块尾指针为空表示，其算法如下：voidInsert(stringS,stringT,charch)//设块大小为m{i=0;p=T;while((p->next)&&(!i)){for(j=1;j<=m;j++)if(p->str[j]==ch)i=j;if(!i)p=p->next;}if(!i)for(j=1;j<=m;j++)if(p->str[j]==ch)i=j;if(!i)p->next=S;else//S插在T后{//ch所在结点分裂，S插在T中分裂的两结点间q=newstructnode;q->str=p->str;q->next=p->next;for(j=i;j<=m;j++)p->str[j]=‘#’;p->next=S;for(j=1;j<i;j++)q->str[j]=‘#’;p=S;while(p->next)p=p->next;p->next=q;}}九、上三角矩阵的存储：k=(i-1)*n+j-i*(i-1)/2=(2n-i+1)*i/2+j-nf1=(2n-i+1)*i/2f2=jc=-n十、循环右移k位：12345678（n=8,k=3）78123457654321北邮算法与数据结构习题参考答案全文共15页，当前为第4页。北邮算法与数据结构习题参考答案全文共15页，当前为第4页。voidExch(arrtypeA,intst,inted){for(i=st;i<=(st+ed)/2;i++)A[i]←→A[ed-i+1];}voidShift(arrtypeA,intk,intn){Exch(A,1,n);Exch(A,1,k);Exch(A,k+1,n)}十一、广义表运算结果：1、(a,b)2、((c,d))3、(c,d)4、(b)5、b6、(d)十二、利用广义表运算取出c原子：Head(Tail(Tail(L1)))Head(Head(Tail(L2)))Head(Head(Tail(Tail(Head(L3)))))Head(Head(Head(Tail(Tail(L4)))))Head(Head(Tail(Tail(L5))))Head(Tail(Head(L6)))Head(Head(Tail(Head(Tail(L7)))))Head(Head(Tail(Head(Tail(L8)))))n-2+kkn-2+kk1、kn-12、n=1无父结点，否则为3、(n-1)k+1+i4、(n-1)Modk≠0十四、叶子结点数目：mmi=1n0=∑(i-1)ni+1i=1北邮算法与数据结构习题参考答案全文共15页，当前为第5页。十五、找最近共同祖先：北邮算法与数据结构习题参考答案全文共15页，当前为第5页。bitptrForefather(bitptrroot,bitptrp,bitptrq){find=0;//0p、q都未找到;>0找到一个；-1都找到了INIT(ff);{定义一个数组ff用于记录查找路径}Fff(root,p,q,0,ft);returnft;}voidFff(bitptrroot,bitptrp,bitptrq,intm,bitptr&ft){if(root&&(find>=0)){m=m+1;if((root==p)||(root==q))if(!find)find=m-1;else{ft=ff[find];find=-1;}ff[m]=root;Fff(root->lc,p,q,m,ft);Fff(root->rc,p,q,m,ft);if(m==find)find=m-1;}}十六、求树的直径等：voidHigh(bitptrt,int*hi,Arrtypepath){*hi=0;INIT(p);{定义数组p动态存储路径}Hhh(t,1,hi,path);}voidHhh(bitptrt,intlevel,int*hi,Arrtypepath){if(t){p[level]=t->data;if(!t->lc&&!t->rc)if(level>hi){hi=level;北邮算法与数据结构习题参考答案全文共15页，当前为第6页。for(i=1;i<=level;i++)path[i]=p[i];北邮算法与数据结构习题参考答案全文共15页，当前为第6页。}Hhh(t->lc,level+1,hi,path);Hhh(t->rc,level+1,hi,path);}}十七、输出中缀表达式并加上括号：voidExpout(treet){if(!t){if(t->lchild)if(((t->lchild->data==‘+’)||(t->lchild->data==‘-’))&&((t->data==‘*’)||(t->data==‘/’))){cout<<‘(’;Expout(t->lchild);cout<<‘)’;}elseExpout(t->lchild);cout<<t->data);if(t->rchild)if((t->data==‘*’)||(t->data==‘/’)){cout<<‘(’;Expout(t->rchild);cout<<‘)’;}elseExpout(t->rchild);}}十八、建立二叉树：voidCreat_bintree(bitptr&t,inti,strings){//i为输入字符串的当前指针，初值为1}if(s[i]==’#’){t=NULL;i++;}else{t=newstructnode;t->data=s[i];i++;if((i>Length(s))||(s[i]!=‘(’)){北邮算法与数据结构习题参考答案全文共15页，当前为第7页。t->lc=t->rc=NULL;北邮算法与数据结构习题参考答案全文共15页，当前为第7页。return;}i++;{去左括号}Creat_bintree(t->lc,i,s);{建左子树}i++;{去逗号}Creat_bintree(t->rc,i,s);{建右子树}i++;{去右括号}}}十九、按凹入表方式打印树：voidPrint_tree(bitptrt){Prt(t,1)}voidPrt(bitptrt,intlevel){if(t){Prt(t->rc,level+1);for(inti=1;i<=level;i++)cout<<‘’;cout<<t->data;Prt(t->lc,level);}}二十、判断是否存在长度为k的简单路经：voidSearchPath(intv,intvt,intk,intm){//存储结构可选用邻接矩阵，路径从vs出发，到vt结束，长度为kvisited[v]=TRUE;P[m]=v;if(v==vt){if(m==k+1){for(i=1;i<=m;i++)cout<<P[i];cout<<endl;}北邮算法与数据结构习题参考答案全文共15页，当前为第8页。}else北邮算法与数据结构习题参考答案全文共15页，当前为第8页。{w=FirstAdj(v);while(w){if(!visited[w])SearchPath(w,vt,k,m+1);w=NextAdj(v,w);}}visited[v]=FALSE;}二十一、求所有简单回路：voidSearchCycle(intv,intm){//存储结构可选用邻接矩阵visited[v]=TRUE;P[m]=v;w=FirstAdj(v);while(w){if(!visited[w])SearchCycle(w,m+1);else{for(j=1;P[j]==w;j++);for(i=j;i<=m;i++)cout<<P[i];cout<<w<<endl;}w=NextAdj(v,w);}visited[v]=FALSE;}二十二、求最小代价生成树：abcdefgabcdefgh222211120∞2∞∞∞∞3∞01∞∞∞∞∞21024∞∞∞∞∞2012∞∞∞∞41021北邮算法与数据结构习题参考答案全文共15页，当前为第9页。∞∞∞∞2203北邮算法与数据结构习题参考答案全文共15页，当前为第9页。∞∞∞∞∞130abcdabcdefgh222211122abcdefgh123456783∧3124∧2134∧12231526∧442617∧24451728∧152628∧3617∧3二十三、求关键路经和最短路经：1、abcdefghive:02361110131417vl:04361110131517关键路经为：acdfegi2、a→bcdefghi2(ab)3(ac)∞∞∞∞∞∞3(ac)4(abd)∞∞∞∞∞4(abd)∞∞∞∞∞7(abde)8(abdf)∞∞∞8(abdf)9(abdeg)∞∞9(abdeg)9(abdfh)∞9(abdfh)13(abdegi)11(abdfhi)二十四、边界标识法：056056080201170213053046201670559av北邮算法与数据结构习题参考答案全文共15页，当前为第10页。北邮算法与数据结构习题参考答案全文共15页，当前为第10页。av0av0560802017021302640462二十五、按访问频度查找：listSearch(listH,keytypeK){p=H;q=NULL;while(p->next&&!q){if(p->next->key==K){q=p->next;q->freq++;while((H!=p)&&(H->next->freq>=q->freq))H=H->next;if(H!=p){p->next=q->next;q->next=H->next;H->next=q;}}p=p->next;}returnq;}北邮算法与数据结构习题参考答案全文共15页，当前为第11页。北邮算法与数据结构习题参考答案全文共15页，当前为第11页。二十六、判断是否二叉排序树：intBST(bitptrt,bitptr&p){if(！t)return1;L=BST(t->lc,p);D=1;if(p&&p->data>t->data)elseD=0;p=t;R=BST(t->rc,p);returnL&&D&&R;}intBinarySortTree(bitptrt){p=NULL;returnBST(t,p);}二十七、建立2-3树：302050302050203020502030526068502030526068502060305230205052插入52插入60插入685260702032526070203260705268203052306820506070插入70删除50删除68北邮算法与数据结构习题参考答案全文共15页，当前为第12页。北邮算法与数据结构习题参考答案全文共15页，当前为第12页。二十八、散列表：（1）：012345678910111213141516AprAugDecFebJanMarMayJunJulSepOctNov1+2+1+1+1+1+2+4+5+2+5+631ASL成功=——————————————=——12125+4+3+2+1+9+8+7+6+5+4+3+2+130ASL不成功=————————————————=——147（2）：012345678910111213141516∧∧∧∧∧∧∧∧∧∧AprDecFebJanMarOctSepAugJunMayNovJul1+2+1+1+1+2+3+1+2+1+2+19ASL成功=——————————————=——1263+1+2+2+1+4+3+3+1+2+1+1+1+113ASL不成功=————————————————=——147ASL不成功=12/14（与空指针比较次数不算）？二十九、证明快速排序退化时的时间复杂度：当待排序列有序时，有T(n)=T(n–1)+n–1=T(n–2)+2*n–3=T(n–3)+3*n–6…北邮算法与数据结构习题参考答案全文共15页，当前为第13页。=T(n–i)+i*n–i*(i+1)/2北邮算法与数据结构习题参考答案全文共15页，当前为第13页。…=T(n–n)+n*n–n*(n+1)/2=n*(n–1)/2故，此时快速排序的时间复杂度为O(n2)。三十、单链表存储结构的简单插入排序：voidInsertSort(pointer&r){H=newstructnode;H->next=r;r=r->next;H->next->next=NULL;while(r){p=r;r=r->next;q=H;while(q->next&&(p->data>q->next->data))q=q->next;p->nex