树图查找排序复习讲解.doc

树 一、判断题： 1.二叉树是一棵无序树。（×） 2.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。（√） 3.度为二的有序树等价于二叉树。（√） 4.树的带权路径长度最小的二叉树中必定没有度为1的结点。（√） 5.哈夫曼树一定是满二叉树。（×） 6.满二叉树也是完全二叉树。（√） 7.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（×） 8.将一棵树转换成二叉树后，根结点没有左子树(×) 9.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（√） 10用二叉树的前序遍历和中序遍历可以导出树的后序遍历。（√） 11.在完全二叉树中,若某结点无左孩子,则它必是叶结点。（√）。 12．任何一棵二叉树都有n0=n2+1的关系式。（√） 13．已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树。（ √ ） 二、填空题 假定一棵二叉树的结点个数为32，则它的最小深度为___6___,最大深度为：32。 在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，那么叶子结点有__6____ 个。 树的双亲表示法便于实现涉及到___双亲___的操作，孩子表示法便于实现涉及到孩子的 操作。 对于一颗具有n个结点的二叉树，对应二叉链表中指针域有__n-1__个用于指向子结点。 下图所示二叉树存储在一维数组中，则元素F的下标位置为___11___。（A为1） A B C D E F 高度为k的二叉树具有的结点数目，最少为___ K ___,最多为___2K-1___。 对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=__ n2+1__。 一棵含有16个结点的完全二叉树，对他按层编号，对于编号为7的结点，他的双亲结编号点为___3___左孩子编号为____14__、右孩子编号为___15___。 在含100个结点的完全二叉树，叶子结点的个数为___50_____。 度数为0的结点，即没有子树的结点叫作___叶子_____结点。同一个结点的儿子结点之间互称为____兄弟____结点。 若一棵完全二叉树含有121个结点，则该树的深度为_____7______。 已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为____ ABCDFE _______。 三、选择题 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于___C___。 A. n B. n-1 C. n+1 D. 2*n 在一棵二叉树的第5层上，最多具有___B___个结点。 A. 14 B. 16 C. 31 D. 32 在一棵深度为h的完全二叉树中，所含结点个数不少于___D___。 A. 2h B. 2h+1 C. 2h -1 D. 2h-1 一棵树的广义表表示为a(b(c), d(e(g(h)), f))，则该二叉树的高度为___D___。 A. 2 B. 3 C. 4 D. 5 将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为___A___。 A.30 B.31 C.16 D.32 在一棵树中，每个结点最多有___B___个直接前驱结点。 A. 0 B. 1 C. 2 D. 任意多个 7. 树中所有结点的度数之和等于结点总数加___C___。 A. 0 B. 1 C. -1 D. 2 二叉树中第5层上的结点个数最多为____C____A.8 B.15 C.16 D.32 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为___A___。A.98 B.99 C.50 D.48 由权值分别为3, 8, 6, 2, 5的叶子结点生成一颗赫夫曼树，它的带权路径长度为__D___。A. 24 B. 48 C. 72 D. 53 把一棵树转换为二叉树后，这棵二叉树的形态是 A 。Ａ.唯一的 Ｂ.有多种Ｃ.有多种，但根结点都没有左孩子 Ｄ.有多种，但根结点都没有右孩子 具有n(n0)个结点的完全二叉树的深度为 C 。Ａ élog2(n)ù Ｂ ?