1、计算机专业基础综合（树与二叉树）模拟试卷 4 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 设树 T 的度为 4，其中度为 1、2，3 和 4 的结点个数分别为 4、1、1、1，则 T中的叶子数为( ) 。（A）10（B） 11（C） 9（D）72 用下列元素序列(22，8，62，35，48)构造平衡二叉树，当插入( )时，会出现不平衡的现象。（A）22（B） 35（C） 48（D）623 下面的算法实现了将二叉树中每一个结点的左右子树互换。addQ(Q，bt) 为进队的函数，delQ(Q)为出队的函数，
2、empty(Q)为判别队列是否为空的函数，空白处应填的内容是( ) 。typedef struct nodeint data；struct node*lchild，*rchild；btnode；void exchange(btnode*bt)btnode*p，*q；if(bt)addQ(Q，bt)；while(TEMPTY(Q)p=delQ(Q)；q=p-rchild；p-rchild=p-lchild；( (1) )=q；if(p-lchild)( (2) )；if(p-rchild)addQ(Q，p-rchild)；（A）p-lchild ，delQ(Q，p-lchild)（B） p-rc
3、hild，delQ(Q，p-lchild)（C） p-lchild，addQ(Q，p-lchild)（D）p-rchild，addQ(Q，p-lchild)4 已知有一棵二叉树，其高度为 n，并且有且只有 n 个结点，那么二叉树的树形有( )种。（A）nlog 2n（B） 2n+1（C） 2n-1（D）2 n-15 已知二叉排序树如下图所示，下列序列构造此二叉排序树不正确的是( )。 （A）(105 ，85，90，65，120，110，138)（B） (105，120，110，138，85，65，90)（C） (105，65，85，90，120，110，138)（D）(105 ，85，65，9
4、0，120，138，110)6 已知某平衡二叉树含有在 15 个结点，25 为其中的一个结点，如果在此平衡二叉树上查找关键字为 25 的结点，下列比较的次序合理的是( )。（A）29，35（B） 35，45，25（C） 45，15，35，25（D）60，30，50，40，38，367 利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30 要进行元素间的比较次数是( )。（A）4（B） 5（C） 6（D）78 构建一个哈夫曼树，如果给定权值的个数为 n，那么哈夫曼树的结点总数为( )。（A）不确定（B） 2n（C） 2n+1（D
5、）2n-19 已知某哈夫曼树的度为 m，其中叶结点个数为 n，那么非叶结点的个数为( )。（A）n-1（B）（C）（D）10 一棵哈夫曼树共有 99 个结点，对其进行哈夫曼编码，共能得到( )种不同的编码。（A）48（B） 50（C） 99（D）10011 一棵含有 n 个结点的 k 叉树，可能达到的最大深度为( )，最小深度为( )。（A）n-k+1，log kn+1（B） n，log kn+1（C） n，log kn-1（D）n-k+1，log kn+112 已知一棵满二叉树的结点个数为 20 到 40 之间的素数，此二叉树的叶子结点有( )个。（A）23（B） 29（C） 16（D）32
6、13 有( )棵不同的二叉树，其结点的前序序列为 a1，a 2，a n。 14 有 n 个叶结点的非满的完全二叉树的高度为( )。（A）2n+1（B） 2n-1（C） log22n+1（D）log 22n-115 在一棵二叉树中，单分支结点数为 30，双分支结点数为 15，则叶子结点数为( )。（A）15（B） 16（C） 17（D）4716 判断线索二叉树中某结点*p 有左孩子的条件是( )。（A）p-lchild=NULL（B） p-lchild=0（C） p-hag=0（D）p-ltag=117 在线索二叉树中，结点*p 没有左子树的充要条件是( )。（A）p-lchild=NULL（B
7、） p-hag=1（C） p-hag=1 且 p-lchild=NULL（D）以上都不对18 如果 T1 是由有序树 T 转换而来的二叉树，那么 T 中结点的前序遍历序列就是T1 中结点的( )-遍历序列。（A）前序（B）中序（C）后序（D）层次序19 在图中所示的 4 棵二叉树中，( )不是完全二叉树。 （A）图(a)（B）图 (b)（C）图 (c)（D）图(d)20 一棵二叉树如下图所示，其中序遍历序列为( )。 （A）abdgcefh（B） dgbaechf（C） gdbehfca（D）abcdefgh21 有 n 个叶子结点的哈夫曼树的结点总数为( )。（A）不确定（B） 2n（C）
8、2n+1（D）2n-122 如图所示的 T2 是由森林 T1 转换而来的二叉树，那么森林 T1 有( )个叶结点。 （A）4（B） 5（C） 6（D）7二、综合应用题41-47 小题，共 70 分。23 假定用两个一维数组 LN和 RN作为有 N 个结点 1，2，N 的二叉树的存储结构。Li和 Ri分别指示结点 i 的左儿子和右儿子；Li=0(Ri=0)表示 i 的左(右)儿子为空。试写一个算法，由 L 和 R 建立一个一维数组 Tn，使 Ti存放结点i 的父亲；然后再写一个判别结点 U 是否为结点 V 的后代的算法。24 试找出分别满足下面条件的所有二叉树：(1)前序序列和中序序列相同。(2
9、)中序序列和后序序列相同。(3)前序序列和后序序列相同。(4)前序、中序、后序序列均相同。25 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树 BT 中，写出计算该算术表达式值的算法。26 画出如下图所示的二叉树所对应的森林。 27 下述编码中，哪一组不是前缀码?00， 01， 10，11 ，0，1，00，11，0 ，10，110，11128 假设用于通信的电文由字符集a，b，c，d，e，f，g，h 中的字母构成，这 8个字母在电文中出现的概率分别为007 ，0 19，002， 006，032，003，021，010 。(1)为这 8 个字母设计哈夫曼编码。(2)若用三位二进制数
10、(0 一 7)对这 8 个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?29 有 n 个结点的完全二叉树存放在一维数组 A1n中，试据此建立一棵用二叉链表表示的二叉树，根由 tree 指向。(可不定义结构体)30 已知深度为 h 的二叉树采用顺序存储结构已存放于数组 BT12 h 一 1中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild， data，rchild)，根结点所在链结点的指针由 T 给出。计算机专业基础综合（树与二叉树）模拟试卷 4 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分
11、。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 根据题中条件可知，14+21+3+4+1=4+1+1+1+n 0，由此可以得出：n0=14+21+3+4+1 一(4+1+1+1)=147=7。【知识模块】 树与二叉树2 【正确答案】 C【试题解析】 由题中所给的结点序列构造二叉排序树的过程如下图： 当插入 48 后，首次出现不平衡子树，虚线框内即为最小不平衡子树。【知识模块】 树与二叉树3 【正确答案】 C【知识模块】 树与二叉树4 【正确答案】 D【试题解析】 由题可得，每层有一个结点，从根结点往下，每个结点都有做左孩子右孩子两种情况，由概率知识
12、可得，二叉树共有 2n-1 种树形。【知识模块】 树与二叉树5 【正确答案】 C【试题解析】 将各选项中对应的二叉排序树画出即可得到答案。【知识模块】 树与二叉树6 【正确答案】 C【试题解析】 设 Nh 表示深度为 h 的平衡二叉树中含有的最少结点数，有：N0=0， N1=1， N2=2，N h=Nh-1+Nh-2+1，N 3=4，N 4=7，N 5=12，N 6=2015。也就是说，高度为 6 的平衡二叉树最少有 20 个结点，因此 15 个结点的平衡二叉树的高度为 5，而最小叶子结点的层数为 3，所以选项 D 错误。而 A 和 B 的查找过程不能构成二叉排序树，因此 A、B 错误。【知识
13、模块】 树与二叉树7 【正确答案】 B【试题解析】 利用逐点插入法建立二叉排序树是从空树开始，通过查找，将每个结点作为一个叶子插入。按题目中数据的输入次序建立的二叉排序树如下图所示，查找元素 30 的比较次数为 5 次。 【知识模块】 树与二叉树8 【正确答案】 D【试题解析】 哈夫曼树中只有度为 0 和度为 2 的结点，即 N=n0+n2，而根据二叉树的性质：n 0=n2+1，可知 n0=n，那么 n2=n1，N=n+n 一 1=2n1。【知识模块】 树与二叉树9 【正确答案】 C【试题解析】 度为 m 的结点个数为 nm 叶子结点个数为n，mn m+1=nm+n，mn m=nm+n1 nm
14、= 。【知识模块】 树与二叉树10 【正确答案】 B【试题解析】 本题考查哈夫曼树的性质。哈夫曼树中只有度为 2 和度为 0 的结点，哈夫曼编码是对哈夫曼树中的叶子结点编码。根据树的性质 N0=N2+1，故N0=(N2+N0+1)2=(99+1)2=50，哈夫曼树共有 50 个叶子结点，所以共能得到 50个不同的码字。【知识模块】 树与二叉树11 【正确答案】 A【试题解析】 当 k 叉树种只有一个层的分支数为 n，其他层的分指数均为 1 时，此时的树具有最大的深度为：n 一 k+1。 当该 k 叉树为完全 k 叉树时，其深度最小。参照二叉树的性质可知，其深度为：1og kn+1。【知识模块】
15、 树与二叉树12 【正确答案】 C【试题解析】 一棵深度为 h 的满二叉树的结点个数为 2h 一 1，则有 202h 一140，即 212h41，h=5(总结点数=2 5 一 1=31，为素数)。满二叉树中叶子结点均集中在最底层，所以结点个数=2 5-1=16 个。【知识模块】 树与二叉树13 【正确答案】 A【试题解析】 这是一个变形的求 n 个结点的互不相似的二叉树个数问题，设 T(n)表示含 n 个结点的二叉树个数，T(0)=T(1)=1，T(2)=2，T(n)=T(n1)T(0)+T(n一 2)T(1)+T(0)T(n1)，而递归方程的解为【知识模块】 树与二叉树14 【正确答案】 A
16、【试题解析】 设 j、k 分别为度为 1、2 的结点数目，则结点总数 m=n+j+k；由于是非满的，所以必有 j=1，且 n=k+1，因此有 m=2n。设树的高度为 h，具有 n 个结点的完全二叉树的深度为 log2n+1。本题中，树的结点个数为 2n，有 h=log2(2n)+1。所以，有 n 个叶结点的非满的完全二叉树的高度为 log2(2n)+1。【知识模块】 树与二叉树15 【正确答案】 B【试题解析】 由二叉树的性质可知：n 0=n2+1=16。【知识模块】 树与二叉树16 【正确答案】 C【试题解析】 有左孩子表示不是线索，即 p 一ltag=0。【知识模块】 树与二叉树17 【正
17、确答案】 B【试题解析】 没有左孩子时指针域指向线索，即 p 一ltag=1 。【知识模块】 树与二叉树18 【正确答案】 A【试题解析】 由树转换为二叉树的过程可知本题答案应为 A。【知识模块】 树与二叉树19 【正确答案】 C【试题解析】 由完全二叉树的定义可知(c)不是完全二叉树。【知识模块】 树与二叉树20 【正确答案】 B【试题解析】 由中序遍历过程可知本题答案应为 B。【知识模块】 树与二叉树21 【正确答案】 D【试题解析】 在哈夫曼树中，由计算公式可计算得结点总数为 2n1，所以选D。【知识模块】 树与二叉树22 【正确答案】 C【试题解析】 T2 对应的森林 T1 如下图所示
18、，由图中可以看出，所有的叶子结点总数为 6。 【知识模块】 树与二叉树二、综合应用题41-47 小题，共 70 分。23 【正确答案】 由指示结点 i 左儿子和右儿子的两个一维数组 Li和 Ri，很容易建立指示结点 i 的双亲的一维数组 Ti，根据 T 数组，判断结点 U 是否是结点V 后代的算法转为判断结点 V 是否是结点 U 的祖先的问题。int Gener|ation(int U，V，N，L，R ，T)L和 R是含有 N 个元素且指示二叉树结点 i 左儿子和右儿子的一维数组本算法据此建立结点 i 的双亲数组 T，并判断结点 U 是否是结点 V 的后代int i：for(i=1；ilchi
19、ld)； 求左子树表示的子表达式的值rv=PostEval(bt 一rchild)： 求右子树表示的子表达式的值switch(bt 一optr)ease+：value=Iv+rv；break ；case一：value=lv-rv ；break ；case*：value=lv*rv；break；case：value=lvrv；return(vahle)：【知识模块】 树与二叉树26 【正确答案】 该二叉树所对应的森林如下图所示，它由四棵树组成。 【知识模块】 树与二叉树27 【正确答案】 在0， 1，00，11 中，由于 0、 1 分别是 00、11 的前缀，所以它不是前缀码。【知识模块】 树与
20、二叉树28 【正确答案】 (1)对应的哈夫曼树如下图所示。各字母的哈夫曼编码如下：a：1010，b： 00，c ：10000 ，d：1001，e：11，f：10001，g：01，h：1011 (2)哈夫曼编码的平均码长为： 0025+0035+0 064+0074+014+0322+0192+0212=261 26l3=087，它是等长编码的 87，它使电文总长平均压缩 13。【知识模块】 树与二叉树29 【正确答案】 BiTree Creat(ElemType A，int i)n 个结点的完全二叉树存于一维数组 A 中，本算法据此建立以二叉链表表示的完全二叉树BiTree tree；if(i
21、data=Ai；if(2*in)tree-lchild=null；else tree-lchild=Creat(A，2*i)；if(2*i+1n)tree 一rchild=null；else tree 一rchild=Creat(A ，2*i+1)；return(tree)； Creat提示：初始调用时 i=1。【知识模块】 树与二叉树30 【正确答案】 二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的，不是完全二叉树的二叉树顺序存储时，要加“虚结点” 。数组中的第一个元素是根结点。本题中采用队列结构。 typedef struct BiTree bt： 二叉树结点指针 int B
22、um； tnode： Bum 是结点在一维数组中的编号 tnode Qmaxsize ； 循环队列，容量足够大 void creat(BiTree T，ElemType BT) 深度 h 的二叉树存于一维数组 BT12 h 一 1中 本算法生成该二叉树的二叉链表存储结构 tnode tq： tq 是队列元素 int len，i： 数组长度 len=strlen(BT)； T=(BiTree)malloc(sizeof(BiNode)； 申请结点 T 一data=BT1； 根结点数据 tqbt=T；tqnum=1 ； Q1：tq； 根入队列 front=0；rear=1 ； 循环队列头、尾指针
23、while(front!=rear) 当队列不空时循环 front=(front+1)maxsize； tq=Qfront；p=tq bt；i=tq num ； 出队，取出结点及编号 if(BT2*i=#|2*ilen) p-lchild=null； 左子树为空，# 表示虚结点 else 建立左子女结点并入队列 p 一lchild=(BiTree)malloc(sizeof(BiNode)； 申请结点空间 p 一lchild 一data=BT2*i ： 左子女数据 tqbt=p 一lchild ； tqBum=2*i ；rear=(rear+1)maxsize； 计算队尾位置 Qrear=tq； 左子女结点及其编号入队 if(BT2*i+1=#|2*i+llen)p 一rchild=null ； 右子树为空 else建立右子女结点并入队列 p 一rchild=(BiTree)malloc(sizeof(BiNode)；申请结点空间 p 一rchild 一data=BT2*i+1；tq bt=p 一rchild； tqBum=2*i+1 ； rear=(Fear+1) maxsize；Qrear=tq： 计算队尾位置，右子女及其编号入队 while 提示：本题中的虚结点用#表示，应根据二叉树的结点数据的类型而定。【知识模块】 树与二叉树
