1
第5章 树和二叉树
一、填空题
1、指向结点前驱和后继的指针称为 线索 。
二、判断题
1、二叉树是树的特殊形式。（ ）
2、完全二叉树中，若一个结点没有左孩子，则它必是叶子。（ ）
3、对于有N个结点的二叉树，其高度为 。（ ）
4、满二叉树一定是完全二叉树，反之未必。（ ）
5、完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。 （ ）
6、若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。（ ）
7、不使用递归也可实现二叉树的先序、中序和后序遍历。（ ）
8、先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。（ ）
9、赫夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（ ）
110、在赫夫曼编码中，出现频率相同的字符编码长度也一定相同。（ ）
三、单项选择题
1、把一棵树转换为二叉树后，这棵二叉树的形态是（ A ）。
A．唯一的 Ｂ．有多种
C．有多种，但根结点都没有左孩子 Ｄ．有多种，但根结点都没有右孩子
解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。
2、由3个结点可以构造出多少种不同的二叉树？（ D ）
A．2 B．3 C．4 D．5
解释：五种情况如下：
ACB ACB ACB ACB ACB
3、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ D ）。
A．250 B． 500 C．254 D．501
解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。
数组与方法
数组可分为一位数组、二维数组和多维数组，大部分只用到二维数组，多维数组一般不用；
一位数组可以存放成千上万个数据，并且这些数据的类型是完全相同的；
要使用java数组，必须经过声明和分配内存给数组两个步骤，这两个步骤的语法结构如下：
数据类型 数组名[]=null //声明数组
数组名=new 数据类型[长度] //为数组分配内存
对于引用类型数据的默认值是NULL；
数组是引用类型，所以数组变量所保存的并非数组的实体，而是数组对内存的参考地址；
一个堆内存空间可以对应多个栈内存空间，也就是说，堆内存中的实体，可以被多个栈内存地址指向；举例来说，就像一个人可以有多个名字一样；这也就是栈内存和堆内存之间的关系；如下图：
数组的静态初始化就是直接用大括号给定几个值；
输出一个数组的最大值和最小值必须将最大值最小值两个变量的初始值赋值为数组中任何一个数值就可以了；
如果一维数组当成几何中的线性图形，那么二维数组就相当于一个表格。
二维数组的声明：
数组类型 数组名[][]=new 数据类型[行的个数][列的个数]；
从程序中我们可以得到，一维数组只需要一层for循环就可以全部输出，而二维数组必须两层for循环张三
李四
王五 也就是一个人可以有多个名字；
栈内存
堆内存 才能全部输出；以此类推，N维数组必须用N层for循环才能全部输出；
方法就是一段可重复调用的代码段；有些书上把方法称之为函数，这两者本身并没有区别，是同样的概念，只是称呼方式不一样；
由main方法直接调用的方法，一定要加上public
static；
在定义类时，全部单词的首字母必须大写，那么在定义方法时也有规则，即第一个单词的首字母小写，从第二个单词开始，首字母大写，这一定要养成一个好的习惯；
方法的重载，就是方法名相同，但参数的类型和参数的个数不同，通过传递参数的个数及类型的不同可以完成不同功能的方法调用
第5章 数字滤波器的基本结构
5.1 学习要求
1 掌握IIR数字滤波器的基本网络结构，包括直接型、级联型和并联型；
2 掌握FIR数字滤波器的基本网络结构，包括直接型、级联型和频率抽样型；
3 了解数字信号处理中的量化效应和数字信号处理的实现。
5.2 学习要点
5.2.1 数字滤波器的结构特点与表示方法
一个数字滤波器可以用系数函数表示为：
01()()()1MkkkNkkkbzYzHzXzaz (5-1)
直接由此式可得出表示输入输出关系的常系数线性差分方程为：
10()()()NMkkkkynaynkbxnk (5-2)
由式(5-2)看出，实现一个数字滤波器需要几种基本的运算单元—加法器、单位延时和常数乘法器。
这些基本的单元可以有两种表示法：方框图法和信号流图法，如图5-1所示。用方框图表示较明显直观，用流图表示则更加简单方便。
1z1z•aa单位延时乘常数相加方框图表示法信号流图表示法
图5-1 基本运算过程的表示
5.2.2 无限长单位脉冲响应(IIR)滤波器的基本结构
无限长单位脉冲响应(IIR)滤波器有以下几个特点： (1) 系统的单位脉冲响应()hn是无限长的；
(2) 系统函数()Hz在有限z平面(0z)上有极点存在；
(3) 结构上存在着输出到输入的反馈，也就是结构上是递归型。
同一种系统函数()Hz的基本网络结构有直接I型、直接Ⅱ型、级联型和并联型四种。
1直接I型
直接型按式(5-2)差分方程式将输入采样值（序列）)(nx延迟并乘以系数kb，将输出采样（序列）)(ny延迟并乘以系数ka，再把它们加起来，这种结构称为直接I型，结构流图如图5-2所示。
由图可看出，总的网络)(zH由0Mkkkbz和11Nkkkaz两部分网络级联组成，第一个网络实现零点，第二个网络实现极点，从图中又可看出，直接I型结构需要NM级延时单元。
92 第5章 递归与广义表
一、复习要点
本章主要讨论递归过程和广义表。一个递归的定义可以用递归的过程计算，一个递归的数据结构可以用递归的过程实现它的各种操作，一个递归问题也可以用递归的过程求解。因此，递归算法的设计是必须掌握的基本功。递归算法的一般形式：
void p ( 参数表 ) {
if ( 递归结束条件)
可直接求解步骤； 基本项
else p ( 较小的参数 ); 归纳项
}
在设计递归算法时，可以先考虑在什么条件下可以直接求解。如果可以直接求解，考虑求解的步骤，设计基本项；如果不能直接求解，考虑是否可以把问题规模缩小求解，设计归纳项，从而给出递归求解的算法。必须通过多个递归过程的事例，理解递归。但需要说明的是，递归过程在时间方面是低效的。
广义表是一种表，它的特点是允许表中套表。因此，它不一定是线性结构。它可以是复杂的非线性结构，甚至允许递归。可以用多重链表定义广义表。在讨论广义表时，特别注意递归在广义表操作实现中的应用。
本章复习的要点：
1、基本知识点
要求理解递归的概念：什么是递归？递归的定义、递归的数据结构、递归问题以及递归问题的递归求解方法。理解递归过程的机制与利用递归工作栈实现递归的方法。通过迷宫问题，理解递归解法，从而掌握利用栈如何实现递归问题的非递归解法。在广义表方面，要求理解广义表的概念，广义表的几个性质，用图表示广义表的方法，广义表操作的使用，广义表存储结构的实现，广义表的访问算法，以及广义表的递归算法。
2、算法设计
求解汉诺塔问题，掌握分治法的解题思路。
求解迷宫问题、八皇后问题，掌握回溯法的解题思路。
对比单链表的递归解法和非递归解法，掌握单向递归问题的迭代解法。
计算广义表结点个数，广义表深度，广义表长度的递归算法。
输出广义表各个原子所在深度的非递归算法。
