填空选择题库(抓紧看)

1、6选4填*20套一、选择题（单选）1-1. 完全二叉树_B_二叉树。A.一定是满 B.可能是满 C.不是 D.一定不是满答案：B 难度：易1-2满二叉树_A_二叉树。A.一定是完全 B.可能是完全 C.不是 D.一定不是完全 答案：A 难度：易1-3完全二叉树中，若某个结点没有左孩子，则它_C_。 A. 有2个右孩子 B. 一定有右孩子 C. 一定没有右孩子 D. 不一定有右孩子 答案：C 难度：中2. 设一个完全二叉树共有699个结点，则在该二叉树中的叶子结点数为_。A.349 B.350 C.255 D.3513.深度为n的完全二叉树的叶子结点有_A.n B.2n C.2n D. 2n-1

2、4.在一棵完全二叉树中，若编号为i的结点存在左子女，则左子女结点的编号为_C_A.2i B.2i-1 C.2i+1 D.2i+2 5.在有n个结点的二叉树的二叉链表表示中，空指针数为（ b ）。    a.不定         b.n+1          c.n            d.n-1

3、6.下列二叉树中，（ a    ）可用于实现符号不等长高效编码。 a.最优二叉树      b.次优查找树      c.二叉平衡树 d.二叉排序树7具有m个结点的二叉排序树，其最大深度为（ f ），最小深度为（ b ）。 a. log 2 m        b. log2 m +1     c. m/2 d . m/2 -1  

4、0;  e. m/2     一、单项选择题(1)-(5)BBCDC (6)-(10)BCABC (11)(15)DABBD (16)-(19)CCABB(20)-(24) BBBAC (25)-(27)DBC二、填空题（1）有零个或多个 （2）有且仅有一个（3）根据树的广义表表示，可以画出这棵村，该树的度为4。（4）树的深度为4(5)树中叶子结点个数为8（6）n0=14 (7)n-2m+1 (8)2k-1 (9)2i-1 (10)133 (11)59(12)25=32 (13)élog2(n+1)ù=élog26

5、9ù=7 (14) 25-1+6=37 (15) 19(16)27-1-20=107 (17)右 （18）m+1 (19)n+1 (20) 2m-1 (21)中序 （22）直接前驱结点 （23）直接后继结点1关于二叉树的下列说法正确的是 B 。 (1)：A二叉树的度为2 B二叉树的度可以小于2 C每一个结点的度都为2 D至少有一个结点的度为2 2设深度为h(h>0)的二叉树中只有度为0和度为2的结点，则此二叉树中所含的结点总数至少为 B 。 (2)A2h B2h-1 C2h+1 Dh+1 3在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为 (3) 。 (3)：A3 B4

6、 C5 D6 4若一棵完全二叉树中某结点无左孩子，则该结点一定是 D 。 A.度为1的结点 B度为2的结点 C分支结点 D叶子结点 5深度为k的完全二叉树至多有 C 个结点，至少有 B 个结点。 A2k-1-1 B2k-1 C2k-1 D2k 6前序序列为ABC的不同二叉树有 (7) 种不同形态。 (7)：A3 B4 C5 D6 7若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其后序序列为 (8) ，层次序列为 (9) 。 (8)-(9)：ABCAGFED BDAEBCFG CABCDEFG DBCAEFGD 8在具有200个结点的完全二叉树中，设根结点的层次编号为1，则层次

7、编号为60的结点，其左孩子结点的层次编号为 (10) ，右孩子结点的层次编号为 (11) ，双亲结点的层次编号为 (12)。 (10)-(12)：A30 B60 C120 D121 9遍历一棵具有n个结点的二叉树，在前序序列、中序序列和后序序列中所有叶子结点的相对次序 (13) 。 (13)：A.都不相同 B完全相同 C前序和中序相同 D中序与后序相同 10在由4棵树组成的森林中，第一、第二、第三和第四棵树组成的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为 （14） ，根结点的右子树中结点个数为 (15) 。 (14)(15)：A20 B

