《Java数据结构》二叉树专项期末考试试题

《Java数据结构》二叉树专项期末考试试题适用专业：计算机科学与技术、软件工程、物联网工程大二本科考试时长：60分钟满分：100分出题说明：贴合本校课本考点，无超纲竞赛题，侧重基础概念+手写代码+遍历算法，适配期末闭卷考试一、单项选择题（共10题，每题2分，合计20分）1.一棵高度为h的非空二叉树，叶子结点最少个数为（）A.1B.hC.2^(h-1)D.2^h-12.已知一棵二叉树前序遍历序列：ABDECF，中序遍历序列：DBEAFC，则后序遍历序列为（）A.DEBFCAB.EDBAFCCC.DBEAFCD.ABDECF3.下列关于满二叉树、完全二叉树说法正确的是（）A.完全二叉树一定是满二叉树B.满二叉树一定是完全二叉树C.二者定义完全一致D.完全二叉树叶子结点全部在最下层4.一棵拥有n个结点的二叉树，二叉链表存储结构中空指针域的数量为（）A.n-1B.nC.n+1D.2n5.二叉树第k层最多拥有结点个数为（k≥1）（）A.2kB.2^(k-1)C.2^k-1D.k6.Java中使用二叉链表自定义二叉树结点，结点属性不包含以下哪项（）A.数据域dataB.左孩子引用leftC.父结点引用parentD.右孩子引用right7.对二叉树进行层序遍历，底层最合适的数据结构是（）A.栈StackB.队列QueueC.数组ArrayD.链表LinkedList8.下列遍历方式中，属于深度优先遍历的是（）A.层序遍历B.前序遍历C.广度遍历D.分层遍历9.一棵含10个结点的完全二叉树，编号为5的结点，左孩子编号为（结点从上到下、从左到右从1编号）（）A.9B.10C.11D.1210.二叉树删除叶子结点，遍历效率最高的方式是（）A.递归前序B.递归后序C.递归中序D.任意遍历一致二、判断题（共8题，每题1.5分，合计12分，对打√，错打×）1.任意一棵二叉树，度为0的结点个数=度为2的结点个数+1。（）2.二叉树和普通树一样，结点孩子个数无上限。（）3.递归实现二叉树遍历代码简洁，运行效率高于非递归遍历。（）4.仅通过二叉树的前序和后序遍历序列，可以唯一确定一棵二叉树。（）5.二叉树的子树有左右之分，次序不能随意颠倒。（）6.高度为3的满二叉树，总结点数量为7个。（）7.二叉链表存储结构，适合存储稀疏、形态不规则的二叉树。（）8.完全二叉树可以直接使用数组顺序存储，无需浪费存储空间。（）三、填空题（共6空，每空3分，合计18分）1.二叉树三大基础遍历：前序、______、后序。2.度为0的二叉树结点，被称为______结点。3.高度为4的完全二叉树，最少有______个结点。4.Java递归遍历二叉树，终止递归的条件是______。5.前序遍历顺序：______→左子树→右子树。6.一棵二叉树共15个结点，度为2的结点6个，则叶子结点有______个。四、简答题（共2题，每题8分，合计16分）1.简述满二叉树、完全二叉树的定义，并用画图简易区分二者差异。2.对比二叉树递归遍历与非递归遍历的优缺点，结合Java运行机制说明。五、基础代码题（共1题，合计16分）使用Java语言完成代码编写，要求如下：1.自定义二叉树结点TreeNode类（4分）；2.手写递归方法，实现二叉树中序遍历（6分）；3.手写递归方法，统计整棵二叉树叶子结点总个数（6分）。六、算法应用题（共1题，合计18分）现有二叉树中序序列：BADCE，前序序列：ABCDE1.画出该二叉树树形结构（8分）2.写出该二叉树后序遍历、层序遍历结果（6分）3.手动计算该二叉树高度、叶子结点数量（4分）参考答案及详细解析（任课教师手写版解析，贴合阅卷得分点）一、单项选择题答案+解析1.A解析：二叉树呈斜树形态时叶子最少，仅1个叶子结点。2.A解析：前序定根结点，中序划分左右子树，推导后序：DEBFCA。3.B解析：满二叉树每层结点填满，一定满足完全二叉树规则，反之不成立。4.C解析：公式固定：n个结点二叉链表空指针=n+1，期末必考公式。5.B解析：第k层最大结点数公式：2^(k-1)6.C解析：课本标准TreeNode结点，默认仅data、left、right，无父结点。7.B解析：层序从上到下从左到右，利用队列先进先出特性实现。8.B解析：前中后序均为深度优先，层序为广度优先。9.A解析：完全二叉树编号公式：左孩子=2*i，右孩子=2*i+1，2*5=10超出10结点，故左孩子为9。10.B解析：后序先遍历子树，最后访问根，适配叶子删除逻辑。选择题答案汇总：1.A2.A3.B4.C5.B6.C7.B8.B9.A10.B二、判断题答案+解析1.√二叉树性质公式，期末核心考点2.×二叉树每个结点最多2个孩子，区分普通树3.×递归频繁压栈，开销大，效率低于非递归4.×前+后无法区分左右子树，无法唯一确定树；前+中、中+后可以5.√二叉树左右子树严格区分6.√高度3满二叉树：1+2+4=7结点7.√顺序存储适合完全二叉树，链表适合不规则二叉树8.√完全二叉树无空位，数组存储无空间浪费判断题答案汇总：1√2×3×4×5√6√7√8√三、填空题答案1.中序2.叶子（终端）3.84.当前结点为null5.根结点6.7填空解析：第6题套用性质：叶子数=度2结点+1=6+1=7；第3题高度4完全二叉树，前3层填满7个，第4层最少1个，合计8个。四、简答题得分版答案（按点给分）1.答题答案（1）满二叉树：一棵二叉树每一层结点数量都达到最大值，所有叶子结点全部在最底层，除叶子结点外，所有结点度均为2。（4分）（2）完全二叉树：深度为h的二叉树，除第h层外，其余每层结点数全部填满，且最后一层结点全部靠左排列。（2分）（3）区分：满二叉树是特殊完全二叉树，完全二叉树最后一层可缺右侧结点，满二叉树无缺失结点。（2分）2.答题答案递归遍历优点：代码极简、逻辑直观、贴合遍历定义，新手易编写，代码行数少；缺点：依托JVM虚拟机栈实现，结点数量过多会出现栈溢出，执行效率低，有额外栈开销。（4分）非递归遍历优点：手动使用集合栈/队列，可控内存，大数据量二叉树不会栈溢出，执行速度快；缺点：代码繁琐，需要手动控制出入栈逻辑，逻辑复杂，易错。（4分）java

//1.自定义二叉树结点类（4分）

classTreeNode{

//数据域

chardata;

//左孩子引用

TreeNodeleft;

//右孩子引用

TreeNoderight;

//构造方法

publicTreeNode(chardata){

this.data=data;

this.left=null;

this.right=null;

}

}

publicclassBinaryTreeDemo{

//2.递归中序遍历：左-根-右（6分）

publicvoidinOrder(TreeNoderoot){

//递归终止条件

if(root==null){

return;

}

inOrder(root.left);

System.out.print(root.data+"");

inOrder(root.right);

}

//3.递归统计叶子结点个数（6分）

publicintgetLeafCount(TreeNoderoot){

if(root==null){

return0;

}

//当前结点左右都为空，判定为叶子

if(root.left==null&&root.right==null){

return1;

}

//递归累加左右子树叶子数量

returngetLeafCount(root.left)+getLeafCount(root.right);

}

}

阅卷扣分点：未写root==null终止条件直接扣分，叶子