1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 5及答案解析(总分：66.00，做题时间：90 分钟)一、单项选择题(总题数：22，分数：44.00)1.一棵有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 A1n中，则二叉树中第 i 个结点(i 从 1 开始用上述方法编号)的右孩子在数组 A 扣的位置是 ( )。【南京理工大学 2000一、4(15 分)】（分数：2.00）A.A2i(2in)B.A2i+1(2i+1n)C.Ai-2D.条件不充分，无法确定2.设 m、n 为一棵二叉树上的两个结点，在中序遍历时，n 在 m 前的条件是：( )。【北京理工大学
2、2006五、9(1 分)】（分数：2.00）A.n 在 m 右方B.n 是 m 祖先C.n 在 m 左方D.n 是 m 子孙3.一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是( )。【北京工业大学 2001 一、2(2分)】（分数：2.00）A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG4.已知一棵二叉树的前序遍历结果为 ABCDEF，中序遍历结果为 CBAEDF，则后序遍历的结果为( )。 【浙江大学 1999 四、2(4 分)】（分数：2.00）A.CBEFDAB.FEDCBAC.CBEDFAD.不定5.二叉树的先序和中序遍历序列分别是 ABCD
3、EFGH，CBEDFAGH，则后序遍历序列是( )。【南京理工大学2005 一、5(1 分)】（分数：2.00）A.HGFEDACBB.GHEDFCBAC.CEFDBHGAD.HGAFDEBC6.某二叉树中序序列为 A，B，C，D，E，E G，后序序列为 B，D，C，A，E G，E，则前序序列是( )。【南京理工大学 2000 一、14(15 分)】（分数：2.00）A.E，G，F，A，C，D，BB.E，A，C，B，D，G，FC.E，A，G，C，F，E，DD.上面的都不对7.一棵二叉树中序序列为 FEABDC，后序序列为 FBADCE，则层序序列为( )。【华南理工大学 2006 一、11(2
4、 分)】（分数：2.00）A.dBCDEFB.EFCDBAC.FECDABD.EFCDAB8.某二又树结点的中序序列为 BDAECF，后序序列为 DBEFCA，则该二叉树对应的森林包括 ( )棵树。【中南大学 2003 一、8(1 分)】（分数：2.00）A.1B.2C.3D.49.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK 中序遍历：HFIEJKG。该二又树根的右子树的根是：( )。【北方交通大学 2001 一、21(2 分)】（分数：2.00）A.EB.FC.GD.H10.对于前序遍历与中序遍历结果相同的二叉树为(1)；对于前序遍历和后序遍历结果相同的二叉树为(2)。【中科院
5、计算所 1999 一、4(4 分)】（分数：2.00）A.一般二叉树B.只有根结点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树E.所有结点只有左子数的二叉树11.前序遍历和后序遍历结果相同的二叉树为(1)前序遍历和中序遍历结果相同的二叉树为(2)中序遍历和后序遍历结果相同的二叉树为(3)【南京理工大学 2005 一、6(1 分)】（分数：2.00）A.一般二叉树B.空树或根结点无左孩子的二叉树C.空树或只有根结点的二叉树D.空树或根结点无右孩子的二叉树E.空树或缺左子树的单支二叉树12.一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( )。【中南大学 2005
6、 一、7(2 分)】（分数：2.00）A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶子结点D.其中度为 2 的结点最多为一个13.某二叉树的前序序列和中序序列正好相反，则该二又树一定具有( )的特征(多项选择)。【华东师范大学 2004】（分数：2.00）A.二叉树为空或只有一个结点B.若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子C.若二叉树不为空，则任一结点没有左孩子D.若二叉树不为空，则任一结点没有右孩子14.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( )。【东华大学 2003 二、1(1 分)】【北京交通大学 2005 一、5(2 分
7、)】（分数：2.00）A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子15.一棵非空二叉树的先序序列和后序序列正好相反，当且仅当( )。【华中科技大学 2007 一、2(2 分)】（分数：2.00）A.二叉树任意一结点都无左孩子B.二叉树任一结点都无右孩子C.二叉树只有一个叶子结点D.二叉树只有一个根结点16.在完全二叉树中，若一个结点是叶结点，则它没( )。【北方交通大学 2001 一、22(2 分)】（分数：2.00）A.左子结点B.右子结点C.左子结点和右子结点D.左子结点、右子结点和兄弟结点17.在下列存储形式中，哪一个不是树的存储形式?( )【北方交通
8、大学 2001 一、23(2 分)】（分数：2.00）A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法18.树的后根遍历序列等同于该树对应的二叉树的( )。【北京理工大学 2001 六、6(2 分)】（分数：2.00）A.先序序列B.中序序列C.后序序列19.将一棵树 t 转换为孩子兄弟链表表示的二叉树 h，则 t 的后根序遍历是 h 的( )。【北京邮电大学 2001一、2(2 分)】（分数：2.00）A.前序遍历B.中序遍历C.后序遍历20.对任意一棵树，设它有 n 个结点，这 n 个结点的度数之和为( )。【南京邮电学院 2004 一、3(3 分)】（分数：2.00）
9、A.nB.n-2C.n-1D.n+l21.高度为 h(h0)的满二叉树对应的森林由( )棵树构成。【北京交通大学 2004 一、9(2 分)】（分数：2.00）A.1B.log2 kC.h2D.h22.在下列情况中，可称为二叉树的是( )。 【西安交通大学 1996 三、4(3 分)】（分数：2.00）A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树E.以上答案都不对二、判断题(总题数：11，分数：22.00)23.在二叉树中插入结点，则此二叉树便不再是二叉树了。( )【北京邮电大学 2000 一、5(1 分)】（分数：2.00）A.正确B
10、.错误24.将一棵树转换成二叉树后，根结点没有左子树。( )【中国海洋大学 2005 二、15(1 分)2006 二、9(1分)】【烟台大学 2007 二、8(1 分)】（分数：2.00）A.正确B.错误25.非空的二又树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子。( )【合肥工业大学2001 二、5(1 分)】（分数：2.00）A.正确B.错误26.在树中，如果 x 是 y 的后代，则 x 的深度大于 y 的深度。( )【吉林大学 2006 一、5(1 分)】（分数：2.00）A.正确B.错误27.Huffrnan 树度为 1 的结点数等于度为 2 和 O 的结点数之差。( )【
11、武汉理工大学 2002 二、9(1 分)】（分数：2.00）A.正确B.错误28.哈夫曼树的结点个数不能是偶数。( )【北京邮电大学 2000 一、6(1 分)】（分数：2.00）A.正确B.错误29.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。( )【合肥工业大学 2000 二、4(1分)】【烟台大学 2007 二、7(1 分)】（分数：2.00）A.正确B.错误30.当一棵具有 n 个叶子结点的二叉树的 WPL 值为最小时，称其树为 Huffman 树，且其二叉树的形状必是唯一的。( )【南京航空航天大学 1995 五、6(1 分)】（分数：2.00）A.正确B.错误31.哈
12、夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。( )【北京邮电大学 1999 二、5(2 分)】【中国海洋大学 2005 二、13(1 分)2007 二、8(1 分)】（分数：2.00）A.正确B.错误32.若从二叉树的任一结点出发,到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。( )【北京交通大学 2005 三、6(2 分)】（分数：2.00）A.正确B.错误33.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应特殊处理。( )【中国海洋大学 2006 二、8(1 分)】（分数：2.00）A.正确B.错误计算机专业基础综合数据结构
13、（树和二叉树）历年真题试卷汇编 5答案解析(总分：66.00，做题时间：90 分钟)一、单项选择题(总题数：22，分数：44.00)1.一棵有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 A1n中，则二叉树中第 i 个结点(i 从 1 开始用上述方法编号)的右孩子在数组 A 扣的位置是 ( )。【南京理工大学 2000一、4(15 分)】（分数：2.00）A.A2i(2in)B.A2i+1(2i+1n)C.Ai-2D.条件不充分，无法确定 解析：2.设 m、n 为一棵二叉树上的两个结点，在中序遍历时，n 在 m 前的条件是：( )。【北京理工大学 2006五、9(1
14、分)】（分数：2.00）A.n 在 m 右方B.n 是 m 祖先C.n 在 m 左方 D.n 是 m 子孙解析：3.一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是( )。【北京工业大学 2001 一、2(2分)】（分数：2.00）A.CABDEFGB.ABCDEFG C.DACEFBGD.ADCFEG解析：解析：判断原则：前序序列第一个元素是根，在中序序列中根结点把序列分成左右子树，再看前序第二个元素，到中序的左右子树中找。答案 A 根左面是 C，答案 C 根左面是 D，答案 D 根左面为空，都不是前序序列的第二个元素 B。只有答案 B 正确。4.已知一棵二叉树的前序遍历结
15、果为 ABCDEF，中序遍历结果为 CBAEDF，则后序遍历的结果为( )。 【浙江大学 1999 四、2(4 分)】（分数：2.00）A.CBEFDA B.FEDCBAC.CBEDFAD.不定解析：5.二叉树的先序和中序遍历序列分别是 ABCDEFGH，CBEDFAGH，则后序遍历序列是( )。【南京理工大学2005 一、5(1 分)】（分数：2.00）A.HGFEDACBB.GHEDFCBAC.CEFDBHGA D.HGAFDEBC解析：解析：由先序序列知，A 是根，因此，A 和 D 是不对的；由中序序列知，右子树有两个结点 G 和H，因此，B 是错误的。不用画出二叉树，用排除法，可以判定
16、 C 是正确的。6.某二叉树中序序列为 A，B，C，D，E，E G，后序序列为 B，D，C，A，E G，E，则前序序列是( )。【南京理工大学 2000 一、14(15 分)】（分数：2.00）A.E，G，F，A，C，D，BB.E，A，C，B，D，G，F C.E，A，G，C，F，E，DD.上面的都不对解析：7.一棵二叉树中序序列为 FEABDC，后序序列为 FBADCE，则层序序列为( )。【华南理工大学 2006 一、11(2 分)】（分数：2.00）A.dBCDEFB.EFCDBAC.FECDABD.EFCDAB 解析：8.某二又树结点的中序序列为 BDAECF，后序序列为 DBEFCA，
17、则该二叉树对应的森林包括 ( )棵树。【中南大学 2003 一、8(1 分)】（分数：2.00）A.1B.2C.3 D.4解析：解析：二叉树根结点和根结点的右子女，右子女的右子女，等等，是二叉树转成森林后树的根。因此，只要找到根结点 A，根结点的右子女 C，右子女的右子女 F，就可以判定 3 棵树，不必画出整棵二叉树。9.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK 中序遍历：HFIEJKG。该二又树根的右子树的根是：( )。【北方交通大学 2001 一、21(2 分)】（分数：2.00）A.EB.FC.G D.H解析：10.对于前序遍历与中序遍历结果相同的二叉树为(1)；对于前序
18、遍历和后序遍历结果相同的二叉树为(2)。【中科院计算所 1999 一、4(4 分)】（分数：2.00）A.一般二叉树B.只有根结点的二叉树 C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树E.所有结点只有左子数的二叉树 解析：解析：第一问虽然选择了 F，但是编者认为，答案 F 应改为“所有结点至垒只有右子树的二叉树”，这就包括了只有根结点的特例。另外选择答案 F 也不严格，成了无限个结点。本题到 72 题的解题原则都是根据二叉树的递归遍历。要掌握前序遍历是“根一左一右”，中序遍历是“左一根一右”，后序遍历是“左一右一根”。据此，可以回答这几道题。例如 69 题，若要前序和后序这两个序列相反
19、，只有单支树，所以本题的 A 和 B 均对，单支树的特点是只有一个叶子结点，故 C 是最合适的，A 或 B 都不完全。11.前序遍历和后序遍历结果相同的二叉树为(1)前序遍历和中序遍历结果相同的二叉树为(2)中序遍历和后序遍历结果相同的二叉树为(3)【南京理工大学 2005 一、6(1 分)】（分数：2.00）A.一般二叉树B.空树或根结点无左孩子的二叉树 C.空树或只有根结点的二叉树 D.空树或根结点无右孩子的二叉树E.空树或缺左子树的单支二叉树 解析：12.一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( )。【中南大学 2005 一、7(2 分)】（分数：2.00）A.
20、其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶子结点 D.其中度为 2 的结点最多为一个解析：13.某二叉树的前序序列和中序序列正好相反，则该二又树一定具有( )的特征(多项选择)。【华东师范大学 2004】（分数：2.00）A.二叉树为空或只有一个结点 B.若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子 C.若二叉树不为空，则任一结点没有左孩子D.若二叉树不为空，则任一结点没有右孩子 解析：14.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( )。【东华大学 2003 二、1(1 分)】【北京交通大学 2005 一、5(2 分)】（分数：2.00）
21、A.空或只有一个结点B.高度等于其结点数 C.任一结点无左孩子D.任一结点无右孩子解析：15.一棵非空二叉树的先序序列和后序序列正好相反，当且仅当( )。【华中科技大学 2007 一、2(2 分)】（分数：2.00）A.二叉树任意一结点都无左孩子B.二叉树任一结点都无右孩子C.二叉树只有一个叶子结点 D.二叉树只有一个根结点解析：16.在完全二叉树中，若一个结点是叶结点，则它没( )。【北方交通大学 2001 一、22(2 分)】（分数：2.00）A.左子结点B.右子结点C.左子结点和右子结点 D.左子结点、右子结点和兄弟结点解析：17.在下列存储形式中，哪一个不是树的存储形式?( )【北方交
22、通大学 2001 一、23(2 分)】（分数：2.00）A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法 解析：18.树的后根遍历序列等同于该树对应的二叉树的( )。【北京理工大学 2001 六、6(2 分)】（分数：2.00）A.先序序列B.中序序列 C.后序序列解析：19.将一棵树 t 转换为孩子兄弟链表表示的二叉树 h，则 t 的后根序遍历是 h 的( )。【北京邮电大学 2001一、2(2 分)】（分数：2.00）A.前序遍历B.中序遍历 C.后序遍历解析：20.对任意一棵树，设它有 n 个结点，这 n 个结点的度数之和为( )。【南京邮电学院 2004 一、3(3
23、 分)】（分数：2.00）A.nB.n-2C.n-1 D.n+l解析：解析：树中任一结点都有一个分支所指，根结点没有分支所指。分支可理解为度。21.高度为 h(h0)的满二叉树对应的森林由( )棵树构成。【北京交通大学 2004 一、9(2 分)】（分数：2.00）A.1B.log2 kC.h2D.h 解析：22.在下列情况中，可称为二叉树的是( )。 【西安交通大学 1996 三、4(3 分)】（分数：2.00）A.每个结点至多有两棵子树的树B.哈夫曼树 C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树E.以上答案都不对解析：解析：本题考核二叉树的定义，但是编者认为题目叙述不够严
24、格。二叉树和树都属于树形结构，但是二叉树不是树的特例(见下面四、1)。选择答案 A 和 c 明显错误。D 错误在于“每个结点只有一棵右子树”，这样会有无限个结点。选择答案 B 接近正确，因为二叉树可以得到前缀码，哈夫曼二叉树可以得到最优的前缀码(即哈夫曼编码)。在本科数据结构的教学中，一提哈夫曼树都是指带权路径长度最小的最优二叉树。但是哈夫曼树并非都是二叉树(如下面第 106 题，以及最佳归并树)。二、判断题(总题数：11，分数：22.00)23.在二叉树中插入结点，则此二叉树便不再是二叉树了。( )【北京邮电大学 2000 一、5(1 分)】（分数：2.00）A.正确B.错误 解析：24.将
25、一棵树转换成二叉树后，根结点没有左子树。( )【中国海洋大学 2005 二、15(1 分)2006 二、9(1分)】【烟台大学 2007 二、8(1 分)】（分数：2.00）A.正确B.错误 解析：25.非空的二又树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子。( )【合肥工业大学2001 二、5(1 分)】（分数：2.00）A.正确 B.错误解析：解析：其中序前驱是其左子树上按中序遍历的最右边(叶子或无右子女)的结点，该结点无右孩子。26.在树中，如果 x 是 y 的后代，则 x 的深度大于 y 的深度。( )【吉林大学 2006 一、5(1 分)】（分数：2.00）A.正确 B.
26、错误解析：27.Huffrnan 树度为 1 的结点数等于度为 2 和 O 的结点数之差。( )【武汉理工大学 2002 二、9(1 分)】（分数：2.00）A.正确B.错误 解析：28.哈夫曼树的结点个数不能是偶数。( )【北京邮电大学 2000 一、6(1 分)】（分数：2.00）A.正确 B.错误解析：29.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。( )【合肥工业大学 2000 二、4(1分)】【烟台大学 2007 二、7(1 分)】（分数：2.00）A.正确B.错误 解析：30.当一棵具有 n 个叶子结点的二叉树的 WPL 值为最小时，称其树为 Huffman 树，且
27、其二叉树的形状必是唯一的。( )【南京航空航天大学 1995 五、6(1 分)】（分数：2.00）A.正确B.错误 解析：31.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。( )【北京邮电大学 1999 二、5(2 分)】【中国海洋大学 2005 二、13(1 分)2007 二、8(1 分)】（分数：2.00）A.正确 B.错误解析：32.若从二叉树的任一结点出发,到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。( )【北京交通大学 2005 三、6(2 分)】（分数：2.00）A.正确B.错误 解析：33.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应特殊处理。( )【中国海洋大学 2006 二、8(1 分)】（分数：2.00）A.正确B.错误 解析：解析：两个频率相同的字符，或做为左右子女去构造二叉树，或其中一个和较小频率(权值)的字符去构造二叉树，它们的哈夫曼编码不可能相同。