8、29 C30 D35 11.具有n个结点(n>1)的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子结点外每个结点 (16) 。 (16)：A.仅有左孩子 B仅有右孩子 C仅有一个孩子 D都有左、右孩子 12判断线索二叉树中p结点有右孩子的条件是 (17) 。 (17)：A.p!=NULL Bp->rchild!=NULL Cp->rtag=0 Dp->rtag=1 13将一棵树转换成二叉树，树的前根序列与其对应的二叉树的 (18) 相等。树的后根序列与其对应的二叉树的 (19)相同。(18)(19)：A前序序列 B中序序列 C后序序列 D层次序列14设数据结构(

9、D，R)，D=dl，d2，d3，d4，d5，d6，R=<d4，d2>，<d2，d1>，<d2，d3>，<d4，d6>，<d6，d5>，这个结构的图形是 (20) ；用 (21) 遍历方法可以得到序列d1，d2，d3，d4，d5，d6。 (20)：A线性表 B二叉树C队列 D栈 (21)：人前序 B中序 C后序 D层次 15对于树中任一结点x，在前根序列中序号为pre(x)，在后根序列中序号为post(x)，若树中结点x是结点y的祖先，下列 （22） 条件是正确的。 (22)：A.pre(x)<pre(y)且post(x)<

10、post(y) Bpre(x)<pre(y)且post(x)>post(y) C. pre(x)>pre(y)且post(x)<post(y) Dpre(x)>pre(y)且post(x)>post(y) 16每棵树都能惟一地转换成对应的二叉树，由树转换的二叉树中，一个结点N的左孩子是它在原树对应结点的 (23) ，而结点N的右孩子是它在原树里对应结点的 (24) 。 (23)(24)：A最左孩子 B最右孩子 C右邻兄弟 D左邻兄弟17二叉树在线索化后，仍不能有效求解的问题是 (25) 。(25)：A前序线索树中求前序直接后继结点 B中序线索树中求中序直接前

11、驱结点 C中序线索树中求中序直接后继结点 D后序线索树中求后序直接后继结点 18一棵具有124个叶子结点的完全二叉树，最多有 (26)个结点。 (26)：A247 B248 C249 D250 。 19实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最有效的存储结构是采用 （27） 。 (27)：A. 二叉链表 B孩子链表 C三叉链表 D顺序表3二叉树后序遍历的次序是什么？ （ ）A 根、左子树、右子树 B左子树、根、右子树C 左子树、右子树、根 D根、右子树、左子树FEDBAC4已给如图二叉树，它的中序遍历是哪一项？ （ ）AABECDF BABCDEF CCBDAEF DCDBFEA6

12、已知完全二叉树有26个结点，则整棵二叉树有多少个度为1的结点？ （ ）A1 B0 C2 D不确定1 以下说法错误的是 ( )A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构任何只含一个结点的集合是一棵树2，以下说法错误的是 ( ) A.二叉树可以是空集B.二叉树的任一结点都有两棵子树C.二叉树与树具有相同的树形结构D.二叉树中任一结点的两棵子树有次序之分3、以下说法错误的是 ( )A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在

13、三叉链表上，二叉树的求双亲运算很容易实现C.在二叉链表上，求根，求左、右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好4、以下说法错误的是 ( ) A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点D.若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树5深度为6的二叉树最多有( )个结点 ( )A.64 B.63 C.32 D.316将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为

14、 ( )A.42 B.40 C.21 D.207任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 ( ) A.肯定发生变化 B.有时发生变化C.肯定不发生变化 D.无法确定8设二叉树有n个结点，则其深度为 ( )A.n-1 B.n C.5floor(log2n) D.无法确定9设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（ ）个A.k+1 B.2k C.2k-1 D.2k+110.下列说法正确的是 ( )A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同C.树的后根遍历序列与其对应的二叉树的

15、先根遍历序列相同D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同11下列说法中正确的是 ( )A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中每个结点的度都为2C.任何一棵二叉树中的度肯定等于2D.任何一棵二叉树中的度可以小于212一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（ ）遍历方式就可以得到这棵二叉树所有结点的递增序列。A.先根 B.中根 C.后根 D.层次13设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右

16、子树上有（ ）个结点。A.n1-1 B.n1 C.n1+n2+n3 D.n2+n3+n4 14森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的左孩子上有（ ）个结点。A.n1-1 B.n1 C.n1+n2+n3 D.n2+n3+n415.对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A.0 B.1 C.2 D.不存在这样的二叉树16讨论树、森林和二叉树的关系，目的是为了（ ）A.借助二叉树上的运算方法去实现对树的一些运算B.将树、森林按二叉树的存储方式进行存储C.将树、森林转换成二叉树D.体

