1、计算机专业基础综合（树与二叉树）-试卷 2及答案解析(总分：70.00，做题时间：90 分钟)一、单项选择题(总题数：23，分数：46.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.设树 T的度为 4，其中度为 1、2、3 和 4的结点个数分别为 4、1、1、1，则 T中的叶子数为( )。（分数：2.00）A.10B.11C.9D.73.用下列元素序列(22，8，62，35，48)构造平衡二又树，当插入( )时，会出现不平衡的现象。（分数：2.00）A.22B.35C.48D.624.下面的算法实现了将二叉树中每一个结点的
2、左右子树互换。addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是( )。 typedef struct node int data； struct node*lchild，*rchild； btnode； void exchange(btnode*bt) btnode*p，*q； if(bt) addQ(Q，bt)； while(!EMPTY(Q) p=delQ(Q)； q=p-rchild；p 一rChild=p 一lchild； ( (1) )=q； if(p-lchild) ( (2) )： if(p-rchild)
3、addQ(Q，p-rchild)： （分数：2.00）A.p一lchild，delQ(Q，p-lchild)B.p-rchild，delQ(Q，p-lchild)C.p一lchild，addQ(Q，p-lchild)D.p-rchild，addQ(Q，p-lchild)5.已知有一棵二叉树，其高度为 n，并且有且只有 n个结点，那么二叉树的树形有( )种。（分数：2.00）A.nlog 2 nB.2 n+1C.2n一 1D.2 n-16.已知二叉排序树如下图所示，下列序列构造此二叉排序树不正确的是( )。 （分数：2.00）A.(105，85，90，65，120，110，138)B.(105，
4、120，110，138，85，65，90)C.(105，65，85，90，120，110，138)D.(105，85，65，90，120，138，110)7.已知某平衡二叉树含有在 15个结点，25 为其中的一个结点，如果在此平衡二叉树上查找关键字为 25的结点，下列比较的次序合理的是( )。（分数：2.00）A.29，35B.35，45，25C.45，15，35，25D.60，30，50，40，38，368.利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30要进行元素间的比较次数是( )。（分数：2.00）A.4B.5C.
5、6D.79.构建一个哈夫曼树，如果给定权值的个数为 n，那么哈夫曼树的结点总数为( )（分数：2.00）A.不确定B.2nC.2n+1D.2n-110.已知某哈夫曼树的度为 m，其中叶结点个数为 n，那么非叶结点的个数为( )。 （分数：2.00）A.B.C.D.11.一棵哈夫曼树共有 99个结点，对其进行哈夫曼编码，共能得到( )种不同的编码。（分数：2.00）A.48B.50C.99D.10012.一棵含有 n个结点的 k叉树，可能达到的最大深度为( )，最小深度为( )。（分数：2.00）A.n-k+1，log k n+1B.n，log k n+1C.n，log k n-1D.n-k+1
6、，log k n+113.已知一棵满 Z树的结点个数为 20到 40之间的素数，此二叉树的叶子结点有( )个。（分数：2.00）A.23B.29C.16D.3214.有( )棵不同的二叉树，其结点的前序序列为 a 1 ，a 2 ，a n 。 （分数：2.00）A.B.C.D.15.有 n个叶结点的非满的完全二叉树的高度为( )。（分数：2.00）A.2n+1B.2n-1C.10g 2 2n+1D.log 2 2n-116.在一棵二叉树中，单分支结点数为 30，双分支结点数为 15，则叶子结点数为( )。（分数：2.00）A.15B.16C.17D.4717.判断线索二叉树中某结点*p 有左孩子
7、的条件是( )。（分数：2.00）A.p-lchild=NULLB.p一lchild=0C.p-hag=0D.p-hag=118.在线索二叉树中，结点*p 没有左子树的充要条件是( )。（分数：2.00）A.p一lchild=NULLB.p一hag=1C.p-ltag=1 且 p-lchild=NULLD.以上都不对19.如果 T1是由有序树 T转换而来的二叉树，那么 T中结点的前序遍历序列就是 T1中结点的( )遍历序列。（分数：2.00）A.前序B.中序C.后序D.层次序20.在图中所示的 4棵二叉树中，( )不是完全二叉树。 （分数：2.00）A.图(a)B.图(b)C.图(c)D.图(
8、d)21.一棵二叉树如下图所示，其中序遍历序列为( )。 （分数：2.00）A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh22.有 n个叶子结点的哈夫曼树的结点总数为( )。（分数：2.00）A.不确定B.2nC.2n+1D.2n-123.如图所示的 T2是由森林 T1转换而来的二又树，那么森林 T1有( )个叶结点。 （分数：2.00）A.4B.5C.6D.7二、综合应用题(总题数：9，分数：24.00)24.综合应用题 41-47小题。_25.假定用两个一维数组 LN和 RN作为有 N个结点 1，2，N 的二叉树的存储结构。Li和 Ri分别指示结点 i的左
9、儿子和右儿子;Li=0(Ri=0)表示 i的左(右)儿子为空。试写一个算法，由 L和 R建立一个一维数组 Tn，使 Ti存放结点 i的父亲；然后再写一个判别结点 U是否为结点 V的后代的算法。（分数：2.00）_试找出分别满足下面条件的所有二叉树：（分数：8.00）(1).前序序列和中序序列相同。（分数：2.00）_(2).中序序列和后序序列相同。（分数：2.00）_(3).前序序列和后序序列相同。（分数：2.00）_(4).前序、中序、后序序列均相同。（分数：2.00）_26.假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树 BT中，写出计算该算术表达式值的算法。（分数：2.00）
10、_27.画出如下图所示的二叉树所对应的森林。 （分数：2.00）_28.下述编码中，哪一组不是前缀码? 00，01，10，11，0，1，00，11，0，10，110，111（分数：2.00）_假设用于通信的电文由字符集a，b，e，d，e，f，g，h中的字母构成，这 8个字母在电文中出现的概率分别为007，019，002，006，032，003，021，010。（分数：4.00）(1).为这 8个字母设计哈夫曼编码。（分数：2.00）_(2).若用三位二进制数(07)对这 8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?（分数：2.00）_29.有 n
11、个结点的完全二叉树存放在一维数组 A1n中，试据此建立一棵用二叉链表表示的二叉树，根由 tree指向。(可不定义结构体)（分数：2.00）_30.已知深度为 h的二叉树采用顺序存储结构已存放于数组 BT12 h -1中，请写一非递归算法，产生该二叉树的二又链表结构。设二又链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由 T给出。（分数：2.00）_计算机专业基础综合（树与二叉树）-试卷 2答案解析(总分：70.00，做题时间：90 分钟)一、单项选择题(总题数：23，分数：46.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最
12、符合题目要求的。（分数：2.00）_解析：2.设树 T的度为 4，其中度为 1、2、3 和 4的结点个数分别为 4、1、1、1，则 T中的叶子数为( )。（分数：2.00）A.10B.11C.9D.7 解析：解析：根据题中条件可知，14+21+3+4+1=4+1+1+1+n 0 ，由此可以得出：n 0 =14+21+3+4+1-(4+1+1+1)=14-7=7。3.用下列元素序列(22，8，62，35，48)构造平衡二又树，当插入( )时，会出现不平衡的现象。（分数：2.00）A.22B.35C.48 D.62解析：解析：由题中所给的结点序列构造二叉排序树的过程如下图：4.下面的算法实现了将二
13、叉树中每一个结点的左右子树互换。addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是( )。 typedef struct node int data； struct node*lchild，*rchild； btnode； void exchange(btnode*bt) btnode*p，*q； if(bt) addQ(Q，bt)； while(!EMPTY(Q) p=delQ(Q)； q=p-rchild；p 一rChild=p 一lchild； ( (1) )=q； if(p-lchild) ( (2) )： if(
14、p-rchild)addQ(Q，p-rchild)： （分数：2.00）A.p一lchild，delQ(Q，p-lchild)B.p-rchild，delQ(Q，p-lchild)C.p一lchild，addQ(Q，p-lchild) D.p-rchild，addQ(Q，p-lchild)解析：5.已知有一棵二叉树，其高度为 n，并且有且只有 n个结点，那么二叉树的树形有( )种。（分数：2.00）A.nlog 2 nB.2 n+1C.2n一 1D.2 n-1 解析：解析：由题可得，每层有一个结点，从根结点往下，每个结点都有做左孩子右孩子两种情况，由概率知识可得，二叉树共有 2 N-1 种树形
15、。6.已知二叉排序树如下图所示，下列序列构造此二叉排序树不正确的是( )。 （分数：2.00）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，90，120，138，110)解析：解析：将各选项中对应的二叉排序树画出即可得到答案。7.已知某平衡二叉树含有在 15个结点，25 为其中的一个结点，如果在此平衡二叉树上查找关键字为 25的结点，下列比较的次序合理的是( )。（分数：2.00）A.29，35B.35，45，25C.45，15，35，25 D.
16、60，30，50，40，38，36解析：解析：设 N h 表示深度为 h的平衡二叉树中含有的最少结点数，有：N 0 =0，N 1 =1，N 2 =2，N h =N h-1 +N h-2 +1，N 3 =4，N 4 =7，N 5 =12，N 6 =2015。也就是说，高度为 6的平衡二叉树最少有 20个结点，因此 15个结点的平衡二叉树的高度为 5，而最小叶子结点的层数为 3，所以选项D错误。而 A和 B的查找过程不能构成二叉排序树，因此 A、B 错误。8.利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30要进行元素间的比较次
17、数是( )。（分数：2.00）A.4B.5 C.6D.7解析：解析：利用逐点插入法建立二叉排序树是从空树开始，通过查找，将每个结点作为一个叶子插入。按题目中数据的输入次序建立的二叉排序树如下图所示，查找元素 30的比较次数为 5次。9.构建一个哈夫曼树，如果给定权值的个数为 n，那么哈夫曼树的结点总数为( )（分数：2.00）A.不确定B.2nC.2n+1D.2n-1 解析：解析：哈夫曼树中只有度为 0和度为 2的结点，即 N=n 0 +n 2 ，而根据二叉树的性质：n 0 =n 2 +1，可知 n 0 =n，那么 n 2 =n一 1，N=n+n1=2n 一 1。10.已知某哈夫曼树的度为 m
18、，其中叶结点个数为 n，那么非叶结点的个数为( )。 （分数：2.00）A.B.C. D.解析：解析：度为 m的结点个数为 n m 叶子结点个数为 n，mn m +1=n m +n，mn m =n m +n一 11.一棵哈夫曼树共有 99个结点，对其进行哈夫曼编码，共能得到( )种不同的编码。（分数：2.00）A.48B.50 C.99D.100解析：解析：本题考查哈夫曼树的性质。哈夫曼树中只有度为 2和度为 0的结点，哈夫曼编码是对哈夫曼树中的叶子结点编码。根据树的性质 N 0 =N 2 +1，故 N 0 =(N 2 +N 0 +1)2=(99+1)2=50，哈夫曼树共有 50个叶子结点，所
19、以共能得到 50个不同的码字。12.一棵含有 n个结点的 k叉树，可能达到的最大深度为( )，最小深度为( )。（分数：2.00）A.n-k+1，log k n+1 B.n，log k n+1C.n，log k n-1D.n-k+1，log k n+1解析：解析：当 k叉树种只有一个层的分支数为 n，其他层的分指数均为 1时，此时的树具有最大的深度为：n-k+1。 当该 k叉树为完全 k叉树时，其深度最小。参照二叉树的性质可知，其深度为：log 2 n1。13.已知一棵满 Z树的结点个数为 20到 40之间的素数，此二叉树的叶子结点有( )个。（分数：2.00）A.23B.29C.16 D.3
20、2解析：解析：一棵深度为 h的满二叉树的结点个数为 2 h 一 1，则有 202 h 一 140，即 212 h 41，h=5(总结点数=2 5 一 1=31，为素数)。满二叉树中叶子结点均集中在最底层，所以结点个数=2 5-1 =16个。14.有( )棵不同的二叉树，其结点的前序序列为 a 1 ，a 2 ，a n 。 （分数：2.00）A. B.C.D.解析：解析：这是一个变形的求 n个结点的互不相似的二叉树个数问题，设 T(n)表示含 n个结点的二又树个数，T(0)=T(1)=1，T(2)=2，T(n)=T(n 一 1)T(0)+T(n一 2)T(1)+T(0)T(n一 1)，而递归方程的
21、解为 T(n)=15.有 n个叶结点的非满的完全二叉树的高度为( )。（分数：2.00）A.2n+1 B.2n-1C.10g 2 2n+1D.log 2 2n-1解析：解析：设 j、k 分别为度为 1、2 的结点数目，则结点总数 m=n+j+k；由于是非满的，所以必有j=1，且 n=k+1，因此有 m=2n。设树的高度为 h，具有 n个结点的完全二叉树的深度为 log 2 n+1。本题中，树的结点个数为 2n，有 h=log 2 (2n)+1。所以，有 n个叶结点的非满的完全二叉树的高度为 log 2 (2n)+1。16.在一棵二叉树中，单分支结点数为 30，双分支结点数为 15，则叶子结点数
22、为( )。（分数：2.00）A.15B.16 C.17D.47解析：解析：由二叉树的性质可知：n 0 =n 2 +1=16。17.判断线索二叉树中某结点*p 有左孩子的条件是( )。（分数：2.00）A.p-lchild=NULLB.p一lchild=0C.p-hag=0 D.p-hag=1解析：解析：有左孩子表示不是线索，即 p一ltag=0。18.在线索二叉树中，结点*p 没有左子树的充要条件是( )。（分数：2.00）A.p一lchild=NULLB.p一hag=1 C.p-ltag=1 且 p-lchild=NULLD.以上都不对解析：解析：没有左孩子时指针域指向线索，即 p一ltag
23、=1。19.如果 T1是由有序树 T转换而来的二叉树，那么 T中结点的前序遍历序列就是 T1中结点的( )遍历序列。（分数：2.00）A.前序 B.中序C.后序D.层次序解析：解析：由树转换为二叉树的过程可知本题答案应为 A。20.在图中所示的 4棵二叉树中，( )不是完全二叉树。 （分数：2.00）A.图(a)B.图(b)C.图(c) D.图(d)解析：解析：由完全二叉树的定义可知(c)不是完全二叉树。21.一棵二叉树如下图所示，其中序遍历序列为( )。 （分数：2.00）A.abdgcefhB.dgbaechf C.gdbehfcaD.abcdefgh解析：解析：由中序遍历过程可知本题答案
24、应为 B。22.有 n个叶子结点的哈夫曼树的结点总数为( )。（分数：2.00）A.不确定B.2nC.2n+1D.2n-1 解析：解析：在哈夫曼树中，由计算公式可计算得结点总数为 2n一 1，所以选 D。23.如图所示的 T2是由森林 T1转换而来的二又树，那么森林 T1有( )个叶结点。 （分数：2.00）A.4B.5C.6 D.7解析：解析：T2 对应的森林 T1如下图所示，由图中可以看出，所有的叶子结点总数为 6。二、综合应用题(总题数：9，分数：24.00)24.综合应用题 41-47小题。_解析：25.假定用两个一维数组 LN和 RN作为有 N个结点 1，2，N 的二叉树的存储结构。
25、Li和 Ri分别指示结点 i的左儿子和右儿子;Li=0(Ri=0)表示 i的左(右)儿子为空。试写一个算法，由 L和 R建立一个一维数组 Tn，使 Ti存放结点 i的父亲；然后再写一个判别结点 U是否为结点 V的后代的算法。（分数：2.00）_正确答案：(正确答案：由指示结点 i左儿子和右儿子的两个一维数组 Li和 Ri，很容易建立指示结点i的双亲的一维数组 Ti，根据 T数组，判断结点 U是否是结点 V后代的算法转为判断结点 V是否是结点U的祖先的问题。 int Generation(int u，V，N，L，R，T) L和 R是含有 N个元素且指示二叉树结点 i左儿子和右儿子的一维数组 本算
26、法据此建立结点 i的双亲数组 T，并判断结点 U是否是结点 V的后代 int i； for(i=1；ilchild)； 求左子树表示的子表达式的值 rv=PostEval(bt 一rchild)； 求右子树表示的子表达式的值 switch(bt-optr) case+：value=lv+rv；break； case一：value=lvrv；break； case*。：value=lv 水 n，：break； case “：value=lvrv： return(value)； )解析：27.画出如下图所示的二叉树所对应的森林。 （分数：2.00）_正确答案：(正确答案：该二叉树所对应的森林如下图
27、所示，它由四棵树组成。 )解析：28.下述编码中，哪一组不是前缀码? 00，01，10，11，0，1，00，11，0，10，110，111（分数：2.00）_正确答案：(正确答案：在0，1，00，11中，由于 0、1 分别是 00、11 的前缀，所以它不是前缀码。)解析：假设用于通信的电文由字符集a，b，e，d，e，f，g，h中的字母构成，这 8个字母在电文中出现的概率分别为007，019，002，006，032，003，021，010。（分数：4.00）(1).为这 8个字母设计哈夫曼编码。（分数：2.00）_正确答案：(正确答案：对应的哈夫曼树如下图所示。各字母的哈夫曼编码如下： a：10
28、10，b：00，C：10000，d：1001，e：11，f：10001，g：01，h：1011 )解析：(2).若用三位二进制数(07)对这 8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?（分数：2.00）_正确答案：(正确答案：哈夫曼编码的平均码长为： 0025+0035+0064+0074+014+0322+0192+0212=261 2613=087，它是等长编码的 87，它使电文总长平均压缩 13。)解析：29.有 n个结点的完全二叉树存放在一维数组 A1n中，试据此建立一棵用二叉链表表示的二叉树，根由 tree指向。(可不定义结构体)（分
29、数：2.00）_正确答案：(正确答案：BiTree Creat(ElemType A，int i) n 个结点的完全二叉树存于一维数组A中，本算法 据此建立以二叉链表表示的完全二叉树 BiTree tree； if(idata=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)解析：30.已知深度为 h的二叉树采用顺序存储结构已存放于数组 BT12 h -1中
30、，请写一非递归算法，产生该二叉树的二又链表结构。设二又链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由 T给出。（分数：2.00）_正确答案：(正确答案：二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的，不是完全二叉树的二叉树顺序存储时，要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。 typedef struct BiTree bt： -叉树结点指针 int num； tnode： aura 是结点在一维数组中的编号 tnode Qmaxsize； 循环队列，容量足够大 void creat(BiTree T，ElemType
31、 BT) 深度 h m-Y-树存于一维数组 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； 循环队列头、尾指针 while(front!=rear) 当队列不空时循环 front=(front+1)maxsize； tq=Qfront；P=tqbt；i=tqhum； 出队，取出结点及
32、编号 if(BT2*i=“#“2*ilen) p 一lehild=null； 左子树为空，“#“表示虚结点 else 建立左子女结点并入队列 p 一lchild=(BiTree)malloc(sizeof(BiNode)； 申请结点空间 P 一lchild 一data=BT2*i； 左子女数据 tqbt=p 一lehild：tqhum=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；tqbt=p-rchild；tqnum=2*i+l； rear=(rear+1)maxsize；Qrear=tq；计算队尾位置，右子女及其编号入队 while )解析：
