数据结构与算法 作业参考答案.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-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 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 ; ilc, 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=/)coutlchild ); coutlchild );coutdata );if (t-rchild) if ( t-data=*)|(t-data=/)coutrchild ); coutrchild ); 十八、建立二叉树：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 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 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 = H-next; delete H;三十一、计数排序：void CountSort ( list A ) for ( i = 1 ; i = n ; i+ ) C i = 0; for ( j = 1 ; j A j ) C i +; for