作业-树和二叉树

《作业-树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、树（树根结点的高度为1）一、选择题3.以下说法错误的是（）。A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求双亲操作很容易实现C.在二叉链表上，求根以及求左、右孩子等操作很容易实现D.在二叉链表上，求双亲操作的时间性能很好4.以下说法错误的是（）oA.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2门-1个结点D.若初始森林中共有n棵二叉树，进行2ml次合并后才能剩下一棵最终的哈夫曼树5.深度为6的二叉树最多有（）个结点。A.64B

2、.63C.32D.316.将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为（）。A.10B.11C.41D.207•设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少（）个。A.k+1B.2kC.2k-1D.2k+l8.下列说法屮正确的是（）。A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中每个结点的度都为2C.任何一棵二叉树屮的每个结点的度肯定等于2D.任何一棵二叉树中的每个结点的度都可以小于29.一棵二叉树满足下列条件：对任意结点，若存在

3、左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（）遍历方式就可以得到这棵二叉树所有结点的递减序列。A.前序B.中序C.后序D.层次10.如图6-1所示的二叉树的中序遍历序列是（）o八・abcdgefB.dfebagcC・dbaefcgD・defbagc8.已知某二叉树的后序遍历序列是deacb,中序遍历序列是dcabc,它的前序遍历序列是（）。A・achedB・baedcC・dceabD.cedba9.某二叉树的前序遍历的结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbacchf,则其后序遍历的结点访问顺序是

4、（）。A.bdgccfhaB.gdbccfhaC.bdgcchfaD・gdbchfca13・在图6-2中的二叉树中，（c）不是完全二叉树。14.树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据15•哈夫曼树的带权路径长度是（）。A.所有结点权值之和B.所有叶结点带权路径长度之和C.带权结点的值D.除根以外所有结点权值之和16•设有一棵22个结点的完全二叉树，那么整棵二叉树有（）个度为0的结点。A.6B.7C.8D.1117.已知完全二叉树有26个结点，则整棵二叉树有（）个度为1的结点。A.0B.1

5、C.2D.1318.已知如图6-3所示的哈夫曼树，那么电文CDAA的编码是（）。A.110100B.11011100C.010110111D.1111110（）—图6-317.在n个结点的完全二叉树中，对任一结点i（l

6、结点最多有两棵子树，并且有左右之分20.图6-4所示的几种结构中属于树形结构的是（b）o图6-4二、判断题（标红色的是错误的）2.树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。3.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点则它必须是该子树的前序遍历序列中的最后一个结点。4.二叉树具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。5.在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。6.已知二叉树的前序遍历和后序遍历序列

7、不能惟一地确定这棵树。三、填空题1.树（及一切树形结构）是一种—分支层次结构。在树中，—根结点没有直接前驱。对树上任一结点x来说，X是它的任一子树的根结点惟一的—双亲O2.—棵树上的任何结点环包括根本身）称为根的—子孙o若B是A的子孙，则称A是B的祖先o1.二叉树第i(i>0)层上至多有—2M个结点。2.深度为k(k>0)的二叉树至多有2k-l个结点。3.对任何二叉树，若度为2的节点数为n2,则叶子数n()=_n2+l。4.满二叉树上各层的节点数已达到了二叉树可以容纳的—最大值。满二叉树也是—完全二叉树，但反之不然。5.具有门个结点的完全二叉树的深度为—1。财

8、取整+1o6.二叉树通常有顺序存储结构