17、现一种技巧，没有什么实际意义 17如图选择题17所示二叉树的中序遍历序列是（ ）A.abcdgef B. dfebagc C.dbaefcg D.defbagc18.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ ）A.acbed B.deabc C.decab D.cedba19.如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的（ ）A.前序 B.中序 C.后序 D.层次序20如果T2是由有序树T转化而来的二叉树，那么T中结点的后序就是T2中结点的（ ）A.前序 B.中序 C.后序 D.层次序21某二叉树的前序遍历结点访问顺序是

18、abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是 （ ）A.bdgcefha B.gdbecfha C.D. bdgechfa D. gdbehfca22.在图选择题22中的二叉树中，（ ）不是完全二叉树。 23、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 ( )A.正确 B.错误24、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 ( )A.五确 B.错误25，二叉树是每个结点的度不超过2的有序树的特殊情况，这种说法 ( )A.正确 B.错误26·树最适合用来表示 ( )A.有序数据元素 B.无

19、序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据27，深度为5的二叉树至多有( )个结点。A.16 B.32 C.31 D.1028、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（ ）数据结构A.栈 B.树 C.双向队列 D.顺序表29.堆(Heap)是 ( )A.完全二叉树 B.线性表 C.满二叉树30、下列说法中正确的是 ( )A.二叉树中任何一个结点的度都为2 B.二叉树的度为2C.任何一棵二叉树中至少有一个结点的度为2 D.一棵二叉树的度可以小于231、设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是（ ）A.2h B.2h-1 C.2

20、h-1 D.2h+1-132、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )A.都不相同 B.完全相同 C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同33·以下说法错误的是 ( )A.存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同B.二叉树是树的特殊情形C.由树转换成二叉树，其根结点的右子树总是空的D.在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树34、以下说法正确的是 ( )A.先根遍历树和前序遍历与该树对应的二叉树，其结果不同B.后根遍历树和前序遍历与该树对应的二叉树，其结果不同C.前序遍历森林和前

21、序遍历与该森林对应的二叉树，其结果相同D.后序遍历森林和中序遍历与该森林对应的二叉树，其结果不同35·以下说法正确的是 ( )A.一般来说，若深度为k的n个结点的二叉树具有最小路径长度，那么从根结点到第k-1层具有最多的结点数为2k-1-1余下的n-2k-1+1个结点在第k层的任一位置上B.若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。C.若一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序遍历序列中的最后一个结点。D.在二叉树中插人结点，该二叉树便不再是二叉树36、以下说法正确的是 ( )A.若一个树

22、叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。B.若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序离历序列中的最后一个结点C.二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。D.在二叉树中，具有一个子女结点，在中序遍历序列中，它没有后继子女结点。37、以下说法错误的是 ( )A.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。B.若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。C.已知二叉树的前序遍历和后序遍历序列并

23、不能惟一地确定这棵树，因为不知道树的根结点是哪一个。D.在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。6.深度为6(根的层次为1)的二叉树至多有（D ）结点。 A) 64     B) 32        C) 31      D) 637.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次堆结点编号，根结点的编号为1。编号为49的结点X的双亲的编号为（ A ）。 A) 24  

24、60;     B) 25        C) 23       D) 无法确定15.设深度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（ C ）。 A) k + 1      B) 2k        C) 2k - 1     D) 2k + 15.&

25、#160;    树最适合用来表示( C )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据6.     二叉树的第k层的结点数最多为( D ). A2k-1 B.2K+1 C.2K-1 D. 2k-14、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ） A 24 B 71 C 48 D 5310在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( C ) A4 B5 C6 D74二叉树中第i(i1

26、)层上的结点数最多有（ C ）个。(A) 2i(B) 2i(C) 2i-1(D) 2i-19根据二叉树的定义可知二叉树共有（ B ）种不同的形态。(A) 4(B) 5(C) 6(D) 72设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B ）个空指针域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m4设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA6设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。(A) 9(B) 1

