文档介绍：****题六树和二叉树一、单项选择题 1. 以下说法错误的是() A .树形结构的特点是一个结点可以有多个直接前趋 B .线性结构中的一个结点至多只有一个直接后继 C .树形结构可以表达( 组织) 更复杂的数据 D .树( 及一切树形结构) 是一种" 分支层次" 结构 E .任何只含一个结点的集合是一棵树 2 .下列说法中正确的是() A. 任何一棵二叉树中至少有一个结点的度为 2 B. 任何一棵二叉树中每个结点的度都为 2 C. 任何一棵二叉树中的度肯定等于 2 D. 任何一棵二叉树中的度可以小于 2 3 .讨论树、森林和二叉树的关系,目的是为了( ) A .借助二叉树上的运算方法去实现对树的一些运算 B .将树、森林按二叉树的存储方式进行存储 C .将树、森林转换成二叉树 D .体现一种技巧,没有什么实际意义 4 .树最适合用来表示() A .有序数据元素 B .无序数据元素 C .元素之间具有分支层次关系的数据 D .元素之间无联系的数据 5. 若一棵二叉树具有 10 个度为 2 的结点,5 个度为 1 的结点, 则度为 0 的结点个数是() . 11C. 15D .不确定 6. 设森林 F 中有三棵树, 第一, 第二, 第三棵树的结点个数分别为 M1, M2和 M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是( )。 A. M1B. M1+M2 C. M3D. M2+M3 7. 一棵完全二叉树上有 1001 个结点,其中叶子结点的个数是() A. 250 B. 500 C. 254 D. 505 E .以上答案都不对 8. 设给定权值总数有 n 个,其哈夫曼树的结点总数为() A .不确定 B. 2nC. 2n+1 D. 2n-1 9 .二叉树的第 I 层上最多含有结点数为( ) I-1 - I- I -1 10 .一棵二叉树高度为 h, 所有结点的度或为 0 ,或为 2 ,则这棵二叉树最少有() 结点 A. 2hB. 2h-1 C. 2h+1 D. h+1 11. 利用二叉链表存储树,则根结点的右指针是( )。 A .指向最左孩子 B .指向最右孩子 C .空 D .非空 12. 已知一棵二叉树的前序遍历结果为 ABCDEF, 中序遍历结果为 CBAEDF, 则后序遍历的结果为()。 A. CBEFDA B. FEDCBA C. CBEDFA D .不定 13 .已知某二叉树的后序遍历序列是 dabec, 中序遍历序列是 debac , 它的前序遍历是()。 A. acbed B. decab C. deabc D. cedba 14 .在二叉树结点的先序序列,中序序列和后序序列中,所有叶子结点的先后顺序( ) A .都不相同 B .完全相同 C .先序和中序相同,而与后序不同 D .中序和后序相同,而与先序不同 15 .在完全二叉树中,若一个结点是叶结点,则它没( )。 A .左子结点 B .右子结点 C .左子结点和右子结点 D .左子结点,右子结点和兄弟结点 16 .在下列情况中,可称为二叉树的是( ) A .每个结点至多有两棵子树的树 B. 哈夫曼树 C .每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E .以上答案都不对 17. 一棵左右子树均不空的二叉树在先序线索化后,其中空的链域的个数是: ()。 D. 不确定 18. 引入二叉线索树的目的是() A .加快查找结点的前驱或后继的速度 B .为了能在二叉树中方便的进行插入与删除 C .为了能方便的找到双亲 D .使二叉树的遍历结果唯一 个结点的线索二叉树上含有的线索数为( ) A. -+ 20 .由 3 个结点可以构造出多少种不同的二叉树?( ) 21 .下面几个符号串编码集合中,不是前缀编码的是( )。 A. {0,10,110,1111} B. {11,10,001,101,0001} C. {00,010,0110,1000} D. {b,c,aa,ac,aba,abb,abc} 22. 一棵有 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 .条件不充分,无法确定 23 、以下说法错误的是() A .哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。 B .若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点,则它必是该子树的后序遍历序列中的第一个结点。 C