计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编12

1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编12(总分：62.00，做题时间：90 分钟)一、 单项选择题(总题数：15，分数：30.00)后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是( )。【2009 年全国试题 3(2 分)】给定二叉树如下图所示。设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历A.LRN B.NRL C.RLN D.KNL已知一棵完全二叉树的第6 层(设根是第1 层)有8 个叶结点，则该完全二叉树的结点个数最多是( )【。2009年全国试题 5(2 分)】A.39 B.52C.11 1D.119本题问“完全二叉树的结点

2、个数最多是多少”。完全二叉树的叶子至多只能在最下面两层上。本题告诉第6 层有 8 个叶子，还会有 24 个分支结点，其在第 7 层最多有 48 个叶子，故选 C。若说第 6 层只有 8 个叶子， 则应选 A。将森林转换为对应的二叉树，若在二叉树中，结点u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是( )。【2009 年全国试题 6(2 分)】I父子关系 兄弟关系u 的父结点与 v 的父结点是兄弟关系A.只有B.I 和C.I 和D.I、和I 指的是二叉树中v 是u 的左子女的右子女，指的是二叉树中v 是u 的右子女的右子女。若成立，则森林转换的二叉树中，u 不可

3、能是v 的父结点的父结点。故选B。A.B.下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是( )。【2010 年全国试题 3(2 分)】C.D.在一棵度为 4 的树T 中，若有20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶结点个数是( )。 【2010 年全国试题 5(2 分)】A.41B.82 C.113 D.122度为 m 的树中，叶子结点个数的求解公式是其中，n是度i 的结点数。i对n(n2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是( )。【2010年全国试题 6(2 分)】该树

4、一定是一棵完全二叉树树中一定没有度为 1 的结点树中两个权值最小的结点一定是兄弟结点树中任一非叶结点的权值一定不小于下一层任一结点的权值若一棵完全二又树有 768 个结点，则该二又树中叶结点的个数是( )。 【2011 年全国试题 4(2 分)】A.257 B.258C.384D.385因为 n=n+n+n012，n=n20-1，所以n=2n+n0-1。在完全二叉树中，n1取 1 或 0。这里 n=768，1n。只能为 1，故选C。在完全二叉树结点计算中，仅知一个量(总结点数，叶子数，度为 2 的结点数)求1其他量，一般就利用该公式。下面的 3133 题都是该关系式的应用。若一棵二叉树的前序遍

5、历序列和后序遍历序列分别是 1，2，3，4 和 4，3，2，1，则该二叉树的中序遍历序列不会是( )。 【2011 年全国试题 5(2 分)】A.1，2，3，4 B.2，3，4，1 C.3，2，4，1 D.4，3，2，1前序遍历序列和后序遍历序列相反的二叉树是高度等于结点数的二叉树，或说只有一个叶子结点的二叉树， 或说每个分支结点至多只有左子女或只有右子女的二叉树。中序遍历的第一个结点是二叉树最左面的结点。A 是分支结点只有右子树的二叉树，D 是分支结点只有左子树的二叉树，B 是以 1 为根，2 是 1 的左子女，3 是 2 的右子女，4 是 3 的右子女。已知一棵有 2011 个结点的树，其

6、叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是( )。【2011 年全国试题 6(2 分)】A.115B.1 16 C.1895D.1 896该树非终端结点的个数为 2011-116=1895。树在转换成二叉树时，非终端结点子女中的最右子女结点的右指针为空(即最右子女无右孩子)。另外，森林中各棵树互为兄弟，转换为二叉树时最右一棵树根结点的右指针为空。1895+1=1896，故选D。若一棵二叉树的前序遍历序列为a，e，b，d,c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点( )。 2012 年全国试题 3(2 分)】只有e有e、b有e、c D.无法确定二叉树前序遍历序列的

7、第一个结点是根。若遍历序列多于一个结点，则第二个结点应是左子树的根，若无左子树则是右子树的根。对后序遍历的分析类似。本题从前序序列分析 e 肯定是孩子，b 也可能是，但结合对后序序列的分析，孩子只能是 e。另外，本题也可这样分析。先假定前序序列第二个结点e 是根a 的左子女。后序遍历是“左一右一根”，在后序序列中 e 的左面是以e 为根的左子树，r 的右面直到最后结点(根结点)苴的结点属于以a 为根的右子树。实际上 e 和a 相邻，说明 a 无右子树。若前序序列中e 是根a 的右子女(该二叉树无左子树)，则后序序列中 e 和 a 应该相邻，事实的确如此。已知三叉树T 中 6 个叶结点的权分别是

8、 2，3，4，5，6，7，T 的带权(外部)路径长度最小是( )。【2013年全国试题 4(2 分)】A.27B.46 C.54 D.56WPL=(2+3)*3+(4+5)*2+(6+7)*1=46对尼叉树，设 m 为叶子数，若(m 一 1)(k-1)0，要增加虚结点。第一次构造用(m1)(k-1)+1 个结点， 之后都用 k 个结点构造k 叉树。需要说明，国内多数教科书对“带权路径长度”的定义是所有叶子结点的带权路径长度之和，而“外部”结点指不存在的结点。本题构造的三叉树如右图。若 X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y，则 X 的右线索指向的是( )。【2013 年全国试题

9、 5(2 分)】A.X 的父结点B.以Y 为根的子树的最左下结点C.X 的左兄弟结点 YD.以Y 为根的子树的最右下结点4(2 分)】若对如下的二叉树进行中序线索化，则结点x 的左、右线索指向的结点分别是( )。【2014 年全国试题A.c,c B.c，a C.d,c D.b，a将森林F 转换为对应的二又树T，F 中叶结点的个数等于( )。2014 年全国试题 5(2 分)】A.T 中叶结点的个数B.T 中度为 1 的结点个数C.T 中左孩子指针为空的结点个数D.T 中右孩子指针为空的结点个数15.5 个字符有如下 4 种编码方案，不是前缀编码的是( )。【2014 年全国试题 6(2 分)】

10、A.01，0000，0001，001，1 B.011，000，001，010，1 C.000，001，010，011，100 D.0，100，110，11 10，1100要注意，前缀码是指一个编码不是另一个编码的前缀。二、 填空题(总题数：6，分数：12.00)含有 3 个结点的不同的二叉树有 棵。【电子科技大学 2005 二、7(1 分)】正确答案：(正确答案：5)一棵二叉树的结点数据采用顺序存储结构，存储在一维数组 t 中，f=e，a，f,0，d，0，g，0，0，c， j，0，0，1，h，i，0，0，0，0，b(其中 0 代表空树)，c 在树中的层次为 。【南京理工大学2004 三、2(1

11、 分)】正确答案：(正确答案：4)一棵有n 个结点的二叉树，叶子结点的数量为加，度为 2 的结点数量为，n2，则 n0 与n2 的关系是(1) ； 如果用二叉链表存储该二叉树，则空指针数量为(2)。【电子科技大学 2013 一、1(2 分)】正确答案：(正确答案：(1)n0=n2+1 (2)n+1)树在计算机内的表示方式有(1)，(2)，(3)。【哈尔滨工业大学 2000 二、4(3 分)】正确答案：(正确答案：(1)双亲链表表示法 (2)孩子链表表示法 (3)孩子兄弟表示法)在二叉树中，指针p 所指结点为叶子结点的条件是 。【合肥工业大学 1999 三、7(2 分)】正确答案：(正确答案：p

12、 一lchild=null&p 一rchlid=ull)中缀式a+b *3+4 *(c-d)对应的前缀式为(1)，若a=1，b=2，c=3，d=4，则后缀式dbcc *a 一b * +的运算结果为(2)。【西南交通大学 2000 一、6】正确答案：(正确答案：(1)+a*b3*4 一 cd (2)1 8)三、 判断题(总题数：10，分数：20.00)二叉树是一般树的特殊情形。( )【北京邮电大学 2000 一、9(1 分)2002 一、6(1 分)】正确错误树与二叉树是两种不同的树形结构。( )【东南大学 2001 一、1-7(1 分)】正确错误二叉树只能采用二叉链表来存储。( )【中南大学 2005 三、2(2 分)】正确错误二叉树中不存在度大于 2 的结点，当某个结点只有一棵子树时，无所谓左右子树之分。( )【中国海洋大学 2007 二、9(1 分)】正确错误二叉树是度为 2 的有序树。( )【中科院软件所 1997 一、9(1 分)】正确错误如果约定树中结点的度数不超过 2，则它实际上就是一棵二叉树。( )【兰州大学 2000 一、10(1 分)】正确错误具有 10 个叶结点的二叉树中，有 9 个度为 2 的结点。