树与二叉树
一.选择题
1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（    ）个。
A．15            B．16            C．17            D．47
2.按照二叉树的定义，具有3个结点的不同形状的二叉树有（    ）种。
A. 3            B. 4            C. 5            D. 6
3.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（    ）种。
A. 5            B. 6            C. 30            D. 32
4.深度为5的二叉树至多有（    ）个结点。
A. 16            B. 32            C. 31            D. 10
5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（    ）。   
A. 2h            B. 2h-1            C. 2h+1            D. h+1
6.对一个满二叉树，m个树叶，n个结点，深度为h，则（    ）。
A. n=h+m         B. h+m=2n      C. m=h-1      D. n=2 h-1
7.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（    ）。
A.不发生改变    B.发生改变        C.不能确定        D.以上都不对
8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为（    ）。       
A. uwvts        B. vwuts        C. wuvts        D. wutsv
9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（    ）。
A. bdgcefha        B. gdbecfha        C. bdgaechf        D. gdbehfca
10.在一非空二叉树的中序遍历序列中，根结点的右边（    ）。
A. 只有右子树上的所有结点        B. 只有右子树上的部分结点
C. 只有左子树上的部分结点        D. 只有左子树上的所有结点
11.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（    ）是正确的。
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D.以上都不对
12.如图所示二叉树的中序遍历序列是（    ）。
A. abcdgef       
B. dfebagc       
C. dbaefcg       
D. defbagc
13.一棵二叉树如图所示，其中序遍历的序列为（    ）。
A. abdgcefh       
B. dgbaechf       
C. gdbehfca       
D. abcdefgh
14.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（    ）。
A．a在b的右方                        B．a在b的左方
C．a是b的祖先                        D．a是b的子孙
15.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（    ）。
A. acbed        B. decab            C. deabc        D. cedba
16.如下图所示的4棵二叉树，（    ）不是完全二叉树。
A                B                C                D
17.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（    ）存储结构。
A. 二叉链表        B. 广义表存储结构    C. 三叉链表        D. 顺序存储结构
18.树最适合用来表示（    ）。
A. 有序数据元素                        B. 无序数据元素
C. 元素之间具有分支层次关系的数据    D. 元素之间无联系的数据
19.某二叉树结点的中序序列为A.B.C.D.E.F.G，后序序列为B.D.C.A.F.G.E，则其左子树中结点数目为（    ）。
A. 3            B. 2                C. 4            D. 5
20.二叉树是非线性数据结构，所以（    ）。
A.它不能用顺序存储结构存储;
B.它不能用链式存储结构存储;
C.顺序存储结构和链式存储结构都能存储;
D.顺序存储结构和链式存储结构都不能使用
21.具有n(n>0)个结点的完全二叉树的深度为（    ）。
A. log2(n)                            B. 10（log2(n)）+1       
C. log2(n) +1                        D. log2(n)+1
22.把一棵树转换为二叉树后，这棵二叉树的形态是（    ）。
A.唯一的                            B.有多种
C.有多种，但根结点都没有左孩子        D.有多种，但根结点都没有右孩子
23.线索二叉树是一种（    ）结构。
A． 逻辑        B． 逻辑和存储        C． 物理        D．线性
24.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（    ）。
A.98                B.99                C.50            D.48
25.设森林F中有三棵树，第一.第二和第三棵树的结点个数分别为M1.M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（    ）。
A．M1            B．M1+M2            C．M3            D．M2+M3
26.将一棵有100个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为（    ）。
  A.48                B.49                C.50            D.51
