资源描述：
《第6章树和二叉树习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途第六章 树和二叉树一、选择题1.算术表达式a＋ｂ*(c＋ｄ／e)转为后缀表达式后为(B )EFDGAB/++*-C*Ａ.aｂ+ｃde/*Ｂ.abcｄe／+*+ C．abcde/*+＋ D．abcdｅ*/＋+2． 设有一表示算术表达式的二叉树(见下图）,它所表示的算术表达式是（C )Ａ．Ａ＊B+C／(D＊Ｅ)+（F-G)B.(A＊B+C）/(D*E)+(F-G）C.(A*B＋C)/(Ｄ*Ｅ＋（F－G）) D.A*B+C／D*Ｅ+F-Ｇ3.设树T的度为4,其中度为1,2，3和4的结点个数分别为4，2，1，1 则Ｔ中的叶子数为(D ）Ａ．5 B.6 Ｃ.７ D．
2、84.在下述结论中,正确的是( D ）①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③ B．②③④ C．②④ D．①④5.设森林F对应的二叉树为B，它有m个结点,B的根为p,ｐ的右子树结点个数为n,森林Ｆ中第一棵树的结点个数是（A)A．m-nＢ.m-ｎ－１ C.ｎ＋1 Ｄ.条件不足,无法确定6.若一棵二叉树具有10个度为２的结点,５个度为１的结点,则度为０的结点个数是（B)A．9 B．11 C．15 Ｄ.不确定7.设森林Ｆ中有三棵树,第一,第二,第三棵树的结点个数分别为M
3、１,M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ D）。Ａ.M1 Ｂ．M１+M2 C.M3 D．M2＋M38．一棵完全二叉树上有1００１个结点，其中叶子结点的个数是（E)A．25０B. ５00 C．２54 Ｄ．505 Ｅ．以上答案都不对 9．有关二叉树下列说法正确的是(B ）A．二叉树的度为２ B.一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为２ Ｄ.二叉树中任何一个结点的度都为2１０．二叉树的第I层上最多含有结点数为( C)Ａ.2Ｉ B．2Ｉ-1－1 C.2I－1 D．2I-１1１
4、．一个具有1０25个结点的二叉树的高ｈ为(C )A.1１ Ｂ．1０ C.1１至１025之间D.10至1024之间12.一棵二叉树高度为h,所有结点的度或为０，或为2,则这棵二叉树最少有( B )结点A．2h B．2h-1C.2h+1 D．h+1 13．一棵树高为K的完全二叉树至少有(C)个结点A．2ｋ–１ Ｂ.2k-１–1 C.2k-1 D. ２ｋ14.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号，可采用( C ）次序的遍历实现编号。A.先序B． 中序 C.后序 Ｄ．从根开始按层次遍
5、历个人收集整理勿做商业用途15.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是（B ）A．CAＢDEFG B.ABＣDEFＧ C.DACＥFBG D.AＤCFEG １６．已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CＢAＥＤF，则后序遍历的结果为（Ａ)。A.CＢEＦDA B.ＦEＤCBA C.CBEDＦＡＤ．不定１7．对于前序遍历与中序遍历结果相同的二叉树为（１F）;对于前序遍历和后序遍历结果相同的二叉树为（２B）。A.一般二叉树 B.只有根结点的二叉树 C．根结点无左孩子的二叉树D.根结点无右孩子的二叉树E．所有结点只有左子数的二叉树Ｆ
6、.所有结点只有右子树的二叉树１8．在下列情况中，可称为二叉树的是（ Ｂ） A.每个结点至多有两棵子树的树 B．哈夫曼树 C．每个结点至多有两棵子树的有序树 Ｄ.每个结点只有一棵右子树 E.以上答案都不对１9．ｎ个结点的线索二叉树上含有的线索数为（ Ｃ ）A．2n B.n-l Ｃ．ｎ+l D．n20.由3个结点可以构造出多少种不同的二叉树？(D)Ａ．２ B．3 C.4 D．5 21.当一棵有n个结点的二叉树按层次从上到下,同层次从左到右将数据存放在一维数组 Ａ［l．.n]中时，数组中第ｉ个结点的左孩子为( D）Ａ.A[2i](2i=7、 C．A[ｉ/２] Ｄ.无法确定二、填空题１.二叉树由_（１)_＿,＿_(2)＿,_(3）__三个基本单元组成。2．中缀式ａ+b*３+４*(c-d)对应的前缀式为__(1)_，若a＝1,b=2,c=3，d=4，则后缀式ｄb／cｃ*a-b＊+的运算结果为_(2）__。３．具有２５6个结点的完全二叉树的深度为____＿_。4.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树
