二级MSOffice高级应用(新大纲)选择题题目、解析及答案(树、二叉树

1、二级MS OffiCe高级应用(新大纲)选择题题目、解析及答案(树、二叉树)1. 某二叉树有 5 个度为 2 的结点，则该二叉树中的叶子结点数是()。A ) 10B ) 8C ) 6D) 4 参考答案： C解析：二叉树中，叶子结点(度为 0的结点)是度为 2的结点个数加 1。2. 下列数据结构中，属于非线性结构的是( )。A) 循环队列B) 带链队列C) 二叉树D) 带链栈 参考答案： C 解析：队列、栈是线性结构；树是非线性结构。3. 下列叙述中正确的是( )。A) 有一个以上根结点的数据结构不一定是非线性结构B) 只有一个根结点的数据结构不一定是线性结构C) 循环链表是非线性结构D) 双向

2、链表是非线性结构 参考答案： B 解析：例如，只有一个根结点的树，其是非线性结构。4. 一棵二叉树共有 25个结点，其中 5 个是叶子结点，则度为 1的结点数为( )A) 16B) 10C) 6D) 4参考答案：A解析：在一棵二叉树中只有度为0、1、2三种结点。且二叉树中，叶子结点 （度为0的结点）是度为2的结点个数加1。所以，度为2的结点是4,度为1的结点 是 25-5-4=16。5. 某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假 设根结点在第1层）（）。A）3B）4C）6D）7参考答案：D解析：在一棵二叉树中只有度为 0、1、2三种结点。且二叉树中，叶子结 点（度为0

3、的结点）是度为2的结点个数加1。所以，度为2的结点是0,度为 1的结点是7-1-0=6。除叶结点外，每一个结点都有一个分支。每个结点在一层， 共7层，如下图所示：6. 对下列二叉树进行前序遍历的结果为（）A) DYBEAFCZXB）YDEBFZXCAC）ABDYECFXZD）ABCDEFXYZ 参考答案： C 解析：先（前）序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： 访问根结点； 遍历左子树； 遍历右子树。遍历过程发下：1：先访问根结点： A2:遍历A的左子树（递归调用）；2_1:先访问A的左子树的根结点：2_2:遍历B的左子树（递归调用）；2_2_1:先访问B的左子树的根结点

4、:2_2_2:遍历D的左子树（递归调用）2_2_3:遍历D的右子树（递归调用）2_2_3_1:遍历D的右子树的根结点: 溯。2_3:遍历B的右子树（递归调用）；2_3_1:先访问B的右子树的根结点: 溯。3:遍历A的右子树（递归调用）；BD, 没有左子树；Y;至此，B的左子树遍历完，向上回E;至此，B的右子树遍历完，向上回依次类推:7. 某二叉树的前序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出（同一层从左到右）的序列为（ ）。A）FEDCBAB）BCDEFAC）DEFABCD）ABCDEF参考答案：D解析：先（前）序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：访问根结

5、点；遍历左子树；遍历右子树。中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：遍历左子树；访问根结点遍历右子树。通过前序遍历和中序遍历可以确定一棵二叉树，（1）前序遍历确定根结点（2）中序遍历确定左、右子树（3）依次循环，直到确定整棵二叉树解题过程：1. 前序：ABCDEJF可知A是根结点；2. 中序：A右子树（BCDEF ；3. 对右子树BCDEF前序遍历：可知B是根结点；4. 中序：B右子树（CDEF ；依此类推：可知该树所有结点均在右子树上，且每一个父结点均只有右子树, 如下图所示。所以，答案选DO8. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF,贝U按层次输

6、出(同一层从左到右)的序列为()。A) ABCDEFB) CBAFEDC) DEFCBAD) FEDCBA参考答案：D解析：后序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：遍历左子树；遍历右子树；访问根结点。中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：遍历左子树；访问根结点遍历右子树。通过后序遍历和中序遍历可以确定一棵二叉树，(1) 后序遍历确定根结点(2) 中序遍历确定左、右子树(3) 依次循环，直到确定整棵二叉树解题过程：1. 后序：ABCDE,可知F是根结点；2. 中序：左子树（ABCDE F;3. 对左子树ABCDE后序遍历：可知E是根结点；4. 中序：左子树（

7、ABCD E；依此类推：可知该树所有结点均在左子树上，且每一个父结点均只有左子树, 如下图所示。9. 某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH亥完全叉树的前序序列为（）。A）ABCDEFGHB）ABDHECFGC）HDBEAFCGD）HDEBFGCA参考答案：B 解析：满二叉树：除最后一层无任何子 节点外，每一层上的所有结点都有两个子结点的完全二叉树：设二叉树的深度为h,除第h层外，其它各层（1h-1）的结点 数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉 树。示例见下图：若二叉树非空，则依次执行如下操作：访问根结点；遍历左子树；遍历右子树。则完全

