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