树测试习题树测试习题.ppt

判断题 1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 2.二叉树中每个结点的两棵子树的高度差等于1。 3.二叉树中每个结点的两棵子树是有序的。 4.二叉树中每个结点有两棵非空子树或有两棵空子树。 5.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i－1个结点。 判断题 6. 具有12个结点的完全二叉树有5个度为2的结点。 7.完全二叉树的某结点若无左孩子，则它必是叶结点。二叉树中，具有两个子女结点的中序后继结点最多只能有一个子女。 8.存在这样的二叉树，对它采用任何次序的遍历，结果相同。 9.二叉树就是结点度为2的树。 10.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。 11. 当k≥1时，高度为k的二叉树至多有2k-1个结点。 判断题 12.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。 13．已知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。 14．一棵含有n个结点的完全二叉树，它的高度是㏒2n+1。 15．将一棵树转换成二叉树后，根结点没有左子树。 16.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 填空题 1． 由３个结点所构成的二叉树有 种形态。 2. 一棵深度为6的满二叉树有 个分支结点和 个叶子。 3． 一棵具有２５７个结点的完全二叉树，它的深度为 。 4. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。 5. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 。 填空题 6、深度为k的完全二叉树至少有___个节点。 7、___的二叉树中序和后序的遍历次序完全相同 8、在二叉树的一维数组存储方式中，父节点和右孩子的索引值之间满足的关系是___ 9．对于一棵具有n个结点的树，该树中所有结点的度数之和为_______。 10．下图为某树的静态双亲链表表示，则结点D、E的双亲结点分别为_______。 填空题 11．一棵具有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点n1=______。 12．如果结点A有3兄弟，而且B是A的双亲，则B的度是______。 13．对于一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，则其编号为________；若右孩子结点存在，则其编号为________；而双亲结点的编号为 _________。 14．在下图的树中，结点H的祖先为_________________。 填空题 15．二叉树通常有_________存储结构和____________存储结构。 16.设高为h的二叉树只有度为0和2的结点,则此类二叉树的结点数至少为( ),至多为( ). 17、 线索二叉树的左线索指向其（），右线索指向其（）。 选择题 1． 不含任何结点的空树 （Ａ）是一棵树; （Ｂ）是一棵二叉树; （Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树 2．二叉树是非线性数据结构，所以 。 （Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储; （Ｃ）顺序存储结构和链式存储结构都能存储; （Ｄ）顺序存储结构和链式存储结构都不能使用 3. 具有n(n0)个结点的完全二叉树的深度为 。 (Ａ) ?log2(n)? (Ｂ) ? log2(n)? (Ｃ) ? log2(n) ?+1 (Ｄ) ?log2(n)+1? 选择题 4. 树是结点的有限集合，它 A 根结点，记为T。其余的结点分成为m（m≥0）个 B 的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数为该结点的 C 。 供选择的答案 A： ①有0个或1个 ②有0个或多个 ③有且只有1个 ④有1个或1个以上 B: ①互不相交 ② 允许相交 ③ 允许叶结点相交 ④ 允许树枝结点相交 C： ①度 ② 维数 ③ 次数 ④ 序 答案：A= B= C=