一、 概念题（每空1分，共55分）
1．树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的________。
2．由３个结点所构成的二叉树有 种形态。
3．一棵深度为6的满二叉树有 个分支结点和 个叶子。
4．一棵具有２５７个结点的完全二叉树，它的深度为 。
5．二叉树第i(i>=1)层上至多有______个结点；深度为k(k>=1)的二叉树至多有______个结点。
6．对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。
7．满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。
8．设一棵完全二叉树有700个结点，则共有 个叶子结点。
9.设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。
10.一棵含有n个结点的k叉树，可能达到的最大深度为 ，最小深度为 。
11.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 。
12.中序遍历的递归算法平均空间复杂度为 。
13.二叉树通常有______存储结构和______存储结构两类存储结构。
14.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：
（1） 若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。
（2） 若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。
（3） 若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。
15. 每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。
16.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指针，或者是______。
17.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。
18.二叉树有不同的链式存储结构，其中最常用的是________与________。
19.若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。
20.树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为________和________，即使在结点只有一棵子树的情况下，也要明确指出该子树是________还是________。
21.树的结点数目至少为________，二叉树的结点数目至少为________。
22. 下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，分别为：数据域 data，左、右孩子域 lchild、rchild和左、右标志域 ltag,rtag。规定，标志域为1是线索，O是指向孩子的指针。
inordethread(thr)
{p=thr->lchild;
while (p<>thr) ∥ 未循环结束
{ while((1) ) p= (2) ;
printf(p->data);
while((3) ) { p=(4) ；printf(p->data);}
p= (5) ;
} }
23.由________转换成二叉树时，其根结点的右子树总是空的。
24.哈夫曼（Huffman）树是带权路径长度________的树，通常权值较大的结点离根________。
25.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 。
二、 选择题（每空1分，共10分）
（ ）1． 不含任何结点的空树 。
（Ａ）是一棵树; （Ｂ）是一棵二叉树;
（Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树
（ ）2．二叉树是非线性数据结构，所以 。
（Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储;
（Ｃ）顺序存储结构和链式存储结构都能存储; （Ｄ）顺序存储结构和链式存储结构都不能使用
（ ）3. 具有n(n>0)个结点的完全二叉树的深度为 。
(Ａ) log2(n) (Ｂ) log2(n) (Ｃ) log2(n) +1 (Ｄ) log2(n)+1
（ ）4．把一棵树转换为二叉树后，这棵二叉树的形态是 。
（Ａ）唯一的 （Ｂ）有多种
（Ｃ）有多种，但根结点都没有左孩子 （Ｄ）有多种，但根结点都没有右孩子
5. 树是结点的有限集合，它 A 根结点，记为T。其余的结点分成为m（m≥0）个 B
的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数为该结点的 C 。
供选择的答案
A： ①有0个或1个 ②有0个或多个 ③有且只有1个 ④有1个或1个以上
B: ①互不相交 ② 允许相交 ③ 允许叶结点相交 ④ 允许树枝结点相交
C： ①权 ② 维数 ③ 次数 ④ 序
答案：A= B= C=
6. 二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的 C 。
供选择的答案
A： ①是特殊的树 ②不是树的特殊形式 ③是两棵树的总称 ④有是只有二个根结点的树形结构
B: ①左子结点 ② 右子结点 ③ 左子结点或者没有右子结点 ④ 兄弟
C： ①最左子结点 ② 最右子结点 ③ 最邻近的右兄弟 ④ 最邻近的左兄弟
⑤ 最左的兄弟 ⑥ 最右的兄弟
答案：A= B= C=
三、 综合题（1-7每题3分，8-10每题4分,共33分）
1．给定二叉树的两种遍历序列，分别是：
前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，
试画出二叉树B。
2. 给定如图所示二叉树T，请画出与其对应的中序线索二叉树。
3．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。
4. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
5. 编写递归算法，计算二叉树中叶子结点的数目。
6. 写出求二叉树深度的算法。
7. 编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。
8．设度为m的树采用多重链表存储。每个结点有m+1个域，其中有一个数据域，m 个指向孩子的指针。则空指针的数目是多少？说明这种存储方式的利弊。
9. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。对于上述实例，比较两种方案的优缺点。
10. 试编写最大堆的向上调整算法函数。
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
：写成内联函数的形式，程序头已给出，已通过数组heap建堆，建堆区间由遍历器first 、mid和last指向，即[mid, last-1）是一个堆，现自底向上将[mid,last)调整为一个堆。
template
inline void _fixup(Raniter first, Raniter mid, Raniter last, T t)
参考答案
一、概念题（每空1分，共55分）
1、 分支层次、根、直接前趋
2、 5
3、 31 32
4、 9
5、 2i-1 2 k-1
6、 n2+1
7、 最大值、完全
8、 350 （[n/2]＝350）
9、 500 499 1 0
10、 n 2
11、 L R N F E G H D C B
12、 O(n)
13、 顺序、链式
14、 根、
、左孩子、右孩子、2i、右孩子、2i+1
15、 根
16、 指向该结点的一个孩子、空指针NULL
17、 2n、n-1、n+1
18、 二叉链表、三叉链表
19、 第一
20、 左子树、右子树、左子树、右子树
21、 1、0
22、 （1）p->ltag=0 (2)p->lchild
(3)p->rtag=1 && p->rchild!=thr (4) p=p->rchild (5)p=p->rchild
继续阅读
浙公网安备 33021202002483