作业参考答案一、（带头结点）多项式乘法 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-expexp) 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; cout 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; inext) & (! i) for ( j=1; jstrj=ch) i=j;if (! i) p=p-next; if (! i) for ( j=1; jstrj=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; jstrj= #; p-next=S;for ( j=1; jstrj= #; 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; i0-找到一个； -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 Hig