1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 4 及答案与解析一、单项选择题1 先序序列为 a，b，c ，d 的不同二叉树的个数是 ( )。【2015 年全国试题 2(2 分) 】（A）13（B） 14（C） 15（D）162 下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是( ) 。【201 5 年全国试题 3(2 分) 】（A）24，10，5 和 24，10，7（B） 24，10，5 和 24，12，7（C） 24，10，10 和 24，14，11 （D）24，10，5 和 24，14，63 树是一种逻辑关系，表示数据元素之间存在的关系为( )。
2、【北京交通大学2007(2 分) 】（A）集合关系（B）一对一关系（C）一对多关系（D）多对多关系4 下列判断，( ) 是正确的。【华南理工大学 2005 一、1(2 分)】（A）二叉树就是度为 2 的树（B）二叉树中不存在度大于 2 的结点（C）二叉树是有序树（D）二叉树的每个结点的度都为 25 有关二叉树下列说法正确的是( )。【南京理工大学 2000 一、11(15 分)】（A）二叉树的度为 2（B）一棵二叉树的度可以小于 2（C）二叉树中至少有一个结点的度为 2 （D）二叉树中任何一个结点的度都为 26 在下述结论中，正确的是( )。【南京理工大学 1999 一、4(1 分)】只有一个
3、结点的二叉树的度为 0；二叉树的度为 2； 二叉树的左右子树可任意交换；深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。（A）（B） （C） （D）7 设有一表示算术表达式的二叉树(见下图)，它所表示的算术表达式是( )。（A）A *B+C(D *E)+(F-G)（B） (A*B+C)(D *E)+(F-G)（C） (A*B+C(D *E+(F-G) （D）A *B+CD *E+F-G【南京理工大学 1999 一、20(2 分)】【烟台大学 2007 一、11(2 分 )】8 已知一算术表达式的中缀表达式为 a 一(b+cd) *e，其后缀形式为( )。【哈尔滨工业大学 200
4、4 二、1(1 分)】（A）一 a+b*cd（B）一 a+b*cde（C）一 +*abcde （D）abcd+e *一9 算术表达式 a+b*(c+d e)转为后缀表达式后为( )。【中山大学 1999 一、5(1 分)】（A）ab+cde *（B） abcde+ *+（C） abcde *+ （D）abcde *+- 。10 每个结点的度或者为 0 或者为 2 的二叉树称为正则二叉树。n 个结点的正则二叉树中有 ( ) 叶子。【武汉理工大学 2004 一、11(3 分)】（A）log 2n（B）（C） log2(n+1)（D）11 设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个
5、数分别为 4，2，1，1，则 T中的叶子数为( ) 。【南京理工大学 2000 一、8(15 分)】（A）5（B） 6（C） 7 （D）812 设有一个度为 3 的树，其叶结点数为，n0，度为 1 的结点数为 n1，度为 2 的结点数为 n2，度 为 3 的结点数为 n3，则 n0 与 n1，n2，n3 满足关系( )。【电子科技大学 2005 一、4(1 分)】（A）n0=n2+1（B） n0=n2+2*n3+1（C） n0=n2+n3+1（D）n0=n1+n2+n313 在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0 的结
6、点数为( )个。【哈尔滨工业大学 2001 二、2(2 分)】（A）4（B） 5（C） 6（D）714 以下说法中，( ) 是正确的。【华南理工大学 2006 一、12(2 分)】（A）完全二叉树中，叶结点的双亲的左兄弟(如果存在)一定不是叶结点（B）任何一棵二叉树，终端结点数为度为 2 的结点数减 1（C）二叉树不适合用顺序结构存储（D）结点按层序编号的二又树，第 i 个结点的左孩子(如果存在)的编号为 2i15 具有 10 个叶结点的二叉树中有( )个度为 2 的结点。【北京航空航天大学 2000一、5(2 分) 】（A）8（B） 9（C） 10（D）11二、填空题16 已知完全二叉树的第
7、 8 层(根结点的层次为 0)有 240 个结点，则整个完全二叉树的叶子结点数是_。【南京大学 2006】17 深度为 H 的完全二叉树至少有(1)个结点；至多有 (2)个结点；H 和结点总数 N之间的关系是(3)。【中科院计算所 1998 一、3(3 分)1999 二、4(3 分)】【中国科技大学 1998 一、3(4 分) 】18 如某二叉树有 20 个叶子结点，有 30 个结点仅有一个孩子，则该二叉树的总结点数为_。【南京理工大学 2001 二、3(2 分)】19 如果结点 A 有 3 个兄弟，而且曰是 A 的双亲，则 B 的度是_。【西安电子科技大学 1999 软件一、5(2 分)】2
8、0 已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度为 2 的结点，4 个度为 3 的结点，则该树有 _个叶子结点。【厦门大学 2000 六、2(163 分)】21 设高为 h 的二叉树只有度为 0 和 2 的结点，则此类二叉树的结点至少为 (1) ；至多为(2)。【 南京理工大学 2005 二、8(2 分) 】三、判断题22 在任意一棵二叉树中，分支结点的数目一定少于叶结点的数目。( )【吉林大学 2006 一、6(1 分) 】（A）正确（B）错误23 完全二叉树中，若一个结点没有左孩子，则它必是树叶。( )【东南大学 2001一、1-8(1 分 )】【中科院软件所 1997 一、
9、2(1 分)】【 山东大学 2001 一、4(1 分) 】【烟台大学 2007 二、9(1 分)】（A）正确（B）错误24 一个深度为 k 的，具有最少结点数的完全二叉树按层次(同层次从左向右)用自然数依次对结点编号，则编号最小的叶子的序号是 2k-2+1；编号是 i 的结点所在的层次号是log 2i+1(log2i表示向上取整)(根所在的层次号规定为 1 层)。( )【南京理工大学 2004 二、8(1 分) 】（A）正确（B）错误25 一棵有 n 个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为 i 的结点的左儿子的编号为 2i(2i0)的满二叉树对应的森林所含的树的个数一定是 h。31 【正确答案】 B【试题解析】 中序序列和后序序列相同的二叉树为：空树和任何结点都缺右子树的单支树。32 【正确答案】 B33 【正确答案】 B【试题解析】 结点的中序后继是其右子树中按中序遍历的第一个结点，即右子树中最左边的结点，可能是叶子，也可能是只有右子女的结点。34 【正确答案】 B【试题解析】 “和 y 可能分别在左子树和右子树上。
