点击查看：2015年计算机二级公共基础知识考点测试题汇总

　　树与二叉树

　　1[单选题]在深度为7的满二叉树中，叶子结点的个数为(　　)

　　A.32B.31C.64D.63

　　参考答案：C

　　参考解析：在满二叉树中每层的结点数都达到最大值， 而且叶子结点全部出现在最底层。第1层(根结点所在的层)有20个结点，第2层有21个结点，……第n层有2n-1个结点。在深度为7的满二叉树中，第7层有2 7-1=64个结点(全部是叶子结点)、在深度为7的满二叉树中，共有2^(7-1)=64个结点、因此本题的正确答案是C。

　　2[单选题]翻某二叉树有5个度为2的结点，则该项树中的叶子结点数是(　　)。

　　A.10B.8C.6D.4

　　参考答案：C

　　参考解析：根据二叉树的性质，在任意二叉树中，度为0的结点(即叶子结点)数总是比度为2的结点数多一个。

　　3[单选题]具有8个结点的完全二叉树中编号为4的结点的右子结点的编号为(　　)

　　A.8B.9C.无此结点D.8或是9

　　参考答案：C

　　4[单选题]某二又树中有n个度为2的结点，则该二叉树中的叶子结点为(　　)

　　A.n+1B.n-1C.2nD.n/2

　　参考答案：A

　　参考解析：二叉树具有这样一个性质：在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。所以某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为n+1。因此本题的正确答案是A。

　　5[单选题]在表示树的多重链表中，除了要存储结点的值和多个指针之外，还必须需要存储(　　)

　　A.结点的度

　　B.结点的层次

　　C.结点的高度

　　D.结点的深度

　　参考答案：A

　　6[单选题]一棵二叉树中共有70个叶子结点与80个度为1的结点，该二叉树中的总结点数为(　　)。

　　参考答案：A

　　参考解析：二叉树具有这样一个性质：在任意一颗二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。本题告知，叶子结点有70个，那度为2的结点就有69个，度为l的结点有80个，这颗二叉树共有70+69+80=219个结点。因此本题的正确答案是A。

　　7[单选题]下列数据结构中，能用二分法进行查找的是(　　)

　　A.顺序存储的有序线性表B.线性链表C.二叉链表D.有序线性链表

　　参考答案：A

　　参考解析：二分法又叫折半(对分)查找法，只适合于顺序存储的有序表(是指线性表中的元 素按值非递减排列)。二分法的基本思想是：设有序线性表的长度为n，被查元素为X，则二分查找的方法如下：

　　将X与线性表的中间项进行比较：若中间项的值等于x，则说明找到，查找结束;若x小于中间项的值，则在线性表的前半部分(即中间项以前的部分)以相同的方法进行查找;若X大于中间项的值，则在线性表的后半部分(即中间项以后的部分)以相同的方法进行查找、这个过程-直进行到查找成功或于表长度为0,(说明线性表中没有这个元素为止)顺序存储的线性袁在计算机中-般用一个-维数组来表示，在数组中我们可以通过数组名和下标来对数组中的任意一个元素进行访问，而在链表(不管是有序还是无序)中，要对元 素进行访问必须从表头结点开始， 顺着链条一个一个结点进行搜索，因此选项A正确。

　　8[单选题]对右图二叉树进行前序遍历的结果为(　　)。

　　参考答案：C

　　参考解析：前序遍历(DLR)的基本思想是：先访问根结点，后前序遍历dzq-树，再前序遍历右子树。本题根结点是A，前序遍历左子树得到的序列为BDYE，前序遍历右子树得到的序列为CFXZ，所以对本题二叉树进行前序遍历的结果为ABDYECFXZ。因此本题的正确答案是C。

　　9[单选题]某二又树中有n个度为2的结点，则该二叉树中的叶子结点为(　　)。

　　参考答案：A

　　参考解析：二叉树具有这样一个性质：在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。所以某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为n+1。因此本题的正确答案是A。

　　10[填空题]深度为5的满二叉树有________个叶子结点。

　　参考解析：16

　　【分析】在满二叉树中每层的结点数都达到最大值，而且叶子结点全部出现在最底层。第1层(根结点所在的层)有20个结点，第2层有21个结点，……第n层有25-1点。在深度为5的满二叉树中，第5层有2n-1=16个结点(全部是叶子结点)。

　　11[填空题]深度为5的满二叉树有(　　)个叶子结点。

　　参考解析：16

　　【分析】在满二叉树中每层的结点数都达到最大值，而且叶子结点全部出现在最底层。第1层(根结点所在的层)有20个结点，第2层有21个结点，……第n层有25-1点。在深度为5的满二叉树中，第5层有2n-1=16个结点(全部是叶子结点)。

　　12[单选题]对右上图二叉树进行中序遍历的结果是(　　)

　　A.ACBDFEG

　　B.ACBDFGE

　　C.ABDCGEF

　　D.FCADBEG

　　参考答案：A

　　参考解析：中序遍历的基本思想是先中序遍历左子树，后访问根结点，再中序遍历右子树。针对本题中序遍历左子树的结果是ACBD，中序遍历右子树的结果是EG。所以本题的中序遍历结果是ACBDFEG，前序遍历结果是FCADBEG，后序遍历结果是ABDCGEF。因此本题的正确答案是A。

　　13[单选题]对右上图二叉树进行中序遍历的结果是(　　)。

　　参考答案：A

　　参考解析：中序遍历的基本思想是先中序遍历左子树，后访问根结点，再中序遍历右子树。针对本题中序遍历左子树的结果是ACBD，中序遍历右子树的结果是EG。所以本题的中序遍历结果是ACBDFEG，前序遍历结果是FCADBEG，后序遍历结果是ABDCGEF。因此本题的正确答案是A。

　　14[填空题]对右图二叉树进行中序遍历的结果为________。

　　参考解析：ACBDFEG【分析】中序遍历的原则是先遍历左子树，然后访问根结点，最后遍历右子树。因此本题中遍历结果是ACBDFEG。

　　相关推荐：

　　2015年9月计算机等级考试成绩查询时间通知

　　2015计算机二级公共基础知识考前冲刺练试题汇总

　　2015计算机二级公共基础知识精选选择题专项练习

　　2015计算机二级《公共基础知识》精选选择题90道