第6章--树和二叉树单元测试(答案)

第六章树和二叉树姓名：学号：一、选择题1.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．82.一棵具有n个结点的完全二叉树的树高度（深度）是（）A．log2n+1B．log2n+1C．log2nD．log2n-13．高度为k的二叉树最大的结点数为（）。A．2kB．2k-1C．2k-1D．2k-1-14.利用二叉链表存储树，则根结点的右指针（）。A．指向最左孩子B．指向最右孩子C．为空指针D．为非空指针5．森林的先序遍历序列等同于对应的二叉树的().A.先序序列B.中序序列C.后序序列D.层次序列6.已知一棵二叉树的先序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不确定7.引入线索二叉树的目的是（）A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便地进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一8．3个结点的二叉树有（）种不同的形态。A．2B．3C．4D．5二、判断题1.二叉树是度为2的有序树。2.对一棵二叉树进行层次遍历时，应借助于一个栈。3.树的先根遍历和其相应的二叉树的先序遍历的结果是一样的。4.中序遍历一棵二叉排序树的结点就可得到排好序的结点序列5.根据任何一棵二叉树的先序序列和后序序列可以唯一确定这棵二叉树。6.二叉树中每个结点至多有2个子结点,而对一般树则无此限制.因此,二叉树是树的特殊情形.7.树形结构中元素之间存在一个对多个的关系。8.完全二叉树的存储结构通常采用顺序存储结构。9.树与二叉树是两种不同的树型结构。10.哈夫曼树的结点个数不能是偶数。1.×2.×3.√4.√5.×6.×7.√8.√9.√10.√三、填空题1.二叉树由根结点、左子树、右子树三个基本单元组成。2.在二叉树中，指针p所指结点为叶子结点的条件是p-lchild==NULL&&p-rchlid==NULL3.具有N个结点的二叉树，采用二叉链表存储，共有N+1个空链域。4.一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。5.若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69。6.设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有2n0-1个结点。四、应用题1．从概念上讲，树、森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。答：树的孩子兄弟链表表示法和二叉树的二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别如下：（1）二叉树的度至多为2，树无此限制；（2）二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制。2．将算术表达式（a+b）-c*(d+e)/f转化为二叉树，并根据该二叉树，求出其前缀和后缀表达式。3.一棵有n(n0)个结点的d度树,若用多重链表表示,树中每个结点都有d个链域,则在表示该树的多重链表中有多少个空链域?为什么?答：n（n0）个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-(n-1)=n(d-1)+1个。4．对于任何一棵非空的二叉树,假设叶子结点的个数为n0,而次数为2的结点个数为n2,请给出n0和n2之间所满足的关系式。解：设度为1和2及叶子结点数分别为n0，n1和n2，则二叉树结点数n满足：n=n0+n1+n2(1)再看二叉树的分支数，除根结点外，其余结点都有一个分支进入，设B为分支总数，则B=n-1。(2)而度为1和2的结点各有1个和2个分支，度为0的结点没有分支，即：B=n1+2n2(3)于是由（1）、（2）和（3），得n0=n2+1。5．设某二叉树的先序遍历序列为:ABCDEFGGI，中序遍历序列为:BCAEDGHFI，试画出这棵二叉树。6．设有正文AADBAACACCDACACAAD,字符集为{A,B,C,D},设计一套二进制编码，使得上述正文的编码最短。五、算法设计题（参加实验大纲）