27.引入二叉线索树的目的是（    ）。
A.加快查结点的前驱或后继的速度
B.为了能在二叉树中方便的进行插入与删除
C.为了能方便的到双亲           
D.使二叉树的遍历结果唯一
28.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（    ）。
A．9            B．11            C．15            D．不确定
29.一棵树深度为K的完全二叉树至少有（    ）个结点
A．2k –1        B. 2k-1-1            C. 2k-1            D. 2k
30.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（    ）。
A．CABDEFG        B．ABCDEFG        C．DACEFBG        D．ADCFEG 
31.有关二叉树下列说法正确的是（    ）。
A．二叉树的度为2                   
B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2   
D．二叉树中任何一个结点的度都为2
32.一个具有1025个结点的二叉树的高h为（    ）。
A．11                            B．10
C．11至1025之间                D．10至1024之间
33.对于有n 个结点的二叉树, 其高度为（    ）。
A．nlog2n        B．log2n            C． log2n+1        D．不确定
34.已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac ,它的先序遍历是（    ）。
A．acbed        B．decab        C．deabc        D．cedba   
35.若二叉树采用二叉链表存储结构，要交换其所有分支结点左.右子树的位置，利用（    ）遍历方法最合适。
A．前序            B．中序            C．后序            D．按层次
36.在下列存储形式中，（    ）一个不是树的存储形式？
A．双亲表示法                    B．孩子链表表示法
C．孩子兄弟表示法                D．顺序存储表示法
37.在下列关于二叉树的叙述中，正确的是（    ）。
①只有一个结点的二叉树度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
    A．①②③        B．②③④        C．②④            D．①④
38.若x是二叉中序线索树中一个不为根的有左孩子的结点则x的前驱为（    ）。
A.X的双亲                        B.X的右子树中最左的结点 
C.X的左子树中最右结点            D.X的左子树中最右叶结点 
39.在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（    ）。
A．都不相同            B．完全相同       
C．先序和中序相同，而与后序不同　
D．中序和后序相同，而与先序不同
40.在线索化二叉树中，t所指结点没有右子树的充要条件是（    ）。
A.t->Rtag==1                         B.t->Rchild==NULL
C.t->Rtag==1 && t->Rchild==NULL        D.以上都不对
41.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（    ）。
A．2h                                B．2h-1
C．2h+1                                D．h+1
42.如右图所示二叉树的中序遍历序列是（    ）。
A．abcdgef       
B．dfebagc       
C．dbaefcg       
D．defbagc
43.设a和b为一棵二叉树上的两个结点，在中序遍历时a在b前的条件是（    ）。
A．a是b的左孩子                            B．b是a的右孩子
C．a是b左子树上结点或b是a右子树上结点    D．以上三项均可
44.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（    ）个。
A．    45            B．15            C．16            D．31
45.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（    ）个空指针域。
A．2m-1            B．2m            C．2m+1            D．4m
46.二叉树的第k层的结点数最多为（    ）。
A．2k-1                            B．2K+1
C．2K-1                            D．2K-1
47.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（    ）。
A．9            B．10            C．11            D．12
48.一棵有n个结点的树，在把它转换成对应的二叉树后，该二叉树根结点的左子树上共有（    ）二叉树定义个结点。
A．n-2            B．n-1            C．n+1            D．n+2
49.对于一棵深度为4的三叉树，最多有（    ）个结点。
A．30            B．36            C．40            D．54
50.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（    ）。
    A．3            B．4            C．5            D．1
51.关于哈夫曼树，下列说法正确的是( )。
A．在哈夫曼树中，权值相同的叶子结点都在同一层上
B．在哈夫曼树中，权值较大的叶子结点一般离根结点较远
C．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近
D．在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理
二.判断题
1.线索二叉树是一种逻辑结构。                                    （×）
2.二叉树中每个结点的两棵子树是有序的。                            （√）
3.深度为K的完全二叉树至少有2K-1个结点。                        （√）
4.在哈夫曼树中，权值最小的结点离根结点最近。                    （×）
5.二叉树中每个结点的两棵子树的高度差等于1。                    （×）
6.具有12个结点的完全二叉树有5个度为2的结点。                （√）
7.二叉树中每个结点有两棵非空子树或有两棵空子树。                （×）
8.哈夫曼树中没有度为1的结点，所以必为满二叉树。                （×）
9.二叉树中所有结点个数是2k-1-1，其中k是树的深度。                （×）
10.二叉树的遍历操作实际上是将非线性结构线性化的过程。            （√）
11.具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。            （√）
12.前序和中序遍历用线索树方式存储的二叉树，不必使用栈。            （√）
13.树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。        （√）
14.树的后根遍历序列与其所转化的二叉树的后序遍历序列相同。        （×）
15.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。    （×）
16.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。    （×）
17.哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。    （×）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。