数据结构练习（二叉树）
一、选择题
1．按照二叉树定义，具有3个结点的二叉树共有    C    种形态。
    (A) 3      (B) 4        (C) 5        (D) 6         
2．具有五层结点的完全二叉树至少有  D    个结点。
    (A) 9      (B) 15      (C) 31        (D) 16         
3．以下有关二叉树的说法正确的是    B    。
(A) 二叉树的度为2              (B)一棵二叉树的度可以小于2 
(C) 至少有一个结点的度为2      (D)任一结点的度均为2
4．已知二叉树的后序遍历是dabec，中序遍历是debac，则其前序遍历是      D    。                   
  （A）acbed    （B）decab      (C)  deabc        (D) cedba   
5．将一棵有1000个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为    B    。
(A) 98        (B) 99        (C) 50      (D) 没有右孩子
6．对具有100个结点的二叉树，若有二叉链表存储，则其指针域共有  D    为空。
(A) 50        (B) 99        (C) 100      (D) 101
7．设二叉树的深度为h，且只有度为1和0的结点，则此二叉树的结点总数为  C      。
(A) 2h        (B) 2h-1      (C) h        (D) h+1
8．对一棵满二叉树，m个树叶，n个结点，深度为h，则    D  。
(A) n=h+m      (B) h+m=2n    (C)m=h-1    (D)n=2h-1
9．某二叉树的先序序列和后序序列正好相反，则下列说法错误的是    A    。
(A) 二叉树不存在
(B) 若二叉树不为空，则二叉树的深度等于结点数
(C) 若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子
(D) 若二叉树不为空，则任一结点的度均为1
10．对二叉树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用  C  遍历实现编号。
(A) 先序      (B)中序    (C)后序      (D)层序
11．一个具有二叉树公式1025个结点的二叉树的高h为  C 。
(A) 10        (B)11        (C)11~1025    (D)10~1024
12．设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是  C    。
( A) n在m右方            (B)n是m祖先
(C) n在m左方            (D) n是m子孙
13．实现对任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用  C    存储结构。
(A) 二叉链表    (B) 广义表      (C)三叉链表      (D)顺序
14. 一棵树可转换成为与其对应的二叉树，则下面叙述正确的是    A      。
(A) 树的先根遍历序列与其对应的二叉树的先序遍历相同
(B) 树的后根遍历序列与其对应的二叉树的后序遍历相同
(C) 树的先根遍历序列与其对应的二叉树的中序遍历相同
(D) 以上都不对
二、填空题
1．对一棵具有n个结点的二叉树，当它为一棵    满    二叉树时具有最小高度；当它为  度为
1        时，具有最大高度。
2．在二叉树的第i（i≥1）层上至多有      2^(i-1)      个结点，深度为k（k≥1）的完全二叉树至多    2^(k)-1      个结点，最少      2^(k-1)      个结点；
3．如果二叉树的终端结点数为n0，度为2的结点数为n2，则n0 =       n2+1       。
4．已知一棵二叉树的中序序列是cbedahgijf，后序序列是cedbhjigfa，则该二叉树的先序序列是    abcdefghig        ，该二叉树的深度为    5        。
5．若一棵二叉树的中序遍历结果为ABC，则该二叉树有  5  中不同的形态。
6．在顺序存储的二叉树中，下标为i和j的两个结点处在同一层的条件是    log2(i)=log2(j)    。
7．已知完全二叉树的第7层有8个结点，则其叶子结点数为  36  个。总结点数为  71  个。
8．在对二叉树进行非递归中序遍历过程中，需要用  栈    来暂存所访问结点的地址；进行层序遍历过程中，需要用  队列    来暂存所访问结点的地址；
9．高度为h，度为k的树中至少有  h+k-1      个结点，至多有    k^(h)-1    个结点。
10．一维数组存放完全二叉树：ABCDEFGHI，则后序遍历该二叉树的序列为      HIDEBFGCA      。
三、应用题
1. 应用题：说明分别满足下列条件的二叉树各是什么？
⑴先序遍历和中序遍历相同；空树，只有一个根节点或右单分支二叉树。
⑵中序遍历和后序遍历相同；空树，只有一个根节点或左单分支二叉树。
⑶先序遍历和后序遍历相同；空树，只有一个根节点的二叉树。
2. 已知一棵二叉树的中序序列是cbedahgijf，后序序列是cedbhjigfa，画出这棵二叉树的逻辑结构图。
                                  A
                          B                F
                    C        D      G
                          E      H      I
                                              J
                                 
3.一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，试构造出该二叉树。
先序序列：A B C D E F G H I J K
中序序列：C B E D F A H J K I G
后序序列：C E F D B K J I H G A
4.有n个结点的二叉树，已知叶子结点个数为n0,回答下列问题：
(1)写出求度为1的结点的个数n1的计算公式；  n1=n+1-2n0
(2)若此树是深度为k的完全二叉树，写出n为最小的公式；  n(min)=2^(k-z)
(3)若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式；n=2n0-1
5.按列表为[ 32,25,16,35,34,20,40 ]中的数据创建一棵二叉查树,画出此二叉查树，并写出此二叉查树的先序、中序、后序遍历序列。
先序：32,25,16,20,35,34,40
中序：16,20,25,32,34,35,40
后序：20,16,25,34,40,35,32
四、算法设计题
1．编写求二叉树BT中结点总数的算法。
2．编写求二叉树BT中叶子结点数的算法。
3．若已知两棵二叉树BT1和BT2皆为空，或者皆不为空且BT1的左、右子树和BT2的左、右子树分别相似，则称二叉树BT1和BT2相似。编写算法，判别给定的两棵二叉树是否相似。
4．编写算法，求二叉树中以元素值为x的结点为根的子树的深度。

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