数据结构习题与答案--树和二叉树.docVIP

PAGE PAGE 1 第七章 树和二叉树 一、判断题 ( t )01、若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 ( f )02、二叉树中每个结点的两棵子树的高度差等于1。 (t )03、二叉树中每个结点的两棵子树是有序的。 ( f )04、二叉树中每个结点有两棵非空子树或有两棵空子树。 ( f )05、二叉树中所有结点个数是2k-1-1，其中k是树的深度。 (f )06、二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 ( f )07、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。 (t )08、用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 (t)09、具有12个结点的完全二叉树有5个度为2的结点。 ( f )10、二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值，且小于其右非空子树(若存在的话)所有结点的关键字值。 ( f )11、二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索。 ( t )12、二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。 二、填空题 01、由3个结点所构成的二叉树有_5_种形态。 02、一棵深度为6的满二叉树有____个分支结点和____个叶子。 03、一棵具有257个结点的完全二叉树，它的高度为______深度为____。 04、设一棵完全二叉树有700个结点，则共有____个叶子结点。 05、设一棵完全二叉树具有1000个结点，则此完全二叉树有____个叶子结点，有____个度为2的结点，有____个结点只有非空左子树，有____个结点只有非空右子树。 06、一棵含有n个结点的k叉树，可能达到的最大深度为____，最小深度为____。 07、二叉树的基本组成部分是：根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种：前序法(即按N L R次序)，后序法(即按LRN次序)和中序法(也称对称序法，即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是____。 08、用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是____。 三、选择题 ( )01、树最适合用来表示__。 A)有序数据元素 B)无序数据元素 C)元素之间具有分支层次关系的数据 D)元素之间无联系的数据 ( )02、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为__个。 A)15 B)16 C)17 ( )03、假定一棵三叉树的结点数为50，则它的最小高度为__。 A)3 B)4 C)5 ( )04、在一棵二叉树上第5层的结点数最多为__。 A)8 B)16 C)15 ( )05、用顺序存储方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有子树，则左子树是结点__。 A)R[2i+1] B)R[2i] C)R[i/2] D)R[2i-1] ( )06、在一棵具有k层的满三叉树中，结点总数为__。 A)(3k-1)/2 B)3k-1 C)(3k-1)/3 ( )07、由带树为9,2,5,7的四个叶子结点树造一棵哈夫曼树，该树的带权路径长度为__。 A)29 B)37 C)46 ( )08、具有n(n0)个结点的完全二叉树的深度为 。 A)?log2(n)? B)?log2(n)? C)?log2(n)?+1 D)?log2(n)+1? ( )09、由n个数据元素构造的哈夫曼树，共有( )个结点。 A)n-1 B)2n-1 C)2n ( )10、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序__。 A)不发生改变 B)发生改变 C)不能确定 D)以上都不对 ( )11、设a,b为一棵二叉树上的两个结点，在中序遍历中，a在b前面的条件是__。 A)a在b的右方 B)a在b的左方 C)a是b的祖先 D)a是b的子孙 ( )12、如图所示，其中__不是完全二叉树。 ( )13、在线索二叉树中，t所指结点没有左子树的充要条件是__。 A)t-lchild==NULL B)t-ltag==1 C)t-ltag==1 t-lchild==NULL D)以上都不对 ( )14、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__。 A)2h B)2h-1 C)2h+1 ( )15、以下