下载文档原格式
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编6(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：33，分数：66.00)1.一棵完全二叉树又是一棵( )。
【华中科技大学2006一、7(2分)】A.平衡二叉树B.堆√C.二叉排序树D.哈夫曼(Huffman)树完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。
平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。
平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。
堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。
哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。
2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。
【合肥工业大学1999一、5(2分)】A.不确定B.0C.1D.2 √左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。
3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。
【合肥工业大学2000一、5(2分)】A.0B.1 √C.2D.不确定4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。
【南京理工大学1996一、6(2分)】A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点√D.X的左子树中最右叶结点5.引入二叉线索树的目的是( )。
【南京理工大学1998一、5(2分)】A.加快查找结点的前驱或后继的速度√B.为了能在二叉树中方便地进行插入与删除C.为了能方便地找到双亲D.使二叉树的遍历结果唯一6.线素二叉树是一种( )结构。
【西安电子科技大学1996一、9(2分)】A.逻辑B.逻辑和存储C.物理√D.线性7.甩个结点的线索二叉树上含有的线索数为( )。
计算机专业基础综合数据结构（图）历年真题试卷汇编4(总分：58.00，做题时间：90分钟)一、综合题(总题数：7，分数：14.00)1.已知一图如下图所示：(1)写出全部拓扑排序；(2)以V1为源点，以V8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；(3)求V1结点到各点的最短距离。
【北京邮电大学2000五(15分)】__________________________________________________________________________________________正确答案：(正确答案：关键路径有3条，长17。
各事件允许发生的最早时间和最晚时间略。
V1→V2→V6→V8，V1→V3→V5→V7→V8，V1→V7→V8→V1→V4→V5→V8 (3)V1结点到其他各结点的最短距离为：2，3，6，12，10，15，16。
)2.(1)对于有向无环图，叙述求拓扑有序序列的步骤；(2)对于以下的图，写出它的四个不同的拓扑有序序列。
【南开大学1998二(12分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)对有向图，求拓扑序列步骤为： 1)在有向图中选一个没有前驱(即入度为零)的顶点并输出。
2)在图中删除该顶点及所有以它为尾的弧。
3)重复1)和2)，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。
(2)这里使用形式化描述方法，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉拓扑序列。
这里只画出从顶点1开始的所有可能的拓扑序列，从顶点3开始的拓扑序列可类似画出。
)3.有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法；若不能，请简述原因。
【西北大学2000二、8(5分)】__________________________________________________________________________________________ 正确答案：(正确答案：图的深度优先遍历可用于拓扑排序。
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编10(总分：68.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.先序序列为a，b，c，d的不同二叉树的个数是( )。
【2015年全国试题2(2分)】（分数：2.00）A.13B.14C.15 √D.16解析：解析：先序序列为1，2，3，…，n的不同的二叉树的数目是1／(n+1)((2n)!／(n!*n!))。
2.下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是( )。
【201 5年全国试题3(2分)】（分数：2.00）A.24，10，5和24，10，7B.24，10，5和24，12，7C.24，10，10和24，14，11D.24，10，5和24，14，6 √解析：解析：A的错误在于若路径上有两个10，叶子5应和另一个权值5组成左右子女，7和3组成左右子女，显然不符合哈夫曼的构造规则(应该3和5组成左右子女构造双亲结点)；若路径上只有一个10，5和7并非其左右子女。
B的错误在于双亲10和双亲12不可能构造双亲24。
C的错误是路径上不可能有相同权值10的结点。
D是正确的，双亲10的另一个子女是5，双亲14的另一个子女是8，而双亲10和双亲14恰是双亲24的左右子女。
3.树是一种逻辑关系，表示数据元素之间存在的关系为( )。
【北京交通大学2007(2分)】（分数：2.00）A.集合关系B.一对一关系C.一对多关系√D.多对多关系解析：4.下列判断，( )是正确的。
【华南理工大学2005一、1(2分)】（分数：2.00）A.二叉树就是度为2的树B.二叉树中不存在度大于2的结点√C.二叉树是有序树D.二叉树的每个结点的度都为2解析：解析：二叉树与树是两个不同的概念。
相同点是二者都是树形结构，不同点有三：一是二叉树的度至多是2，树无此限制；二是二叉树的子树有左右子树之分，只有一棵子树时，也必须区分是左子树还是右子树，树不必这样；三是二叉树允许为空，树不准为空，但是多数教科书认为树可以为空，否则空二叉树无法转换成空树，本题第一问有二义性。
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编5(总分：66.00，做题时间：90分钟)一、单项选择题(总题数：22，分数：44.00)1.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点(i从1开始用上述方法编号)的右孩子在数组A扣的位置是( )。
【南京理工大学2000一、4(1．5分)】（分数：2.00）A.A[2i](2i≤n)B.A[2i+1](2i+1≤n)C.A[i-2]D.条件不充分，无法确定√解析：2.设m、n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是：( )。
【北京理工大学2006五、9(1分)】（分数：2.00）A.n在m右方B.n是m祖先C.n在m左方√D.n是m子孙解析：3.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是( )。
【北京工业大学2001一、2(2分)】（分数：2.00）A.CABDEFGB.ABCDEFG √C.DACEFBGD.ADCFEG解析：解析：判断原则：前序序列第一个元素是根，在中序序列中根结点把序列分成左右子树，再看前序第二个元素，到中序的左右子树中找。
答案A根左面是C，答案C根左面是D，答案D根左面为空，都不是前序序列的第二个元素B。
只有答案B正确。
4.已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为( )。
【浙江大学1999四、2(4分)】（分数：2.00）A.CBEFDA √B.FEDCBAC.CBEDFAD.不定解析：5.二叉树的先序和中序遍历序列分别是ABCDEFGH，CBEDFAGH，则后序遍历序列是( )。
【南京理工大学2005一、5(1分)】（分数：2.00）A.HGFEDACBB.GHEDFCBAC.CEFDBHGA √D.HGAFDEBC解析：解析：由先序序列知，A是根，因此，A和D是不对的；由中序序列知，右子树有两个结点G和H，因此，B是错误的。
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1(总分：86.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。
【西安交通大学1996三、2(3分)】（分数：2.00）A.250B.500C.254D.505E.以上答案都不对2.一棵124个叶结点的完全二叉树，最多有( )个结点。
【中国科学技术大学1995十四、3(2分)】（分数：2.00）A.247B.248C.249D.250E.2513.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。
【上海交通大学2005四、6(2分)】（分数：2.00）A.3 11B.3 12C.3 13D.3 14E.其他4.具有300个结点的二叉树，其高度至少应为( )。
【北京理工大学2006五、8(1分)】（分数：2.00）A.6B.7C.8D.95.当结点数目一定时，具有最小深度的二叉树是( )。
【北京航空航天大学2005】（分数：2.00）A.满二叉树B.完全二叉树C.线索二叉树D.二叉排序树6.二叉树的第I层上最多含有的结点数为( )。
【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】（分数：2.00）A.2 IB.2 I-1一1C.2 I-1D.2 I一17.从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h 层的从左到右第k个结点的编号为( )。
【电子科技大学2005一、6(1分)】（分数：2.00）A.2 h +h-1B.2 h一k+1C.2 h +k+1D.2 h一k-18.下列判断中，( )是正确的。
【华南理工大学2006一、2(2分)】（分数：2.00）A.深度为k的二叉树最多有2 k -1个结点(k≥1)，最少有k个结点B.二叉树中不存在度大于2的结点C.对二叉树遍历是指先序、中序或后序遍历中的一种D.构造线索二叉树是为能方便找到每个结点的双亲9.一个具有1025个结点的二叉树的高h为( )。
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编13(总分：66.00，做题时间：90分钟)一、综合题(总题数：4，分数：12.00)1.已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。
【北京工业大学1998五(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：()解析：设T是一棵二叉树，除叶子结点外，其他结点的度数皆为2，若T中有6个叶结点，试问：（分数：6.00）(1).T树的最大可能深度Kmax=?最小可能深度Kmin=?（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：(1)T树的最大深度：Kmax=6(除根外，每层均是两个结点)。
T树的最小深度Kmin=4(具有6个叶子的完全二叉树是其中的一种形态)。
)解析：(2).T树中共有多少非叶结点?（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：非叶子结点数是5(n2=n0—1)。
)解析：(3).若叶结点的权值分别为1，2，3，4，5，6。
请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wp1。
【北京邮电大学1992一、3(15／3分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：哈夫曼树见右图，其带权路径长度wp1=51从本题到97题都是哈夫曼树的试题。
2024计算机科学综合考试试题2024年计算机科学综合考试试题（样题）注意事项：1. 考试时间为180分钟，满分100分。
2. 试题分为选择题和主观题两部分，选择题为单选，主观题部分包括简答题和编程题。
一、选择题（每题2分，共20分）1. 下列关于栈的描述中，错误的是（）。
A. 栈是先进后出（FILO）的数据结构B. 栈通过链表实现，可以动态增长和收缩C. 栈顶元素总是最后入栈的元素D. 栈底元素是最早入栈的元素2. 二叉树中，节点的度是指该节点的子树个数。
对于一棵二叉树，其节点度数的分布情况可以决定该树的形状。
下列关于二叉树的描述中，正确的是（）。
A. 所有节点的度数都为2或0的二叉树称为满二叉树B. 所有节点的度数都为1或2的二叉树称为满二叉树C. 所有节点的度数都为1或2的二叉树称为完全二叉树D. 所有节点的度数都为0或1的二叉树称为完全二叉树3. 在数据库设计中，关系模型是一种非常重要的数据模型。
关系模型的主要特点是（）。
A. 数据结构单一，以表格形式表示数据B. 数据结构复杂，以表格形式表示数据C. 数据结构复杂，以图形形式表示数据D. 数据结构单一，以图形形式表示数据4. 在计算机网络中，路由器是一种重要的网络设备，其主要功能是实现（）。
A. 数据传输和路由选择B. 数据传输和网络安全C. 路由选择和网络安全D. 数据传输和网络管理5. 在软件开发过程中，需求分析阶段的主要任务是（）。
A. 设计软件架构B. 编写代码实现功能C. 确定软件需求和功能要求D. 进行系统测试6. 下列排序算法中，时间复杂度为O(nlogn)的是（）。
A. 冒泡排序B. 选择排序C. 归并排序D. 快速排序7. 在HTML中，用于定义超链接的标签是（）。
A. <a> 标签B. <b> 标签C. <i> 标签D. <u> 标签8. 下列关于面向对象编程的描述中，正确的是（）。
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编3(总分：84.00，做题时间：90分钟)一、单项选择题(总题数：26，分数：52.00)1.树是一种逻辑关系，表示数据元素之间存在的关系为____。
【北京交通大学2007年】（分数：2.00）A.集合关系B.一对一关系C.一对多关系√D.多对多关系解析：解析：考查树的概念。
树是一种特殊的数据结构，表示元素之间的一对多的关系，例如：一个父结点可能有多个儿子结点，而一个儿子结点一定只有一个父结点。
2.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为____个。
【哈尔滨：[业大学2001年】（分数：2.00）A.4B.5C.6 √D.7解析：解析：考查树结点数与度的相关计算。
树中结点数等于所有结点度数和加1。
所以，2十1+2+X=2.3+1．2十2.1+x．0+1，解得X=6。
3.设有一表示算术表达式的二叉树(见图3-1)，它所表示的算术表达式是____1999年】（分数：2.00）A.A+B+C／(D*E)+(F—G)B.(A*B+C)／(D*E)+(F—G)C.(A+B+C)／(D*E+(F—G)) √D.A*B+C／D*E+F—G解析：解析：考查二又树表示算术表达式的方法。
叶子结点表示运算值，非叶子结点表示运算符，运算符的子结点或子树即该运算符的运算值。
4.在下述结论中，正确的是____。
【南京理工大学1999年】①只有一个结点的二叉树的度为0：②二叉树的度为2；③二叉树的左右子树可任意交换：④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
（分数：2.00）A.①②③B.②③④C.②④D.①④√解析：解析：考查二叉树的相关概念。
二叉树的度最多为2，可以比2小。
二叉树的左有了树是有顺序的，不可随意交换。
完全二叉树从最底层右边起比层数相同的满二叉树连续缺失若干个叶结点。
5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是____。
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1(总分：86.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。
【西安交通大学1996三、2(3分)】A.250B.500C.254D.505E.以上答案都不对√2.一棵124个叶结点的完全二叉树，最多有( )个结点。
【中国科学技术大学1995十四、3(2分)】A.247B.248 √C.249D.250E.2513.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。
【上海交通大学2005四、6(2分)】A.3 11B.3 12C.3 13 √D.3 14E.其他4.具有300个结点的二叉树，其高度至少应为( )。
【北京理工大学2006五、8(1分)】A.6B.7C.8D.9 √5.当结点数目一定时，具有最小深度的二叉树是( )。
【北京航空航天大学2005】A.满二叉树B.完全二叉树√C.线索二叉树D.二叉排序树设结点数目是n，n个结点未必是满二叉树，A错。
C和D明显错误。
6.二叉树的第I层上最多含有的结点数为( )。
【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】A.2 IB.2 I-1一1C.2 I-1√D.2 I一17.从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h 层的从左到右第k个结点的编号为( )。
【电子科技大学2005一、6(1分)】A.2 h +h-1 √B.2 h一k+1C.2 h +k+1D.2 h一k-18.下列判断中，( )是正确的。
【华南理工大学2006一、2(2分)】A.深度为k的二叉树最多有2 k -1个结点(k≥1)，最少有k个结点√B.二叉树中不存在度大于2的结点√C.对二叉树遍历是指先序、中序或后序遍历中的一种D.构造线索二叉树是为能方便找到每个结点的双亲9.一个具有1025个结点的二叉树的高h为( )。
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编8(总分：66.00，做题时间：90分钟)一、填空题(总题数：22，分数：44.00)1.设一棵完全二叉树叶子结点数为k，最后一层结点数>2，则该二叉树的高度为__________。
【北京科技大学1998一、3】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：[log 2 k]+1)解析：2.已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是__________。
【东南大学2005数据结构部分二、7(1分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：235。
参见上面一、2的分析。
)解析：3.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点编号为0，则编号为50的结点的右孩子编号为__________。
【中南大学2005二、l(2分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：102。
假定编号为i的结点的左右孩子存在，左孩子的编号是2*i+1，右孩子的编号是2*i+2。
)解析：4.高度为i(i≥1)的完全二叉树最多有__________个结点；最少有__________个结点；若按自上而下，从左到右的次序给结点编号(从1开始)，则编号最小的叶子结点的编号为__________。
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编4(总分：74.00，做题时间：90分钟)一、综合题(总题数：35，分数：74.00)1.(1)试找出满足下列条件的二叉树：1)先序序列与后序序列相同2)中序序列与后序序列相同3)先序序列与中序序列相同4)中序序列与层次遍历序列相同(2)已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA，画出这棵二叉树。
【东北大学1999六(4分)】【东南大学2000一、4(6分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：(1)先序遍历二叉树的顺序是“根一左子树一右子树”，中序遍历“左子树一根一右子树”，后序遍历顺序是“左子树一右子树一根”，根据以上原则，本题解答如下：1)若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
2)若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。
3)若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。
4)若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。
(2)由中序序列DBEAFIHCG和后序序列DEBHIFGCA)解析：2.分别给出满足下列条件的二叉树。
(1)前序和中序遍历结果相同；(2)前序和中序遍历结果不相同而是相反；(3)中序和后序遍历结果相同；(4)前序和后序遍历结果相同。
【四川大学2004】【烟台大学2007四、2(8分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：空二叉树满足题目要求，若二叉树非空，则(1)前序和中序遍历结果相同的二叉树是任一结点无左子女； (2)前序和中序遍历结果不相同而是相反的二叉树是任一结点无右子女； (3)中序和后序遍历结果相同的二叉树是任一结点无右子女； (4)前序和后序遍历结果相同的二叉树是只有根结点。
)解析：3.将下列由三棵树组成的森林转换为二叉树(只要求给出转换结果)1998一(10分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：森林转为二叉树的三步： (1)连线(将兄弟结点相连，各树的根看作兄弟)； (2)切线(保留最左边子女为独生子女，将其他子女分支切掉)；(3)旋转(以最左边树的根为轴，顺时针向下旋转45度)。
其实经过(1)和(2)，已转为二又树，执行(3)只是为了与平时的二又树的画法一致。
)解析：4.设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：AB D，C E G H 中序遍历序列：B FDAG E H C(1)画出这棵二叉树。
(2)画出这棵二叉树的后序线索树。
(3)将这棵二叉树转换成对应的树(或森林)。
【南京航空航天大学1997二(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)(2)(3))解析：5.已知一棵二叉树的对称序和后序序列如下：对称序：GLDHBEIACJFK 后序：LGHDIEBJKFCA(1)(2分)给出这棵二叉树；(2)(2分)转换为对应的森林；(3)(4分)画出该森林的带右链的先根次序表示法；(4)(4分)画出该森林带度数的后根次序表示法；(5)(4分)在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。
写出以结点x为根的子树在后根次序序列中的前驱的求法。
(用语言叙述，不用写算法。
)【山东大学1998八(16分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)(2)(3)森林的带右链的前序表示法。
在前序序列中，任何结点的子树的所有结点都直接跟在该结点之后；每棵子树的所有结点都聚集在一起，中间不会插入其他结点；任何分支结点后面跟的是它的第一个子女。
故结点可采用如下结构(1tag，data，rlink)。
其中，ltag为左标记，ltag=1表示该结点无子女或二叉树无左子女，Itag=0表示其后存储其第一子女或二叉树的左子女；data是结点的数据；rlink指向下一兄弟或二叉树的右子女。
用左标记代替左指针，占用存储单元少，不会丢失信息。
本题森林的带右链的前序表示法为(注：“下标”行不是结点成分)：(4)带度数的后根次序表示法。
在后序序列中，任何一棵子树的结点聚在一起，根结点在最后。
结点按后根次序顺序存储在一片连续的存储单元中，结点结构可描述为：(data，degree)。
(5)该森林带度数的后根次序表示法如下：后根次序序列中任何一棵子树的结点个数减边数为1。
设某结点的度degree=m，即该结点有m个子女，最右边的子女就是该结点的前驱。
在后根次序表示法中最后的第2个子女是最右子女为根的子树的前驱，以结点x为根的子树的前驱求法如下：令q=0，从x开始从后往前走，每经过一个结点z，作q=q++-degree(z)；到q=1时，再往前走一个结点就是以结点x)解析：6.设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。
(1)试画出该二叉树。
(2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。
(3)设具有4个结点的二叉树的前序遍历序列为abcd；S为长度等于4的由a，b，c，d排列构成的字符序列，若任取S作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么?试列出具有4个结点二叉树的全部形态及相应的中序遍历序列。
【浙江大学1997六(15分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(2)设二叉树的前序遍历序列为P1，P2，…，Pm，中序遍历序列为S1，S2，…，Sm。
因为前序遍历是“根一左一右”，中序遍历是“左一根一右”，则前序遍历序列中第一个结点P1是根结点。
到中序序列中查询到Si=P1，根据中序遍历时根结点将中序序列分成左右两部分的原则，有：若i=1，即S1=P1，则这时的二叉树没有左子树；否则，S1，S2，…，Si一1是左子树的中序遍历序列，用该序列和前序序列p2，P3，…，Pi去构造该二叉树的左子树。
若i=m，即Sm=P1，则这时的二叉树没有右子树；否则，Si+1，Si+2，…，Sm是右子树的中序遍历序列，用该序列和前序序列中Pi+1，Pi+2，…，Pm，、去构造该二叉树的右子树。
算法描述请参见下面算法设计题第49题。
(3)若前序序列是abed，并非由这四个字母的任意组合(4 1=24)都能构造出二叉树、因为以abed为输入序列，通过栈只能得到1／n+1)*2n!／(n!*n!)=14种，即以abcd为前序序列的二叉树的数目是14。
任取以abed作为中序遍历序列，并不全能与前序的abed序列构成二叉树。
例如：若取中序序列dcab就不能。
该14棵二叉树的形态及中序序列略。
)解析：7.假设一棵二叉树的前序序列为ABCD，它的中序序列可能是DABC吗?【石油大学1998一、1(5分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：不能。
因DABC并不是ABCD的合法出栈序列)解析：8.已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。
【重庆大学2000二、2】（分数：2.00）__________________________________________________________________________________________正确答案：()解析：9.已知一棵二叉树T的诸结点在先根次序下的排列为:ABCEDFGHI，在中根次序下的排列为：ECBDFAHIG，画出此树形状并给出其后根序列。
【吉林大学2007二、3(3分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：二叉树略，其后根序列为：ECFDBIHGA。
)解析：10.在某二叉树上进行前序、中序遍历后发现该二叉树的前序序列的最后一个结点和中序序列的最后一个结点是同一个结点。
请问该结点具有何种性质?为什么?【上海交通大学2003五(10分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：该结点应是二叉树最右边的叶子结点。
因为前序遍历是“根一左一右”，中序遍历是“左一根一右”，只有在最右边的叶子处，前序和中序遍历才能是同一个结点。
)解析：11.在二叉树上进行前序遍历时，结点A在结点B之前，而在进行后序遍历时，结点A在结点B之后，那么结点A是结点B的祖先，对吗?为什么?【上海交通大学2003六(10分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：正确。
前序遍历是“根一左一右”，后序遍历是“左一右一根”。
前序遍历结点A 在结点B之前，说明结点A到B有路径，或A在B的左面。
后序遍历结点A在结点B之后，说明结点A到B有路径，或A在右面，B在左面。
