数据结构作业参考答案~

1、作业参考答案一、（带头结点）多项式乘法 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;

2、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; P

3、olyAdd(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

4、, int i, int t ) / 初始值为: 1 1 t for ( k=i; k<=n; k+ ) solutionm = weightk;if ( t = weightk ) for ( j=1; j<=m; j+ ) cout<<solutionj; cout<<endl; else if ( t > weightk ) Pack ( m+1, k+1, t - weightk ); 四、判断括号是否配对：int Correct ( string s ) Inistack(Q); for ( i=0; si = =; i+ ) / 表达式以=

5、结束 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

6、 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 Deque

7、ue ( ) 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=“”;

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

9、) && (! 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->

10、;strj= #; p->next=S;for ( j=1; j<i; 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

11、=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

12、(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-都找到了

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

14、 ); 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 )

15、 if ( level>hi )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-

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

17、 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 Pri

18、nt_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结束，长度为

19、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 ) / 存储结构可选用邻接

20、矩阵 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

21、 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(ab

22、deg) 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) &&

23、; (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->

24、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二十八、散列表：（

25、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 13AS

26、L不成功 = = 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