2022年北邮算法与数据结构习题参考答案.docx

作业参考答案一、带头结点多项式乘法C = A ×B：voidPolyAdd list&C,listR/ R 为单个结点p=C;while！p->next && p->next->exp>R->expp=p->next; ifp->next | p->next->exp<R->expR->next=p->next;p->next=R;elsep->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;PolyAddC, 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 + 2 i 1假设 n=i , 就 M n-n = 0, 故： M n = 2 nM n-n + 2 n 1= 2n 1学习文档 仅供参考所以，梵塔的移动次数为 2n 1 次；三、简化的背包问题：voidPack intm,inti,intt / 初始值为 : 1 1 tfor k=i;k<=n;k+ solutionm = weightk; if t = weightk for j=1;j<=m;j+ cout<<solutionj;cout<<endl;elseif t > weightk Pack m+1, k+1, t - weightk ;四、判定括号是否配对：intCorrect strings InistackQ;for i=0;si = =i+;/ 表达式以 =终止switch si case :case :case :Push Q, s i ;break; case :case :case :if EmptyQreturn0;t=PopQ; if .Matching t, si return0;if .EmptyQ return0; return1;五、堆栈可能的输出：123412431324134214231432213421432314234124132431312431423214324134123421412341324213423143124321六、用两个堆栈实现一个队列：intFullQ ifFull S1 && . Empty S2return1;return0;intEmptyQ if Empty S1 && Empty S2return1;return0;voidEnqueue elemtype xif FullS1 if EmptyS2 while . Empty S1 PushS2, PopS1; if. FullS1PushS1, x;elemtypeDequeue if EmptyS2while . EmptyS1 PushS2, PopS1; if. EmptyS2returnPopS2;七、生成新串及字符第一次显现位置：intIndex stringS,stringT for i=1;i + LenT-1<=LenS;i+ ifEqual Sub S, I, Len T, T returni; return0;voidCreatNewStr stringS,stringT,stringR,arrantPR=“” ;j=0;for i=1;i<=LenS;i+ ch=Sub S, i, 1 ;if . IndexT, ch && . IndexR, ch R=ConcatR, ch;Pj+=i; 八、块链字符串插入： 为防止字符串内部块间大量的数据移动，最好的方法是定义两种字符串中不显现的字符作为空标记和串终止标记，如#和 $；也可只使用空标记，串终止以块尾指针为空表示，其算法如下：voidInsert stringS,stringT,charch/ 设块大小为 mi=0;p=T;whilep->next && . ifor j=1;j<=m;j+ ifp->strj=chi=j; if. ip=p->next;if. ifor j=1;j<=m;j+ ifp->strj=chi=j; if. ip->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->strj=#p-> next=S; for j=1;j<i;j+ q->strj=#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-n f 1=2n-i+1*i/2f 2=jc=-n十、循环右移 k 位：12345678n=8, k=36781234587654321voidExch arrtypeA,intst,inted for i=st;i<=st+ed / 2;i+ Ai Aed-i+1;voidShift arrtypeA,intk,intn ExchA, 1, n;ExchA, 1, k;ExchA, k+1, n十一、广义表运算结果：1、a,b2、c,d3、c,d4、b5、b6、d十二、利用广义表运算取出c 原子：1、HeadTailTailL1 2、HeadHeadTailL23、HeadHeadTailTailHeadL3 4、HeadHeadHeadTailTailL4 5、HeadHeadTailTailL56、HeadTailHeadL67、HeadHeadTailHeadTailL7 8、HeadHeadTailHeadTailL8n-2+k k十三、满 k 叉树问题：1、kn-12、n=1 无父结点，否就为3、n-1k+1+i4、n-1 Mod k 0十四、叶子结点数目：mn0= i-1ni +1i=1十五、找最近共同祖先：bitptrForefather bitptrroot,bitptrp,bitptrq find = 0;/ 0-p、q 都未找到 ;>0- 找到一个； -1- 都找到了INIT ff ; 定义一个数组ff 用于记录查找路径 Fff root, p, q, 0, ft ; returnft;voidFff bitptrroot,bitptrp,bitptrq,intm,bitptr&ftif root&& find >= 0 m = m+1;if root=p | root=qif. findfind = m-1;elseft = ff find ; find = -1;ff m = root;Fff root->lc, p, q, m, ft ;Fff root->rc, p, q, m, ft ;ifm=findfind = 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;fori=1 ; i<=level ; i+pathi = pi;Hhh t->lc, level+1, hi, path ; Hhh t->rc, level+1, hi, path ;十七、输出中缀表达式并加上括号：voidExpout treet if . t ift->lchildif t ->lchild->data= +|t->lchild->data= - && t ->data= *|t->data=/cout<< ;Expout t->lchild ;cout<< elseExpout t->lchild ;cout<<t-> data ;ift->rchild if t-> data= *|t->data=/cout<< ;Expout t->rchild ;cout<< elseExpout t->rchild ;十八、建立二叉树：voidCreat_bintree bitptr&t,inti,strings /i 为输入字符串的当前指针，初值为1 if si= #t = NULL; i+;elset = newstructnode; t->data = si;i+;if i >Lengths | si.= t->lc = t->rc = NULL;return;i+; 去左括号 Creat_bintree t->lc, i, s; 建左子树 i+; 去逗号Creat_bintree t->rc, i, s; 建右子树 i+; 去右括号 十九、按凹入表方式打印树：voidPrint_tree bitptrt Prt t, 1voidPrt 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 终止，长度为 k visitedv = TRUE;Pm = v;if v=vt if m = k+1 for i =1 ; i <= m ; i+ cout << Pi; cout << endl;elsew = FirstAdj v ; while w if . visitedw SearchPathw, vt, k, m+1; w = NextAdj v, w ;visitedv = FALSE;二十一、求全部简洁回路：voidSearchCycle intv,intm / 储备结构可选用邻接矩阵visitedv = TRUE; Pm = v;w = FirstAdj v ; while w if . visitedw SearchCyclew, m+1;elsefor j = 1 ; Pj=w ;j+;for i =j ; i <= m ; i+ cout << Pi; cout << w << endl;w = NextAdj v, w ;visitedv = FALSE;二十二、求最小代价生成树：2b22ade12gc1f1h0232023012102420124102122031、 13022331242134122315 2644 261724 45172815 262836 1732、1 a2 b3 c4 d5 e6 f7 g8 h2b22adc 1e 2g11f h二十三、求关键路经和最短路经：1、abcdefghive:02361110131417vl:04361110131517关键路经为： a c d f e g i2、 abcdefghi2ab3ac3ac 4abd4abd7abde 8abdf8abdf9abdeg9abdeg 9abdfh9abdfh 13abdegi11abdfhi二十四、边界标识法：1、80221346255905601170530 16700学习文档0仅供参考0av80205621301746202640002、av二十五、按拜访频度查找：listSearch listH,keytypeK p = H;q = NULL;while p ->next&&. q ifp->next->key = Kq = p->next; q->freq+;while H.=p && H->next->freq>=q->freqH = H->next; ifH.=pp->next = q->next;q->next = H->next; H->next = q;p = p->next;returnq;学习文档 仅供参考二十六、判定是否二叉排序树：intBST bitptrt,bitptr&p if ！ t return1; L = BST t->lc , p ;D = 1;if p&&p->data > t->dataelseD = 0; p = t;R = BST t->rc , p ;returnL&&D&&R;intBinarySortTree bitptrp=NULL;t returnBST t , p ;二十七、建立2-3 树：202030302050插入20插入30插入 50303052305220505220506020506068插入 52插入 60插入 68525268523068203060702032607020506070插入 70删除 50删除 68二十八、散列表：1：AprAugDecFebJanMarMayJunJulSepOctNovASL 胜利=1+2+1+1+1+1+2+4+5+2+5+61231= 12ASL 不胜利=5+4+3+2+1+9+8+7+6+5+4+3+2+11430= 72：012345678910111213141516012345678910111213141516AprDecFebJanMarOctSepAugJun JulMayNov1+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= T n i + i * n i * i + 1 / 2= T n n + n * n n * n + 1 / 2= n * n 1 / 2故，此时快速排序的时间复杂度为O n 2 ；三十、单链表储备结构的简洁插入排序：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->next = q->next;q->next = p;r = H->next; deleteH;三十一、计数排序：voidCountSort listA for i = 1 ; i <= n ; i+ C i = 0;for j = 1 ; j <= n ; j+ ifA i > A j C i +;for i = 1 ; i <= n ; i+ B C i +1 = A i ;for i = 1 ; i <= n ; i+ A i = B i ;三十二、求前 k 个元素：即部分排序即可得到所需结果的方法有：1、冒泡排序：比较次数为n-1+n-2+ +n-k = nk-kk+1/2;2、简洁项挑选择排序：比较次数同上，为nk-kk+1/2;3、树形排序：需附加 2n-1 个空间，比较次数为 n-1+k-1 log 2n ；4、堆排序：比较次数为 < 4n+k-1 log 2n ；5、快速排序：比较次数为< 2n；三十三、求最大最小元素：假设不增加储备空间，就用下法，最多比较次数为2n-3 次：ifr 1 < r 2 min = r 1 ;max = r 2 ;elsemin = r 2 ;max = r 1 ;for i = 3 ; i <= n ; i+ if r i > max max = r i ;elseif r i < min min = r i ;假设能增加空间， 就可先将记录两两比较， 将较大的和较小的记录分别储备在不同的数组中， 再从较大的里面选出最大值， 从较小的里面选出最小值，总得比较次数为n/2+2n/2-1=1.5n-2；三十四、三路平稳归并：4791112182332394773159总的读写次数为 : 4+7+11+9+11+12+32+18+23+32+73+39+47+73+159 = 550；