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