1、数据结构一些习题答案殷人昆编著 清华大学出版社第一章 序论1-5 (2) 简单易证，过程略。1.7 求程序步数(2)答案 1111211 ()22()()(1)62(1)(2)jni ni nijkij inni i innn (4)答案N 的取值 语句执行次数 N 的取值 语句执行次数1 100 6 302 68 7 283 51 8 或 9 3*N4 44 10 到 14 2*N5 35 15 或以上 N第二章 数组2-7 答案 6922-9 答案 (1) (1)2n(2) ()(iiji(3) (1)12ij2-11 答案 1023ijBaki第三章 链表3-1 (1) 答案见课本第四章
2、 栈和队列4-2 答案(1) 出栈序列可用 catalan 数列描述，共 132 种序列21nnSA(2) 不能得到 435612 和 154623 这样的出栈序列。因为若在 4, 3, 5, 6 之后再将 1, 2 出栈，则 1, 2 必须一直在栈中，此时 1 先进栈，2 后进栈，2 应压在 1 上面，不可能 1 先于 2 出栈。154623 也是这种情况。出栈序列 325641 和 135426 可以得到。3 5 6 2 2 4 4 4 4 1 1 1 1 1 1 1 1 3 32 32 325 325 3256 32564 325641 5 3 4 4 1 2 2 2 2 6 1 1 1
3、3 135 1354 13542 13542 135426 4-3 证明用反证法：对于 1,2,3,4,5,6,7,8,9,10,ni j k假设 pk class RecurveArray /数组类声明private:int *Elements; /数组指针int ArraySize; /数组尺寸int CurrentSize; /当前已有数组元素个数public :RecurveArray ( int MaxSize =10 ) :ArraySize ( MaxSize ), Elements ( new intMaxSize ) RecurveArray ( ) delete Eleme
4、nts; void InputArray(); /输入数组的内容int MaxKey ( int n ); /求最大值int Sum ( int n ); /求数组元素之和float Average ( int n ); /求数组元素的平均值;void RecurveArray : InputArray ( ) /输入数组的内容cout Elementsi;int RecurveArray : MaxKey ( int n ) /递归求最大值if ( n = 1 ) return Elements0;int temp = MaxKey ( n - 1 );if ( Elementsn-1 te
5、mp ) return Elementsn-1;else return temp;int RecurveArray : Sum ( int n ) /递归求数组之和if ( n = 1) return Elements0;else return Elementsn-1 + Sum (n-1);float RecurveArray : Average ( int n ) /递归求数组的平均值if ( n = 1) return (float) Elements0;else return ( (float) Elementsn-1 + ( n - 1) * Average ( n - 1 ) )
6、/ n;Void main ( ) int size = -1;cout size;RecurveArray ra ( size );ra.InputArray();cout “nThe max is: “ ra.MaxKey ( size) endl;cout “nThe sum is: “ ra.Sum ( size ) endl;cout “nthe avr is: “ ra.Average ( size ) endl;第六章 树与森林6-5 答案三个节点的树共有两种形态三个节点的二叉树共有 5 种形态（catalan 数列可求得）注意二叉树有左右子树之区别，而普通的树则没有。6-6 答
7、案证明：设该树中所有节点个数为 n 个，那么有012mnn考虑树枝与节点之间的关系，设总树枝数目为 k，则 k=n-1，此外，又有 1miikn比较上述三式，可得 012 1mmiinnn所以 01()miinn6-7 答案(1) ABA(2) ABA(3) A6-14 答案(1)2 13 5 3 95 7 8 6 4 8 4 27 3 6 61 0 0(3) 0 61 2 2 03 0 5 2 2 3 4 23 81 0 39 7 6 6 5 66-18 答案当前序序列为 ABECDFGHIJ，中序序列为 EBCDAFHIGJ 时，逐步形成二叉树的递归过程如下图所示： 6-21 答案已知字母
8、集 c1, c2, c3, c4, c5, c6, c7, c8 ，频率 5, 25, 3, 6, 10, 11, 36, 4 ，则 Huffman 编码为c1 c2 c3 c4 c5 c6 c7 c80110 10 0000 0111 001 010 11 0001 电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4= 257EBCD FHIGJA ABEFCD HIGJABEFCDGJHIABEFCDGJHI1006139362522177 10 11 1143 65C3 C8C5 C6C1 C4C2 C700000001111111
