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