数据结构复习(6树习题).ppt

《数据结构复习(6树习题).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构复习(习题)7/24/20211第六章树和二叉树(选择题)1．已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE2．算术表达式a+b*（c+d/e）转为后缀表达式后为（）A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++√√7/24/202123.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）

2、A．5B．6C．7D．84.在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④√因为每个结点都有一条枝指向它，分支数为1*4+2*2*3*1+4*1所有结点数为分支数+1，所以1*4+2*2*3*1+4*1=4+2+1+1+xx=8√7/24/202136．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15

3、D．不确定7.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M3√√森林转换得到的二叉树中，其左子树加根为森林的第一棵树√7/24/202149．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．50

4、0C．254D．50110.设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-1完全二叉树中度为1的结点最多只有1个，由二叉树的度和结点的关系n=n0+n1+n2n=n1+2n2+1得n=2n0+n1-1√哈夫曼树中没有度为1的节点，叶子节点个数为n√7/24/2021511.有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为212.一个具有1025个结点的二叉树的高h为（）A．

5、11B．10C．11至1025之间D．10至1024之间13．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A．2hB．2h-1C．2h+1D．h+1√√完全二叉树和单枝树之间√7/24/2021614．对于有n个结点的二叉树,其高度为（）A．nlog2nB．log2nC．log2n

6、+1D．不确定15.一棵具有n个结点的完全二叉树的树高度（深度）是（）A．logn+1B．logn+1C．lognD．logn-116．深度为h的满m叉树的第k层有（）个结点。(1=

7、=

8、始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历21．树的后根遍历序列等同于该树对应的二叉树的().A.先序序列B.中序序列C.后序序列22．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG√√√当该二叉树所有结点的左子树为空时，先序遍历序列和中序遍历序列相同。7/24/2021

9、923．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定24.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是：A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不对25.上题的二叉树对应的森林包括多少棵树（）A．