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

《2022年北邮算法与数据结构习题参考答案.docx》由会员分享，可在线阅读，更多相关《2022年北邮算法与数据结构习题参考答案.docx（26页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、作业参考答案一、带头结点多项式乘法C = A B：voidPolyAdd list&C,listR/ R 为单个结点p=C;while！p-next & p-next-expR-expp=p-next; ifp-next | p-next-expexpR-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; Wh

2、ile 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学习文档 仅供参考所以，梵塔的

3、移动次数为 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+ coutsolutionj;cout 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; cas

4、e :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 S2return

5、1;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;vo

6、idCreatNewStr stringS,stringT,stringR,arrantPR=“” ;j=0;for i=1;inext & . ifor j=1;jstrj=chi=j; if. ip=p-next;if. ifor j=1;jstrj=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;jstrj=#p-; next=S; for j=1;jstrj=#p=;S;while p-next p=p-nex

7、t;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;i0- 找到一个； -1- 都找到了INIT ff ; 定义一个数组ff 用于记录查找路径 Fff root, p, q, 0, ft ; returnft;voidFff bitptrroot,bitptrp,bitptrq,intm,bitptr&ftif root& fi

8、nd = 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,Arrtypep

9、ath if t p level = t-data;if . t-lc&. t-rc if levelhi hi = level;fori=1 ; ilc, 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=/coutlchild ;coutlchild ;cout data ;ift-rchild if t- data= *|t-d

10、ata=/coutrchild ;coutrchild ;十八、建立二叉树：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+; 去右括号 十九、按凹入表方式打

11、印树：voidPrint_tree bitptrt Prt t, 1voidPrt bitptrt,intlevel if t Prt t-rc, level+1;for inti=1 ; i=level ; i+ cout ; cout 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+ c

12、out 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+

13、cout Pi; cout w 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 = B

14、ST 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 不胜利=

15、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

16、 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

17、;r = H-next; deleteH;三十一、计数排序：voidCountSort listA for i = 1 ; i = n ; i+ C i = 0;for j = 1 ; j 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 个空间，比较次数

18、为 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 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；