65. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组a[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组a中的位置是（ ）
a．a[2i](2i<=n) b．a[2i+1](2i+1<=n) c．a[i-2] d．条件不充分，无法确定
【南京理工大学2000 一、4(1.5分）】
66．从下列有关树的叙述中,选出5条正确的叙述(共5分) （ ）
a．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。
b．当k≥1时高度为k的二叉树至多有2k-1个结点。
c．用树的前序周游和中序周游可以导出树的后序周游。
d．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。
e．将一棵树转换成二叉树后,根结点没有左子树。
f．一棵含有n个结点的完全二叉树,它的高度是ëlog2nû+1。
g．在二叉树中插入结点,该二叉树便不再是二叉树。
h．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。
i．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
j．用一维数组存储二叉树时,总是以前序周游存储结点。【山东工业大学 1995 三、 (5分)】
69．设有二叉树bt，每个结点包括ltag、lchild、data、rchild、rtag五个字段，依次为左标志、左儿子、数据、右儿子、右标志。给出将二叉树bt建成前序（即先序）线索二叉树的递归算法。
【四川联合大学2000 三】【东南大学1999六(15分)】
70．写出中序线索二叉树的线索化过程（已知二叉树t）。
【山东大学 2000 五、2 (10分)】【长沙铁道学院 1997 五、6 (10分)】
71．已知一中序线索二叉树,写一算法完成对它的中序扫描。【山东大学2001软件与理论三(8分)】
72．已知中序线索二叉树t右子树不空。设计算法，将s所指的结点作为t的右子树中的一个叶子结点插入进去，并使之成为t的右子树的（中序序列）第一个结点（同时要修改相应的线索关系）。
【合肥工业大学 2001 五、2（8分)】
73．写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：（ltag,lc,data,rc,rtag）。其中，data存放结点的值；lc，rc为指向左、右孩子或该结点前驱或后继的指针；ltag，rtag为标志域，各值为：0，则lc，rc为指向左、右孩子的指针；值为1，则lc，rc为指向某前驱后继结点的指针。【北京邮电大学 1996 八(20分)】
74．设后序线索树中结点构造为(ltag,lchild,data,rchild,rtag)。其中:ltag,rtag 值为0时,lchild、rchild 分别为儿子指针；否则分别为直接前驱,直接后继的线索。请写出在后序线索树上找给定结点p^ 的直接前驱q 的算法。【武汉交通科技大学 1996 四、1（13分）】
75．用算法说明在对称序穿线树中，如何对任意给定的结点直接找出该结点的对称序后继。
【山东大学 1999 六、３(10分）】
76．写出在中序线索二叉树里；找指定结点在后序下的前驱结点的算法。【河海大学1998七(10分）】
77．设中序穿线二叉树的结点由五个域构成：info:给出结点的数据场之值。ll：当lt 为1 时，则给出该结点的左儿子之地址，当lt为0时，则给出按中序遍历的前驱结点的地址。lt:标志域，为1或为0。rl：当rt为1时，则给出该结点的右儿子的地址；当rt为0时，则给出按中序遍历的后继结点地址。rt: 标志域为0或为1。
请编写程序，在具有上述结点结构的中序穿线二叉树上，求某一结点p的按后序遍历次序的后继结点的地址q，设该中序穿线二叉树的根结点地址为r。另外，请注意必须满足：（1）额外空间的使用只能为o(1)，(2)程序为非递归。【上海交通大学 2000 十(20分)】
78．写出按后序序列遍历中序线索树的算法。【东南大学 2000 六(15分)】
79．给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman 树。（1）给出构造huffman 树 的算法。（2）给定项及相应的权如下表：画出执行上述算法后得到的huffman树。（3）用c语言编写构造huffman 树的程序. 【浙江大学 2000 七 (18分)】
|
序号 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
向 |
a |
b |
c |
d |
e |
f |
g |
h |
i |
|
|
15 |
6 |
7 |
12 |
25 |
4 |
6 |
1 |
15 |
80、二叉树t的中序遍历序列和层次遍历序列分别是bafdgce和abcdefg，试画出该二叉树（3分），并写出由二叉树的中序遍历序列和层次遍历序列确定二叉树的算法（5分）。
【烟台大学 2004 四、1(8分)】
责任编辑：小草
