计算机专业基础综合数据结构历年真题试卷汇编10

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编10（总分：68.00，做题时间：90 分钟）、 单项选择题（ 总题数：15 ，分数：30.00）1先序序列为a, b, c, d的不同二叉树的个数是（）。【2015年全国试题2（2分）】A. 13B. 14C. 15丿D. 16先序序列为1, 2, 3,，n的不同的二叉树的数目是1 / （n+1）（2n）! / （n!*n!）。2. 下列选项给出的是从根分别到达两个叶结点路径上的权值序列,能属于同一棵哈夫曼树的是（）。【2015年全国试题3（2分）】A. 24, 10, 5 和 24, 10, 7B. 24, 10, 5 和 24, 12, 7C. 24, 10, 10和24, 14, 11D. 24, 10, 5 和 24, 14, 6 丿A的错误在于若路径上有两个10,叶子5应和另一个权值5组成左右子女，7和3组成左右子女，显然不 符合哈夫曼的构造规则（应该3和5组成左右子女构造双亲结点）；若路径上只有一个10, 5和7并非其左 右子女。B的错误在于双亲10和双亲12不可能构造双亲24。C的错误是路径上不可能有相同权值10的结 点。D是正确的，双亲10的另一个子女是5,双亲14的另一个子女是8,而双亲10和双亲14恰是双亲24的左右子女。3. 树是一种逻辑关系,表示数据元素之间存在的关系为（ ） 。 【北京交通大学2007 （2分） 】A. 集合关系B. 一对一关系C. 一对多关系丿D. 多对多关系4. 下列判断, （ ）是正确的。【华南理工大学2005一、1（2分）】A. 二叉树就是度为 2 的树B. 二叉树中不存在度大于2的结点 丿C. 二叉树是有序树D. 二叉树的每个结点的度都为2 二叉树与树是两个不同的概念。相同点是二者都是树形结构,不同点有三：一是二叉树的度至多是2,树 无此限制；二是二叉树的子树有左右子树之分,只有一棵子树时,也必须区分是左子树还是右子树,树不 必这样；三是二叉树允许为空,树不准为空,但是多数教科书认为树可以为空,否则空二叉树无法转换成 空树,本题第一问有二义性。5. 有关二叉树下列说法正确的是（ ）。【南京理工大学2000一、11（15分）】A. 二叉树的度为2B. 一棵二叉树的度可以小于2丿C. 二叉树中至少有一个结点的度为2D. 二叉树中任何一个结点的度都为26. 在下述结论中，正确的是（）。【南京理工大学1999 一、4（1分）】只有一个结点的二叉树的度为0；二叉树的度为2；二叉树的左右子树可任意交换；深度为K的完全二叉树的结点个数小于或等于深 度相同的满二叉树。A. B. C.B. （A * B+C）（D * E）+（F-G）C. （A * B+C / （D * E+（F-G） 丿D. A * B+C / D * E+F-G【南京理工大学1999 一、20（2分）】【烟台大学2007 、11（2分）】8已知一算术表达式的中缀表达式为a 一 （b+c/d） * e,其后缀形式为（）。【哈尔滨工业大学2004二 1（1 分）】A. 一 a+b * c/ dB. 一 a+b * cd/ eC. 一+ * abc/ deD. 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. logB.nC.log匸(n+1)11. 设树T的度为4,其中度为1, 2, 3和4的结点个数分别为4, 2, 1, 1,则T中的叶子数为（）。【南 京理工大学2000一、 8（15分）】A. 5B. 6C. 7D. 8V12设有一个度为3的树，其叶结点数为，n0,度为1的结点数为n1,度为2的结点数为n2,度为3的结 点数为n3,则n0与n1, n2, n3满足关系（）。【电子科技大学2005 一、4（1分）】A. n0=n2+1B. n0=n2+2 * n3+1 VC. n0=n2+n3+1D. n0=n1+n2+n313. 在一棵三元树中度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,则度为0的 结点数为（ ）个。 【哈尔滨工业大学2001二、 2（2分）】A. 4B. 5C. 6 VD. 714. 以下说法中, （ ）是正确的。 【华南理工大学2006一、 12（2分）】A. 完全二叉树中,叶结点的双亲的左兄弟（如果存在）一定不是叶结点 VB. 任何一棵二叉树,终端结点数为度为 2 的结点数减 1C. 二叉树不适合用顺序结构存储D. 结点按层序编号的二又树，第i个结点的左孩子（如果存在）的编号为2i 完全二叉树叶子结点的双亲是最后一个分支结点时，其双亲的右兄弟（如果存在）肯定是叶子，其左兄弟肯 定是分支结点，不可能是叶子。任何二叉树，终端（叶子） 结点数为度为 2 的结点数加 1；用顺序存储结构 可以存储二叉树，特别是完全二叉树；只有完全二叉树顺序存储时双亲结点和子女结点的存储位置（下标） 间才存在确定关系。15. 具有 10 个叶结点的二叉树中有（ ） 个度为 2 的结点。【北京航空航天大学 2000 一、5（2 分）】A.8B. 9 丿C. 10D. 11二、 填空题（总题数：6，分数：12.00）16. 已知完全二叉树的第 8 层（根结点的层次为 0） 有 240 个结点，则整个完全二叉树的叶子结点数是 。【南京大学 2006】正确答案：（正确答案：248 （第 7 层的 8 个叶子结点+第 8 层 240 个结点）17. 深度为H的完全二叉树至少有（1 ）个结点；至多有（2）个结点；H和结点总数N之间的关系是（3）。【中 科院计算所 1998 一、3（3 分）1999 二、4（3 分） 】【中国科技大学 1998 一、3（4 分） 】正确答案：（正确答案：（1）2 H-1 （2）2 H 1 （3）H=logN+1）218. 如某二叉树有 20 个叶子结点，有 30 个结点仅有一个孩子，则该二叉树的总结点数为。【南京理工大学 2001 二、3（2 分）】 正确答案：（正确答案：69）19. 如果结点 A 有 3 个兄弟，而且曰是 A 的双亲，则 B 的度是。【西安电子科技大学 1999 软件一、5（2 分） 】 正确答案：（正确答案：4）20. 已知一棵度为 3 的树有 2 个度为 1 的结点， 3 个度为 2 的结点， 4 个度为 3 的结点，则该树有 个叶子结点。【厦门大学 2000 六、2（163 分） 】 正确答案：（正确答案：12）21. 设高为 h 的二叉树只有度为 0 和 2 的结点，则此类二叉树的结点至少为 （1） ；至多为（2） 。【南京理工 大学 2005 二、8（2 分） 】 正确答案：（正确答案：（1）2h 1 （2）2 h 一 1）三、 判断题（总题数：13，分数：26.00）22. 在任意一棵二叉树中，分支结点的数目一定少于叶结点的数目。 （ ） 【吉林大学 2006 一、6（1 分）】A. 正确B. 错误丿在任意二叉树中，度为2的结点数和度为0（叶子）的结点数有确定关系，即n0=n2+1。二叉树中还有度为1 的结点，度为 1 的结点和度为 0 的结点在数量上无确定关系。例如，单支树中，分支结点数就大干等于叶 子结点数。23. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。 （ ） 【东南大学 2001 一、1-8（1 分） 】【中科 院软件所 1997 一、2（1 分）】【山东大学 2001 一、4（1 分）】【烟台大学 2007 二、9（1 分） 】A. 正确丿B. 错误24. 一个深度为 k 的，具有最少结点数的完全二叉树按层次（同层次从左向右） 用自然数依次对结点编号，则 编号最小的叶子的序号是2k-2+1；编号是i的结点所在的层次号是1叮+1（1叮表示向上取整）（根 所在的层次号规定为 1 层） 。 （ ）【南京理工大学 2004 二、8（1 分）】A. 正确B. 错误丿该完全二叉树的第k层只有最左边的一个结点，第k-1层从左数第2个结点是编号最小的叶子，序号是2 k-2 +1;编号i的结点所在的层次号是logi+l。25. 一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的 编号为2i（2in），右儿子是2i+1（2i+1A. 正确B. 错误丿只对完全二叉树适用，编号为i的结点的左儿子的编号为2i（2iWn），右儿子是2i+1（2i+1Wn）。26深度为k具有n个结点的完全二叉树，其编号最小的叶结点序号为2k-2+1。（）【东北大学1997二、 3（2分）】A. 正确丿B. 错误27. 完全二叉树的存储结构通常采用顺序存储结构。 （ ）【南京航空航天大学1996六、 3（1 分）】A. 正确丿B. 错误28. 在二叉树顺序存储结构中（根的下标为1） ，下标为130的结点一定处于左子树中。 （ ）【中国科学技术 大学 2004】A. 正确丿B. 错误 二叉树的顺序存储结构是按完全二叉树存储的，一般二叉树加“虚结点”。题目设根结点编号为1，则编 号i的左子女是2i（可能是虚结点），因此，130肯定在左子树中。29. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息（他们反映的信息不独立）。 （ ）【华南理工大 学 2002 一、 7（1 分）】A. 正确丿B. 错误30. 高度为h（h0）的完全二叉树对应的森林所含的树的个数一定是h。（）【北京交通大学2004三、1（2 分）】A. 正确B. 错误丿高度为h（h0）的满二叉树对应的森林所含的树的个数一定是ho31. 中序序列和后序序列相同的二叉树为：空树和缺右子树的单支树。（）【南京理工大学2004二、3（1 分）】A. 正确B. 错误丿 中序序列和后序序列相同的二叉树为：空树和任何结点都缺右子树的单支树。32. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是哪一个，则可以确定 这棵二叉树。 （ ）【上海海事大学1995 一、 6（1 分）】A. 正确B. 错误丿33. 二叉树中有双子女的父结点，在中序遍历中后继一定是其中一个子女结点。（）【北京邮电大学2006二、 1（5分）】A. 正确B. 错误丿 结点的中序后继是其右子树中按中序遍历的第一个结点，即右子树中最左边的结点，可能是叶子，也可能 是只有右子女的结点。34. 完全二叉树的前序序列中，若结点u在结点v之前，则u 定是v的祖先。（）【中国海洋大学2003 一、 4（2分）】A. 正确B. 错误丿“和y可能分别在左子树和右子树上。