(山东科技大学)PTA数据结构答案与解析

PTA数据结构的部分答案与解析树和二叉树作业二叉树1 .判断问题1-1某二叉树的后序和中序扫描序列恰好相同，该二叉树的任何节点上一定没有右边的孩子。 (2点)解析：略，解析是1-6的回答： T 1-2的某个二叉树的后序和中序扫描序列恰好相同，这个二叉树的任何节点一定没有左边的孩子。 (2点)分析：略，分析同1-6的答案： F 1-3中共有2016个节点的二叉树，其中16个节点只有一个孩子。 (3点)解析：此处只说二叉树，因为没有说什么形状，所以错误的回答： f作者：何钦单位：浙江大学1-4如果a和b是一个二叉树叶的节点，那么存在这样的二叉树，之前的扫描序列是A.B.中的扫描序列是B.A. (2点)解析：回答： F 1-5如果有一个节点是二叉树中顺序扫描序列的最后一个节点，那么它必定是该树前顺序扫描序列的最后一个节点。 (2点)分析：可以进行制图分析，考虑到只有两个节点没有右子树的二叉树，中顺扫描的最后一个节点是根节点，根节点在前顺扫描中必定位于开头。 答： F 1-6某二叉树的序言和中序扫描序列正好相同，这二叉树中的任何节点一定都没有左边的孩子。 (2点)分析：有左边的孩子时，按照前面的顺序被遍历的第一个要素与按照中间顺序被遍历的第一个要素不同。 分析第一层次，假设根节点的左子树不存在，前向扫描和中向扫描的结果相等，判断根节点的右子树的部分，确认左子树不存在。 递归分析一定没有左边的孩子。 答： t作者： DS课程组单位：浙江大学1-7知道二叉树首次扫描结果为ABC，CAB不是中顺扫描结果。 (2点)解析：知道中顺扫描和先顺扫描，可以画树。 如果这个方法不太好的话，反正只有3个节点，所以可以画画。 没有树木先到顺序必须是ABC，中位顺序必须是CAB。 我们是这样分析的。 a是根节点。在中顺扫描中，c是左边的孩子，b是右边的孩子，在先顺扫描中，b是左边的孩子，c是右边的孩子，因为不一致，所以不能滴答： F 2.单选问题2-1*在非空的k(k2 )的分支树t中分别有k个孩子的情况下，把t称为正则k分支树。 如果t的高度为h (单节点树h=1)，则t的节点数带有(3分钟)1.()/(k1)2.()/(k1)3.()/(k1)4.或更高的未分析： k=2，并且应用二叉树的节点树的结论发现a是正确的： A 2-2*条非空k(k2 ) 如果t的高度为h (单节点树h=1)，则t的节点数最少： (3分钟)1.()/(k1)1.2.()/(k1)1.4.解析：这个问题不知道如何正确导出正确答案，但这个问题可以举出正确答案的二叉树的例子。 用带有解答的排除法得出答案： D 2-3使1根非空二叉树的先到顺序与中顺序相同，其所有非叶节点应满足的条件为(2分)1.左子树2 .右子树3 .节点的度均为1.4 .节点的度均为2解析：省略答案： B 2-4是知道1根二叉树的树如下图树中与节点a同层的节点，(3分)1. c 2. d 3. f 4. 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(k2 )在树t的非叶节点有k个孩子的情况下，t是正则k 如果t中有m个非叶节点，则t中的叶节点的数量为(3分钟)1.mk2.m(k1)3.m(k1)1.m(k1)1解析： b是分支数，n是节点数，联立上的二式可得到正解，因此c回答：在c单元：浙江大学2-8中有四叉树，度2的节点数为2，度2的节点数为2 这个树叶节点的数量是多少(2点)1.10.2.12.3.20.21解析：可以根据题意随意画出符合题意的图来判断，也可以用式子导出。 b表示分支数，n表示总括点数，如果联立上式后输入主题中的数据，则D 2-9为二叉树前的扫描序列为 4，2，1，3，6，5，7 ，中的扫描序列为 1，2，3，4，5，6， 7那么下面哪个句子错了(3分)1.这是完整的二叉树2 .所有奇数都在叶节点3 .这是二叉搜索树4. 2为5的父节点解析：根据序言，中顺扫描可以制图，并且根据图回答： D 2-10是二叉树的定义，3个(2点)1.3.2.4.5.6解析：绘画列举即可。 其中，二叉树的种类不应考虑二叉树的节点值差异。 答： C 2-11任何二叉树的叶节点都在序列中的相对顺序(两点)在前言、中文和后文中追溯。 2 .不变。 3 .不能确定。 4 .以上不进行分析：他们全部在左-右，因为询问相对顺序所以根节点插入哪里都可以的回答： B 2-12二叉树中第5层(根的层号为1 )的节点数最多的是(2分)1.8.15.16.32分析：回答： C 2-13先横切图的二叉树的结果c，d，h，e，I，f，G 2. A，b，d，h，I，e，c，f G 3. H，d，I，b，e，a，f，c，G 4. H，I，d，b，e，f，g，a， c分析：首先巡视根节点，然后巡视左子树，最后巡视右子树，递归地回答： B 2-14三叉树中，度为1的节点为5个，度为2的节点为3个，度为3的节点为2个，该树中包含多少叶节点(3点) 1.8.2.10.3.12.13分析：思路类似于2-8，在此不作回答： a单位：浙江大学2-15某二叉树的中序序列与后序列正相反，该二叉树必须(2分)1.空或一个节点2 .高度等于其节点数。 任何节点上没有左边儿童的4 .任何节点上没有右边儿童的分析：中顺扫描为左-根-右，后顺扫描为左-右-根，没有左边的子树正好是满足条件的答案：如果c单元：浙江大学2-16的二叉树前后的循环序列相反，则该二叉树只有一个节点2 .高度等于其节点数3 .任何节点没有左边儿童4 .任何节点没有右边儿童的分析：构想相同2-15这里不叙述答案： D 2-17把n，m作为一棵二叉树上的两个节点，中序巡视时，n为m的1 .分析n是m的左边2. n是m的右边3. n是m的祖先4. n是m的后代：选择明显容易得到的a的答案： A 2-18二叉树如下图所示。 假设n表示二叉树的根，l表示根节点的左子树，并且r表示根节点的右子树。如果扫描后的节点序列为3、1、7、5、6、2、4，则其扫描方式为(2分钟)1. NRL 2. RNL 3. LRN 4. RLN解析：明显容易得到，b的回答：将B 2-19设为h的二叉树(将叶的节点的高度设为1 )， 只有度为0和2的节点这样的二叉树的最小节点数和最大节点数分别为(3分)1.2.3.4.解析：根据二叉树的节点数的性质，b的回答正确，容易错误地选择d，除了根节点以外，在各层中存在2个节点的情况下，节点数最少(画画不方便) 二叉树的度为2 二叉树左右的子树可以任意交换深度k的完全二叉树的节点数在深度相同的满二叉树以下。 1.、2.、3.、4.解析：考察二叉树的定义和性质，可以参考教科书p13页的答案： A 3.函数问题4 .编程问题线性表1 .单选问题2-1采用多项式的非项式记忆表现，如果两个多项式的非零项分别为N1和N2个， 实现最高项指数分别为M1和M2的两个多项式的乘法运算的时间复杂度为(2分钟)1. o (n1n2)2. o (m1m2)3. o (n1n2)4. o (m1m2)解析：略解： A 2.编程问题堆栈1 .对断定问题1-1堆栈s的操作： Push(S，1 )，push 输出的序列为123。 (2点)解析：水平问题，略答： f作者： DS课程组1-2一个堆栈的输入序列为1，2，3，n，输出序列的第一个元素为I，第j个输出元素为Ji1。 (2点)解析：第j个输出的要素不确定，可以具有i=2，j=3的特指验证回答：如果f作者： DS课程组1-3一个堆栈的输入序列为 1，2，3，4，5 ，则不能得到 3，4，1，2，5 这一堆栈序列。 (2点)解析： 2必须先堆栈1的回答： T 2.单选问题2-1将一个堆栈的堆栈序列设为 1，2，n ，堆栈序列设为 p1，p2，pn 。 如果p2=n，则存在多少不同的堆栈序列？ (2点)1.1.2.2.3.n1.n解析：首先在p1之前有n-1的选择项，然后p2之后的序列必须是唯一的，因为已经没有要素，所以出场序列变化的回答： C 2-2把堆栈的入垒顺序定为1、2、3、4、5。 如果第一个堆栈的元素是4，则最后一个堆栈的元素必须(2分钟)1.1.3.5.1或5分析：1-4将所有堆栈进一步前进到5，否则完整答案： D 2-3堆栈上的指针从ST链堆栈中删除节点，并将删除节点的值保存为x 2. X=ST； ST=ST-next； 3. X=ST-data； ST=ST-next； 4. ST=ST-next； X=ST-data； 分析：考察链条堆栈的把握。 在链接栈中，ST代表栈元素，并且元素a、b、c、d、e、f、g依次进入栈s，其中data存储的元素值的答案为： C 2-4指示栈s和队列q的所有初始状态为空。如果每个元素在堆栈后立即进入队列q，并且七个元素的堆栈顺序为b、d、c、f、e、a、g，则堆栈s的容量至少为(二分钟)1. 1 2. 2 3. 3 4. 4分析：在模拟中回答： C 2-5将五个整数以1、2、3、4、5的顺序堆栈假设堆栈顺序为3、5、4、2、1，为了获得这种输出，堆栈大小至少为： (2分钟)1.2.3.4.5分析：在模拟一次中回答： C 2-6元素a、b、c、d、e、f依次堆栈，堆栈，解除堆栈操作(2点)1. BC AEF2. CBA ef3. DC beba4. afbedcb解析： d中的d c d明显是连续退出3次的回答：如果D 2-7一个堆栈的输入序列是1、2、3、4、5，则以下序列中堆栈的合法输出序列是(2点) 1.32154.5123.45124.43125分析：如果某个子序列位于某个数量的左侧，则在输出时必须确定此子序列的输出。 例如，假设1、2、3位于4的左侧，对于我的堆栈输出，可以首先输出3、输出2、最后输出1、中间插入其它元素。 利用此性质，您可以确定选择是否是合法答案。 A 2-8按6、5、4、3、2和1的顺序堆叠了六个元素。 哪个不是合法的堆栈序列？ (2点)1.23456.34652.3551.54612.45326分析：通过逐个选项进行验证来回答： B 2-9对于一个堆栈的输入堆栈序列为1、2、3、n的输出序列的第一个元素为I的第j个输出元素，(2分钟)1.iji1.ij3.Ji1.不确定性分析： I为当i=N时，这是因为可能插入了新的元素并且在任何位置处改变输出，则输出序列是确定性的答案：如果D 2-10栈的输入序列是1，2，3， n，则输出序列是p1，p2，p3， pN。 如果p1=N，pi为(2分钟)1.i2.ni3.ni1.不确定性分析： p1等于n，p2-pn是唯一的序列，pi=n - i 1的