第6章--树和二叉树-作业.docx

《第6章--树和二叉树-作业.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树和二叉树2一、选择题1.设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-12.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个A．4B．5C．6D．73.二叉树的第I层上最多含有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-14.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）A．4B．5C．6D．75.一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间6.对二叉树的结点从1开始进行连续编号，要求每个结

2、点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。【北京理工大学2000一、4（2分）】A．先序B．中序C．后序D．从根开始按层次遍历7.在下列存储形式中，哪一个不是树的存储形式？（）A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法8.下面的说法中正确的是（）.（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；（2）按二叉树定义，具有三个结点的二叉树共有6种。A．(1)(2)B．(1)C．(2)D．(1)、(2)都错9.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A．空或只有

3、一个结点B．任一结点无左子树C．高度等于其结点数D．任一结点无右子树10.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树11.在完全二叉树中，若一个结点是叶结点，则它没（）。A．左子结点B．右子结点　C．左子结点和右子结点D．左子结点，右子结点和兄弟结点12．在下列情况中，可称为二叉树的是（）A．每个结点至多有两棵子树的树B.哈夫曼树C．每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树E．以上答案都不对13.线索二叉树是一种（）结构。A．逻辑B．逻辑和存储C．物理D．线

4、性14.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()A．X的双亲B．X的右子树中最左的结点C．X的左子树中最右结点D．X的左子树中最右叶结点15.引入二叉线索树的目的是（）A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一题号12345678910答案题号1112131415答案二、判断题1.完全二叉树中，若一个结点没有左孩子，则它必是树叶。2.对一棵二叉树进行层次遍历时，应借助于一个栈。3.由一棵二叉树的前序序列和后序序列可以唯一确定它。4.二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们

5、还知道该树的根结点是那一个，则可以确定这棵二叉树。5.二叉树的遍历只是为了在应用中找到一种线性次序。6.二叉树中序线索化后，不存在空指针域。7.非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子8.霍夫曼树的结点个数不能是偶数。题号12345678答案三、应用题1.试证明，在具有n(n>=1)个结点的m次树中，有n(m-1)+1个指针是空的。2.将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）NPGHJMOLIKEDFBAC3.已知一个森林的先序序列和后序序列如下，请构造出该森林。先根序列：ABCDEFGHIJKLMNO后根序列：CDEBFHIJGAMLONK4.已

6、知一组字符及其权值如下：a:35,b:9,c:19,d:27,e:81,f:14,g:21,h:12,i:25,j:5,k:11,l:8请构造相应的哈夫曼树，画出结果哈夫曼树并计算出WPL。四、算法设计题1.设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不能用栈。KHFEABGICD2.利用栈的基本操作写出先序遍历二叉树的非递归算法要求进栈的元素最少，并指出下图中二叉树中需进栈的元素。3.编写一个函数或过程判定两棵二叉树是否相似（相似只是对比树的形状，不对比结点的数据域），所谓两棵二叉树s和t相似，即是要么它们都为空或都只有一个结点，要么它们的左右子树都相似。