一、选择题。
1．按照二叉树定义，具有3个结点的二叉树共有 c 种形态。
(a) 3 (b) 4 (c) 5d) 6
2．具有五层结点的完全二叉树至少有 d 个结点。
(a) 9 (b) 15 (c) 31 (d) 16
3．以下有关二叉树的说法正确的是 b 。
a) 二叉树的度为2b)一棵二叉树的度可以小于2
c) 至少有一个结点的度为2 (d)任一结点的度均为2
4．已知二叉树的后序遍历是dabec，中序遍历是debac，则其前序遍历是 d
（a）acbed （b）decab (c) deabc (d) cedba
5．将一棵有1000个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为 b 。
a) 98b) 99 (c) 50 (d) 没有右孩子。
6．对具有100个结点的二叉树，若有二叉链表存储，则其指针域共有 d 为空。
a) 50b) 99 (c) 100 (d) 101
7．设二叉树的深度为h，且只有度为1和0的结点，则此二叉树的结点总数为 c 。
a) 2hb) 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个结点的二叉树，当它为一棵完全二叉树时具有最小高度；当它为单分支时，具有最大高度。
2．在二叉树的第i（i≥1）层上至多有 2i-1 个结点，深度为k（k≥1）的完全二叉树至多 2k-1 个结点，最少 2k-1 个结点；
3．如果二叉树的终端结点数为n0，度为2的结点数为n2，则n0 = n2+1
4．已知一棵二叉树的中序序列是cbedahgijf，后序序列是cedbhjigfa，则该二叉树的先序序列是 abcdefghij该二叉树的深度为 5
5．若一棵二叉树的中序遍历结果为abc，则该二叉树有 5 中不同的形态。
6．在顺序存储的二叉树中，下标为i和j的两个结点处在同一层的条件是 log2i=log2j 。
7．已知完全二叉树的第7层有8个结点，则其叶子结点数为 36 个。总结点数为 71 个。
8．在对二叉树进行非递归中序遍历过程中，需要用栈来暂存所访问结点的地址；进行层序遍历过程中，需要用队列来暂存所访问结点的地址；
9．高度为h，度为k的树中至少有 h+k-1 个结点，至多有 (kn-1)/(k-1) 个结点。
10．一维数组存放完全二叉树：abcdefghi，则后序遍历该二叉树的序列为 hidebfgca
三、应用题。
1. 应用题：说明分别满足下列条件的二叉树各是什么？
先序遍历和中序遍历相同；
中序遍历和后序遍历相同；
3)先序遍历和后序遍历相同；
思考：tlr、ltr、lrt
（1）空树、只有根结点、右单分支二叉树；
2）空树、只有根结点、左单分支二叉树。
3）空树、只有根结点。
2. 已知一棵二叉树的中序序列是cbedahgijf，后序序列是cedbhjigfa，画出这棵二叉树的逻辑结构图。
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的计算公式；
2)若此树是深度为k的完全二叉树，写出n为最小的公式；
3)若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式；
(1)记度为2的结点个数为n2，则 n=n0+n1+n2，另一方面，除了根结点以外，其余结点均有父结点的分支射出，所以结点数n=1+n1+2*n2；综合上面两式可得n1=n+1-2n0。
2)当树是深度为k的完全二叉树时，n的最小值nmin=2k-1；
3)当二叉树中仅有度为0和2的结点时，二叉树的结点个数n=2n0-1。
四、算法设计题。
1．编写求二叉树bt中结点总数的算法。
int btreecount(btreenode *bt) ｛二叉树中结点的总数。
if(bt==null)
return 0;
else if(bt->left ==null&&bt->right ==null)
return 1;
elsereturn btreecount(bt->left ) btreecount(bt->right ) 1;
2．编写求二叉树bt中叶子结点数的算法。
int btreecount(btreenode *bt) /二叉树中结点的总数。
if(bt==null)
return 0;
else if(bt->left ==null&&bt->right ==null)
return 1;
elsereturn btreecount(bt->left ) btreecount(bt->right )
3．若已知两棵二叉树bt1和bt2皆为空，或者皆不为空且bt1的左、右子树和bt2的左、右子树分别相似，则称二叉树bt1和bt2相似。编写算法，判别给定的两棵二叉树是否相似。
int btreesim(btreenode *bt1, btreenode *bt2) /判断两棵二叉树是否相似。
if(!bt1&&!bt2) return 1;
else if (!bt1||!bt2) return 0;
else return btreesim(bt1->lchild,bt2->lchile)&&btreesim(bt1->rchild,bt2->rchild);
4．编写算法，求二叉树中以元素值为x的结点为根的子树的深度。
int get_sub_depth(btreenode *bt , elemtype x) /值为x的结点为根的子树的深度。
if(!bt) return 0;
else if(bt->data==x) return depthbtree(bt);
else if(bt->lchild!=null) return get_sub_depth(bt->lchild ,x);
else if(bt->rchild!=null) return get_sub_depth(bt->rchild,x);
else return 0;
int depthbtree(btreenode *bt)｛ 求二叉树bt的深度。
if(!bt) return 0; /空树深度为0
else 5．编写算法，计算二叉树中度为1的结点数和度为2的结点数。
int s1=0,s2=0;
void btreebranch(btreenode *bt) {
if(bt!=null) {
数据结构实验二叉树
下列程序中的统计二叉树结点的函数，是对二叉树遍历方法的应用，请认真理解然后模仿练习。二叉树的建立与遍历 include include typedef int etype typedef struct bitnode 树结点结构体 bitnode 函数原形声明 bitnode creat bt1 b...
数据结构实验十 树及二叉树的应用试验
一，实验题目。试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表存储，且树中结点的关键字均不相同。二，问题分析。本程序要求判别一个以二叉链表存储且树中结点的关键字均不相同的给定的二叉树是否为二叉排序树，完成这些操作需要解决的关键问题是 以二叉链表的存储形式输入一个二叉树。用一个函数实现...
第六章树和二叉树习题 数据结构
一 单项选择题。1 以下说法错误的是 a 树形结构的特点是一个结点可以有多个直接前趋。b 线性结构中的一个结点至多只有一个直接后继。c 树形结构可以表达 组织 更复杂的数据。d 树 及一切树形结构 是一种 分支层次 结构。e 任何只含一个结点的集合是一棵树。2 下列说法中正确的是 a 任何一棵二叉树...