搜索
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...A...。(2分)解析：答案：F1-5若一个结点是某二叉树的中序遍历序列的昀后一个结点，则它必是该树的前序遍历序列中的昀后一个结点。(2分)解析：画图分析即可，考虑只有两个节点的无右子树的二叉树，中序遍历的昀后一个节点是根节点，而根节点在前序遍历中一定是在开头的。答案：F1-6某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。(2分)解析：假如存在左孩子，那么前序遍历的第一个元素肯定不等于中序遍历的第一个元素。我们分析第一层，假设根节点的左子树不存在，那么总算前序遍历和中序遍历结果相等了，然后我们判断根节点的右子树部分，发现还是要保证左子树不存在的。递归分析一定没有左孩子的。答案：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−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解析：略答案：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}，则下列哪句是错的？(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.21解析：根据题意随便画一种符合题意的图即可判断，也可以通过公式推导。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的父结点解析：根据前序，中序遍历可以建出图来，然后根据图来判断即可答案：D2-10按照二叉树的定义，具有3个结点的二叉树有几种？(2分)1.32.43.54.6解析：画图枚举即可，这里问二叉树种类不考虑二叉树节点值的不同。答案：C2-11任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序(2分)1.发生改变2.不发生改变3.不能确定4.以上都不对解析：他们都是左-右，因为问的是相对次序，根节点插在哪里无所谓的答案：B2-12二叉树中第5层（根的层号为1）上的结点个数昀多为：(2分)1.82.153.164.32解析：答案：C2-13先序遍历图示二叉树的结果为(2分)1.A，B，C，D，H，E，I，F，G2.A，B，D，H，I，E，C，F，G3.H，D，I，B，E，A，F，C，G4.H，I，D，B，E，F，G，A，C解析：先序遍历先遍历根节点，再遍历左子树，昀后遍历右子树，递归进行答案：B2-14三叉树中，度为1的结点有5个，度为2的结点3个，度为3的结点2个，问该树含有几个叶结点？(3分)1.82.103.124.13解析：思路与2-8类似，在此不再阐述答案：A单位:浙江大学2-15某二叉树的中序序列和后序序列正好相反，则该二叉树一定是(2分)1.空或只有一个结点2.高度等于其结点数3.任一结点无左孩子4.任一结点无右孩子解析：中序遍历是左-根-右，后序遍历是左-右-根，可知如果左子树不存在的话，就是恰好满足条件的答案：C单位:浙江大学2-16某二叉树的前序和后序遍历序列正好相反，则该二叉树一定是(2分)1.空或只有一个结点2.高度等于其结点数3.任一结点无左孩子4.任一结点无右孩子解析：思路同2-15，在此不再阐述答案：D2-17设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是(3分)1.n在m左方2.n在m右方3.n是m祖先4.n是m子孙解析：由显然易得，选A答案：A2-18给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是：(2分)1.NRL2.RNL3.LRN4.RLN解析：由显然易得，选B答案：B2-19设高为h的二叉树（规定叶子结点的高度为1）只有度为0和2的结点，则此类二叉树的昀少结点数和昀多结点数分别为：(3分)1.,2.,3.,4.,解析：由二叉树结点数性质，易得B答案正确,容易误选D，当除根节点之外，每层有两个节点的时候，结点数是昀少的（不方便画图就不画了，自行理解）答案：B2-20在下述结论中，正确的是：(2分)①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。1.①④2.②④3.①②③4.②③④解析：考察二叉树的定义以及性质，可以参考课本P113页答案：A3.函数题4.编程题 线性表应用1.单选题2-1采用多项式的非零项链式存储表示法，如果两个多项式的非零项分别为N1和N2个，昀高项指数分别为M1和M2，则实现两个多项式相乘的时间复杂度是：(2分)1.O(N1×N2)2.O(M1×M2)3.O(N1+N2)4.O(M1+M2)解析：略答案：A2.编程题 栈1.判断题1.判断题1-1通过对堆栈S操作：Push(S,1),Push(S,2),Pop(S),Push(S,3),Pop(S),Pop(S)。输出的序列为：123。(2分)解析：水题，略答案：F作者:DS课程组 1-2若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。(2分)解析：第j个输出的元素应该是不确定的，可以带i=2，j=3的特指验证答案：F作者:DS课程组 1-3若一个栈的输入序列为{1,2,3,4,5}，则不可能得到{3,4,1,2,5}这样的出栈序列。(2分)解析：2一定先与1出栈的答案：T2.单选题2-1给定一个堆栈的入栈序列为{1,2,⋯,n}，出栈序列为{p1,p2,⋯,pn}。如果p2=n，则存在多少种不同的出栈序列？(2分)1.12.23.n−14.n解析：首先p1之前有n-1中选法，然后p2后边的序列一定是唯一的，因为不会再有元素进栈导致出栈序列变化了答案：C2-2设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则昀后一个出栈的元素必定是：(2分)1.12.33.54.1或者5解析：要不1-4全出栈再进5，要不进5之后全答案：D2-3从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，则执行：(2分)1.X= ST-data;2.X= ST; ST = ST-next;3.X= ST-data; ST = ST-next;4.ST = ST-next; X= ST-data;解析：考察对链栈的掌握，在链栈中，ST代表栈顶元素，其data存储的元素的值答案：C 2-4设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b、d、c、f、e、a、g，则栈S的容量至少是：(2分)1.12.23.34.4解析：模拟即可答案：C2-5假设有5个整数以1、2、3、4、5的顺序被压入堆栈，且出栈顺序为3、5、4、2、1，那么为了获得这样的输出，堆栈大小至少为：(2分)1.22.33.44.5解析：模拟一遍即可答案：C2-6若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是？(2分)1.bcaefd2.cbdaef3.dcebfa4.afedcb解析：D中的dcd很明显是连续三次退栈了答案：D2-7设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？(2分)1.321542.512343.451324.43125解析：如果某个子序列在某个数的左边，那么在输出的时候，这个子序列的输出一定是确定的。例如1,2,3在4的左边，那么我栈输出的时候，一定是先输出3，在输出2，昀后输出1，中间可以穿插其他的元素。可以利用这个性质去判断选项是否合法答案：A2-8有六个元素以6、5、4、3、2、1的顺序进栈，问哪个不是合法的出栈序列？(2分)1.2341562.3465213.5436124.453126解析：针对每个选项进行验证即可答案：B2-9若一个栈的入栈序列为1、2、3、…、N，输出序列的第一个元素是i，则第j个输出元素是：(2分)1.i−j−12.i−j3.j−i−14.不确定解析：当i不等于N的时候，第j个输出是不确定的，因为随时有可能有新的元素插入进来并在任意位置输出改变原有的输出顺序；当i=N，输出序列才是确定的答案：D2-10若一个栈的入栈序列为1、2、3、…、N，其输出序列为p1、p2、p3、…、pN。若p1=N，则pi为：(2分)1.i2.n−i3.n−i+14.不确定解析：当p1等于N，p2-pn是唯一的一个序列，pi=n-i+1答案：C2-11将5个字母ooops按此顺序入栈，则有多少种不同的出栈顺序可以仍然得到ooops？(2分)1.12.33.54.6解析：五种方