数据结构习题(三).doc

数据结构习题（三） 一、填空题 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、如图是用孩子兄弟链表法所表示的一个森林，则该森林是由 棵树构成。 A．1 B．2 C．3 D．4 三、算法阅