《数据结构》一些习题答案
殷人昆编著 清华大学出版社
第一章 序论
(2)n
i ====
(4)答案
第二章 数组 2-7 答案692 (1) (2)
(3)
B B k
第三章 链表 3-1 (1) 答案见课本 第四章 栈和队列 4-2
(1) S n (2)
栈，
1 1 13 135 1354 13542 13542 135426
Ppt99专业课件下载网
4-3 证明
用反证法：
对于1,2,3,4,5,6,7,8,9,10,…,n i j k
假设p k
4-5 中80页4.2.3部分内容）
(1) (2) (3) (4)
AB *C *
BDAC +
CAB
AB *EFAD *+/+C +
(5)
AB &&EF >!||
ABC ||!&&CE
(6)
Ppt99专业课件下载网
4-6 答案
(1) 解答
显然，形如下面样子的表达式e 在进行中缀到后缀的变换过程中所需要的栈空间最大
a 1∙(a 2∙(a 3∙...(a k ∙a k +1
其中∙由于表达式e n ，又显然可见，操作数的个数为k+1个，括号的个数为2*(k-1)个，可得到如下等式：
n =(k 2*(k +1)
k +k -1
=2k -1
=2*((n -3) /4) -1 =(n -5) /2
Ppt99专业课件下载网
(2) 解答
优先级种类共三种，最大元素个数为6×4＋3＝27
第五章 递归 5-1 答案
#include class RecurveArray { //private:
int *Elements ; // int ArraySize ;
int CurrentSize ; public : RecurveArray ( int ArraySize ( MaxSize new int[MaxSize ] ){ } ~RecurveArray ( ); } void ; //输入数组的内容 int MaxKey //求最大值 int Sum ( ); //求数组元素之和 float int n ); //求数组元素的平均值 };
:: InputArray ( ){ //输入数组的内容 ; ( int i = 0; i > Elements[i ]; }
int RecurveArray :: MaxKey ( int n ) { //递归求最大值 if ( n == 1 ) return Elements [0]; int temp = MaxKey ( n - 1 ); if ( Elements [n -1] > temp ) return Elements [n -1]; else return temp ; }
int RecurveArray :: Sum ( int n ) {
//递归求数组之和
Ppt99专业课件下载网
Void main ( ) {
float RecurveArray :: Average ( int n ) { //递归求数组的平均值 if ( n == 1) return (float ) Elements [0]; else return ( (float ) Elements [n -1] + ( n - 1) * Average ( n - 1 ) ) / n ; }
}
else return Elements [n -1] + Sum (n -1) ;
6-5 三个节点的二叉树共有5种形态（catalan 数列可求得）
Ppt99专业课件下载网
6-6 答案
证明：
设该树中所有节点个数为n n 0+n 1+n m =n
k ，则k=n-1，此外，又有
m
k =∑i ⨯n i
i =1
m
n 0+n 1+n 2+ n m -1=∑i ⨯n i i =1
所以
n 0=1+∑m
(i -1) ⨯n i
i =1
6-7 答案
(1)
(1)
逐
编码
3814
第七章 集合与搜索
7-13 答案
序列可用catalan 数列
1
S n =
n +1
n 2n
7-14
8-3 设每个节点与对应数字之间关系为A=0 B=1 C=2 D=3 E=4 F=5，那么
邻接矩阵如图：
⎧0⎪0⎪⎪⎪0⎨⎪0⎪0⎪⎪⎩0
100100
010000
100000
010101
0⎫0⎪⎪1⎪⎪⎬0⎪
0⎪⎪0⎪⎭
8-4 的。
《数据结构》一些习题答案
殷人昆编著 清华大学出版社
第一章 序论
(2)n
i ====
(4)答案
第二章 数组 2-7 答案692 (1) (2)
(3)
B B k
第三章 链表 3-1 (1) 答案见课本 第四章 栈和队列 4-2
(1) S n (2)
栈，
1 1 13 135 1354 13542 13542 135426
Ppt99专业课件下载网
4-3 证明
用反证法：
对于1,2,3,4,5,6,7,8,9,10,…,n i j k
假设p k
4-5 中80页4.2.3部分内容）
(1) (2) (3) (4)
AB *C *
BDAC +
CAB
AB *EFAD *+/+C +
(5)
AB &&EF >!||
ABC ||!&&CE
(6)
Ppt99专业课件下载网
4-6 答案
(1) 解答
显然，形如下面样子的表达式e 在进行中缀到后缀的变换过程中所需要的栈空间最大
a 1∙(a 2∙(a 3∙...(a k ∙a k +1
其中∙由于表达式e n ，又显然可见，操作数的个数为k+1个，括号的个数为2*(k-1)个，可得到如下等式：
n =(k 2*(k +1)
k +k -1
=2k -1
=2*((n -3) /4) -1 =(n -5) /2
Ppt99专业课件下载网
(2) 解答
优先级种类共三种，最大元素个数为6×4＋3＝27
第五章 递归 5-1 答案
#include class RecurveArray { //private:
int *Elements ; // int ArraySize ;
int CurrentSize ; public : RecurveArray ( int ArraySize ( MaxSize new int[MaxSize ] ){ } ~RecurveArray ( ); } void ; //输入数组的内容 int MaxKey //求最大值 int Sum ( ); //求数组元素之和 float int n ); //求数组元素的平均值 };
:: InputArray ( ){ //输入数组的内容 ; ( int i = 0; i > Elements[i ]; }
int RecurveArray :: MaxKey ( int n ) { //递归求最大值 if ( n == 1 ) return Elements [0]; int temp = MaxKey ( n - 1 ); if ( Elements [n -1] > temp ) return Elements [n -1]; else return temp ; }
int RecurveArray :: Sum ( int n ) {
//递归求数组之和
Ppt99专业课件下载网
Void main ( ) {
float RecurveArray :: Average ( int n ) { //递归求数组的平均值 if ( n == 1) return (float ) Elements [0]; else return ( (float ) Elements [n -1] + ( n - 1) * Average ( n - 1 ) ) / n ; }
}
else return Elements [n -1] + Sum (n -1) ;
6-5 三个节点的二叉树共有5种形态（catalan 数列可求得）
Ppt99专业课件下载网
6-6 答案
证明：
设该树中所有节点个数为n n 0+n 1+n m =n
k ，则k=n-1，此外，又有
m
k =∑i ⨯n i
i =1
m
n 0+n 1+n 2+ n m -1=∑i ⨯n i i =1
所以
n 0=1+∑m
(i -1) ⨯n i
i =1
6-7 答案
(1)
(1)
逐
编码
3814
第七章 集合与搜索
7-13 答案
序列可用catalan 数列
1
S n =
n +1
n 2n
7-14
8-3 设每个节点与对应数字之间关系为A=0 B=1 C=2 D=3 E=4 F=5，那么
邻接矩阵如图：
⎧0⎪0⎪⎪⎪0⎨⎪0⎪0⎪⎪⎩0
100100
010000
100000
010101
0⎫0⎪⎪1⎪⎪⎬0⎪
0⎪⎪0⎪⎭
8-4 的。