27、0(C) 11(D) 126设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为（ B ）。(A) O(1)(B) O(log2n)(C)(D) O(n2)2设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。(A) 2k-1(B) 2k(C) 2k-1(D) 2k-19设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ C ）。(A) N0=N1+1(B) N0=Nl+N2(C) N0=N2+1(D) N0=2N1+l6设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为m的结点数为Nm，则N0=（ B ）。(

28、A) Nl+N2+Nm(B) l+N2+2N3+3N4+(m-1)Nm(C) N2+2N3+3N4+(m-1)Nm(D) 2Nl+3N2+(m+1)Nm5设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ D ）。(A) 空或只有一个结点(B) 高度等于其结点数(C) 任一结点无左孩子(D) 任一结点无右孩子7设某棵三叉树中有40个结点，则该三叉树的最小高度为（ B ）。(A) 3(B) 4(C) 5(D) 610. 深度为k的完全二叉树中最少有（ B ）个结点。(A) 2k-1-1(B) 2k-1(C) 2k-1+1(D) 2k-114.设二叉排序树上有n个结点，则在二叉

29、排序树上查找结点的平均时间复杂度为（ D ）。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)5设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ B ）。(A) 2i+1(B) 2i(C) i/2(D) 2i-18设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ C ）。(A) 20(B) 256(C) 512(D) 10245.        在二叉排序树中插入一个关键字值的平均时间复杂度为（ B ）。(A) O(n)(B) O(

30、1og2n)(C) O(nlog2n)(D) O(n2)7.        设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ B ）。(A) 8(B) 7(C) 6(D) 58.        设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（ C ）个度数为0的结点。(A) 5(B) 6(C) 7(D) 83设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N

31、1、N2和N3，则二叉树B的根结点的左子树的结点数为（ A ）。 (A) N1-1(B) N2-1(C) N2+N3(D) N1+N39设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（ C ）个。(A) 4(B) 5(C) 6(D) 76设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，Nm个度数为m的结点，则该树中共有（ D ）个叶子结点。(A) (B) (C) (D) 7. 二叉排序树中左子树上所有结点的值均（ A ）根结点的值。(A) <(B) >(C) =(D) !=8. 设一组权值集合W=(

32、15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ D ）。(A) 129(B) 219(C) 189(D) 22910.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（ C ）个结点。(A) 2n(B) n+l(C) 2n-1(D) 2n+l 1假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点 数为_。A15 B16 C17 D47 答案：B2假定一棵二叉树的结点数为18个，则它的最小高度_。A4 B5 C6 D18 答案：B3在一棵二叉树中第五层上的结点数最多为_。A

33、8 B15 C16 D32 答案：C4在一棵具有五层的满二叉树中，结点总数为_。A31 B32 C33 D16 答案：A5已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为_。A1 B2 C3 D4 答案：B6 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_。A23 B37 C44 D46 答案：C7、在树中除根结点外，其余结点分成m(m0)个_的集合T1,T2,T3.Tm,每个 集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1im)。A互不相交 B可以相交

34、C叶结点可以相交 D树枝结点可以相交 答案：A8、下面答案_是查找二叉树（又称二叉排序树）。A二叉树中的每个结点的两棵子树的高度差的绝对值不大于。B二叉树中的每个结点的两棵子树的高度差等于。C二叉树中的每个结点的两棵子树是有序的。D二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值，且小于其右子树（如果存在）所有结点的关键字值。答案：D9、如果结点A有三个兄弟，而且B是A的双亲，则B的出度是_。A3 B4 C5 D1 答案：B10、一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每 个结点都有K棵非空子树。如果按层次顺序从开始对全部结点编号，编号为n的

35、有右兄弟的条件是_。A(n-1) % k= =0 B(n-1) % k!=0 Cn % k= =0 Dn % k!=0 答案：B11、在完全二叉树中，当i为奇数且不等于时，结点i的左兄弟是结点_，否则没有左兄弟。A2i-1 Bi+1 C2i+1 Di-1 答案：D12、某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按_编号。A中序遍历序列 B前序遍历序列 C后序遍历序列 D层次遍历序列 答案：B13、最小代价生成树_。A是唯

36、一的。 B不是唯一的。 C唯一性不确定。 D唯一性与原因的边的权数有关。 答案：D14、将递归算法转换成对应的非递归算法时,通常需要使用_。A栈 B队列 C链表 D树 答案：A6、在二叉树的第4层上至多有多少个结点： A. 10个 B. 8个 C. 16个 D. 以上都不是。 答案：B7、若一棵二叉树具有8个度为2的结点，则该二叉树的叶子个数是（ ）A. 9 B. 11 C. 7 D. 不确定 答案：A6、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加( )。A. 2 B. -1 C. 0 D. 1 答案：D9、某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则

