一、选择题(每小题1分)
1．二叉树第i(i≥1)层最多有( )个结点。
(a)2i， (b)2i (c)2i-1 (d)2i-1
2．线索化二叉树中某结点d，没有左孩子的主要条件是( )
(a)d一＞lchild＝null (b)d一＞ltag＝1
(c)d一＞rchild＝null (d)d一＞ltag＝0
3．在下列4棵树中，哪一棵是完全二叉树( )
4．具有2000个结点的二叉树，其高度至少为( )
〔a)9 (b)10 (c)11 (d)12
5．在一棵度为3的树中，度为3的结点数有2个，度为2的结点数有1个，度为l的结点数有2个，那么度为0的结点数有( )个。
(a)4 (b)5c)6d)7
6．一棵完全二叉树中根结点的编号为l，而且23号结点有左孩子但没有右孩子，则完全二叉树总共有( )个结点。
(a)24 (b)45 (c)46 (d)47
7．一棵huffman树总共有11个结点，则叶子结点有( )个。
(a)5 (b)6c)7d)9
8．森林转换为二叉树后，从根结点开始一直沿着右子树下去，一共有4个结点，表明( )
(a)森林有4棵树b)森林的最大深度为4
(c)森林的第一棵树有4层 (d)森林有4个结点。
9．在有n个结点的二叉链表中，值为非空链域的个数为( )
a)n-l (b)2n-1 (c)n+1 (d)2n+1
10．某二叉树的中序序列和后序序列正好相反，则该二叉树一定是( )的二叉树。
(a)空或只有一个结点 (b)高度等于其结点数。
(c)任一结点无左孩子 (d)任一结点无右孩子。
二、填空题(每空2分)
1．给定一个整数集合，画出其对应的一棵huffman树。
2．设f是森林，b是由f转换得到的二叉树，f中有n个非终端结点，b中右指针域为空的结点有。
3．先序序列和中序序列相同的二叉树为。
4．已知一棵二叉树的中序遍历结果为dbheaficg，后序遍历结果为dhebifgca，画出该二又树。
5．线索化二叉树中某结点d，没有左孩子的主要条件是。
6．后序序列和中序序列相同的二叉树为。
7．具有128个结点的完全二叉树的深度为。
8．如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子的逻辑表达式为。
9．一棵深度为k的完全二叉树的结点至多有___个，至少有___个。
10．一棵含有n个结点的m叉树，可能达到的最大深度是可能达到的最小深度是。
11．已知一棵树共有n（n>1）个结点的树，其中所有分支结点的度均为k（1≤k＜n），则该树的叶子数目为个。
12．已知一棵度为m（m>1）的树中有n1个度为1的结点，n2个度为2的结点，……nm个度为m的结点，则该树中有个叶子结点。
13．下列算法是输出一颗二叉树的第i层的所有结点的值，假定根结点是第1层。
typedef struct linknode
outiouti
三、应用题。
1．设二叉树的顺序存储结构如下：(4分)
(1)根据其存储结构，画出二叉树。
(2)写出按先序、中序、后序遍历该二叉树所得的结点序列。
(3)画出二叉树的后序线索化树。
2．一棵完全二叉树共有21个结点，现顺序存放在一个矢量中，矢量的下标正好为结点的序号，试问序号为12的双亲结点存在吗？为什么？(4分)
3．已知一棵二叉树的中序遍历结果为dbheaficg，先序遍历结果为abdefhcfig，试画出该二叉树。
4．设右图所示的二叉树是由森林转换而成的，试将它还原为森林。(5分)
5．假设用于通信的电文仅有8个字母组成，字母在电文**现的频率分别为7，19，2，6，32，3，21，10，试为这8个字母设计哈夫曼编码。
6．(1)给出右图所示树的后序遍历结果。(4分)
(2)采用孩子-兄弟法将该树转换为一棵二叉树。（5分）
四、算法设计。
1．试写出求二又树结点数目的算法。
2．设计一个算法，用于查找中序线索二叉树中结点*p的中序前驱结点。
3．设计一个算法，求出指定结点在给定的二叉树中所在的层次。
4．已知二叉树结点数据结构如下，编写算法，在一棵二叉树中查找值为x的叶子结点，若找到返回该结点的指针，找不到则返回空指针。
typedef struct linknode{
int data;
struct linknode *lchild; *rchild;
node;5．已知二叉树结点数据结构如下，编写算法求二叉树的非叶子结点数目。
typedef struct linknode{
int data;
struct linknode *lchild; *rchild;
node;
第6章 树作业提示
第6章树。6.1 求二叉树的叶子结点数。1 参 1，利用函数返回值记录叶子结点数。int leafcount bitree root 返回二叉树root中的叶子结点数。if root null return 0 if root lchild null root rchild null return ...
第6章作业
15.设某异步通信接口，每帧信息格式为10位，当接口每秒传送1000个字符，其波特率为多少？答 波特率为 1000 10bit s 10000bit s 19 用汇编语言和c语言编程实现一个双机通信系统，将甲机的片内ram中30h 3fh的数据块，传送到乙机片外ram中0030h 003fh中，并画...
第6章作业
第6章高聚物的分子运动。1.已知聚乙烯 pe 和聚甲基丙烯酸甲酯 pmma 的流动活化能 e 分别为10千卡 摩尔和46千卡 摩尔，聚乙烯在200 时粘度为9.1 102泊，聚甲基丙烯酸甲酯在240 时粘度为2.0 103泊，a 分别计算聚乙烯在210 和190 时以及聚甲基丙烯酸甲酯在250 和2...