应栏内。
树是结点的有限集合，它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：①权
②维数
③次数（或度）
④序
答案：ABC＝1，1，3
6从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。
二叉树A。在完全的二叉树中，若一个结点没有B，则它必定是叶结点。每棵树都能惟一地转
换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的C，
而N的右子女是它在原树里对应结点的D。
供选择的答案
A：①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构
B①左子结点②右子结点③左子结点或者没有右子结点④兄弟
C～D：①最左子结点
②最右子结点③最邻近的右兄弟
④最邻近的左兄弟
⑤最左的兄弟⑥最右的兄弟
2
f答案：A
B
C
D＝
答案：ABCDE＝2，1，1，3
四、简答题（每小题4分，共20分）
1设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchilddatarchild）。其
中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：
1对下列二叉树B，执行下列算法traversalroot，试指出其输出结果；
2假定二叉树B共有
个结点，试分析算法traversalroot的时间复杂度。（共8分）
C的结点类型定义如下：struct
odechardatastruct
odelchildrchild
二叉树B
A
B
D
C
F
G
E
C算法如下：voidtraversalstruct
oderootifroot
pri
tf“c”rootdata
解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：ABCCEEBADFFDGG特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A，B，D等结点。反之马上就会重复出现。如C，E，F，
traversalrootlchildpri
tf“c”rootdatatraversalrootrchild
G等结点。
时间复杂度以访问结点的次数为主，精确值为2
，时间渐近度为O

2给定二叉树的两种遍历序列，分别是：
前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，
r