资源描述：
《(山东科技大学)PTA数据结构答案与解析-.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、PTA数据结构部分答案与解析树和二叉树作业—二叉树1.判断题1-1某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。(2分)解析：略，分析同1-6答案：T1-2某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。(2分)解析：略，分析同1-6答案：F1-3存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子。(3分)解析：这里只说了是二叉树，没说是什么形状的，所以错误答案：F作者:何钦铭单位:浙江大学1-4若A和B都是一棵二叉树的叶子结点，则存在这样的二叉树，其前序遍历序列为...A...B...，而中序遍历序列为...B...
2、A...。(2分)解析：答案：F1-5若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。(2分)解析：画图分析即可，考虑只有两个节点的无右子树的二叉树，中序遍历的最后一个节点是根节点，而根节点在前序遍历中一定是在开头的。答案：F1-6某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。(2分)解析：假如存在左孩子，那么前序遍历的第一个元素肯定不等于中序遍历的第一个元素。我们分析第一层，假设根节点的左子树不存在，那么总算前序遍历和中序遍历结果相等了，然后我们判断根节点的右子树部分，发现还是要保证左子树不存在的。递归分析一定没有
3、左孩子的。答案：T作者:DS课程组单位:浙江大学1-7已知一棵二叉树的先序遍历结果是ABC,则CAB不可能是中序遍历结果。(2分)解析：知道中序遍历和先序遍历，是可以画出树来的。如果不是很会这种方法，反正只有三个节点，大可以画图举例。可得没有树满足先序是ABC，中序是CAB的。我们这样去分析：由先序遍历可得A是根节点；由中序遍历可得C是左孩子，B是右孩子，而先序遍历中B是左孩子，C是右孩子，矛盾，所以不可能滴答案：F2.单选题2-1*如果一棵非空k（k≥2）叉树T中每个非叶子结点都有k个孩子，则称T为正则k叉树。若T的高度为h（单结点的树h=1），则T的结点数最多为：(3分)1.()/(k−
4、1)2.()/(k−1)3.()/(k−1)4.以上都不是解析：将k=2带入，套用二叉树的结点树结论，发现A为正确形式答案：A2-2*如果一棵非空k（k≥2）叉树T中每个非叶子结点都有k个孩子，则称T为正则k叉树。若T的高度为h（单结点的树h=1），则T的结点数最少为：(3分)1.()/(k−1)+12.()/(k−1)−13.4.解析：这道题我不知道怎么正确推导答案，不过这题可以举一个正确的二叉树的例子，带答案用排除法做答案：D2-3要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是：(2分)1.只有左子树2.只有右子树3.结点的度均为14.结点的度均为2解析：略答案
5、：B2-4已知一棵二叉树的树形如下图所示，其后序序列为{e,a,c,b,d,g,f}。树中与结点a同层的结点是：(3分)1.c2.d3.f4.g解析：模拟一遍求解即可答案：B单位:浙江大学2-5在下述结论中，正确的是：(2分)①只有2个结点的树的度为1；②二叉树的度为2；③二叉树的左右子树可任意交换；④在最大堆（大顶堆）中，从根到任意其它结点的路径上的键值一定是按非递增有序排列的。1.①④2.②④3.①②③4.②③④解析：二叉树度数不一定为2，比如空二叉树答案：A单位:浙江大学2-6若一棵二叉树的后序遍历序列是{1,3,2,6,5,7,4}，中序遍历序列是{1,2,3,4,5,6,7}，则下
6、列哪句是错的？(3分)1.这是一棵完全二叉树2.2是1和3的父结点3.这是一棵二叉搜索树4.7是5的父结点解析：根据后序遍历与中序遍历建树判断即可答案：A单位:浙江大学2-7如果一棵非空k（k≥2）叉树T中每个非叶子结点都有k个孩子，则称T为正则k叉树。若T有m个非叶子结点，则T中的叶子结点个数为：(3分)1.mk2.m(k−1)3.m(k−1)+14.m(k−1)−1解析：B代表分支数，n代表结点数,联立上边二式可得正确答案，故选C答案：C单位:浙江大学2-8有一个四叉树，度2的结点数为2，度3的结点数为3，度4的结点数为4。问该树的叶结点个数是多少？(2分)1.102.123.204.2
7、1解析：根据题意随便画一种符合题意的图即可判断，也可以通过公式推导。B代表分支数，n代表总结点数，将上边式子联立，然后带入题目中数据，可得答案：D2-9若一棵二叉树的前序遍历序列是{4,2,1,3,6,5,7}，中序遍历序列是{1,2,3,4,5,6,7}，则下列哪句是错的？(3分)1.这是一棵完全二叉树2.所有的奇数都在叶子结点上3.这是一棵二叉搜索树4.2是5的父结点解析：根据前序，中序遍历可以建出图来，
