文档介绍：树和二叉树习题第四课树和二叉树一、选择题1(已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为()。A(-A+B*C/DEB(-A+B*CD/EC(-+*ABC/DED(-+A*BC/DE参考答案:D2(当一棵有n个结点的二叉树按层次从上到下,同层次从左到右将数据存放在一维数组A[l..n]中时,数组中第i个结点的左孩子为()。A(A[2i](2i<=n)B(A[2i+1](2i+1<=n)C(A[i/2]D(无法确定参考答案:D3(一棵完全二叉树上有1001个结点,其中叶子结点的个数是()。A(250B(500C(254D(505E(以上答案都不对参考答案:E4(设树T的度为4,其中度为1、2、3和4的结点个数分别为4、2、1、1,则T中的叶子数为()。A(5B(6C(7D(8参考答案:D5(在下述结论中,正确的是()。?只有一个结点的二叉树的度为0;?二叉树的度为2;?二叉树的左右子树可任意交换;?深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A(???B(???C(??D(??参考答案:D6(设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是()。A(m-nB(m-n-1C(n+1D(条件不足,无法确定参考答案:A7(若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是()。A(9B(11C(15D(不确定参考答案:B8(在一棵三元树中度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,则度为0的结点数为()个。A(4B(5C(6D(7参考答案:C9(设森林F中有三棵树,第一、第二、第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是()。A(M1B(M1+M2C(M3D(M2+M3参考答案:D10(具有10个叶结点的二叉树中有()个度为2的结点。A(8B(9C(10D(11参考答案:B11(下述编码中不是前缀码的是()。A((00,01,10,11)B((0,1,00,11)C((0,10,110,111)D((1,01,000,001)参考答案:B12(设给定权值总数有n个,其哈夫曼二叉树的结点总数为()。A(不确定B(2nC(2n+1D(2n-1参考答案:D13(下面几个符号串编码集合中,不是前缀编码的是()。A({0,10,110,1111}B({11,10,001,101,0001}C({00,010,0110,1000}D({b,c,aa,ac,aba,abb,abc}参考答案:B14(有关二叉树下列说法正确的是()。A(二叉树的度为2B(一棵二叉树的度可以小于2C(二叉树中至少有一个结点的度为2D(二叉树中任何一个结点的度都为2参考答案:B15(二叉树的第i层上最多含有结点数为()。ii-1i-1iA(2B(2-1C(2D(2-1参考答案:C16(一个具有1025个结点的二叉树的高h为()。A(11B(10C(11至1025之间D(10至1024之间参考答案:C17(一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有()结点。A(2hB(2h-1C(2h+1D(h+1参考答案:B18(对于有n个结点的二叉树,其高度为()。A(nlognB(lognC(,logn,+1D(不确定222参考答案:D19(一棵具有n个结点的完全二叉树的树高度(深度)是()。A(,logn,+1B(logn+1C(,logn,D(logn-1参考答案:A20(深度为h的满m叉树的第k层有()个结点。(1=<k=<h)k-1kh-1hA(mB(m-1C(mD(m-1参考答案:A21(在一棵高度为k的满二叉树中,结点总数为()。k-1kkkA(2B(2C(2-1D(,log2,+1参考答案:C22(高度为k的二叉树最大的结点数为()。kk-1kk-1A(2B(2C(2-1D(2-1参考答案:C23(一棵树高为k的完全二叉树至少有()个结点。kk-1k-1kA(2–1B(2–1C(2D(2参考答案:C24(将有关二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高度()。A(4B(5C(6D(7参考答案:C25(利用二叉链表存储树,则根结点的右指针是()。A(指向最左孩子B(指向最右孩子C(空D(非空参考答案:C26(对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用()次序的遍历实现编号。A(先序B(中序C(后序D(从根开始按层次遍历参考答案:C27(树的后根遍历序列等同于该树对应的二叉树的()。A(先序序列B(中序序列C(后序序列参考答案: