1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 3 及答案与解析一、单项选择题1 给定二叉树如下图所示。设 N 代表二叉树的根， L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是( )。【2009 年全国试题 3(2 分) 】（A）LRN（B） NRL（C） RLN（D）KNL2 已知一棵完全二叉树的第 6 层(设根是第 1 层)有 8 个叶结点，则该完全二叉树的结点个数最多是( ) 。【2009 年全国试题 5(2 分) 】（A）39（B） 52（C） 11 1（D）1193 将森林转换为对应的二叉树，若在二叉树中，结
2、点 u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是( )。【2009 年全国试题 6(2 分)】I父子关系 兄弟关系u 的父结点与 v 的父结点是兄弟关系（A）只有（B） I 和（C） I 和（D）I、和4 下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是( )。【2010 年全国试题 3(2 分) 】（A）（B）（C）（D）5 在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点， 10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶结点个数是 ( )。 【2010 年全国试题 5(2 分) 】（A）4
3、1（B） 82（C） 113（D）1226 对 n(n2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是( )。【2010 年全国试题 6(2 分) 】（A）该树一定是一棵完全二叉树（B）树中一定没有度为 1 的结点（C）树中两个权值最小的结点一定是兄弟结点（D）树中任一非叶结点的权值一定不小于下一层任一结点的权值7 若一棵完全二又树有 768 个结点，则该二又树中叶结点的个数是( )。 【2011年全国试题 4(2 分) 】（A）257（B） 258（C） 384（D）3858 若一棵二叉树的前序遍历序列和后序遍历序列分别是 1，2，3，4 和4，3，2，1，则该二叉
4、树的中序遍历序列不会是( )。 【2011 年全国试题 5(2 分)】（A）1，2，3，4（B） 2，3，4，1（C） 3，2，4，1 （D）4，3，2，19 已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是( ) 。 【2011 年全国试题 6(2 分)】（A）115（B） 1 16（C） 1895（D）1 89610 若一棵二叉树的前序遍历序列为 a，e ，b，d,c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点( )。 2012 年全国试题 3(2 分)】（A）只有 e（B）有 e、b（C）有 e、c （D）无法确定11 已知三叉树
5、 T 中 6 个叶结点的权分别是 2，3， 4，5，6，7，T 的带权(外部)路径长度最小是( ) 。【2013 年全国试题 4(2 分) 】（A）27（B） 46（C） 54（D）5612 若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右线索指向的是( )。【2013 年全国试题 5(2 分) 】（A）X 的父结点（B）以 Y 为根的子树的最左下结点（C） X 的左兄弟结点 Y （D）以 Y 为根的子树的最右下结点13 若对如下的二叉树进行中序线索化，则结点 x 的左、右线索指向的结点分别是( )。【2014 年全国试题 4(2 分)】（A）c,c（B） c，a（
6、C） d,c（D）b，a14 将森林 F 转换为对应的二又树 T，F 中叶结点的个数等于 ( )。2014 年全国试题 5(2 分) 】（A）T 中叶结点的个数（B） T 中度为 1 的结点个数（C） T 中左孩子指针为空的结点个数（D）T 中右孩子指针为空的结点个数15 5 个字符有如下 4 种编码方案，不是前缀编码的是( )。【2014 年全国试题 6(2分)】（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二、填空题16 含有 3 个结点的不同的二叉树有_棵。
7、【电子科技大学 2005 二、7(1分)】17 一棵二叉树的结点数据采用顺序存储结构，存储在一维数组 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 分)】18 一棵有 n 个结点的二叉树，叶子结点的数量为加，度为 2 的结点数量为，n2，则 n0 与 n2 的关系是(1) ；如果用二叉链表存储该二叉树，则空指针数量为(2)。【电子科技大学 2013 一、1(2 分)】19 树在计算机内的表示方式有(1)，(2) ，(3)。【哈尔滨工业大学 2000 二、
8、4(3 分)】20 在二叉树中，指针 p 所指结点为叶子结点的条件是_。【合肥工业大学 1999 三、7(2 分) 】21 中缀式 a+b*3+4*(c-d)对应的前缀式为(1)，若 a=1，b=2，c=3，d=4，则后缀式dbcc *a 一 b*+的运算结果为(2)。【西南交通大学 2000 一、6】三、判断题22 二叉树是一般树的特殊情形。( )【北京邮电大学 2000 一、9(1 分)2002 一、6(1 分)】（A）正确（B）错误23 树与二叉树是两种不同的树形结构。( )【东南大学 2001 一、1-7(1 分)】（A）正确（B）错误24 二叉树只能采用二叉链表来存储。( )【中南大
9、学 2005 三、2(2 分)】（A）正确（B）错误25 二叉树中不存在度大于 2 的结点，当某个结点只有一棵子树时，无所谓左右子树之分。( )【中国海洋大学 2007 二、9(1 分) 】（A）正确（B）错误26 二叉树是度为 2 的有序树。( )【中科院软件所 1997 一、9(1 分)】（A）正确（B）错误27 如果约定树中结点的度数不超过 2，则它实际上就是一棵二叉树。( )【兰州大学 2000 一、10(1 分) 】（A）正确（B）错误28 具有 10 个叶结点的二叉树中，有 9 个度为 2 的结点。( )【同济大学 2005 二、6(15 分) 】（A）正确（B）错误29 对于有
10、n 个结点的二叉树，其高度为 log2n。( )【上海海事大学 1998 一、6(1 分)】（A）正确（B）错误30 深度为 k 的二叉树中结点总数2 k-1。( )【南京航空航天大学 1995 五、1(1 分)】（A）正确（B）错误31 在二叉树的第 i 层上至少有 2i-1 个结点(i1)。( )【燕山大学 1998 二、3(2 分)】（A）正确（B）错误计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 3 答案与解析一、单项选择题1 【正确答案】 D2 【正确答案】 C【试题解析】 本题问“完全二叉树的结点个数最多是多少”。完全二叉树的叶子至多只能在最下面两层上。本题告诉第 6
11、层有 8 个叶子，还会有 24 个分支结点，其在第 7 层最多有 48 个叶子，故选 C。若说第 6 层只有 8 个叶子，则应选 A。3 【正确答案】 B【试题解析】 I 指的是二叉树中 v 是 u 的左子女的右子女，指的是二叉树中 v是 u 的右子女的右子女。若成立，则森林转换的二叉树中，u 不可能是 v 的父结点的父结点。故选 B。4 【正确答案】 D5 【正确答案】 B【试题解析】 度为 m 的树中，叶子结点个数的求解公式是 其中，ni 是度 i 的结点数。6 【正确答案】 A7 【正确答案】 C【试题解析】 因为 n=n0+n1+n2，n 2=n0-1，所以 n=2n0+n1-1。在完
12、全二叉树中，n 1取 1 或 0。这里 n=768，n 1。只能为 1，故选 C。在完全二叉树结点计算中，仅知一个量(总结点数，叶子数，度为 2 的结点数)求其他量，一般就利用该公式。下面的 3133 题都是该关系式的应用。8 【正确答案】 C【试题解析】 前序遍历序列和后序遍历序列相反的二叉树是高度等于结点数的二叉树，或说只有一个叶子结点的二叉树，或说每个分支结点至多只有左子女或只有右子女的二叉树。中序遍历的第一个结点是二叉树最左面的结点。A 是分支结点只有右子树的二叉树，D 是分支结点只有左子树的二叉树， B 是以 1 为根，2 是 1 的左子女，3 是 2 的右子女，4 是 3 的右子女
13、。9 【正确答案】 D【试题解析】 该树非终端结点的个数为 2011-116=1895。树在转换成二叉树时，非终端结点子女中的最右子女结点的右指针为空(即最右子女无右孩子)。另外，森林中各棵树互为兄弟，转换为二叉树时最右一棵树根结点的右指针为空。1895+1=1896，故选 D。10 【正确答案】 A【试题解析】 二叉树前序遍历序列的第一个结点是根。若遍历序列多于一个结点，则第二个结点应是左子树的根，若无左子树则是右子树的根。对后序遍历的分析类似。本题从前序序列分析 e 肯定是孩子，b 也可能是，但结合对后序序列的分析，孩子只能是 e。另外，本题也可这样分析。先假定前序序列第二个结点 e 是根
14、 a 的左子女。后序遍历是“左一右一根”，在后序序列中 e 的左面是以 e 为根的左子树，r 的右面直到最后结点 (根结点 )苴的结点属于以 a 为根的右子树。实际上 e 和 a 相邻，说明 a 无右子树。若前序序列中 e 是根 a 的右子女(该二叉树无左子树)，则后序序列中 e 和 a 应该相邻，事实的确如此。11 【正确答案】 B【试题解析】 对尼叉树，设 m 为叶子数，若(m 一 1)(k-1)0，要增加虚结点。第一次构造用(m1)(k-1)+1 个结点，之后都用 k 个结点构造 k 叉树。需要说明，国内多数教科书对“带权路径长度”的定义是所有叶子结点的带权路径长度之和，而“外部”结点指
15、不存在的结点。本题构造的三叉树如右图。WPL=(2+3)*3+(4+5)*2+(6+7)*1=4612 【正确答案】 A13 【正确答案】 D14 【正确答案】 C15 【正确答案】 D【试题解析】 要注意，前缀码是指一个编码不是另一个编码的前缀。二、填空题16 【正确答案】 517 【正确答案】 418 【正确答案】 (1)n0=n2+1 (2)n+119 【正确答案】 (1)双亲链表表示法 (2) 孩子链表表示法 (3)孩子兄弟表示法20 【正确答案】 p 一lchild=null&p 一rchlid=ull21 【正确答案】 (1)+a*b3*4 一 cd (2)1 8三、判断题22 【正确答案】 B23 【正确答案】 A24 【正确答案】 B25 【正确答案】 B26 【正确答案】 B27 【正确答案】 B28 【正确答案】 A29 【正确答案】 B30 【正确答案】 A31 【正确答案】 B
