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.349B.350C.255D.3513.深度为n的完全二叉树的叶子结点有__________A.nB.2nC.2nD. 2n-14.在一棵完全二叉树中，若编号为i的结点存在左子女，则左子女结点的编号为___C_____A.2iB.2i-1C.2i+1D.2i+25.在有n个结点的二叉树的二叉链表表示中，空指针数为（ b ）。
a.不定 b.n+1 c.n d.n-16.下列二叉树中，（ a ）可用于实现符号不等长高效编码。
a.最优二叉树 b.次优查找树 c.二叉平衡树 d.二叉排序树7．具有m个结点的二叉排序树，其最大深度为（ f ），最小深度为（ b ）。
a. log 2 m b. └ log2 m ┘ +1 c. m/2 d .┌ m/2 ┐ -1 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)⎤=⎡log269⎤=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．二叉树的度可以小于2C．每一个结点的度都为2 D．至少有一个结点的度为22．设深度为h(h>0)的二叉树中只有度为0和度为2的结点，则此二叉树中所含的结点总数至少为B。
(2)A．2h B．2h-1 C．2h+1 D．h+13．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为 (3) 。
(3)：A．3 B．4 C．5 D．64．若一棵完全二叉树中某结点无左孩子，则该结点一定是D。
A.度为1的结点 B．度为2的结点 C．分支结点 D．叶子结点5．深度为k的完全二叉树至多有C个结点，至少有B个结点。
A．2k-1-1 B．2k-1 C．2k-1 D．2k6．前序序列为ABC的不同二叉树有 (7) 种不同形态。
(7)：A．3 B．4 C．5 D．67．若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其后序序列为 (8) ，层次序列为 (9) 。
(8)-(9)：A．BCAGFED B．DAEBCFG C．ABCDEFG D．BCAEFGD8．在具有200个结点的完全二叉树中，设根结点的层次编号为1，则层次编号为60的结点，其左孩子结点的层次编号为 (10) ，右孩子结点的层次编号为 (11) ，双亲结点的层次编号为 (12)。
(10)-(12)：A．30 B．60 C．120 D．1219．遍历一棵具有n个结点的二叉树，在前序序列、中序序列和后序序列中所有叶子结点的相对次序 (13) 。
(13)：A.都不相同 B．完全相同 C．前序和中序相同 D．中序与后序相同10．在由4棵树组成的森林中，第一、第二、第三和第四棵树组成的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为（14），根结点的右子树中结点个数为 (15) 。
(14)—(15)：A．20 B．29 C．30 D．3511.具有n个结点(n>1)的二叉树的前序序列和后序序列正好相反，则该二叉树中除叶子结点外每个结点 (16) 。
(16)：A.仅有左孩子 B．仅有右孩子 C．仅有一个孩子 D．都有左、右孩子12．判断线索二叉树中p结点有右孩子的条件是 (17) 。
(17)：A.p!=NULL B．p->rchild!=NULL C．p->rtag=0 D．p->rtag=113．将一棵树转换成二叉树，树的前根序列与其对应的二叉树的 (18) 相等。
树的后根序列与其对应的二叉树的 (19)相同。
(18)—(19)：A．前序序列 B．中序序列 C．后序序列 D．层次序列14．设数据结构(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)<post(y)B．pre(x)<pre(y)且post(x)>post(y)C. pre(x)>pre(y)且post(x)<post(y)D．pre(x)>pre(y)且post(x)>post(y)16．每棵树都能惟一地转换成对应的二叉树，由树转换的二叉树中，一个结点N的左孩子是它在原树对应结点的 (23) ，而结点N的右孩子是它在原树里对应结点的 (24) 。
(23)—(24)：A．最左孩子 B．最右孩子 C．右邻兄弟 D．左邻兄弟17．二叉树在线索化后，仍不能有效求解的问题是 (25) 。
(25)：A．前序线索树中求前序直接后继结点B．中序线索树中求中序直接前驱结点C．中序线索树中求中序直接后继结点D．后序线索树中求后序直接后继结点18．一棵具有124个叶子结点的完全二叉树，最多有 (26)个结点。
(26)：A．247 B．248 C．249 D．250 。
19．实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最有效的存储结构是采用（27）。
(27)：A. 二叉链表 B．孩子链表 C．三叉链表 D．顺序表3．二叉树后序遍历的次序是什么？（）A 根、左子树、右子树B左子树、根、右子树C 左子树、右子树、根D根、右子树、左子树（）46．已知完全二叉树有26个结点，则整棵二叉树有多少个度为1的结点？（）A．1 B．0 C．2 D．不确定1．以下说法错误的是 ( )A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构⑤任何只含一个结点的集合是一棵树2，以下说法错误的是 ( )A.二叉树可以是空集B.二叉树的任一结点都有两棵子树C.二叉树与树具有相同的树形结构D.二叉树中任一结点的两棵子树有次序之分3、以下说法错误的是 ( )A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.在三叉链表上，二叉树的求双亲运算很容易实现C.在二叉链表上，求根，求左、右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好4、以下说法错误的是 ( )A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点D.若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树5．深度为6的二叉树最多有( )个结点 ( )A.64B.63C.32D.316．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为 ( )A.42B.40C.21D.207．任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 ( ) A.肯定发生变化 B.有时发生变化C.肯定不发生变化D.无法确定8．设二叉树有n个结点，则其深度为 ( )A.n-1B.nC.5floor(log2n)D.无法确定9．设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（）个A.k+1B.2kC.2k-1D.2k+110.下列说法正确的是 ( )A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同11．下列说法中正确的是 ( )A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中每个结点的度都为2C.任何一棵二叉树中的度肯定等于2D.任何一棵二叉树中的度可以小于212．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。
现采用（）遍历方式就可以得到这棵二叉树所有结点的递增序列。
A.先根B.中根C.后根D.层次13．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（）个结点。
A.n1-1B.n1C.n1+n2+n3D.n2+n3+n414．森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的左孩子上有（）个结点。
A.n1-1B.n1C.n1+n2+n3D.n2+n3+n415.对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A.0B.1C.2D.不存在这样的二叉树16．讨论树、森林和二叉树的关系，目的是为了（）A.借助二叉树上的运算方法去实现对树的一些运算B.将树、森林按二叉树的存储方式进行存储C.将树、森林转换成二叉树D.体现一种技巧，没有什么实际意义17．如图选择题17所示二叉树的中序遍历序列是（）A.abcdgefB. dfebagcC.dbaefcgD.defbagc18.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（）A.acbedB.deabcC.decabD.cedba19.如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的（）A.前序B.中序C.后序D.层次序20．如果T2是由有序树T转化而来的二叉树，那么T中结点的后序就是T2中结点的（）A.前序 B.中序 C.后序 D.层次序21．某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）A.bdgcefhaB.gdbecfhaC.D. bdgechfa D. gdbehfca22.在图选择题22中的二叉树中，（）不是完全二叉树。