树与二叉树：选择题50个

单项选择题
(C) 1． 不含任何结点的空树         。
      （Ａ）是一棵树;                         （Ｂ）是一棵二叉树; 
      （Ｃ）是一棵树也是一棵二叉树;           （Ｄ）既不是树也不是二叉树

(C) 2．二叉树是非线性数据结构，所以             。
       （Ａ）它不能用顺序存储结构存储;     （Ｂ）它不能用链式存储结构存储;  
      （Ｃ）顺序存储结构和链式存储结构都能存储;  （Ｄ）顺序存储结构和链式存储结构都不能使用

(C) 3.  具有n(n>0)个结点的完全二叉树的深度为
      (Ａ) [log2(n)]   (Ｂ)[log2(n)]  (Ｃ) [log2(n)]+1  (Ｄ)[log2(n)+1]

(A) 4．把一棵树转换为二叉树后，这棵二叉树的形态是           。
       （Ａ）唯一的                          （Ｂ）有多种
       （Ｃ）有多种，但根结点都没有左孩子    （Ｄ）有多种，但根结点都没有右孩子


(D 5.已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为(    )
       A．-A+B*C/DE    B. -A+B*CD/E   C．-+*ABC/DE    D. -+A*BC/DE


(A) 6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是
         A．m-n   B．m-n-1    C．n+1   D．条件不足，无法确定

(D) 7. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1  则T中的叶子数为（    ）
         A．5    B．6     C．7      D．8
         注：度为4的节点只有一个，也就是树的根节点。

(B) 8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（  ）
       A．9    B．11   C．15       D．不确定

(C) 9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（    ）个
       A．4    B．5    C．6      D．7 

(D) 10．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（    ）。
       A．M1   B．M1+M2       C．M3     D．M2+M3

(B)  11．具有10个叶结点的二叉树中有（  ）个度为2的结点
       A．8           B．9             C．10          D．ll

(E)  12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（    ）
     A． 250   B． 500    C．254     D．505      E．以上答案都不对  

(D)  13. 设给定权值总数有n 个，其哈夫曼树的结点总数为(    )
     A．不确定        B．2n         C．2n+1         D．2n-1

(D) 14. 有n个叶子的哈夫曼树的结点总数为（    ）。
    A．不确定          B．2n          C．2n+1          D．2n-1

(B) 15．算术表达式a+b*（c+d/e）转为后缀表达式后为（    ）
     A．ab+cde/*    B．abcde/+*+      C．abcde/*++    D．abcde*/++


(B) 16. 有关二叉树下列说法正确的是（    ）
     A．二叉树的度为2                   B．一棵二叉树的度可以小于2                                                                                
     C．二叉树中至少有一个结点的度为2   D．二叉树中任何一个结点的度都为2

(C) 17．二叉树的第I层上最多含有结点数为（  ）
     A．2^I     B． 2^(I-1)-1     C． 2^(I-1)     D．2^I-1

(C) 18. 一个具有1025个结点的二叉树的高h为（    ）
     A．11      B．10      C．11至1025之间      D．10至1024之间

(B) 19．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有(    )结点
     A．2h     B．2h-1        C．2h+1         D．h+1  

(D) 20．对于有n 个结点的二叉树, 其高度为（    ）
     A．nlog2(n)      B．log2(n)          C．[log2(n)]+1       D．不确定

(A) 21. 一棵具有 n个结点的完全二叉树的树高度（深度）是（    ）
     A．[log2(n)]+1       B．log2(n)+1        C．[log2(n)]      D．log2(n)-1

(A) 22．深度为h的满m叉树的第k层有（  ）个结点。(1=<k=<h)
      A．m^(k-1)     B．m^k-1      C．m^(h-1(      D．m^h-1

(C) 23．在一棵高度为k的满二叉树中，结点总数为（    ）
     A．2^(k-1)     B．2^k     C．2^k-1        D．[log2(k)]+1

(C) 24．高度为 K的二叉树最大的结点数为（    ）。
     A．2^k   B．2^(k-1)      C．2^k -1    D．2^(k-1)-1

(C) 25. 一棵树高为K的完全二叉树至少有（    ）个结点
     A．2^k –1   B. 2^(k-1( –1     C. 2^(k-1)       D. 2^k

(C) 26. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）
     A．4         B．5           C．6           D．7

(C) 27. 利用二叉链表存储树，则根结点的右指针是（    ）。
      A．指向最左孩子        B．指向最右孩子         C．空        D．非空

(C) 28．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，
其左孩子的编号小于其右孩子的编号，可采用(    )次序的遍历实现编号。
      A．先序      B. 中序          C. 后序          D. 从根开始按层次遍历

(B) 29．树的后根遍历序列等同于该树对应的二叉树的(    ).
     A. 先序序列         B. 中序序列            C. 后序序列


(D) 30. 在下述结论中，正确的是（    ）
      ①只有一个结点的二叉树的度为0;  ②二叉树的度为2； ③二叉树的左右子树可任意交换;
      ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
      A．①②③        B．②③④      C．②④       D．①④


(D) 31．在下列存储形式中，哪一个不是树的存储形式？（    ）
    A．双亲表示法  B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法

(B) 32．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（    ）
    A．CABDEFG    B．ABCDEFG    C．DACEFBG    D．ADCFEG 
  
(A) 33．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（    ）。
    A．CBEFDA       B． FEDCBA       C． CBEDFA       D．不定  

(D) 34．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac ,  它的前序遍历是（    ）。

      A．acbed       B．decab    C．deabc      D．cedba  

(D) 35. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，  则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（    ）
     A．A[2i](2i<=n)  B．A[2i+1](2i+1<=n)  C．A[i-2]   D．条件不充分，无法确定
    注：没有要把这棵二叉树当作完全二叉树。

(D) 36. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左孩子为（    ）
     A．A[2i](2i=<n)  B. A[2i+1](2i+1=< n)    C．A[i/2]    D．无法确定

(C) 37．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJGK 。该二叉树根的右子树的根是：
    A、 E    B、 F　     C、 G　      D、 H  

(B) 38．将一棵树t 转换为孩子—兄弟链表表示的二叉树h，则t的后根序遍历是h 的
    A．前序遍历     B．中序遍历      C．后序遍历（    ）

(B) 39．下面几个符号串编码集合中，不是前缀编码的是（    ）。
     A．{0,10,110,1111}  B．{11,10,001,101,0001} 
    C．{00,010,0110,1000}     D．{b,c,aa,ac,aba,abb,abc}

(B) 40．下面的说法中正确的是（    ）.
（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；
（2）按二叉树定义，具有三个结点的二叉树共有6种。
    A．(1)(2)   B．(1)   C．(2)    D．(1)、(2)都错 

41．对于前序遍历与中序遍历结果相同的二叉树为（F）;
    对于前序遍历和后序遍历结果相同的二叉树为（B）。
    A．一般二叉树    B．只有根结点的二叉树     C．根结点无左孩子的二叉树
    D．根结点无右孩子的二叉树  E．所有结点只有左子数的二叉树
    F．所有结点只有右子树的二叉树

(C) 42．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（    ）
    A．所有的结点均无左孩子  B．所有的结点均无右孩子 
    C.只有一个叶子结点  D．是任意一棵二叉树

(B) 43．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（    ）
     A．都不相同　　B．完全相同   C．先序和中序相同，而与后序不同　
     D．中序和后序相同，而与先序不同 

(C) 44．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。
     A．空或只有一个结点    B．任一结点无左子树  
     C．高度等于其结点数    D．任一结点无右子树

(C) 45．在完全二叉树中，若一个结点是叶结点，则它没（    ）。
    A．左子结点    B．右子结点　  C．左子结点和右子结点
    D．左子结点，右子结点和兄弟结点

(B) 46．在下列情况中，可称为二叉树的是（    ）
    A．每个结点至多有两棵子树的树     B. 哈夫曼树 
    C．每个结点至多有两棵子树的有序树
    D. 每个结点只有一棵右子树         E．以上答案都不对 

(D) 47. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：(    )
    A．不确定         B. 0        C. 1        D. 2  

(B) 48. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：(    )。
    A. 0            B. 1        C. 2          D. 不确定

(C) 49. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为(    )
    A.X的双亲   B.X的右子树中最左的结点
     C.X的左子树中最右结点   D.X的左子树中最右叶结点

(A)   50. 引入二叉线索树的目的是（    ）
     A．加快查找结点的前驱或后继的速度   B．为了能在二叉树中方便的进行插入与删除
     C．为了能方便的找到双亲      D．使二叉树的遍历结果唯一

(C) 51. 线索二叉树是一种（    ）结构。
    A． 逻辑    B． 逻辑和存储   C． 物理     D．线性

(C) 52．n个结点的线索二叉树上含有的线索数为（    ）
     A．2n      B．n－l       C．n＋l         D．n
     注：线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。

(C) 53．（    ）的遍历仍需要栈的支持.
     A．前序线索树     B．中序线索树      C．后序线索树 

(D) 54．二叉树在线索后，仍不能有效求解的问题是（    ）。
    A．前（先）序线索二叉树中求前（先）序后继  B．中序线索二叉树中求中序后继
    C．中序线索二叉树中求中序前驱  D．后序线索二叉树中求后序后继