数据结构第六章题目.doc

02一 选择题：1、以下说法错误的是 ①树形结构的特点是一个结点可以有多个直接前趋 ②线性结构中的一个结点至多只有一个直接后继③树形结构可以表达(组织)更复杂的数据 ④树(及一切树形结构)是一种分支层次结构⑤任何只含一个结点的集合是一棵树 2．深度为6的二叉树最多有( )个结点 ①64 ②63 ③32 ④31 3 下列说法中正确的是 ①任何一棵二叉树中至少有一个结点的度为2 ②任何一棵二叉树中每个结点的度都为2 二叉树可空 ③任何一棵二叉树中的度肯定等于2 ④任何一棵二叉树中的度可以小于2 4 设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（ ）个结点。 ①n1-1 ②n1 ③n1+n2+n3 ④n2+n3+n4 二．名词解释：1 结点的度 3。叶子 4。分支点 5。树的度 三 填空题 二叉树第i(i=1)层上至多有_____个结点。 深度为k(k=1)的二叉树至多有_____个结点。 如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1=i=n)的结点X有：若i=1,则结点X是_ ____；若i〉1,则X的双亲PARENT(X)的编号为__ ____。 若2in，则结点X无_ _____且无_ _____；否则，X的左孩子LCHILD(X)的编号为____。 若2i+1n，则结点X无__ ____；否则，X的右孩子RCHILD(X)的编号为_____。 4．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。 Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/ {if(t!=NULL) {if((t-lchild==NULL)(t-rchild==NULL))__ __; countleaf(t-lchild,count); countleaf(t-rchild,count);} } 5 先根遍历树和先根遍历与该树对应的二叉树，其结果_____。 6 由 ____转换成二叉树时，其根结点的右子树总是空的。 7 哈夫曼树是带权路径度___ _____的树，通常权值较大的结点离根__ ______。 8 一棵树的形状如图填空题33所示，它的根结点是_____，叶子结点是______，结点H的度是_____，这棵树的度是_____，这棵树的深度是________，结点F的儿子结点是______，结点G的父结点是_____。 9任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为_____ ___个。 03一、填空1． 由３个结点所构成的二叉树有 种形态。 2. 一棵深度为6的满二叉树有 个分支结点和 个叶子。 3． 一棵具有２５７个结点的完全二叉树，它的深度为 。 4. 设一棵完全二叉树具有1000个结点，则此完全二叉树有(100-511)= 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。 5. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 。 6. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 。 7.一个深度为h的二叉树最多有 结点，最少有 结点。 二、选择题1．二叉树是非线性数据结构，所以 。 （Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储; （Ｃ） 顺序存储结构和链式存储结构都能存储; （Ｄ）顺序存储结构和链式存储结构都不能使用 2. 具有n(n0)个结点的完全二叉树的深度为 。 (Ａ) (log2(n)( (Ｂ) ( log2(n)( (Ｃ) ( log2(n) (+1 (Ｄ) (log2(n)+1( 3．把一棵树转换为二叉树后，这棵二叉树的形态是 。（