2022年数据结构二叉树 3.pdf
练习六一.单选题1.设二叉树的第1 层为根结点，则第i 层最多有 _个结点。A)2i B)2i -1C)2i-1 D)2i+1 2.设二叉树的第1 层为根结点，深度为k 的二叉树最多有_个结点。A)2k-1B)2k+1C)2k-1D)2k 3.对任一棵二叉树T，如果其叶结点数为n0，度数为1 的结点数为n1，度数为2 的结点为n2，则 n0=_。A)n1+1B)n+1 C)n2+1 D)n1+n2 4.在一棵二叉树中，若一个结点是叶结点，则它没有_。A)左子结点B)右子结点C)左子结点和右子结点D)左子结点、右子结点和兄弟结点5.在二叉树结点的先序序列、中序序列和后序序列中，所有叶结点的先后顺序_。A)都不相同B)先序和中序相同，而与后序不同C)完全相同D)中序和后序相同，而与先序不同6.由 3 个结点可以构造出_种不同形态的二叉树。A)2 B)3C)4D)5 7.带权路径长度最短的二叉树称为_。A)诺伊曼树B)线索二叉树C)B+ 树 D)赫夫曼树8.树结构最适合用来表示_ 。A)有序数据B)元素间没有关联的数据C)无序数据D)元素间具有分支、层次关系的数据9.深度为 k 的二叉树所含叶子的个数最多为_。A)2k-1B)kC)2kD)2k-1 10.设有一棵n 个叶结点的哈夫曼树，其树中总结点数是_。A)n(n+1) B)n C)n-1D)2n-1 11.具有 10 个叶结点的二叉树中有_个度为 2 的结点。 P124 A) 9 B) 8C) 10 D) 11 12.一个具有1025 个结点的二叉树的高h 为_。P124 A)11 至 1025 之间 B)11C)10 D)10 至 1024 之间13.在线索二叉树中，t 所指结点没有左子树的必要条件是_。P132 A)t-ltag =1 B)t-left =NULL C)t-ltag =1 且 t-left =NULLD)以上都不对14.由权值 3，8，6，5，2 的叶子结点生成一棵赫夫曼树，它的带权路径长度为_。A)53 B)48 C)72D)24 15.已知某二叉树的后序遍历是dabec，中序序列是debac，则它的先序序列是_。A)cedbaB)acbedC)deabcD)decab 16.线索二叉树是一种_结构。A)逻辑 B)存储 C) 线性存储D)逻辑存储17.深度为 5 的二叉树最多有_结点。A)32 B)31C)16 D)10 18.下列关于哈夫曼树的叙述中，错误的是_。A)具有 n 个权值的哈夫曼树共有2n-1 个结点 B)哈夫曼树是一棵二叉树，因此，它的结点的度可以是0、1 或 2 C) 哈夫曼树根结点的权值等于所有叶结点的权值之和D)具有 n 个权值的哈夫曼树含有n-1 个非叶结点19.下面的说法中，正确的是_。A)任何一棵二叉树的叶子结点在三种遍历中的相对次序不同名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - B)用二叉树的前序遍历和中序遍历可以导出其后序遍历C)按二叉树定义，具有三个结点的二叉树共有6 种D)完全二叉树一定存在度为1 的结点20.下面的说法中，错误的是_。A)用二叉树的前序遍历和中序遍历可以导出其后序遍历B)任何一棵二叉树的叶子结点在三种遍历中的相对次序相同C)按二叉树定义，具有三个结点的二叉树共有5 种D)完全二叉树可以存在度为1 的结点21.在下述二叉树的结论中，正确的是_。A)二叉树的度为2B)深度为 K的完全二叉树的结点个数大于或等于深度相同的满二叉树。C)二叉树的左右子树可任意交换;D)只有一个结点的二叉树的度为0 22.在下述二叉树的结论中，正确的是_。A)只有一个结点的二叉树的度为1B)二叉树的度为2C)深度为K 的完全二叉树的结点个数大于或等于深度相同的满二叉树。D)二叉树的左右子树不可以任意交换; 23.一棵完全二叉树上有1001 个结点，其中叶子结点的个数正确是_。A)500B)254C)505D)501(最大层有490=1001-511 个结点，次最大层有11=511-1001/2) 个结点 ) 24.关于二叉树，下面说法错误的是_。A)完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B)在三叉链表上，二叉树的求双亲操作很容易实现C)在二叉链表上，求根以及左、右孩子等操作很容易实现D)在二叉链表上，求双亲的时间性能很好25.关于二叉树，下面说法正确的是_。A)完全二叉树上结点之间的父子关系不能完全由它们编号之间的关系来表达B)在二叉链表上，求双亲的时间性能很好C)在二叉链表上，求根以及左、右孩子等操作不容易实现D)在三叉链表上，二叉树的求双亲操作很容易实现二、判断题1.用二叉链表存储有n 个结点的二叉树，结点的2n 个指针中，只利用了n-1 个指针，其余n+1 个是空指针。2.树是一种线性数据结构。3.用一维数组存储二叉树，总是以先序遍历的顺序存储各结点。4.哈夫曼树是一棵二叉树，它的结点的度可以是0、1 或 2。5.深度为 K的完全二叉树的结点个数小于或等于深度相同的满二叉树。三、填空题1.假设二叉树的第1 层为根结点，则具有n 个结点的二叉树的最大高度是_。2.带权结点A、B、C、D 的权值分别为8、6、1、5，则 B 结点的哈夫曼编码（二进制）为_。(权值小的叶结点为左子树) 3.设森林 F由 n 棵树组成， 它的第一棵树， 第二棵树， , ，第 n 棵树分别有t1，t2，, ，tn 个结点，则与森林F 对应的二叉树中，根结点的左子树有_个结点。4.在树中，一个结点的直接子结点的个数称为该结点的_。5.已知完全二叉树的第七层有10 个结点，则整个二叉树有_ 个结点。6.若叶结点A 只有三个兄弟(不包括 A 本身 ),并且 B是 A 的双亲结点 ,则 B 的度是 _。7.将一棵有50 个结点的完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组b51中，并从b1开始存放，这棵二叉树最下面一层上最左边一个结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 存储在数组元素_中。8.假定一棵二叉树的结点数为18， 则它的最小深度为_， 最大深度为 _。9.对于具有30 个结点的完全二叉树，若一个结点的编号为5，则它的左孩子的编号为_，右孩子的结点为_ ，双亲结点结点的编号为_ 。10.设森林中有4 棵树，结点个数分别为n1、n2、n3、 n4，当把森林转换成一棵二叉树后，根结点的右子树上有_结点。四、应用题1.简要回答树和二叉树之间有什么区别和联系。2.已知一棵二叉树如下，请分别写出按先序、中序、后序和层次遍历时得到的结点序列。3.假设用于通信的电文由字符集A，B，C，D，E， F ，G中的字母构成，它们出现的频率依次为 10、9、2、7、8、6、3。试画出对应的哈夫曼树，并计算它的WPL 值。4.试画出下图所示森林对应的二叉树。5.已知二叉树的中序和后序序列分别如下，请构造出该二叉树。中序序列： CBEDAFIGH 后序序列： CEDBIFHGA 6.已知二叉树的中序和后序序列分别如下，请构造出该二叉树。中序序列： BDFHGIJECA 后序序列： HJIGFEDCBA 7.有一份电文中共使用6 个字符： a，b，c， d，e，f，它们的出现频率依次为2，3，4， 7，8，9，试构造一棵哈夫曼树，计算其加权路径长度WPL 和字符c 的编码（要求将频率小的结点出现在左子树上） 。五、编程题1.一棵 n 个节点的完全二叉树以一维数组作为存储结构，一维数组sMAX用于实现栈， top表示栈顶的位置。写非递归算法实现对该二叉树的前序遍历；用C语言实现。给定结构说明如下：#define MAX 100 函数首部为：Preorder (int n, char a ) /* 前序遍历由数组a 存储的具有n 个节点的完全二叉树*/ 1. 参考答案Preorder (intn ,char a ) int sMAX, top= -1, i=1; if(n=0) return 0; else top+; stop=i; /* 结点入栈 (根节点序号 )*/ while(top-1) /* 栈不空 */ printf( “c%,astop) ；top-; /* 输出结点，退栈*/ if(2*i+1n) /* 确定左子树，右子树位置*/ i=2*i; top+;stop=i+1; /* 右子树序号入栈*/ top+;stop=i; /* 左子树序号入栈*/ else if (2*idata)为二叉树结点访问函数，可直接调用。# include #define MAX 100 typedefstructBSTNode /* 二叉排序树的存储结构*/ TElemType data；structBSTNode *lchild ， *rchild ； BSTNode,*Bitree void inorder(Bitreebt) /* 中序遍历二叉树非递归算法*/ 2. 参考答案voidinorder(Bitreebt) Bitree stackMAX，p；int top ；if(bt= =NULL) return；top=0；p=bt；while(!(p= =NULL & top= =0) while(!p= =NULL) if(toplchild；/ 指针指向左孩子 if(topdata); p=p-rchild ； 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -
