北邮算法与数据结构习题参考答案作业参考答案一、（带头结点）多项式乘法 C = A×B：void PolyAdd ( list &C, list R) // R 为单个结点{p=C;while ((！p->next) && (p->next->exp>R->exp)) p=p->next; if ((p->next) || (p->next->exp<R->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= 2i M ( n-i ) + 2i– 1若n=i ,则M ( n-n ) = 0,故：M ( n ) = 2n M ( 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++ ){solution[m] = weight[k];if ( t == weight[k] ){for ( j=1; j<=m; j++ ) cout<<solution[j]; cout<<endl;} else if ( t > weight[k] ) Pack ( m+1, k+1, t - weight[k] ); }}四、判断括号是否配对：int Correct ( string s ){Inistack(Q);for ( i=0; s[i] == ‘=’; i++ ) // 表达式以‘=’结束{switch ( s[i] ){case ‘(’:case ‘[’:case ‘{’:Push ( Q, s[ i ] ); break;case ‘)’:case ‘]’:case ‘}’:if ( Empty(Q)) return 0; t=Pop(Q);if ( ! Matching( t, s[i] )) return 0;}}if ( ! Empty(Q) ) return 0;return 1;}五、堆栈可能的输出：12341243 1324 1342 1423143221342143 2314 2341 24132431312431423214 3241 3412 342141234132 42134231 43124321六、用两个堆栈实现一个队列：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); P[j++]=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->str[j]==ch) i=j;if (! i) p=p->next;}if (! i) for ( j=1; j<=m; j++ ) if (p->str[j]==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->str[j]= ‘#’; p->next=S;for ( j=1; j<i; j++ ) q->str[j]= ‘#’; 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）67 8 1 2 3 4 587 6 5 4 3 2 1void Exch ( arrtype A, int st, int ed ){for ( i=st; i<=(st+ed) / 2; i++ ) A[i]←→A[ed-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、b6、(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)))))十三、满k叉树问题：1、k n-12、n=1无父结点，否则为3、(n-1)k+1+i4、(n-1) Mod k≠0十四、叶子结点数目：n0=∑(i-1)n i+1 n-2+k ki=1 m十五、找最近共同祖先：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; else{ft = 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 ( level>hi ){hi = level;for (i=1 ; i<=level ; i++) path[i] = p[i];}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 );cout<<t->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 (s[i]==’#’){t = NULL;i++;} else{t = new struct node;t->data = s[i];i++;if (( i >Length(s)) || (s[i]!= ‘(’ )){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 visited[v] = TRUE;P[m] = v;if ( v==vt ){if ( m == k+1 ){for ( i =1 ; i <= m ; i++ ) cout << P[i];cout << endl;}} else{w = FirstAdj ( v );while ( w ){if ( ! visited[w] ) SearchPath(w, vt, k, m+1);w = NextAdj ( v, w );}}visited[v] = FALSE;}二十一、求所有简单回路：void SearchCycle ( int v, int m ){ // 存储结构可选用邻接矩阵visited[v] = TRUE;P[m] = v;w = FirstAdj ( v );while ( w ){if ( ! visited[w] ) SearchCycle(w, m+1); else{for ( j = 1 ; P[j]==w ; j++);for ( i =j ; i <= m ; i++ ) cout << P[i];cout << w << endl;}w = NextAdj ( v, w );}visited[v] = FALSE;}二十二、求最小代价生成树：1、0 2 3∞∞∞∞∞2 0 ∞2∞∞∞∞3 ∞0 1 ∞∞∞∞abcdefgh2 2 2 2111∞ 2 1 0 2 4 ∞ ∞ ∞ ∞ ∞ 2 0 1 2 ∞ ∞ ∞ ∞ 4 1 0 2 1 ∞ ∞ ∞ ∞ 2 2 0 3 ∞ ∞ ∞ ∞ ∞ 1 3 02、二十三、求关键路经和最短路经：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、a →b 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)2 2 a b c de f gh1 2 3 4 5 6 7 8 3 ∧ 3 1 2 4 ∧ 21 3 4 ∧ 12 23 1 5 2 6 ∧4 4 2 6 1 7 ∧ 2 4 45 1 7 2 8 ∧ 15 26 2 8 ∧ 3 6 17 ∧ 3 a b c d e f g h 2 2 2 2 1 1 1二十四、边界标识法： 1、2、二十五、按访问频度查找：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;0 5 0 8 0 1 0 2 0 5 0 4 01 0 5av av 0 5 0 8 0 1 02 0 2 0 4二十六、判断是否二叉排序树：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 树：插入20 插入30 插入50插入52 插入60 插入68 20 20 30 30 20 50 30 20 50 52 50 20 60 30 52 50 20 30 52 60 68 52 3068 60 70 52 68 20 3052 60 7020 32插入70 删除50 删除68二十八、散列表：（1）：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Apr Aug Dec Feb Jan Mar May Jun Jul Sep Oct Nov1+2+1+1+1+1+2+4+5+2+5+6 31ASL成功= ——————————————= ——12 125+4+3+2+1+9+8+7+6+5+4+3+2+1 30ASL不成功= ————————————————= ——14 7（2）：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16∧∧∧∧∧∧∧∧∧∧Apr Dec Feb Jan Mar Oct SepAug Jun May NovJul1+2+1+1+1+2+3+1+2+1+2+1 9ASL成功= ——————————————= ——12 63+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 )。