广义表具有可共享性，因此在遍历一个广义表时必须为每一个结点增加一个标志域mark，以记录该结

因为广义表有原子结点和子表结点之分，若把原子结点当作叶结点，子表结点当作分支结点，可以借助二叉树的前序遍历算法对广义表进行遍历。（)

此题为判断题(对，错)。

广义表是一种递归的数据结构，子表结点则指示下一层广义表的（)。

具体规定如下：

(1)树的根结点作为内子树构成的表的表名，放在表的最前面。

(2)每个结点的左子树和右子树用逗号隔开。若仅有在子树没有左子树，则逗号不能省略。

(3)在整个广义表表示输人的结尾加上一个特殊的符号(例如)表示输入结束。例如，对于如图5-26所示的二叉树，广义表表示为：A(B(D，E(G，)).C(，F))

判断下列叙述的对错，（1)若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则

判断下列叙述的对错，

(1)若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。

(2)若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

(3)若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。

(4)若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

（1)在有N个结点的AVL树中，为结点增加一个存放结点高度的数据成员，那么每一个结点需要增加多少

位(bit)？

(2)若每一个结点中的高度计数器有8bit，那么这样的AVL树可以有多少层？最少有多少个关键码？

树插入一个元素时，若树中已存在与该元素的关键码柑同的结点，则就使该结点的count域增1，否则就由该元素生成一个新结点而插入到树中，并使其count域置为1，试按照这种插入要求编写一个算法。

的思想是在遍历过程中沿着结点的左子女或右子女方向“下降”时，临时改变其leftChild或rightChild的值，使之指向该结点的父结点，从商为以后的“上升”提供路径;在上升的过程中将结点的leftChild或rightChild的值恢复原来的值。为了在上升的过程中区分是从该结点的左子树上升的还是从右子树上升的，在结点中设置一个tag标志。进人算法时，所有结点的tag设为0，当遍历过程中进入结点的左子树时，将该结点的tag置为l、从左子树退出进人右子树时再将该结点的tag置为0.