数据结构作业（四）2013-11-12.doc

数据结构作业（四） 2013-11-12 年级 2012B 班级 姓名 学号 一、填空题 1、一颗深度为6的二叉树总结点数值少为 ，最多为 ；一颗深度为6的完全二叉树第5层上的结点数为____，总结点数最小值为 ，总结点数最多时称为 二叉树。 2、对于一颗具有n个结点的二叉树，当它为一颗完全二叉树时具有最小高度，高度为 ，当它为一颗单支树具有最大高度，高度为 。 3、一颗完全二叉树第6层有7个结点，则共有 个结点，其中度为1的结点有 个，度为0的结点有 个，若按从上到下，从左到右次序给结点编号（从1开始），编号最大的非叶子结点是 ，编号最小的叶子结点是 。 4、设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为 ，至多为 。 5、对于一颗具有n个结点的二叉树，当进行二叉链表存储时，其指针域的总数为 个，其中 个用于链接孩子结点， 个空闲着。 6、已知二叉树中叶子数为50，仅一个孩子的结点数为30，则总结点数____；在有50个叶子结点的哈夫曼树中，总结点数是_ ___。 7、有5813个结点构成一棵完全二叉树，其叶子结点数为 ；有5813个结点构成一棵二叉树，已知2度结点数为0，则树高是 。 8、先序为a,b,c,且后序为c,b,a,的二叉树有 棵。 9、在二叉链表中，数据域值为data，左右子树的指针分别为lchild和rchild，则判断某指针p所指结点为0度结点的条件是 ；p所指结点为1度结点的条件是 ；p所指结点为2度结点的条件是 。 10、由带权为3，9，6，2，5的5个叶子结点构成一颗Huffman树，则带权路径长度为 。 二、选择题 1、按照二叉树的定义，具有三个结点的二叉树有 种形状。 A、3 B、4 C、5 D、6 2、一棵二叉树的叶子结点数为6，则度为1的结点个数为 。 A、5 B、7 C、6 D、不能确定 3、在非空二叉树的中序遍历序列中，根结点的右边 。 A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的部分结点 D、只有左子树上的所有结点 4、下列陈述中正确的是 。 A、二叉树是度为2的有序树 B、二叉树中结点只有一个孩子时无左右之分 C、二叉树中必有度为2的结点 D、二叉树中最多只有两棵子树，并且有左右之分 5、对有100个结点的完全二叉树按层次依次编号，则编号为49的结点右孩子编号为 。 A、98 B、51 C、99 D、97 6、如果n1和n2是二叉树T中两个不同结点，n2是n1的孩子，那么按 遍历二叉树T时，结点n2一定比结点n1先被访问。 A、先序 B、中序 C、后序 D、逆中序 7、某二叉树的中序序列和后序序列正好相反，则该二叉树一定是 的二叉树。 A、空或只有一个结点? B、高度等于其结点数? C、任一结点无左孩子? D、任一结点无右孩子 8、某二叉树的先序序列和后序序列正好相同，则该二叉树一定是 的二叉树。 A、空或只有一个结点 B、高度等于其结点数 C、任一结点无左孩子 D、任一结点无右孩子 9、一棵深度为8（根的层次号为1）的满二叉树有 个叶子结点 A、256 B、255 C、 128 D、 127 10、如图是用孩子兄弟链表法所表示的一个森林，则该森林是由 棵树构成。