计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编12
(总分：62.00，做题时间：90分钟)
一、 单项选择题(总题数：15，分数：30.00)
1.给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是( )。【2009年全国试题3(2分)】
 A.LRN
 B.NRL
 C.RLN
 D.KNL √
2.已知一棵完全二叉树的第6层(设根是第1层)有8个叶结点，则该完全二叉树的结点个数最多是( )。【2009年全国试题5(2分)】
 A.39
 B.52
 C.11 1 √
 D.119
本题问“完全二叉树的结点个数最多是多少”。完全二叉树的叶子至多只能在最下面两层上。本题告诉第6层有8个叶子，还会有24个分支结点，其在第7层最多有48个叶子，故选C。若说第6层只有8个叶子，则应选A。
3.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是( )。【2009年全国试题6(2分)】I．父子关系 Ⅱ．兄弟关系Ⅲ．u的父结点与v的父结点是兄弟关系
 A.只有Ⅱ
 B.I和Ⅱ √
 C.I和Ⅲ
 D.I、Ⅱ和Ⅲ
I指的是二叉树中v是u的左子女的右子女，Ⅱ指的是二叉树中v是u的右子女的右子女。若Ⅲ成立，则森林转换的二叉树中，u不可能是v的父结点的父结点。故选B。
4.下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是( )。【2010年全国试题3(2分)】
 A.
 B.
 C.
 D. √
5.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是( )。 【2010年全国试题5(2分)】
 A.41
 B.82 √
 C.113
 D.122
度为m的树中，叶子结点个数的求解公式是 其中，n i 是度i的结点数。
6.对n(n≥2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是( )。【2010年全国试题6(2分)】
 A.该树一定是一棵完全二叉树 √
 B.树中一定没有度为1的结点
 C.树中两个权值最小的结点一定是兄弟结点
 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值
7.若一棵完全二又树有768个结点，则该二又树中叶结点的个数是( )。 【2011年全国试题4(2分)】
 A.257
 B.258
 C.384 √
 D.385
因为n=n 0 +n 1 +n 2 ，n 2 =n 0 -1，所以n=2n 0 +n 1 -1。在完全二叉树中，n 1 取1或0。这里n=768，n 1 。只能为1，故选C。在完全二叉树结点计算中，仅知一个量(总结点数，叶子数，度为2的结点数)求其他量，一般就利用该公式。下面的31~33题都是该关系式的应用。
8.若一棵二叉树的前序遍历序列和后序遍历序列分别是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的右子女。
9.已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是( )。 【2011年全国试题6(2分)】
 A.115
 B.1 16
 C.1895
 D.1 896 √
该树非终端结点的个数为2011-116=1895。树在转换成二叉树时，非终端结点子女中的最右子女结点的右指针为空(即最右子女无右孩子)。另外，森林中各棵树互为兄弟，转换为二叉树时最右一棵树根结点的右指针为空。1895+1=1896，故选D。
10.若一棵二叉树的前序遍历序列为a，e，b，d,c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点( )。 [2012年全国试题3(2分)】
 A.只有e √
 B.有e、b
 C.有e、c
 D.无法确定
二叉树前序遍历序列的第一个结点是根。若遍历序列多于一个结点，则第二个结点应是左子树的根，若无左子树则是右子树的根。对后序遍历的分析类似。本题从前序序列分析e肯定是孩子，b也可能是，但结合对后序序列的分析，孩子只能是e。另外，本题也可这样分析。先假定前序序列第二个结点e是根a的左子女。后序遍历是“左一右一根”，在后序序列中e的左面是以e为根的左子树，r的右面直到最后结点(根结点)苴的结点属于以a为根的右子树。实际上e和a相邻，说明a无右子树。若前序序列中e是根a的右子女(该二叉树无左子树)，则后序序列中e和a应该相邻，事实的确如此。
11.已知三叉树T中6个叶结点的权分别是2，3，4，5，6，7，T的带权(外部)路径长度最小是( )。【2013年全国试题4(2分)】
 A.27
 B.46 √
 C.54
 D.56
对尼叉树，设m为叶子数，若(m一1)％(k-1)≠0，要增加虚结点。第一次构造用(m—1)％(k-1)+1个结点，之后都用k个结点构造k叉树。需要说明，国内多数教科书对“带权路径长度”的定义是所有叶子结点的带权路径长度之和，而“外部”结点指不存在的结点。本题构造的三叉树如右图。WPL=(2+3)*3+(4+5)*2+(6+7)*1=46
12.若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
 C.d,c
 D.b，a √
14.将森林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 √
要注意，前缀码是指一个编码不是另一个编码的前缀。
二、 填空题(总题数：6，分数：12.00)
16.含有3个结点的不同的二叉树有__________棵。【电子科技大学2005二、7(1分)】
__________________________________________________________________________________________
正确答案：(正确答案：5)
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分)】
__________________________________________________________________________________________
正确答案：(正确答案：4)
18.一棵有n个结点的二叉树，叶子结点的数量为加，度为2的结点数量为，n2，则n0与n2的关系是(1) ；如果用二叉链表存储该二叉树，则空指针数量为(2)。【电子科技大学2013一、1(2分)】
__________________________________________________________________________________________