资源描述：
《树图查找排序复习讲解.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、树一、判断题：1.二叉树是一棵无序树。（×）2.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。（√）3.度为二的有序树等价于二叉树。（√）4.树的带权路径长度最小的二叉树中必定没有度为1的结点。（√）5.哈夫曼树一定是满二叉树。（×）6.满二叉树也是完全二叉树。（√）7.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（×）8.将一棵树转换成二叉树后，根结点没有左子树(×)9.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。
2、（√）10用二叉树的前序遍历和中序遍历可以导出树的后序遍历。（√）11.在完全二叉树中,若某结点无左孩子,则它必是叶结点。（√）。12．任何一棵二叉树都有n0=n2+1的关系式。（√）13．已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树。（√）二、填空题1.假定一棵二叉树的结点个数为32，则它的最小深度为___6___,最大深度为：32。2.在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，那么叶子结点有__6____个。3.树的双亲表示法便于实现涉及到___双亲___的操作，孩子表示法便于实现涉及到孩子的操作。4.对于
3、一颗具有n个结点的二叉树，对应二叉链表中指针域有__n-1__个用于指向子结点。5.下图所示二叉树存储在一维数组中，则元素F的下标位置为___11___。（A为1）ABCDEF1.高度为k的二叉树具有的结点数目，最少为___K___,最多为___2K-1___。2.对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=__n2+1__。3.一棵含有16个结点的完全二叉树，对他按层编号，对于编号为7的结点，他的双亲结编号点为___3___左孩子编号为____14__、右孩子编号为___15___。4.在含100
4、个结点的完全二叉树，叶子结点的个数为___50_____。5.度数为0的结点，即没有子树的结点叫作___叶子_____结点。同一个结点的儿子结点之间互称为____兄弟____结点。6.若一棵完全二叉树含有121个结点，则该树的深度为_____7______。7.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为____ABCDFE_______。三、选择题1.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于___C___。A.nB.n-1C.n+1D.2*n2.在一棵二叉树的第5层上，
5、最多具有___B___个结点。A.14B.16C.31D.323.在一棵深度为h的完全二叉树中，所含结点个数不少于___D___。A.2hB.2h+1C.2h-1D.2h-14.一棵树的广义表表示为a(b(c),d(e(g(h)),f))，则该二叉树的高度为___D___。A.2B.3C.4D.55.将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为___A___。A.30B.31C.16D.321.在一棵树中，每个结点最多有___B___个直接前驱结点。A.0B
6、.1C.2D.任意多个2.7.树中所有结点的度数之和等于结点总数加___C___。A.0B.1C.-1D.23.二叉树中第5层上的结点个数最多为____C____A.8B.15C.16D.324.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为___A___。A.98B.99C.50D.485.由权值分别为3,8,6,2,5的叶子结点生成一颗赫夫曼树，它的带权路径长度为__D___。A.24B.48C.72D.536.把一棵树转换为二叉树后，这棵二叉树的形态是
7、A。Ａ.唯一的Ｂ.有多种Ｃ.有多种，但根结点都没有左孩子Ｄ.有多种，但根结点都没有右孩子7.具有n(n>0)个结点的完全二叉树的深度为C。Ａélog2(n)ùＢëlog2(n)ûＣëlog2(n)û+1Ｄélog2(n)+1ù8.ù四、应用题1..将下图转换为二叉树，对转换后的二叉树进行先序、中序、后序遍历序列。ABCDEFGJ先序：ABEFCDGJ中序：EFBCGJDA后序：FEJGDCBA2.写出下图所示二叉树的先序、中序、后序序列ABCDEF先序序列：ABDEFC中序序列：DBFEAC后序序列：DFEBCA3.已知一棵二叉树的
8、先根和中根序列，画出其对应的二叉树并求其后根序列。先根序列：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,A6已知一棵二叉树的先序、中序和后序遍历序
