树和二叉树习题

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

1、第6章树和二叉树一、选择题1．算术表达式a+b*（c+d/e）转为后缀表达式后为（B）EFDGAB/++*-C*A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++2.设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（C）A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C.(A*B+C)/(D*E+（F-G）)D.A*B+C/D*E+F-G3.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中

2、的叶子数为（D）A．5B．6C．7D．84.在下述结论中，正确的是（D）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④5.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（A）A．m-nB．m-n-1C．n+1D．条件不足，无法确定6．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（

3、B）A．9B．11C．15D．不确定7．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（D）。A．M1B．M1+M2C．M3D．M2+M38．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（E）A．250B．500C．254D．505E．以上答案都不对(501)9.有关二叉树下列说法正确的是（B）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为210

4、．二叉树的第I层上最多含有结点数为（c）A．2IB．2I-1-1C．2I-1D．2I-111.一个具有1025个结点的二叉树的高h为（C）A．11B．10C．11至1025之间D．10至1024之间12．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有(B)结点A．2hB．2h-1C．2h+1D．h+113.一棵树高为K的完全二叉树至少有（C）个结点A．2k–1B.2k-1–1C.2k-1D.2k14．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号

5、，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用(C)次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历15．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（B）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG16．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（A）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定17．对于前序遍历与中序遍历结果相同的二叉树为（F）;对于

6、前序遍历和后序遍历结果相同的二叉树为（B）。A．一般二叉树B．只有根结点的二叉树C．根结点无左孩子的二叉树D．根结点无右孩子的二叉树E．所有结点只有左子数的二叉树F．所有结点只有右子树的二叉树18．在下列情况中，可称为二叉树的是（B）A．每个结点至多有两棵子树的树B.哈夫曼树C．每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树E．以上答案都不对19．n个结点的线索二叉树上含有的线索数为（C）A．2nB．n－lC．n＋lD．n20．由3个结点可以构造出多少种不同的二叉树？（D）A．2B．3

7、C．4D．521.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（A）A．A[2i](2i=

8、结点的完全二叉树的深度为___9___。4．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有____12__个叶子结点。5．深度为k的完全二叉树至少有___2^(k-1)____个结点，至多有___(2^k)-1___个结点。6．设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为_N/2_____。7．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是__2^(k-2)