8、二叉树的前序遍历为：1.根（A）- 1.1根（A）的左子树-1.2根（A）的右子树;1.1遍历根（A）的左子树：根（B）- 1.1.1根（B）的左子树-1.1.2 根（B） 的右子树；1.1.1遍历根（B）的左子树：根（D）- 1.1.1.1根（D）的左子树-1.1.1.2 根（D）的右子树；1.1.1.1遍历根（D）的左子树：根（H）- 根（H）的左子树为空-根（H）的 右子树为空；1.1.1.2遍历根（D）的右子树为空1.1.2遍历根（B）的右子树：根（E）- 根（ E的左子树为空-根（D）的右 子树为空；1.2遍历根（A）的右子树：根（C）- 1.2.1根（C）的左子树-1.2.2 根（

9、C） 的右子树；1.2.1遍历根（C）的左子树：根（F）- 根（ F）的左子树为空-根（F）的右 子树为空；I. 2.2遍历根（C）的右子树：根（G）- 根 （ Q的左子树为空-根（Q的右 子树为空；至此，前序遍历结束，依次访问到的结点为：ABDHECFG10. 设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子 树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树 的遍历结果为有序序列的是（）。A）中序序列B）前序序列C）后序序列D）前序序列或后序序列 参考答案：A前序遍历：访问根结点- 遍历左子树- 遍历右子树。中序遍历：遍历左子树- 访问根结点- 遍历右子

10、树。后序遍历：遍历左子树- 遍历右子树- 访问根结点。根据前面3种遍历特点可知，该排序树使用中序遍历为从小到大排序，符合要求。II. 在具有2n个结点的完全二叉树中，叶子结点个数为（）A) n/2B) n-1C) nD) n+1参考答案：C 解析:满二叉树：除最后一层无任何子 节点外，每一层上的所有结点都有两个子结点的h,除第h层外，其它各层（1h-1）的结点17数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉此处，依据完全二叉树的定义，设 n=1 ,画出2n=2个结点的完全二叉树如下图 所示:通过观察可知，叶子结点个数为1,即n个。12.某二叉树的中序遍历序列为 CBAD

11、E ,后序遍历序列为CBADE ,则前序遍历 序列为（）。A）CBADEB）CBEDAC）EDABCD）EDCBA参考答案：C解析：前序遍历：访问根结点- 遍历左子树- 遍历右子树。中序遍历：遍历左子树- 访问根结点- 遍历右子树。后序遍历：遍历左子树- 遍历右子树- 访问根结点。后序遍历确定根结点，中序遍历确定左右子树。贝1. 后序遍历序列为CBADE根结点为EO2. 中序遍历序列为CBADE有左子树（CBAD -根（E）-右子树（空）。2.1左子树（CBAD的后序遍历为：CBAD根结点为DO2.2左子树（CBAD的中序遍历为CBAD有左子树（CBA-根（D）-右子树（空）。2.2.1左子树

12、（CBA的后序遍历为：CBA,根结点为Ao2.2.2左子树（CBA的中序遍历为CBA有左子树（CB -根（A）-右子树（空）。2.2.2.1左子树（CB）的后序遍历为：CB,根结点为Bo2.2.2.2左子树（CB的中序遍历为CB有左子树（C）-根（B）-右子树（空）。 则此二叉树如下图所示：前序遍历：1.访问根结点E-2.遍历左子树2.1访问根结点D-2.2遍历左子树2.2.1访问根结点 A-2.2.2遍历左子树 2.2.2.1 访问根结点B-2.2.2.2 遍 历左子树 2.2.2.2.1 访问根结点C-2.2.2.2.2 遍历左子树（空）-2.2.2.2.3 遍历右子树（空） -2.2.2

13、.3 遍历右子树（空） -2.2.3 遍历右子树（空） -2.3遍历右子树（空）-3.遍历右子树（空）。13. 设一棵树的度为4,其中度为4, 3, 2, 1的结点个数分别为2, 3, 3, 0。 则该棵树中的叶子结点数为（）。A）16B）15C）17D）不可能有这样的树参考答案：A解析：结点的度：有根树T中，结点X的子女数目称为X的度。也就是：在树中，结点 有几个分叉，度就是几。树的度：有根树T中，结点的最大度数即为树的度。树中结点数=总分叉数+1。（这里的分叉数就是所有结点的度之和）树中结点数=4 2+3 3+2 3+1 0+ 仁8+9+6+ 仁24设叶子结点为X,则有：2+3+3+X=2

