1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 7 及答案与解析一、单项选择题1 一棵完全二叉树又是一棵( )。【华中科技大学 2006 一、7(2 分)】（A）平衡二叉树（B）堆（C）二叉排序树（D）哈夫曼(Huffman) 树2 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学 1999 一、5(2 分)】（A）不确定（B） 0（C） 1（D）23 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学 2000 一、5(2 分)】（A）0（B） 1（C） 2（D）不确定4 若 X 是二叉中序线索树中一个有左孩子的结点
2、，且 X 不为根，则 X 的前驱为( )。【南京理工大学 1996 一、6(2 分)】（A）X 的双亲（B） X 的右子树中最左的结点（C） X 的左子树中最右结点（D）X 的左子树中最右叶结点5 引入二叉线索树的目的是( )。【南京理工大学 1998 一、5(2 分)】（A）加快查找结点的前驱或后继的速度（B）为了能在二叉树中方便地进行插入与删除（C）为了能方便地找到双亲（D）使二叉树的遍历结果唯一6 线素二叉树是一种( ) 结构。【西安电子科技大学 1996 一、9(2 分)】（A）逻辑（B）逻辑和存储（C）物理（D）线性7 甩个结点的线索二叉树上含有的线索数为( )。【中山大学 1998
3、 二、8(2 分)】（A）2n（B） n-1（C） n+1 （D）n8 ( )的遍历仍需要栈的支持。【中科院计算所 1999 一、1(2 分)】（A）前序线索树（B）中序线索树（C）后序线索树9 二叉树在线素化后，仍不能有效求解的问题是( )。【北方交通大学 2003 一、4(2 分)】（A）先序线索二又树中求先序后继（B）中序线索二叉树中求中序后继（C）中序线索二叉树中求中序前驱（D）后序线索二叉树中求后序后继10 在线索二叉树中，下面说法不正确的是( )。【南京理工大学 2004 一、8(1 分)】（A）在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的左支末端结点（B）线索二叉
4、树是利用二叉树的 n+1 个空指针来存放结点前驱和后继信息的（C）每个结点通过线索都可以直接找到它的前驱和后继（D）在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的右支末端结点11 采用双亲表示法表示树，则具有 n 个结点的树至少需要( )个指向双亲的指针。【中山大学 2004】（A）n（B） n+1（C） n-1（D）2n12 树用孩子兄弟表示法，每个结点有两个指针域，分别指向“第一个孩子” 和“下一个兄弟”。若指向 “下一个兄弟 ”的指针有 n 个为空，则该树有( )个非终端结点。【哈尔滨工程大学 2004】（A）n 2（B） n-1（C） n（D）n+113 设森林 F 对应
5、的二叉树为 B，它有 m 个结点，B 的根为 p，p 的右子树结点个数为 n，森林 F 中第一棵树的结点个数是 ( )。【 南京理工大学 2000 一、17(15分)】（A）m-n（B） m-n-1（C） n+l （D）条件不足，无法确定14 设森林 F 中有三棵树，第一、第二、第三棵树的结点个数分别为 M1、M2 和M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是( )。【北方交通大学 2001 一、16(2 分) 】（A）M1（B） M1+M2（C） M3 （D）M2+M315 设 F 是一个森林， B 是由 F 变换得的二叉树。若 F 中有 n 个非终端结点，则 B中右指针域为
6、空的结点有( )个。【西安电子科技大学 1998 一、10(2 分)】（A）n-1（B） n（C） n+1 （D）n+216 如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的后序就是 T2 中结点的( )。【西安电子科技大学 1996 一、2(2 分) 】【电子科技大学 2005 一、7(1 分)】（A）先序（B）中序（C）后序（D）层次序17 由 3 个结点可以构造出多少种不同的有向树?( )【北方交通大学 2001 一、6(2分)】（A）2（B） 3（C） 4 （D）518 含有 4 个结点的二叉树有( )种树型。【北京邮电大学 2005 一、5(2 分)】（A）4（B）
7、5（C） 10 （D）1419 由 3 个结点可以构造出多少种不同的二叉树?( )【北方交通大学 2001 一、7(2分)】（A）2（B） 3（C） 4 （D）520 一棵共有 n 个结点的树，其中所有分支结点的度均为 k2 则该树中叶子结点的个数为( )。【华南理工大学 2005 一、1(2 分) 】（A）n(k-1)k（B） nk（C） (n+1)k （D）(nk-n+1)k21 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序( ) 。【中国科技大学 1998 二、8(2 分)】【中科院计算所1998 二、8(2 分) 】【北京工业大学 2005 一
8、、5(2 分)】【电子科技大学 2005 一、1(1 分)】【南京理工大学 2004 一、10(1 分) 】（A）二叉排序树（B）哈夫曼树（C） AVL 树（D）堆22 具有 n 个结点，其路径长度最短的二叉树是( )。【电子科技大学 2005 一、3(1分)】（A）哈夫曼树（B）完全二叉树（C） AVL 树（D）二叉排序树23 在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法( )。【中国科技大学 1998 二、10(2 分) 】【中科院计算所 1998 二、10(2 分)】（A）正确（B）错误24 设二叉树只有度为 0 和 2 的结点，其结点个数是 15，则该二叉树最
9、大深度为( )。【北京理工大学 2007 一、8(1 分)】（A）4（B） 5（C） 8（D）925 一棵 Huffman 树共有 215 个结点，对其进行 Huffrnan 编码，共能得到( )个不同的码字。【北京邮电大学 2005 一、6(2 分)】（A）107（B） 108（C） 214（D）21526 设哈夫曼编码的长度不超过 4，若已对两个字符编码为 1 和 01，则还可以对( )字符编码。【哈尔滨工程大学 2005】（A）2（B） 3（C） 4（D）527 若度为 m 的哈夫曼树中，其叶结点个数为 n，则非叶结点的个数为 ( )。【中科院计算所：1999 一、2(2 分)】（A）n
10、-1（B） nm一 1（C） (n-1)(m-1)（D）n (m-1) 一 1（E）(n+1)(m+1) 一 128 下述编码中哪一个不是前缀码? ( ) 【中科院计算所 2000 一、2(2 分)】（A）(00 ，01，10，11)（B） (0，1，00，11)（C） (0，10，1 10，111)（D）(1 ，01，000，001)29 下述编码哪一组不是前缀码?( ) 【哈尔滨工业大学 2004 二、1(1 分)2005 二、1(1 分)】（A）00 ，01 ，10，11)（B） 0，1，00，11)（C） 0，10，110，111)（D）000 001，010，101)30 下列编码中
11、，( ) 不是前缀码。【湖南大学 2003】（A）00 ，01 ，10，11（B） 0，1，00，11)（C） 0，10，110，111)（D）10 ，110 ，1110，1111)31 有 5 个字符，根据其使用频率设计对应的哈夫曼编码，以下( )是可能的哈夫曼编码。【武汉大学 2006】（A）000，001，010，011，1（B） 0000，0001，001，01，1（C） 000，001，01，10，11 （D）00，100，101，110，11132 现有一“遗传 ”关系，设 x 是 y 的父亲，则 x 可以把它的属性遗传给 y，表示该遗传关系最适合的数据结构为( )。【中国科学院
12、2006】（A）向量（B）树（C）图（D）二叉树33 一棵深度为 7 的满二叉树共有( )非终端结点。【北京邮电大学 2007】（A）3 1（B） 63（C） 127 （D）255二、填空题34 在顺序存储的二叉树中，编号为 i 和 j 的两个结点处在同一层的条件是_。【厦门大学 2002 六、3(4 分)】35 一棵有 n 个结点的满二叉树有(1)个度为 1 的结点、有(2)个分支(非终端)结点和(3)个叶子，该满二叉树的深度为(4) 。【华中理工大学 2000 一、6(3 分)】36 设只含根结点的二又树的高度为 0，则高度为尼的二又树的最大结点数为_，最小结点数为_。【北京大学 1997
13、 一、1(4 分)】37 完全二叉树结点的平衡因子取值只可能为_。【电子科技大学 2008 二、1(1 分)】38 高度为 K 的完全二叉树至少有个叶子结点。 【合肥工业大学 1999 二、6(2分)】39 已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少是_。【厦门大学 2002 六、4(4 分) 】【北京交通大学 2005 二、1(2 分)】40 设根的层次为 1，则有 64 个结点的完全二叉树的深度为_。【中南大学 2005 二、10(2 分) 】41 已知完全二叉树有 266 个结点，则整棵树上度为 1 的结点数是_。【北京交通大学 2006 二、3(2 分)】42 一个有 2
14、001 个结点的完全二叉树的高度是_。【南京理工大学 1997三、2(1 分) 】43 若按层次顺序将一棵有 n 个结点的完全二叉树的所有结点从 1 到 n 编号，那么结点 i 没有右兄弟的条件为_。【北京工业大学 2005 二、2(3 分)】44 对于非空满 k 叉树，其分支结点数目为 n，则其叶子结点数目为_。【北京大学 2005】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 7 答案与解析一、单项选择题1 【正确答案】 B【试题解析】 完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。平衡二叉树任何结点的左右子树的高度差的绝对值不超过 1，但其结点的值符
15、合二叉排序树的定义。平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。堆是一个序列，有大堆和小堆，编号为 i 的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。2 【正确答案】 D【试题解析】 左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共 2 个空链域。3 【正确答案】 B4 【正确答案】 C5 【正确答案】 A6 【正确答案】 C7 【正确答案】 C【试题解析】 线索二叉树是利用二叉树的空链域加上线索，n 个结
16、点的二叉树有n+1 个空链域。8 【正确答案】 C9 【正确答案】 D【试题解析】 答案应选 D。其实，先序线索二叉树求先序前驱也不能有效求解。10 【正确答案】 C11 【正确答案】 C【试题解析】 树的双亲表示法除根结点外，每个结点都有一个指向双亲的指针。12 【正确答案】 B13 【正确答案】 A14 【正确答案】 D15 【正确答案】 C16 【正确答案】 B17 【正确答案】 A【试题解析】 n(n0)个结点可以构造出 1(n+1) 木(2n)!(n!) 2 种不同的二叉树。n 个结点构造的不同的树的数量等于 n 一 1 个结点可以构造出的不同的二叉树的数量。18 【正确答案】 D1
17、9 【正确答案】 D20 【正确答案】 D21 【正确答案】 D22 【正确答案】 A23 【正确答案】 B24 【正确答案】 C25 【正确答案】 B26 【正确答案】 C【试题解析】 因为哈夫曼编码长度不超过 4，且已有两个字符编码为 1 和 01，则还可以最多为 4 个字符编码，这 4 个字符的编码分别为0000，0001，0010，0011。27 【正确答案】 C28 【正确答案】 B29 【正确答案】 B30 【正确答案】 B31 【正确答案】 A,B,C【试题解析】 D 之所以错误，是因为若有编码 00，至少必须有编码 01，否则只一个结点不可能构成双亲。32 【正确答案】 B33
18、 【正确答案】 B二、填空题34 【正确答案】 用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加 “虚结点” 。设编号为 i 和 j 的结点在顺序存储中的下标为s 和 t，则结点 i 和 j 在同一层上的条件是log 2s=log2t。35 【正确答案】 (1)0 (2)(n1)2 或n2 (3)(n+1)2 (4)log 2(n+1)36 【正确答案】 (1)2 k+1 一 1 (2)k+137 【正确答案】 1，0，一 138 【正确答案】 2 k-2。设根结点层次为 1，则该二叉树第 K 层有 1 个叶子结点，第k-1 层有 2k-2 一 1 个叶子结点。39 【正确答案】 0.9940 【正确答案】 741 【正确答案】 1。详细分析见上面一、7。42 【正确答案】 1143 【正确答案】 2*i+1n44 【正确答案】 n(k-1)+1
