的集合T1,T2,…,Tm,每个集合又都是树,此时结点T称为T的父结点,T称为T的子结点(1≤i ≤m)。一个结点的子结点个数为该结点的C。 供选择的答案 A:①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上 B:①互不相交 ②允许相交 允许叶结点相交④允许树枝结点相交 C:①权 ②维数 ③次数(或度) ④序 答案:ABC=1,1,3 6.【%5程P13】从供选择的答案中,选出应填入下面叙述_?内的最确切的解答,把相应编号写在 答卷的对应栏内 叉树A。在完全的二叉树中,若一个结点没有B,则它必定是叶结点。每棵树都能惟一地转 换成与它对应的二叉树。由树转换成的二叉树里,一个结点N的左子女是N在原树里对应结点的C 而N的右子女是它在原树里对应结点的D 供选择的答案 A:①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构 B:①左子结点②右子结点⑧左子结点或者没有右子结点④兄弟 C~D:①最左子结点 ②最右子结点③最邻近的右兄弟 ④最邻近的左兄弟 ⑥最左的兄弟 最右的兄弟 谷案:A= 答案: ABCDE=2,1,1,3 四、简答题(每小题4分,共20分) 1.【严题集62①】一棵度为2的树与一棵二叉树有何区别? 答:度为2的树从形式上看与二叉树很相似,但它的子树是无序的,而二叉树是有序的。即,在一般树中 若某结点只有一个孩子,就无需区分其左右次序,而在二叉树中即使是一个孩子也有左右之分。 2.〖01年计算机研题〗设如下图所示的二叉树B的存储结构为二叉链表,root为根指针,结点结构为 ( Child. data, rchild)。其中 Child, rchild分别为指向左右孩子的指针, data为字符型,rot为根指针,试回答下列问题: C的结点类型定义如下 对下列二叉树B,执行下列算法 traversal(root),试指出其输出结 2.假定二叉树B共有n个结点,试分析算法 traversal(ro的时间复 struct node *lchild, rchild 杂度。(共8分) C算法如下 void traversal(struct node * root) 二叉树B fif (root) printf("%c”,root->data) 解:这是“先根再左再根再右”,比前序遍历多打印各结点一次,输 traversal(root->lchild) 出结果为: ABCCEEBADFFDGG 特点:①每个结点肯定都会被打印两次:;②但出现的顺序不同,其| traversal( root->rchild) 规律是:凡是有左子树的结点,必间隔左子树的全部结点后再重复 出现:如A,B,D等结点。反之马上就会重复出现。如C,E,F, G等结点。 时间复杂度以访问结点的次数为主,精确值为2n,时间渐近度为Om)3 的集合 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. 【95 程 P13】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在 答卷的对应栏内。 二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转 换成与它对应的二叉树。由树转换成的二叉树里，一个结点 N 的左子女是 N 在原树里对应结点的 C ， 而 N 的右子女是它在原树里对应结点的 D 。 供选择的答案 A： ①是特殊的树 ②不是树的特殊形式 ③是两棵树的总称 ④有是只有二个根结点的树形结构 B: ①左子结点 ② 右子结点 ③ 左子结点或者没有右子结点 ④ 兄弟 C～D： ①最左子结点 ② 最右子结点 ③ 最邻近的右兄弟 ④ 最邻近的左兄弟 ⑤ 最左的兄弟 ⑥ 最右的兄弟 答案：A= B= C= D＝ 答案：ABCDE＝2，1，1，3 四、简答题（每小题 4 分，共 20 分） 1. 【严题集 6.2①】一棵度为 2 的树与一棵二叉树有何区别？ 答：度为 2 的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中 若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。 2.〖01 年计算机研题〗设如下图所示的二叉树 B 的存储结构为二叉链表，root 为根指针，结点结构为： （lchild,data,rchild）。其中 lchild，rchild 分别为指向左右孩子的指针， data 为字符型，root 为根指针，试回答下列问题： 1. 对下列二叉树 B，执行下列算法 traversal(root)，试指出其输出结 果； 2. 假定二叉树 B 共有 n 个结点，试分析算法 traversal(root)的时间复 杂度。（共 8 分） 二叉树 B 解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输 出结果为：A B C C E E B A D F F D G G 特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其 规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复 出现；如 A，B，D 等结点。反之马上就会重复出现。如 C，E，F， G 等结点。 时间复杂度以访问结点的次数为主，精确值为 2*n，时间渐近度为 O(n). A B D C F G E C 的结点类型定义如下： struct node {char data; struct node *lchild, rchild; }; C 算法如下： void traversal(struct node *root) {if (root) {printf(“%c”, root->data); traversal(root->lchild); printf(“%c”, root->data); traversal(root->rchild); } }