37、后序遍历的结果为（ ）。A. DBFEAC B. DFEBCAC. BDFECA D. BDEFAC 答案：B1. 非线性结构是数据元素之间存在一种： A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系. 答案：（ B ）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有_个非空指针域。A. n B. n-1 C. n+1 D. n+2 答案：B 3. 二叉树中每个结点的两棵子树是_的。 A. 有序 B. 无序 C. 不确定 D.相同 答案：A9. 用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个空指针。A. n B.

38、n+2 C. n+1 D. n-1 答案：D 1 不含任何结点的空树 。 ）是一棵树; ）是一棵二叉树; ）是一棵树也是一棵二叉树; ）既不是树也不是二叉树 答案：C 2二叉树是非线性数据结构，所以 。 ）它不能用顺序存储结构存储; ）它不能用链式存储结构存储; ）顺序存储结构和链式存储结构都能存储; ）顺序存储结构和链式存储结构都不能使用 答案：C 4把一棵树转换为二叉树后，这棵二叉树的形态是 。 ）唯一的 ）有多种 ）有多种，但根结点都没有左孩子 ）有多种，但根结点都没有右孩子 答案：A 二、填空题7.        二

39、叉树是指度为2的_有序_树。一棵结点数为n的二叉树，其所有结点的度的总和是_n-1_。9.        对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_2n _个，其中_n-1_个用于指向孩子，_n+1_个指针是空闲的。10.    若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A0中。其余类推，则A i 元素的左孩子元素为_2i+1_,右孩子元素为_2i+2_，双亲元素为_(i-1)/2_。3.  &#

40、160;      设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_n_次。5.         设一棵m叉树脂的结点数为n，用多重链表表示其存储结构，则该树中有_ n(m-1)+1_个空指针域。13.     下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedef struct nodeint data;struct node *lchild;_ struct node *rchild

41、 _ _;bitree;void createbitree(bitree *&bt)scanf(“%c”,&ch);if(ch='#') _ bt=0_;else bt=(bitree*)malloc(sizeof(bitree); bt->data=ch;_createbitree(bt->lchild _;createbitree(bt->rchild);2       设某棵完全二叉树中有100个结点，则该二叉树中有_50 _个叶子结点。7   &#

42、160;   设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为_ CBDA _。5   设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为_ CABD _。6   完全二叉树中第5层上最少有_1_个结点，最多有_16_个结点。5.        设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有_14_个。6.    &

43、#160;   高度为h的完全二叉树中最少有_2h-1_个结点，最多有_2h-1_个结点。9.        设一棵二叉树的前序序列为ABC，则有_5_种不同的二叉树可以得到这种序列。5设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_129_个结点数。7设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_ p->lchild=0&&p->rchild=0_。5.  

44、0;      设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为_ ABDECF_，中序遍历序列为_DBEAFC_，后序遍历序列为_DEBFCA _。6.         设一棵完全二叉树有128个结点，则该完全二叉树的深度为_8_，有_64 _个叶子结点。3    根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为_3_。4    深度为k的完

45、全二叉树中最少有_2k-1_个结点。6    设哈夫曼树中共有99个结点，则该树中有_50_个叶子结点；若采用二叉链表作为存储结构，则该树中有_51_个空指针域。5.         设哈夫曼树中共有n个结点，则该哈夫曼树中有_0_个度数为1的结点。7.         _中序 _遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。10.    

46、 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为_i/2_，右孩子结点的编号为_2i+1_。3.         中序遍历二叉排序树所得到的序列是_有序_序列（填有序或无序）。5.         设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_ N0-1_；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_2N0+N1_个空指针域

47、。3.        设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有_2n_个指针域，_n+1_个空指针域。7.        设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为_CBA_。8.        设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是_4_，编号为

48、8的左孩子结点的编号是_16_。21已知一棵完全二叉树中共有768结点，则该树中共有 384 个叶子结点。1.在一棵高度为h的完全二又树中，最少含有_2h_个结点假定树根结点的高 度为O2.将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。 typedef struct node int data ; struct node *lchild, *rchild; btnode; void  EXCHANGE(btnode *bt) btnode *

49、p, *q;  if (bt)ADDQ(Q,bt);          while(!EMPTY(Q)           p=DELQ(Q);  q=(1)_; p->rchild=(2)_; (3)_=q; if(p->lchild) (4)_; if(p->rchild) (5)_; 3已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。 其后序遍历次序为ed cgbfa。层次遍历次序为afbcgde。4请在下划线上填入适