北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案

北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案PAGE1.作業(yè)參考答案一、（帶頭結(jié)點(diǎn)）多項(xiàng)式乘法C=A×B：voidPolyAdd(list&C,listR)//R為單個(gè)結(jié)點(diǎn){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;}}二、梵塔的移動(dòng)次數(shù)：已知移動(dòng)次數(shù)迭代公式為：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北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第1頁。=2n–北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第1頁。所以，梵塔的移動(dòng)次數(shù)為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]);}}四、判斷括號(hào)是否配對：intCorrect(strings){Inistack(Q);for(i=0;s[i]==‘=’;i++)//表達(dá)式以‘=’結(jié)束{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;}北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第2頁。五、堆?？赡艿妮敵觯罕编]算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第2頁。124313241342142314322143231423412413243131243142321432413412342141324213423143124321六、用兩個(gè)堆棧實(shí)現(xiàn)一個(gè)隊(duì)列：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);}七、生成新串與字符第一次出現(xiàn)位置：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++)北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第3頁。{北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第3頁。ch=Sub(S,i,1);if(!Index(T,ch)&&!Index(R,ch)){R=Concat(R,ch);P[j++]=i;}}}八、塊鏈字符串插入：{為避免字符串內(nèi)部塊間大量的數(shù)據(jù)移動(dòng)，最好的方法是定義兩種字符串中不出現(xiàn)的字符作為空標(biāo)記和串結(jié)束標(biāo)記，如‘#’和‘$’；也可只使用空標(biāo)記，串結(jié)束以塊尾指針為空表示，其算法如下：voidInsert(stringS,stringT,charch)//設(shè)塊大小為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所在結(jié)點(diǎn)分裂，S插在T中分裂的兩結(jié)點(diǎn)間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;}}九、上三角矩陣的存儲(chǔ)：k=(i-1)*n+j-i*(i-1)/2=(2n-i+1)*i/2+j-nf1=(2n-i+1)*i/2f2=jc=-n十、循環(huán)右移k位：12345678（n=8,k=3）78123457654321北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第4頁。北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第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)}十一、廣義表運(yùn)算結(jié)果：1、(a,b)2、((c,d))3、(c,d)4、(b)5、b6、(d)十二、利用廣義表運(yùn)算取出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無父結(jié)點(diǎn)，否則為3、(n-1)k+1+i4、(n-1)Modk≠0十四、葉子結(jié)點(diǎn)數(shù)目：mmi=1n0=∑(i-1)ni+1i=1北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第5頁。十五、找最近共同祖先：北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第5頁。bitptrForefather(bitptrroot,bitptrp,bitptrq){find=0;//0p、q都未找到;>0找到一個(gè)；-1都找到了INIT(ff);{定義一個(gè)數(shù)組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);{定義數(shù)組p動(dòng)態(tài)存儲(chǔ)路徑}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;北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第6頁。for(i=1;i<=level;i++)path[i]=p[i];北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第6頁。}Hhh(t->lc,level+1,hi,path);Hhh(t->rc,level+1,hi,path);}}十七、輸出中綴表達(dá)式并加上括號(hào)：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為輸入字符串的當(dāng)前指針，初值為1}if(s[i]==’#’){t=NULL;i++;}else{t=newstructnode;t->data=s[i];i++;if((i>Length(s))||(s[i]!=‘(’)){北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第7頁。t->lc=t->rc=NULL;北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第7頁。return;}i++;{去左括號(hào)}Creat_bintree(t->lc,i,s);{建左子樹}i++;{去逗號(hào)}Creat_bintree(t->rc,i,s);{建右子樹}i++;{去右括號(hào)}}}十九、按凹入表方式打印樹：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的簡單路經(jīng)：voidSearchPath(intv,intvt,intk,intm){//存儲(chǔ)結(jié)構(gòu)可選用鄰接矩陣，路徑從vs出發(fā)，到vt結(jié)束，長度為kvisited[v]=TRUE;P[m]=v;if(v==vt){if(m==k+1){for(i=1;i<=m;i++)cout<<P[i];cout<<endl;}北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第8頁。}else北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第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){//存儲(chǔ)結(jié)構(gòu)可選用鄰接矩陣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;}二十二、求最小代價(jià)生成樹：abcdefgabcdefgh222211120∞2∞∞∞∞3∞01∞∞∞∞∞21024∞∞∞∞∞2012∞∞∞∞41021北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第9頁。∞∞∞∞2203北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第9頁?！蕖蕖蕖蕖?30abcdabcdefgh222211122abcdefgh123456783∧3124∧2134∧12231526∧442617∧24451728∧152628∧3617∧3二十三、求關(guān)鍵路經(jīng)和最短路經(jīng)：1、abcdefghive:02361110131417vl:04361110131517關(guān)鍵路經(jīng)為：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)二十四、邊界標(biāo)識(shí)法：056056080201170213053046201670559av北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第10頁。北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第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;}北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第11頁。北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第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北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第12頁。北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第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（與空指針比較次數(shù)不算）？二十九、證明快速排序退化時(shí)的時(shí)間復(fù)雜度：當(dāng)待排序列有序時(shí)，有T(n)=T(n–1)+n–1=T(n–2)+2*n–3=T(n–3)+3*n–6…北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第13頁。=T(n–i)+i*n–i*(i+1)/2北郵算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案全文共15頁，當(dāng)前為第13頁。…=T(n–n)+n*n–n*(n+1)/2=n*(n–1)/2故，此時(shí)快速排序的時(shí)間復(fù)雜度為O(n2)。三十、單鏈表存儲(chǔ)結(jié)構(gòu)的簡單插入排序：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