资源描述
计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编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可能分别在左子树和右子树上。
展开阅读全文