数据结构习题答案严蔚敏《数据结构(c语言版)习题集》最全版本.doc

数据结构一些习题答案殷人昆编著 清华大学出版社第一章 序论1-5 (2) 简单易证，过程略。1.7 求程序步数(2)答案(4)答案N的取值语句执行次数N的取值语句执行次数11006302687283518或93*N44410到142*N53515或以上N第二章 数组2-7 答案6922-9 答案 (1) (2) (3) 2-11 答案第三章 链表3-1 (1) 答案见课本第四章 栈和队列4-2 答案(1) 出栈序列可用catalan数列描述，共132种序列(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 13 135 1354 13542 13542 135426 4-3 证明用反证法：对于1,2,3,4,5,6,7,8,9,10,n i j k假设pk pi pj成立，这意味着在pk出栈之前pi和pj都已经入栈，且留在栈中，但是在pk出栈后，要满足pipj的出栈次序是不可能的，必然pi被pj封盖，所以根据栈后进先出的性质，当ijk时有pkpjpi，与假设矛盾，所以命题不成立。4-5 写出中缀表达式的后缀表达式（本题的解法请详看课本中80页4.2.3部分内容）(1) (2) 顺序进行了调整(3) 顺序进行了调整(4) (5) (6) 4-6 答案(1) 解答显然，形如下面样子的表达式e在进行中缀到后缀的变换过程中所需要的栈空间最大由于表达式e的全部运算符号和分界符号总和为n，又显然可见，操作数的个数为k+1个，操作符的个数为k个，括号的个数为2*(k-1)个，可得到如下等式：而栈中最大元素个数为所有的操作符号和所有的左括号数目之和，即最大元素个数为：(2) 解答优先级种类共三种，最大元素个数为64327第五章 递归5-1 答案#include class RecurveArray /数组类声明private:int *Elements;/数组指针int ArraySize;/数组尺寸int CurrentSize;/当前已有数组元素个数public :RecurveArray ( int MaxSize =10 ) :ArraySize ( MaxSize ), Elements ( new intMaxSize ) RecurveArray ( ) delete Elements; void InputArray();/输入数组的内容int MaxKey ( int n );/求最大值int Sum ( int n );/求数组元素之和float Average ( int n );/求数组元素的平均值;void RecurveArray : InputArray ( )/输入数组的内容cout Input the number of Array: n;for ( int i = 0; i Elementsi;int RecurveArray : MaxKey ( int n ) /递归求最大值if ( n = 1 ) return Elements0;int temp = MaxKey ( n - 1 );if ( Elementsn-1 temp ) 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 ) ) / n;Void main ( ) int size = -1;cout No. of the Elements : ;while ( size 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 答案证明：设该树中所有节点个数为n个，那么有 考虑树枝与节点之间的关系，设总树枝数目为k，则k=n-1，此外，又有比较上述三式，可得所以6-7 答案(1) (2) (3) 6-14 答案(1)(3) 6-18 答案当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的递归过程如下图所示： AAAAFBBFFBEBCDGECGECHIGJCDEFHIGJHDJHIJDI6-21 答案已知字母集 c1, c2, c3, c4, c5, c6, c7, c8 ，频率 5, 25, 3, 6, 10, 11, 36, 4 ，则Huffman编码为 c1 c2 c3 c4 c5 c6 c7 c8 0110 10 0000 0111 001 010 11 0001 电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4= 25710100139611001100C217223625C771111101100C6C55634C4C1C8C3第七章 集合与搜索7-13 答案序列可用catalan数列 7-14 答案第八