树
一、判断题：
1。二叉树是一棵无序树。（×）
2.在一棵二叉树中，假定每个结点只有左子女，没有右子女,对它分别进行中序遍历和后序遍历，则具有相同的结果。（√）
3。度为二的有序树等价于二叉树。（√）
4.树的带权路径长度最小的二叉树中必定没有度为1的结点。（√)
5。哈夫曼树一定是满二叉树。（×）
6.满二叉树也是完全二叉树.（√)
7。设与一棵树T所对应的二叉树为BT,则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。(×）
8.将一棵树转换成二叉树后，根结点没有左子树（×）
9。已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（√)
10用二叉树的前序遍历和中序遍历可以导出树的后序遍历.（√）
11.在完全二叉树中，若某结点无左孩子,则它必是叶结点。（√）。
12．任何一棵二叉树都有n0=n2+1的关系式.（√）
13．已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树.( √ ）
二、填空题
1.假定一棵二叉树的结点个数为32，则它的最小深度为___6___，最大深度为：32.
2.在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，那么叶子结点有__6____
个.
3.树的双亲表示法便于实现涉及到___双亲___的操作，孩子表示法便于实现涉及到孩子的
操作。
4.对于一颗具有n个结点的二叉树，对应二叉链表中指针域有__n—1__个用于指向子结点。
5.下图所示二叉树存储在一维数组中，则元素F的下标位置为___11___。（A为1)
6.高度为k的二叉树具有的结点数目，最少为___ K ___,最多为___2K—1___。
7.对任何一棵二叉树,若n0，n1,n2分别是度为0，1，2的结点的个数，则n0=__ n2+1__.
8.一棵含有16个结点的完全二叉树，对他按层编号,对于编号为7的结点，他的双亲结编号点为___3___左孩子编号为____14__、右孩子编号为___15___。
9.在含100个结点的完全二叉树，叶子结点的个数为___50_____。
10.度数为0的结点，即没有子树的结点叫作___叶子_____结点。同一个结点的儿子结点之间互称为____兄弟____结点。
11.若一棵完全二叉树含有121个结点,则该树的深度为_____7______。
12.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为____ ABCDFE _______。
三、选择题
1.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于___C___。
A. n    B. n-1    C。 n+1    D. 2＊n
2.在一棵二叉树的第5层上，最多具有___B___个结点.
A. 14    B. 16    C。 31    D. 32
3.在一棵深度为h的完全二叉树中，所含结点个数不少于___D___。
A. 2h    B。 2h+1    C。 2h —1    D. 2h—1
4.一棵树的广义表表示为a(b（c)， d（e(g（h）)， f)），则该二叉树的高度为___D___。
A。 2    B。 3    C. 4    D. 5
5.将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号,根结点的编号为1,则编号为15的结点的左孩子的编号为___A___。
A.30                  B.31       
C.16                  D.32
6.在一棵树中，每个结点最多有___B先序中序后序遍历二叉树___个直接前驱结点.
A。 0    B. 1    C。 2    D. 任意多个
7.7.  树中所有结点的度数之和等于结点总数加___C___。
A. 0    B。 1    C. -1    D. 2
8.二叉树中第5层上的结点个数最多为____C____
A。8                          B。15           
C.16                          D。32
9.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为___A___。
A.98                  B.99         
C.50                  D.48
10.由权值分别为3， 8， 6， 2, 5的叶子结点生成一颗赫夫曼树,它的带权路径长度为__D___。
A。 24    B。 48    C。 72    D。 53
11.把一棵树转换为二叉树后,这棵二叉树的形态是    A      。
Ａ。唯一的                          Ｂ。有多种
Ｃ。有多种，但根结点都没有左孩子    Ｄ。有多种,但根结点都没有右孩子
12.具有n（n>0)个结点的完全二叉树的深度为 C        。
Ａ ⎡log2（n)⎤  Ｂ ⎣ log2（n)⎦  Ｃ ⎣ log2（n) ⎦+1    Ｄ ⎡log2(n）+1⎤
13.ù
四、应用题
1..将下图转换为二叉树，对转换后的二叉树进行先序、中序、后序遍历序列。
先序：ABEFCDGJ
中序:EFBCGJDA
后序：FEJGDCBA
2.写出下图所示二叉树的先序、中序、后序序列
                                            先序序列：ABDEFC
中序序列：DBFEAC
后序序列：DFEBCA
3。已知一棵二叉树的先根和中根序列，画出其对应的二叉树并求其后根序列。
先根序列：A， B, C， D, E， F， G， H， I, J
中根序列：C, B， A, E， F, D, I, H， J,G
后根序列：C, B, F, E， I, J, H， G, D， A
6已知一棵二叉树的先序、中序和后序遍历序列分别为： (参看课件）
先序: BE×KCJADG×HI
中序: LK×CAJ××FGIH
后序： KL×JCEF××GDB 其中有些字母已丢失,请添写完整并画出此二叉树
7.在一份电文中共使用8种字符，即a， b， c, d, e， f, g, h，它们出现的频率依次为0。07， 0.19， 0.02,0。06, 0.32, 0.03， 0.21， 0.10，试画出对应的赫夫曼树，求出每个字符的赫夫曼编码，以及带权路径长度。
哈夫曼编码：a：0010 b：10 c：00000 d：0001 e：01 f:00001 g:11 树和wpl：略。
8.写出下图所示森林的先序、中序序列。将该森林转换为相应的二叉树.
先序序列：1、2、3、4、5、6、8、7、9、10、11、12、13、15、14
中序序列：3、4、8、6、7、5、2、1、10、9、11、15、13、14、12
9。 设二叉树后根遍历为BAC，画出所有可能的二叉树。
10、将如下森林转化成二叉树
11、已知某系统在通讯时，只出现C,A，S，T，B五种字符,它们出现的频率依次为2，4,2，3，3，试设计Huffman编码。要求画出哈夫曼树，给出编码，并求出带权路径长度）
12、假定用于通信的电文仅由a,b,c,d 4个数据元素,各字母在电文中出现的频率分别为7,5,2，4,试为这4个字母设计不等长的哈夫曼编码。（要求画出哈夫曼树，给出编码,并求出带权路径长度)
a：0  b:10  c：110  d：111  或  a:1  b:01  c:001  d:000
wpl=7*1+5＊2+2＊3+4＊3=35
13、在一份电文中共使用8种字符，即a, b， c, d, e, f， g， h，它们出现的频率依次为0。10, 0.09, 0.32， 0.02,0.26， 0。03， 0.01， 0。17 ，试画出对应的赫夫曼树，求出每个字符的赫夫曼编码.要求画出哈夫曼树，给出编码，并求出带权路径长度）
五、算法：
1.中序遍历二叉树（对二叉排序树,按递增顺序输出)。(先写存储结构，再写算法)
存储结构定义：
typedef struct BiTNode ｛ // 结点结构
    Selemtype data;
    struct BiTNode  *lchild， *rchild；  ｝ BiTNode， *BiTree；

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。