计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编4
(总分74, 做题时间90分钟)
6. 综合题
1. 
(1)试出满足下列条件的二叉树：1)先序序列与后序序列相同2)中序序列与后序序列相同3)先序序列与中序序列相同4)中序序列与层次遍历序列相同(2)已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA，画出这棵二叉树。【东北大学1999六(4分)】【东南大学2000一、4(6分)】
2. 
分别给出满足下列条件的二叉树。(1)前序和中序遍历结果相同；(2)前序和中序遍历结果不相同而是相反；(3)中序和后序遍历结果相同；(4)前序和后序遍历结果相同。【四川大学2004】【烟台大学2007四、2(8分)】
3. 
将下列由三棵树组成的森林转换为二叉树(只要求给出转换结果)。【南京航空航天大学1998一(10分)】
4. 
设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：AB D，C E G H  中序遍历序列：B FDAG E H C(1)画出这棵二叉树。(2)画出这棵二叉树的后序线索树。(3)将这棵二叉树
转换成对应的树(或森林)。【南京航空航天大学1997二(10分)】
5. 
已知一棵二叉树的对称序和后序序列如下：对称序：GLDHBEIACJFK  后序：LGHDIEBJKFCA(1)(2分)给出这棵二叉树；(2)(2分)转换为对应的森林；(3)(4分)画出该森林的带右链的先根次序表示法；(4)(4分)画出该森林带度数的后根次序表示法；(5)(4分)在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。写出以结点x为根的子树在后根次序序列中的前驱的求法。(用语言叙述，不用写算法。)【山东大学1998八(16分)】
6. 
设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。(1)试画出
该二叉树。(2)写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。(3)设具有4个结点的二叉树的前序遍历序列为abcd；S为长度等于4的由a，b，c，d排列构成的字符序列，若任取S作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么?试列出具有4个结点二叉树的全部形态及相应的中序遍历序列。【浙江大学1997六(15分)】
7. 
假设一棵二叉树的前序序列为ABCD，它的中序序列可能是DABC吗?【石油大学1998一、1(5分)】
8. 
已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。【重庆大学2000二、2】
9. 
已知一棵二叉树T的诸结点在先根次序下的排列为:ABCEDFGHI，在中根次序下的排列为：ECBDFAHIG，画出此树形状并给出其后根序列。  【吉林大学2007二、3(3分)】
10. 
在某二叉树上进行前序、中序遍历后发现该二叉树的前序序列的最后一个结点和中序序列的最后一个结点是同一个结点。请问该结点具有何种性质?为什么?【上海交通大学2003五(10分)】
11. 
在二叉树上进行前序遍历时，结点A在结点B之前，而在进行后序遍历时，结点A在结点B之后，那么结点A是结点B的祖先，对吗?为什么?【上海交通大学2003六(10分)】
12. 
某二叉树的后序遍历序列为：，φ，φ，A，φ，φ，E，φ，φ，C D，B，其中φ表示空格符，代表空二叉树。能否以此序列作为输入创建二叉树?如不能，请说明理由；如能够，试画出对应二叉树。【华中科技大学2007三、23(8分)】
13. 
输入带空二叉树信息(O)的前序遍历序列：A，G，φ，φ，B，φ，C，D，E，φ，E φ，φ，φ，E φ，φ建立一棵二又树，其中φ表示空格符，代表空二叉树，试画出该二叉树。【华中科技大学2006三、1(6分)】
14. 
已知某二叉树的每个结点，要么其左、右子树皆为空，要么其左、右子树皆不空。又知该二叉树的前序序列为(即先根次序)：J、F、D、B、A、C、E、H、X、I、K；后序序列为(即后根次序)：A、C、B、E、D、X、，、H、F、K、，。请给出该二叉树的中序序列(即中根次序)。【上海交通大学2001二(8分)】
15. 
假设一棵二叉树的层次序列为ABCDEFGHIJ，中序序列DBGEHJACIF。请画出这棵二叉树。【武汉大学2000三、1】【东南大学2000一、1(6分)】【大连理工大学2005二、3(20／4分)】【中国海洋大学2007一、5(8分)】
16. 
已知一个森林的先序序列和后序序列如下，请构造出该森林。先序序列：ABCDEFGHIJKLMNO后序序列：CDEBFHIJGAMLONK【合肥工业大学2000四、1(5分)】
先序中序后序遍历二叉树
17. 
画出同时满足下列两条件的两棵不同的二叉树。(1)按先根序遍历二叉树顺序为ABCDE。(2)高度为5其对应的树(森林)的高度最大为4。【东北大学1 997一、3(5分)】
18. 
用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。【西安电子科技大学1999计算机应用一、6(5分)】
19. 
一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。先序序列为：一一CDE—GHI一K中序序列为：C B一一F A—J K I G后序序列为：一E F D B—J I H—A【电子科技大学2001三、1(5分)】【厦门大学2002七、l(6分)】
20. 
M叉树的前序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应?【中国人民大学2000一、2(4分)】
21. 
设树形T在后根次序下的结点排列和各结点相应的次数如下：后根次序：BDEFCGJKILHA次    数：XX4请画出T的树形结构图。【吉林大学2001一、2(4分)】
22. 
已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成?请简述原因。【西北大学2001三、6】
23. 
对于二叉树T的两个结点N1和N2，我们应该选择树T结点的前序、中序和后序中哪两个序列来判断结点n1必定是结点n2的祖先，并给出判断的方法。不需证明判断方法的正确性。【复旦大学1999五(10分)】
24. 
在二又树的前序遍历和中序遍历的递归算法中，最后一个递归调用语句在调用时所保留的参数有什么作用?如何清除最后这个递归语句?【北京邮电大学1994三(8分)】
25. 
在二叉树的Llink-一Rlink存储表示中，引入“线索”的好处是什么?【山东大学1999六、1(2分)】
26. 
按下面要求解下图中二叉树的有关问题：(1)对此二叉树进行后序后继线索化；(2)将此二叉树变换为森林；(3)用后根序遍历该森林，写出遍历后的结点序列。【北京邮电大学1996五(10分)】
27. 
一棵h层、度为k(k＞1)的树，最多有多少个结点?【北京科技大学2006】
设二叉树BT的存储结构如下：其中BT为树根结点的指针，其值为6，Lchild，Rchild分别为结点的左、右孩子指针域，data为结点的数据域。试完成下列各题：
28. 
画出二叉树BT的逻辑结构；
29. 
写出按前序、中序、后序遍历该二叉树所得到的结点序列；
30. 
画出二叉树的后序线索树。【中国矿业大学2000二(15分)】
31. 
请说明是否存在这样的二叉树，即它可以实现后序线索树进行后序遍历时不使用栈；而对前序线索树进行前序遍历时，又有什么样的二叉树可不使用栈。【西安电子科技大学1996二、
l(5分)】
32. 
一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少?【西安电子科技大学2000计算机应用一、2(5分)】
33. 
在前序线索树上，要出结点p的直接后继结点，请写出相关语句。结点结构为(1tag，lc，data，  nag，rc)。  【西北大学2000二、6(5分)】
34. 
对于后序线索二叉树，怎样查任意结点的直接后继；对于中序线索二叉树，怎样查任意结点的直接前驱?【西北工业大学1998一、4(4分)】
35. 
将下列树的孩子兄弟链表改为后根遍历全线索链表。【清华大学1994二(10分)】
36. 
若森林共有n个结点和b条边(b<n)，则该森林中有多少棵树?  【厦门大学20062(3)(20／3分)】
37. 
给定权W1，W2，…，Wm。说明怎样来构造一个具有最小的加权路径长度的k叉树。试对于权1，4，9，16，25，36，49，64，8l，100来构造最优的三叉树，并给出其最小加权路径长度。【北方交通大学1994四(12分)】

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。