14、4所以X=1614. 某二叉树共有399个结点，其中有199个度为2的结点，则该二叉树中的叶 子结点数为（）。A）不存在这样的二叉树B）200C）198D）199参考答案：B解析：二叉树中，叶子结点（度为 0的结点）是度为2的结点个数加115. 下列叙述中错误的是（）。A）向量是线性结构B）非空线性结构中只有一个结点没有前件C）非空线性结构中只有一个结点没有后件D）只有一个根结点和一个叶子结点的结构必定是线性结构参考答案：D解析：如下所示二叉树只有一个根结点和一个叶子结点，其是非线性结构。16. 设某二叉树中共有140个结点，其中有40个度为1的结点。则（）A）该二叉树中有51个叶子结点B）该

15、二叉树中有50个叶子结点C）该二叉树中有51个度为2的结点D）不可能有这样的二叉树参考答案：D解析：二叉树中，叶子结点（度为0的结点）是度为2的结点个数加1。设度为2的结点个数为X,则叶子结点个数为X+1；40+X+X+1=1402X=99X=44.5显然没有这样的二叉树。17. 设二叉树的前序序列为 ABDEGHCFIJ中序序列为DBGEHACIFJ则按层次输 出（从上到下，同一层从左到右）的序列为（ ）。A）ABCDEFGHIJB）DGHEBIJFCAC）JIHGFEDCBAD）GHIJDEFBCA参考答案： A 解析：前序遍历：访问根结点 -遍历左子树 - 遍历右子树。 中序遍历：遍历左

16、子树 - 访问根结点 - 遍历右子树。 后序遍历：遍历左子树 - 遍历右子树 - 访问根结点。前序序列为ABDEGHCF,可知根为A。给定答案中只有选项A符合。18. 设二叉树的前序序列为 ABDEGHCFIJ中序序列为DBGEHACIFJ则后序序列 为（ ）。A）DGHEBIJFCAB）JIHGFEDCBAC）GHIJDEFBCAD）ABCDEFGHIJ 参考答案： A解析：前序遍历：访问根结点 -遍历左子树 - 遍历右子树。 中序遍历：遍历左子树 - 访问根结点 - 遍历右子树。 后序遍历：遍历左子树 - 遍历右子树 - 访问根结点。前序序列为ABDEGHCF，可知根为AO中序序列可知：左

17、子树（DBGE）-根（A）-右子树（CIFJ）O根据后序遍历的定义可知，只有选项A符合定义。19. 设某棵树的度为 3，其中度为 3,2,1 的结点个数分别为 3,0,4 。 则该树中的叶子结点数为（ ）。A）6B）7C）8D) 不可能有这样的树 参考答案： B解析：结点的度：有根树T中，结点X的子女数目称为X的度。也就是：在树中， 结点有几个分叉，度就是几。树的度：有根树T中，结点的最大度数即为树的度。树中结点数 = 总分叉数 +1。 (这里的总分叉数就是所有结点的度之和 ) 树中结点数 =3 3+2 0+14+1=9+4+1=14设叶子结点为X,则有：3+4+X=14所以X=720. 度为

18、 3的一棵树共有 30个结点，其中度为 3、1 的结点个数分别为 3、4。 则该树中的叶子结点数为( )。A) 14B) 15C) 16D) 不可能有这样的树 参考答案： B解析：结点的度：有根树T中，结点X的子女数目称为X的度。也就是：在树中， 结点有几个分叉，度就是几。树的度：有根树T中，结点的最大度数即为树的度。 树中结点数 = 总分叉数 +1 。 (这里的总分叉数就是所有结点的度之和 )设度为2的结点个数为X,树中结点数=3 3+2X+1 4+仁9+2X+4+1=30X=8设叶子结点为丫，则有：3+8+4+Y=30所以丫=1521. 设某棵树的度为 3，其中度为 3、1、0的结点个数分

19、别为 3、4、15。则该树 中总结点数为( )。A) 22B) 30C) 35D) 不可能有这样的树参考答案： B 解析：见上题。22. 某完全二叉树有 256 个结点，则该二叉树的深度为( )。A) 7B) 8C) 9D) 10参考答案： C解析：具有n个结点的完全二叉树的深度为匚log 2j +1。23. 设二叉树中有 20个叶子结点， 5个度为 1的结点，则该二叉树中总的结点数 为( )。A) 46B) 45C) 44D) 不可能有这样的二叉树参考答案： C解析：二叉树中度为 0 的结点(叶子结点)数是度为 2 的结点数 +1；所以度为 2 的结点数为 19；树中的总结点数为： 20+19+5=44。24. 树的度为 3，且有 9 个度为 3 的结点， 5个度为 1 的结点，但没有度为 2的 结点。则该树总的结点数为( )。A) 32B) 14C) 33D) 19参考答案： C解析：结点的度：有根树T中，结点X的子女数目称为X的度。也就是：在树中， 结点有几个分叉，度就是几。树的