1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 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.6D.73.设有一表示算术表达式的二叉树(见图 3-1)，它所表示的算术表达式是_
2、。 （分数：2.00）A.A+B+C(D*E)+(FG)B.(A*B+C)(D*E)+(FG)C.(A+B+C)(D*E+(FG)D.A*B+CD*E+FG4.在下述结论中，正确的是_。【南京理工大学 1999 年】只有一个结点的二叉树的度为 0：二叉树的度为 2；二叉树的左右子树可任意交换：深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。（分数：2.00）A.B.C.D.5.若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是_。【北京工商大学 2001 年】（分数：2.00）A.9B.11C.15D.不确定6.具有 10 个叶结点的二
3、叉树中有_个度为 2 的结点。【北京航空航天大学 2000 年】（分数：2.00）A.8B.9C.10D.117.一棵完全二叉树上有 1001 个结点，其中叶_了结点的个数是_。【西安交通大学 1996 年】（分数：2.00）A.250B.500C.254D.505E.以上答案都不对8.若一棵深度为 6 的完全二叉树的第 6 层有 3 个叶子结点，则该二叉树共有个叶了结点。【北京航空航天大学 2003 年】（分数：2.00）A.17B.18C.19D.209.有关二叉树下列说法正确的是_。【南京理工大学 2000 年】（分数：2.00）A.二叉树的度为 2B.一棵二叉树的度可以小于 2C.二叉
4、树中至少有一个结点的度为 2D.二又树中任何一个结点的度都为 210.二叉树的第 i 层上最多含有结点数为_。【北京理工大学 2001 年】（分数：2.00）A.2 iB.2 i-1 一 1C.2 i-1D.2 i 一 111.当结点数目一定时，具有最小深度的二又树是_。【北京航空航天大学 2005 年】（分数：2.00）A.满二叉树B.完全二叉树C.线索二叉树D.二叉排序树12.一棵具有 n 个结点的完全二又树的树高度(深度)是_。【南京理工大学 1996 年】（分数：2.00）A.log 2 n+1B.log 2 n+1C.log 2 nD.log 2 n 一 113.一棵深度为 4 的完
5、全二叉树，最少有_个结点。【华南理工大学 2005 年】（分数：2.00）A.4B.8C.15D.614.一棵树高为 k 的完全二叉树至少有_个结点。【南京理工大学 1998 年】（分数：2.00）A.2 k 1B.2 k-1 一 1C.2 k-1D.2 k15.有 n 个结点的二叉树的深度最小值是_。【华中科技大学 2006 年】（分数：2.00）A.log 2 (n)B.log 2 (n+1)C.log 2 (n+1)D.log 2 (n)16.在一棵高度为 k 的满二叉树中，结点总数为_。【北京工商大学 2001 年】（分数：2.00）A.2 k-1B.2 kC.2 k 一 1D.log
6、2 k +117.一棵深度为 7 的满二叉树共有_个非终端结点。【北京邮电大学 2007 年】（分数：2.00）A.31B.63C.127D.25518.有 n 个结点，并且高度为 n 的二叉树的数目为_。【华中科技大学 2007 年】（分数：2.00）A.log 2 nB.n2C.nD.2 n-119.下列判断中_是正确的。【华南理工大学 2006 年】（分数：2.00）A.深度为 k 的二叉树最多有 2 k-1 个结点(k1)，最少有 k 个结点B.二叉树中不存在度大于 2 的结点C.对二叉树遍历是指先序、中序或后序遍历中的一种D.构造线索二叉树是为能方便找到每个结点的双亲20.以下说法中
7、_是正确的。【华南理工大学 2006 年】（分数：2.00）A.完全二叉树中，叶结点的双亲的左兄弟(如果存在)一定不是叶结点B.任何一棵二叉树，终端结点数为度为 2 的结点数减 1C.二叉树不适合用顺序结构存储D.结点按层序编号的二叉树，第 i 个结点的左孩子(如果存在)的编号为 2i21.利用二叉链表存储树，则根结点的右指针是_。【青岛大学 2001 年】（分数：2.00）A.指向最左孩子B.指向最右孩子C.空D.非空22.当一棵有 n 个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 AL,n中时，数组中第 i 个结点的左孩子为_。【南京理工大学 1999 年】（分数：2.
8、00）A.A2i(2in)B.A2i+1(2i+1n)C.Ai2D.无法确定23.一棵有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 ALn中，则二又树中第 i(i 从 1 开始用上述方法编号)个结点的右孩予在数组 A 中的位置是_。【南京理工大学 2000年】（分数：2.00）A.A2i(2in)B.A2i+1(2i+1n)C.Ai-2D.条件不充分，无法确定24.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用_遍历方法最合适。【北京航空航天大学 1999 年】（分数：2.00）A.前序B.中序C.后序D.按层次25.树的后根遍历序列等同于
9、该树对应的二叉树的_。【湖南大学 2008 年】（分数：2.00）A.先序序列B.中序序列C.后序序列D.层次遍历26.已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为 ABCDEFGH，该完全二叉树的后序遍历序列为_。【北京航空航天大学 2002 年】（分数：2.00）A.HDEBFGCAB.HEDBFGCAC.HDEBAFGCD.HDEFGBCA二、综合题(总题数：16，分数：32.00)27.假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树 BT 中，写出计算该算术表达式值的算法。【东北大学 2000 年】（分数：2.00）_28.假定用两个一维数组 LN和 RN
10、作为有 N 个结点 1，2，N 的二叉树的存储结构。Li和 Rj分别指示结点 i 的左儿子和右儿子，Li=0(Ri=0)表示 i 的左(右)儿子为空。试写一个算法，由 L 和 R 建立一个一维数组 Tn，使 Ti存放结点 i 的父亲；然后再写一个判别结点 U 是否为结点 V 的后代的算法。【哈尔滨工业大学 1999 年】（分数：2.00）_29.已知一棵二叉树按顺序方式存储在数组 A1，n中。设计算法，求出下标分别为 i 和 j 的两个结点的最近的公共祖先结点的值。【武汉大学 2000 年】（分数：2.00）_30.有 n 个结点的完全二叉树存放在一维数组 A1,n中，试据此建立一棵用二叉链表
11、表示的二叉树，根由tree 指向。【南京理工大学 1998 年】（分数：2.00）_31.已知深度为 h 的二叉树采用顺序存储结构_已存放于数组 BT12 h 一 1中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1ehild，data，rehild)，根结点所在链结点的指针由 T 给出。【北京航空航天大学 2007 年】（分数：2.00）_32.编写递归算法，依据树的双亲表示法及其根结点创建树的孩子一兄弟链表存储结构。【清华大学 1995年】（分数：2.00）_33.编程，判断一棵二叉链表表示的二又树是否是完全二叉树。【南京航空航天大学 2001 年】（分数：2
12、.00）_34.二叉树采用二叉链表存储。1)编写计算整个二叉树高度的算法(二叉树的高度也称为二叉树的深度)。2)编写计算二叉树最大宽度的算法(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。【西北大学2001 年】（分数：2.00）_35.在二叉树中查找值为 x 的结点，试编写算法(用 c 语言)打印值为 x 的结点的所有祖先，假设值为 x 的结点不多于一个。【上海交通大学 1998 年】（分数：2.00）_36.设一棵完全二叉树使用顺序存储结构存放在数组 btL,n中，请写出进行非递归的前序遍历算法。【西安电子科技大学 1998 年】（分数：2.00）_37.设计算法返回二叉树 T 的
13、先序序列的最后一个结点的指针，要求采用非递归形式，且不允许用栈。【合肥工业大学】999 年】（分数：2.00）_38.对于二叉树的链接实现，完成非递归的中序遍历过程。【中山大学 1999 年】（分数：2.00）_39.试给出二叉树的自下而上、自右而左的层次遍历算法。【吉林大学 2001 年】（分数：2.00）_40.已知一二叉树中结点的左、右孩子为 left 和 right，p 指向二叉树的某一结点。请用 C 语言编写一个非递归函数 postfirst(p)，求 p 所对应子树的第一个后序遍历结点。【浙江大学 1998 年】（分数：2.00）_41.请设计一个算法，要求该算法把二叉树的叶子结点
14、按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。【华南师范大学 1999 年】（分数：2.00）_42.设两棵二叉树的根结点地址分别为 p 和 q，采用二叉链表的形式存储这两棵树上所有的结点。请编写程序，判断它们是否相似。【上海交通大学 2000 年】【北京航空航天大学 2005 年】（分数：2.00）_计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 3答案解析(总分：84.00，做题时间：90 分钟)一、单项选择题(总题数：26，分数：52.00)1.树是一种逻辑关系，表示数据元素
15、之间存在的关系为_。【北京交通大学 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+12 十
16、 2.1+x0+1，解得 X=6。3.设有一表示算术表达式的二叉树(见图 3-1)，它所表示的算术表达式是_。 （分数：2.00）A.A+B+C(D*E)+(FG)B.(A*B+C)(D*E)+(FG)C.(A+B+C)(D*E+(FG) D.A*B+CD*E+FG解析：解析：考查二又树表示算术表达式的方法。叶子结点表示运算值，非叶子结点表示运算符，运算符的子结点或子树即该运算符的运算值。4.在下述结论中，正确的是_。【南京理工大学 1999 年】只有一个结点的二叉树的度为 0：二叉树的度为 2；二叉树的左右子树可任意交换：深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。（分数
17、：2.00）A.B.C.D. 解析：解析：考查二叉树的相关概念。二叉树的度最多为 2，可以比 2 小。二叉树的左有了树是有顺序的，不可随意交换。完全二叉树从最底层右边起比层数相同的满二叉树连续缺失若干个叶结点。5.若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是_。【北京工商大学 2001 年】（分数：2.00）A.9B.11 C.15D.不确定解析：解析：考查二叉树结点数和度的关系。二叉树结点度数最多为 2。设度为 0 的结点个数为 x，根据“树中结点数等于所有结点度数和加 1”，可得 10+5+X=10*2+5+1+X*0+1，解得 x=11。6
18、.具有 10 个叶结点的二叉树中有_个度为 2 的结点。【北京航空航天大学 2000 年】（分数：2.00）A.8B.9 C.10D.11解析：解析：考查二叉树结点数和度的关系。根据“非空二叉树卜叶子结点数等于度为 2 的结点数加 1”，所以选 B。7.一棵完全二叉树上有 1001 个结点，其中叶_了结点的个数是_。【西安交通大学 1996 年】（分数：2.00）A.250B.500C.254D.505E.以上答案都不对 解析：解析：考查完全二叉树叶子结点数的计算。对完全二叉树按从上到下、从左到右的顺序进行编号1，2，N，第 1001 个结点的父结点编号为10012=500，此后的所有结点都没
19、有孩子结点，即为叶子结点。叶子结点数为 1001-500=501。8.若一棵深度为 6 的完全二叉树的第 6 层有 3 个叶子结点，则该二叉树共有个叶了结点。【北京航空航天大学 2003 年】（分数：2.00）A.17 B.18C.19D.20解析：解析：考查完全二叉树叶子结点数的计算。第 5 层共有结点 24 个，即 16 个叶子结点。第 6 层最左边有 3 个叶子结点，对应第 5 层最左边两个结点，所以第 5 层右边有 162=14 个叶子结点，加上第 6 层3 个，共 17 个叶予结点。9.有关二叉树下列说法正确的是_。【南京理工大学 2000 年】（分数：2.00）A.二叉树的度为 2
20、B.一棵二叉树的度可以小于 2 C.二叉树中至少有一个结点的度为 2D.二又树中任何一个结点的度都为 2解析：解析：考查二叉树的相关概念。二叉树的度至多为 2，可以小于 2。当二叉树只有一个结点时，度为 0。10.二叉树的第 i 层上最多含有结点数为_。【北京理工大学 2001 年】（分数：2.00）A.2 iB.2 i-1 一 1C.2 i-1 D.2 i 一 1解析：解析：考查二叉树一层结点最大数。第 i 层最多含有结点数为 2 i-111.当结点数目一定时，具有最小深度的二又树是_。【北京航空航天大学 2005 年】（分数：2.00）A.满二叉树B.完全二叉树 C.线索二叉树D.二叉排序
21、树解析：解析：考查最小深度的二又树。当结点组成完全二叉树的时候，树的深度最小。满二叉树是完全二叉树的特殊情况。12.一棵具有 n 个结点的完全二又树的树高度(深度)是_。【南京理工大学 1996 年】（分数：2.00）A.log 2 n+1 B.log 2 n+1C.log 2 nD.log 2 n 一 1解析：解析：考查完全二叉树高度的计算。具有 n 个结点的完全二叉树的高度为10g2(n+1)或log 2 n+1。13.一棵深度为 4 的完全二叉树，最少有_个结点。【华南理工大学 2005 年】（分数：2.00）A.4B.8 C.15D.6解析：解析：考查完全二叉树的结点数。深度为 4 的
22、完全二叉树，前 3 层结点总数为 2 3 一 1=7。第 4 层只有一个结点时，完全二叉树结点数最少。即 8 个。14.一棵树高为 k 的完全二叉树至少有_个结点。【南京理工大学 1998 年】（分数：2.00）A.2 k 1B.2 k-1 一 1C.2 k-1 D.2 k解析：解析：考查完全二叉树的结点数。15.有 n 个结点的二叉树的深度最小值是_。【华中科技大学 2006 年】（分数：2.00）A.log 2 (n)B.log 2 (n+1)C.log 2 (n+1) D.log 2 (n)解析：解析：考查二叉树深度最小值。当结点组成完全二叉树的时候，树的深度最小。16.在一棵高度为 k
23、 的满二叉树中，结点总数为_。【北京工商大学 2001 年】（分数：2.00）A.2 k-1B.2 kC.2 k 一 1 D.log2 k +1解析：解析：考查满二叉树的结点数。考生只要记住公式即可。17.一棵深度为 7 的满二叉树共有_个非终端结点。【北京邮电大学 2007 年】（分数：2.00）A.31B.63 C.127D.255解析：解析：考查满二叉树非终端结点的计算。深度为 n 的满二叉树结点个数为 2 n -1，叶予结点个数为2 n-1 ，非终端结点个数为 2 n-1 -1。18.有 n 个结点，并且高度为 n 的二叉树的数目为_。【华中科技大学 2007 年】（分数：2.00）A
24、.log 2 nB.n2C.nD.2 n-1 解析：解析：考查二叉树的树形。由题可得，每层有一个结点，从根结点往下，每个结点都有作左孩子、右孩子两种情况，由概率知识可得，二叉树共有 2 n-1 种树形。19.下列判断中_是正确的。【华南理工大学 2006 年】（分数：2.00）A.深度为 k 的二叉树最多有 2 k-1 个结点(k1)，最少有 k 个结点B.二叉树中不存在度大于 2 的结点 C.对二叉树遍历是指先序、中序或后序遍历中的一种D.构造线索二叉树是为能方便找到每个结点的双亲解析：解析：考查二叉树的各种性质。二叉树的遍历有各种不同的方法，比如层次遍历。引入线索二叉树是为了方便找到结点在
25、某个遍历序列中的前驱和后继结点。20.以下说法中_是正确的。【华南理工大学 2006 年】（分数：2.00）A.完全二叉树中，叶结点的双亲的左兄弟(如果存在)一定不是叶结点 B.任何一棵二叉树，终端结点数为度为 2 的结点数减 1C.二叉树不适合用顺序结构存储D.结点按层序编号的二叉树，第 i 个结点的左孩子(如果存在)的编号为 2i解析：解析：考查二叉树的各种性质。非空二叉树卜叶子结点数等于度为 2 的结点数加 1，二叉树可以使用顺序结构存储。D 中性质只针对完全二叉树。21.利用二叉链表存储树，则根结点的右指针是_。【青岛大学 2001 年】（分数：2.00）A.指向最左孩子B.指向最右孩
26、子C.空 D.非空解析：解析：考查二又链表存储树。根结点的右指针为空。22.当一棵有 n 个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 AL,n中时，数组中第 i 个结点的左孩子为_。【南京理工大学 1999 年】（分数：2.00）A.A2i(2in)B.A2i+1(2i+1n)C.Ai2D.无法确定 解析：解析：考查二叉树的顺序存储。完全二叉树时，第 i 个结点的左孩了编号为 2i，普通二叉树并无此规律。23.一棵有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 ALn中，则二又树中第 i(i 从 1 开始用上述方法编号)个结点的右孩予在数组 A
27、中的位置是_。【南京理工大学 2000年】（分数：2.00）A.A2i(2in)B.A2i+1(2i+1n)C.Ai-2D.条件不充分，无法确定 解析：解析：考查二叉树的顺序存储。完全二叉树时，第 i 个结点的右孩子编号为 2i+1，普通二叉树并无此规律。24.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用_遍历方法最合适。【北京航空航天大学 1999 年】（分数：2.00）A.前序B.中序C.后序 D.按层次解析：解析：考查二叉树各种遍历顺序。要交换分支结点的左右子树，应该最后才访问分支结点。应采用后序遍历。25.树的后根遍历序列等同于该树对应的二叉树的_。【湖南大
28、学 2008 年】（分数：2.00）A.先序序列B.中序序列 C.后序序列D.层次遍历解析：解析：考查树的遍历与二叉树遍历的对应。树和森林的遍历，可采用对应二叉树的遍历算法来实现，见表 3-1。26.已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为 ABCDEFGH，该完全二叉树的后序遍历序列为_。【北京航空航天大学 2002 年】（分数：2.00）A.HDEBFGCA B.HEDBFGCAC.HDEBAFGCD.HDEFGBCA解析：解析：考查完全二叉树的存储和后序遍历序列。按照顺序结构建立二叉树，然后按照后序遍历顺序遍历该二叉树。二、综合题(总题数：16，分数：32.00)2
29、7.假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树 BT 中，写出计算该算术表达式值的算法。【东北大学 2000 年】（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：以二叉树表示算术表达式，根结点用于存储运算符。先分别求出左子树和右子树表示的子表达式的值，最后根据根结点的运算符的要求，计算出表达式的最后结果。算法的代码： typedef struct node( float val； char optr； 只取“+“， “一“， “*“， “ struct node *lchild， *rchild BiNode，*BiTree; float PostEval(BiT
30、ree bt) 以后序遍历算法求以二叉树表示的算术表达式的值 float lv，rv； if(bt 一lchild=NULL bt 一rchild=NULL) return bt 一val； e1Se lv=PostEval(bt-ichiid); 求左子树表示的子表达式的值 rv=PostEval(bt-rchiid)； 求右了树表示的子表达式的值 switch(bt 一optr) Case“+“：valUe=lv+rv： break; Case“一“：valUe=1Vrv： break; case“*“：valme=1v*rv： break; Case“：valUe=1vrv： retur
31、n valUe； PoStEval)解析：28.假定用两个一维数组 LN和 RN作为有 N 个结点 1，2，N 的二叉树的存储结构。Li和 Rj分别指示结点 i 的左儿子和右儿子，Li=0(Ri=0)表示 i 的左(右)儿子为空。试写一个算法，由 L 和 R 建立一个一维数组 Tn，使 Ti存放结点 i 的父亲；然后再写一个判别结点 U 是否为结点 V 的后代的算法。【哈尔滨工业大学 1999 年】（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：由指示结点 i 左儿子和右儿子的两个一维数组 Li和 Ri，建立指示结点 i 的双亲的一维数组 Ti。若结点 i 的左了女是 L，则结点
32、 L 的双亲是结点 i，若 i 的右子女是 r，则 r 的双亲是 i。根据 T 数组，判断结点 u 足否是结点 V 后代的算法，转为判断结点 V 是否是结点 u 的祖先的问题。算法的代码： int Generation(int u，int v，int N，int L，int R，int T) L和 R是含有 N 个元素且指示二叉树结点 i 左儿子和右儿子的一维数组 本算法据此建立结点 i 的双亲数组 T，并判断结点 U 是否是结点 v 的后代 for(i=1 ; ij) i=i2 ; 下标为 i 的结点的双亲结点的下标 e1Se J=j2； 下标为 j 的结点的双亲结点的下标 printf(“
33、所查结点的最近公共祖先的下标为d，值为d“，i，Ai)， 设元素类型为整型 AnCeStor)解析：30.有 n 个结点的完全二叉树存放在一维数组 A1,n中，试据此建立一棵用二叉链表表示的二叉树，根由tree 指向。【南京理工大学 1998 年】（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：利用递归算法，先建立根的链结点表示，然后分别以根结点的孩子(左右子树的根)为根建立左右子树。算法的代码： BiTree Creat(E1emType A，int i) n 个结点的完全二叉树存于一维数组 A 中 本算法据此建立以二叉链表表示的完全二叉树 BiTree tree ; if(i
34、data=Ai; if(2*in) tree 一1child=NULL; e1Se tree 一-child=Creat(A，2*i)； if(2*i+1n) tree 一rchild=NULL： e1Se tree一rchild=Creat(A，2*i+1); return tree； /Creat 初始调用时，i=1。)解析：31.已知深度为 h 的二叉树采用顺序存储结构_已存放于数组 BT12 h 一 1中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1ehild，data，rehild)，根结点所在链结点的指针由 T 给出。【北京航空航天大学 2007 年
35、】（分数：2.00）_正确答案：(正确答案：二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的，不是完全二叉树的二叉树顺序存储时，要加“虚结点”。数组中的第一个元素是根结点。算法的基本设计思想：采用队列结构，先建立根结点入队。当队列不空时循环执行以下步骤：队头结点出队，如果有左孩子，则建立左孩子结点并入队；如果有右孩子，则建立右孩子结点并入队。算法的代码： typedef struct BiTree bt： 二叉树结点指针 int num； num 是结点在一维数组中的编号 tnode tnode Qmaxsize； 循环队列，容量足够大 void creat(BiTree T，E1
36、emType BT，int h) 深度为 h 的二叉树存于一维数组 BT12 h 一 1中 本算法生成该二叉树的二叉链表存储结构 tnode tq； tq 是队列元素 int len=pow(2，h)一 1; 数组长度 T=(BiTree)malloc(Si zeof(BiNode);申请结点 T一data=BT1； 根结点数据 tqbt=T; tqnum=1; Q1=tq； 根入队列 front=0； 循环队列头、尾指针 rear=1; while(front!=rear) 当队列不空时循环 front=(front+1)maxsi ze; tq：Qfront； 出队，取出结点及编号 p=t
37、qbt； i=tqnum； if(BT2+i=“#“2*ilen) 左子树为空，“#“，表示虚结点 P 一ichild=NULL; else 建立左子女结点并入队列 p 一lchiid=(BiTree)melloc(Sizeof(BiNode); p-ichild-data=BT2*i； 左子女数据 tqbt=P 一1child; tqnum=2*i； rear=(rear+1)maxsize; 计算队尾位置 Qrear=tq； 左子女结点及其编号入队 if(BT2*i+1=“#“2*i+1len) p-rchild=NULL; 右子树为空 e1Se 建立右子女结点并入队列 P 一rchild
38、=(BiTree)mallOC(Si Zeof(BiNode); P 一rchild 一data=BT2*i+1; tqbt=P 一rchild： tqnum=2*i+1; rear=(rear+1)maxsi ze； 计算队尾位置，右子女及其编号入队 Qrear=tq； while Creat 本题中的虚结点用“#“表示，应根据二叉树的结点数据的类型而定。)解析：32.编写递归算法，依据树的双亲表示法及其根结点创建树的孩子一兄弟链表存储结构。【清华大学 1995年】（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：首先给出根结点在双亲表示法中的下标，找根结点的子女要遍历双亲表示法
39、的整个静态链表，根结点的第一个子女是孩子兄弟表示法中的孩子，其他子女结点作兄弟。对双亲表示法中的任一结点，均递归建立其孩子兄弟链表子树。算法的代码： CSTree PtreeToCStree(PTree pt，int root) 本算法将双亲表示法的树 pt 转为孩子兄弟链表表示的树 root 是根结点在双亲表示法中的下标 CSTree child，Sibling； int firstchild； CSTree cst=(CSTree)mall0(2(SiZeof(CSNode); cst 一data=ptnodesrootdata;根结点 Cst 一firstchilct=NULL; cst
40、 一nextsibling=NULL； firstchild=1 ; for(i=1; ifirstchild=child； firStchild=0 ; sibling=cst 一firstch1d； e1Se child 不是root 的第一个孩子，作兄弟处理 Sibling 一nextsibling=chiid； Sibling=sibling 一nextsibling; )if end for return cst; PtreetoCStree)解析：33.编程，判断一棵二叉链表表示的二又树是否是完全二叉树。【南京航空航天大学 2001 年】（分数：2.00）_正确答案：(正确答案：算
41、法的基本设计思想：判定是否是完全二叉树，可以使用队列进行从上至下、从左至右的层次遍历，当首次出现叶子结点或无右孩子结点后，后面全部都应该是叶子结点。同时在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。算法的代码： int JudgeComplete(BiTree bt) 判断二叉树是否是完全二叉树，如是，返回 1，否则，返回 0 int tag=0； BiTree p=bt，Q； Q 是队列，元素是二叉树结点指针，容量足够大 if(p=NULL) return 1; QueueInit(Q)； QueueIn(Q，p)； 初始化队列，根结点指针入队 while(!QueueEmpty(Q) p=QueueOut(Q); 出队 if(p 一1chiid!tag) QueueIn(Q，p 一ichild); 左子女入队 e1Se if(p 一ichiid) 前边已有结点为空，本结点不空 return 0； else 首次
