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

作业参考答案一、（带头结点）多项式乘法 C = AB：void PolyAdd ( list C, list R) / R 为单个结点 p=C; while (！p-next) (p-next-expR-exp) p=p-next; if (p-next) | (p-next-expR-exp) R-next=p-next; p-next=R; else p-next-inf += R-inf; delete R; if ( ! p-next-inf ) R=p-next; p-next=R-next; delete R; void PolyMul ( list A, list B, list C ) C=new struct node; C-next=NULL; q=B-next; While ( q ) p=A-next;while ( p ) r = new struct node; 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 = 2n 1所以，梵塔的移动次数为2n 1次。三、简化的背包问题：void Pack ( int m, int i, int t ) / 初始值为: 1 1 t for ( k=i; k=n; k+ ) solutionm = weightk;if ( t = weightk ) for ( j=1; j=m; j+ ) coutsolutionj; coutendl; else if ( t weightk ) Pack ( m+1, k+1, t - weightk ); 四、判断括号是否配对：int Correct ( string s ) Inistack(Q); for ( i=0; si = =; i+ ) / 表达式以=结束 switch ( si )case (:case :case : Push ( Q, s i ); break;case ):case :case : if ( Empty(Q) return 0; t=Pop(Q); if ( ! Matching( t, si ) return 0; if ( ! Empty(Q) ) return 0;return 1;五、堆栈可能的输出：1234 1243 1324 1342 1423 14322134 2143 2314 2341 2413 24313124 3142 3214 3241 3412 34214123 4132 4213 4231 4312 4321六、用两个堆栈实现一个队列：int FullQ ( ) if (Full (S1) ! Empty (S2) return 1; return 0;int EmptyQ ( ) if ( Empty (S1) Empty (S2) return 1; return 0;void Enqueue ( elemtype x) if (Full(S1) if (Empty(S2) while (! Empty (S1) Push(S2, Pop(S1); if (! Full(S1) Push(S1, x);elemtype Dequeue ( ) if (Empty(S2) while (! Empty(S1) Push(S2, Pop(S1); if (! Empty(S2) return Pop(S2);七、生成新串及字符第一次出现位置：int Index ( string S, string T ) for ( i=1; i + Len(T)-1=Len(S); i+ ) if Equal ( Sub ( S, I, Len (T), T ) return i; return 0;void CreatNewStr ( string S, string T, string R, arrant P) R=“”; j=0; for ( i=1; i=Len(S); i+ ) ch=Sub( S, i, 1 );if ( ! Index(T, ch) ! Index(R, ch) ) R=Concat(R, ch); Pj+=i; 八、块链字符串插入：为避免字符串内部块间大量的数据移动，最好的方法是定义两种 字符串中不出现的字符作为空标记和串结束标记，如 #和 $；也可只使用空标记，串结束以块尾指针为空表示，其算法如下：void Insert ( string S, string T, char ch) / 设块大小为m i=0; p=T; while (p-next) (! i) for ( j=1; j=m; j+ ) if (p-strj=ch) i=j;if (! i) p=p-next; if (! i) for ( j=1; j=m; j+ ) if (p-strj=ch) i=j; if (! i) p-next=S; else / S插在T后 / ch所在结点分裂，S插在T中分裂的两结点间q= new struct node; q-str=p-str; q-next=p-next;for ( j=i; j=m; j+ ) p-strj= #; p-next=S;for ( j=1; ji; 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-nf1=(2n-i+1)*i/2f2=jc=-n十、循环右移k位：1 2 3 4 5 6 7 8 （n=8, k=3）6 7 8 1 2 3 4 58 7 6 5 4 3 2 1void Exch ( arrtype A, int st, int ed ) for ( i=st; i=(st+ed) / 2; i+ ) AiAed-i+1;void Shift ( arrtype A, int k, int n ) 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、b 6、(d)十二、利用广义表运算取出c原子：1、 Head(Tail(Tail(L1)2、 Head(Head(Tail(L2)3、 Head(Head(Tail(Tail(Head(L3)4、 Head(Head(Head(Tail(Tail(L4)5、 Head(Head(Tail(Tail(L5)6、 Head(Tail(Head(L6)7、 Head(Head(Tail(Head(Tail(L7)8、 Head(Head(Tail(Head(Tail(L8)n-2+kk十三、满k叉树问题：1、kn-1 2、n=1无父结点，否则为 3、(n-1)k+1+i 4、(n-1) Mod k0十四、叶子结点数目：mi=1n0=(i-1)ni+1十五、找最近共同祖先：bitptr Forefather ( bitptr root, bitptr p, bitptr q ) find = 0; / 0-p、q都未找到; 0-找到一个； -1-都找到了 INIT ( ff ); 定义一个数组 ff 用于记录查找路径 Fff ( root, p, q, 0, ft ); return ft;void Fff (bitptr root, bitptr p, bitptr q, int m, bitptr ft) if ( root ( find = 0 ) m = m+1;if (root=p) | (root=q) if (! find) find = m-1; elseft = 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; 十六、求树的直径等：void High ( bitptr t, int *hi, Arrtype path ) *hi = 0; INIT ( p ); 定义数组 p 动态存储路径 Hhh ( t, 1, hi, path);void Hhh( bitptr t, int level, int *hi, Arrtype path ) if ( t ) p level = t-data; if ( ! t-lc ! t-rc ) if ( levelhi )hi = level;for (i=1 ; i=level ; i+) pathi = pi; Hhh ( t-lc, level+1, hi, path );Hhh ( t-rc, level+1, hi, path ); 十七、输出中缀表达式并加上括号：void Expout ( tree t ) if ( ! t ) if ( t-lchild) if ( t-lchild-data=+)|(t-lchild-data= -) ( t -data=*)|(t-data=/)cout(; Expout ( t-lchild ); cout); else Expout ( t-lchild );coutt-data );if (t-rchild) if ( t-data=*)|(t-data=/)cout(; Expout ( t-rchild ); cout); else Expout ( t-rchild ); 十八、建立二叉树：void Creat_bintree ( bitptr t, int i, string s ) / i 为输入字符串的当前指针，初值为 1 if (si=#) t = NULL; i+; else t = new struct node;t-data = si;i+;if ( i Length(s) | (si!= ( )t-lc = t-rc = NULL;return; i+; 去左括号 Creat_bintree ( t-lc, i, s); 建左子树 i+; 去逗号 Creat_bintree ( t-rc, i, s); 建右子树 i+; 去右括号 十九、按凹入表方式打印树：void Print_tree ( bitptr t ) Prt ( t, 1)void Prt ( bitptr t, int level ) if ( t ) Prt ( t-rc, level+1);for ( int i=1 ; i=level ; i+ ) cout ; cout t-data; Prt ( t-lc, level); 二十、判断是否存在长度为 k 的简单路经：void SearchPath ( int v, int vt, int k, int m ) /存储结构可选用邻接矩阵，路径从vs出发，到vt结束，长度为 k visitedv = TRUE; Pm = v; if ( v=vt ) if ( m = k+1 ) for ( i =1 ; i = m ; i+ ) cout Pi; cout endl; else w = FirstAdj ( v ); while ( w ) if ( ! visitedw ) SearchPath(w, vt, k, m+1); w = NextAdj ( v, w ); visitedv = FALSE;二十一、求所有简单回路：void SearchCycle ( int v, int m ) / 存储结构可选用邻接矩阵 visitedv = TRUE; Pm = v; w = FirstAdj ( v ); while ( w ) if ( ! visitedw ) SearchCycle(w, m+1); else for ( j = 1 ; Pj=w ; j+); for ( i =j ; i = m ; i+ ) cout Pi; cout w endl; w = NextAdj ( v, w ); visitedv = FALSE;二十二、求最小代价生成树：abcdefgh22221111、 0 2 3 2 0 2 3 0 1 2 1 0 2 4 2 0 1 2 4 1 0 2 1 2 2 0 3 1 3 0abcdefgh222211122abcdefgh123456783312421341223152644261724451728152628361732、二十三、求关键路经和最短路经：1、 a b c d e f g h ive: 0 2 3 6 11 10 13 14 17vl: 0 4 3 6 11 10 13 15 17 关键路经为：a c d f e g i2、ab c d e f g h i2(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)二十四、边界标识法：056080201170213053046201670559av1、av05608020170213026404622、二十五、按访问频度查找：list Search ( list H, keytype K ) 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; return q;二十六、判断是否二叉排序树：int BST ( bitptr t, bitptr p ) if ( ！ t ) return 1; L = BST ( t-lc , p ); D = 1; if ( p p-data t-data) else D = 0; p = t; R = BST ( t-rc , p ); return L D R;int BinarySortTree ( bitptr t ) p=NULL;return BST ( t , p );二十七、建立 2-3 树：30205020 3020 502030 5260 6850206030 52302050 52插入20 插入30 插入50 插入52 插入60 插入685260 7020 32607052 6820 3052306820506070 插入70 删除50 删除68二十八、散列表：（1）：012345678910111213141516AprAugDecFebJanMar MayJunJulSepOctNov 1+2+1+1+1+1+2+4+5+2+5+6 31ASL成功 = = 12 12 5+4+3+2+1+9+8+7+6+5+4+3+2+1 30ASL不成功 = = 14 7 （2）：012345678910111213141516Apr Dec Feb Jan Mar Oct SepAug Jun May Nov Jul 1+2+1+1+1+2+3+1+2+1+2+1 9ASL成功 = = 12 6 3+1+2+2+1+4+3+3+1+2+1+1+1+1 13ASL不成功 = = 14 7ASL不成功 = 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 )。三十、单链表存储结构的简单插入排序：void InsertSort ( pointer r ) H = new struct node; 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 =