《数据结构》期末考试复习题_第6章_树和二叉树.pdf

第六章树和二叉树一、选择题1.已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为A B O+D E/-,其前缀形式为()A.-A+B*C/D E B.-A+B*C D/E C.-+*A B C/D E D.-+A*B C/D E【北京航空航天大学19 9 9 一、3(2分)】2.算术表达式a+b*(c+d/e)转为后缀表达式后为()【中山 大 学 19 9 9 一、5A.ab+c d e/*B.ab c d e/+*+C.ab c d e/*+D.ab c d e*/+3.设有一表示算术表达式的二叉树(见下图)，它所表示的算术表达式是()GT _X-【南京理工大学19 9 9 一、20 (2分 (*/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 3 W 34.设树T 的度为4,其中度为1,2,3 和 4 的结点个数分别为4,2,1,1则 T 中的叶子数 为()A.5 B.6 C.7 D.8【南京理工大学20 0 0 一、8(1.5分】5.在下述结论中，正确的是()【南京理工大学19 9 9 一、4(1分】只有一个结点的二叉树的度为0；二叉树的度为2；二叉树的左右子树可任意交换；深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.B.C.D.6 .设森林F对应的二叉树为B,它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是()A.m-n B.m-n-1 C.n+1 D.条件不足，无法确定【南京理工大学20 0 0 一、17 (1.5 分 7.树是结点的有限集合，它(1)根结点，记为T。其余结点分成为m (m 0)个(2)的集合Tl,T 2,，T m,每个集合又都是树，此时结点T 称 为 T i 的父结点，T i 称 为 T的子结点(I W i W m)。一个结点的子结点个数称为该结点的(3)。二叉树与树是两个不同的概念，二叉树也是结点的有限集合，它(4)根结点。可以把树的根结点的层数定义 为 1,其他结点的层数等于其父结点所在层数加上1。令 T 是一棵二叉树，K i 和 K j 是 T中子结点数小于2 的结点中的任意两个，它们所在的层数分别为入K i 和入K j,当关系式|X Ki-X Kj|W1 一定成立时，则称T 为 一 棵(5)o 供选择的答案：(1)(4)A.有 0个 或 1 个B.有 0个 或 多 个 C.有且只有一个 D.有 1 个 或 1个以上(2)A.互不相交 B.允许相交(3)A.权 B.维数(5)A.丰满树 B.查找树C.允许叶结点相交D,允许树枝结点相交C.次数 D.序C.平衡树 D.完 全 树【上海海运学院19 9 9 二、2(5 分 8.若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点，则度为0的结点个数是()A.9 B.11 C.15 D.不 确 定【北京工商大学20 0 1.7(3分)】9.在一棵三元树中度为3 的结点数为2 个，度为2 的结点数为1 个，度 为 1 的结点数为2个，则度为0的结点数为（）个A.4 B.5 C.6 D.7【哈尔滨工业大学20 0 1二、2（2分】10 .设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为Ml,M2和 M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（）。【北方交通大学20 0 1 一、16 （2分】A.Ml B.M1+M2 C.M3 D.M2+M311.具 有 10 个叶结点的二叉树中有（）个度为2 的结点，【北京航空航天大学20 0 0 、5（2 分）】A.8 B.9 C.10 D.1112.一棵完全二叉树上有10 0 1个结点，其中叶子结点的个数是（）【西安交通大学19 9 6三、2（3 分）】A.250 B.50 0 C.254 D.50 5 E.以上答案都不对13.设给定权值总数有n个，其哈夫曼树的结点总数为（）【福 州 大 学 19 9 8 一、5（2分）】A.不确定 B.2n C.2n+l D.2n-l14.有 n个叶子的哈夫曼树的结点总数为（）。【青岛大学20 0 2二、1 （2 分】A.不确定 B.2n C.2n+l 1）.2n T15.若度为m的哈夫曼树中，其叶结点个数为n,则非叶结点的个数为（）。【中科院计算所 19 9 9 ,2（2 分】A .n-1 B .Ln/m J-1 C .（n T）/（m T）|D .n/（mT）】TE.F（n+1）/（m+l）|-l16 .有关二叉树下列说法正确的是（）【南京理工大学20 0 0 一、11（1.5分】A.二叉树的度为2 B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为217 .二叉树的第I 层上最多含有结点数为（）【中山大学19 9 8二、7 （2 分）】【北京理工大学20 0 1六、5（2 分】A.2 B.2 -1 C.2IH D.2 -118.个具有10 25个结点的二叉树的高卜为（）【南京理工大学19 9 9 一、19 （2 分】A.11 B.10 C.11 至 10 25 之间 1）.10 至 10 24 之间19 .一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（）结点A.2 h B.2 h-l C.2 h+l D.h+1 【南京理工大学 2 0 0 1 、1 1 （1.5分】2 0 .对于有n个结点的二叉树，其高度为（）【武汉交通科技大学1 996 一、5 （4分）】A.n l og 2 n B.l og 2 n C.Ll og2n J|+1 D.不确定2 1 .一棵具有n个结点的完全二叉树的树高度（深度）是（）【南京理工大学1 996 、8 （2 分】A.Ll og n J+1 B.l og n+1 C.Ll og n J D.l og n-12 2 .深度为h的满m叉树的第k层 有（）个结点。（l=k=3 （6分 A.结 点 数 B.叶 结 点 数 C.非 叶 结 点 数 D.度 为 2 的 结 点 数 E.需要一张n 个关键字的有序表F.需要对n 个关键字进行动态插入 G.需要n 个关键字的查找概率表 H.不需要任何前提6 2.下述编码中哪一个不是前缀码()。【中科院计算所20 0 0 一、2(2分】A.(0 0,0 1,1 0,1 1)B.(0,1,0 0,1 1)C.(0,1 0,1 1 0,1 1 1)1).(1,0 1,0 0 0,0 0 1)6 3.下面几个符号串编码集合中，不是前缀编码的是(A .0,1 0,1 1 0,1 1 1 1 B .1 1,1 0,0 0 1,1 0 1,0 0 0 1 C.0 0,0 1 0,0 1 1 0,1 0 0 0 D.b,c,aa,ac,aba,abb,a b c【西安电子科技大学20 0 1 应 用 一、6 (2分】6 4.当一棵有n 个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A l.n 中时，数组中第i 个结点的左孩子为()【南京理工大学1 9 9 9 一、1 8(2分】A.A 2i (2i=n)B.A 2i+1 (2i+l=n)C.A i/2 D.无法确定6 5.一 棵 有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A L.n 中，则二叉树中第i个 结 点(i 从 1 开始用上述方法编号)的右孩子在数组A中的位 置 是()A.A 2i (2i =n)B.A 2i+1 (2i+K=n)C.A i-2 D.条件不充分，无法确定【南京理工大学20 0 0 、4(1.5分】6 6.从下列有关树的叙述中，选出5 条正确的叙述(共5分)()A.二叉树中每个结点有两个子结点,而树无此限制，因此二叉树是树的特殊情况。B.当 K 与1 时高度为K的 二 叉 树 至 多 有 个 结 点。C.用树的前序周游和中序周游可以导出树的后序周游。D.线索二叉树的优点是便于在中序下查找前驱结点和后继结点。E.将一棵树转换成二叉树后,根结点没有左子树。F.棵含有N个结点的完全二叉树,它的高度是L L 0 G2N j+l oG.在二叉树中插入结点，该二叉树便不再是二叉树。H.采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。I .哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。J.用一维数组存储二叉树时，总是以前序周游存储结点。【山东工业大学1 9 9 5 三、(5分)】二、判断题1 .二叉树是度为2 的有序树。【长沙铁道学院1 9 9 7 -、3(1 分)】【中科院软件所1 9 9 7 、9(1 分)】2.完全二叉树一定存在度为1 的结点。【青岛大学20 0 2 一、4 (1 分】3 .对于有N个结点的二叉树，其高度为l o g 2n。【上海海运学院1 9 9 8 一、6 (1 分】4 .深度为K的二叉树中结点总数忘2-1。【南京航空航天大学19 9 5 五、1 (1分】5 .二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立)。【华南理工大学2 002 、7 (1分】6 .二叉树的遍历结果不是唯一的.【南京理工大学19 9 7二、8(2 分】7 .二叉树的遍历只是为了在应用中找到一种线性次序。【青岛大学2 001四、4 (1分】8 .树可用投影法进行中序遍历。【青岛大学2 002 一、6 (1分】9.一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。【上海海运学院1995 一、4(1 分】10.二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。【上海海运学院1995 一、6(1 分】11.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。【上海海运学院1996 一、6(1 分】12.对一棵二叉树进行层次遍历时，应借助于一个栈。【南京航空航天大学1995五、3(1分】13.用树的前序遍历和中序遍历可以导出树的后序遍历。【北京邮电大学1999二、3(2分】14.采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。【北京邮电大学2000、2(1 分)15.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。【上海海运学院1995 一、8(1 分】16.中序遍历二叉链存储的二叉树时；一般要用堆栈；中序遍历检索二叉树时，也必须使用堆栈。【上海海运学院1998、7(1 分】17.中序遍历-棵二叉排序树的结点就可得到排好序的结点序列【中科院软件所1999六、1-1(2 分】18.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。【长沙铁道学院1998一、2(1 分)】19.任何二叉树的后序线索树进行后序遍历时都必须用栈。【西安交通大学1996二、2(3分)】20.任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。【西安交通大学1996二、1 (3 分)】21.由一棵二叉树的前序序列和后序序列可以唯一确定它。【中科院软件所1997 一、3(1分】22.完全二叉树中，若一个结点没有左孩子，则它必是树叶。【东南 大 学 2001 1-8(1 分)】【中科院软件所1997、2(1 分】【山东大学2001-、4(1 分)】23.二叉树只能用二叉链表表示。【南京理工大学1997二、6(2 分】24.一 棵 有 n 个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i n),右儿子是2i+l(2i+l=l)。【燕 山 大 学 19 9 8 二、3 (2 分】3 1.必须把一般树转换成二叉树后才能进行存储。【南京航空航天大学19 9 7 一、4 (1分】3 2 .完全二叉树的存储结构通常采用顺序存储结构。【南京航空航天大学19 9 6 六、3 (1分】3 3 .将一棵树转成二叉树，根结点没有左子树：【北京邮电大学19 9 9 二、2 (2 分】3 4 .在二叉树中插入结点，则此二叉树便不再是二叉树了。【北京邮电大学2 000 一、5 (1分】3 5 .二叉树是一般树的特殊情形。【北京邮电大学2 000 一、9 (1 分)2 002 一、6 (1分】3 6 .树与二叉树是两种不同的树型结构。【东南 大 学 2 001 一、1-7 (1分】3 7 .非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子【合肥工业大学2 001二、5 (1分】3 8 .在任意一棵非空二叉排序树，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同。【中科院软件所1 997 、7 (1 分】3 9.度为二的树就是二叉树。【大连海事大学2 0 0 1 一、7 (1 分)】4 0 .深度为k具有n 个结点的完全二叉树，其编号最小的结点序号为 2 修+1。【东北 大 学 1 997 二、3 (2 分)】4 1 .下面二叉树的定义只有一个是正确的，请在正确的地方画“4,(1)它是由一个根和两株互不相交的、称为左子树和右子树的二叉树组成。(2)(a)在一株二叉树的级i 上，最大结点数是2 一(i l)(b)在一棵深度为k的二叉树中，最大结点数是2 1+1 (k 2 l)。(3)二叉树是结点的集合，满足如下条件：(a)它或者是空集；(b)或者是由一个根和两个互不相交的、称为左子树和右子树的二叉树组成。【中科院自动化所1 995、2 (6分】4 2 .在中序线索二叉树中，每一非空的线索均指向其祖先结点。【合肥工业大学2 0 0 0 二、5(1 分】4 3 .线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。【上海海运学院1 995,96,97 一、7 (1 分】4 4 .二叉树中序线索化后，不存在空指针域。【青岛大学2 0 0 0 四、3 (1 分】4 5.霍夫曼树的结点个数不能是偶数。【北京邮电大学2 0 0 0 一、6(1 分】4 6.一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。【合肥工业大学2 0 0 0二、4 (1 分)】4 7 .哈夫曼树无左右子树之分。【青岛大学2 0 0 0 四、8(1 分】4 8.当一棵具有n 个叶子结点的二叉树的WP L 值为最小时，称其树为H u f f ma n树，且其二叉树的形状必是唯一的。【南京航空航天大学1 995五、6(1 分】4 9.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。【北京邮电大学1 999二、5(2 分】50 .用 链 表(llink-r link)存储包含n 个结点的二叉树时，结点的2 n个指针区域中有n+1个空指针。()【上海海运学院1 999 一、6(1 分】三、填空题1.二叉 树 由(1),(2),(3)三个基本单元组成。【燕山 大 学 1 998、5(3 分】2 .树在计算机内的表示方式有 U1,（2）,（3）o【哈尔滨工业大学2 0 0 0 二、4 （3分）】3 .在二叉树中，指 针 p所 指 结 点 为 叶 子 结 点 的 条 件 是=【合肥工业大学1 999三、7（2分】4 .中 缀 式 a+b*3+4*（c-d）对 应 的 前 缀 式 为（1）,若 a=l,b=2,c=3,d=4,则后缀式d b/c c*a-b*+的运算结果为（2）.【西南交通大学2 0 0 0 一、65.二叉树中某一结点左子树的深度减去右子树的深度称为该结点的。【燕山大学1 998一、9（1 分）】6.具有2 56个结点的完全二叉 树 的 深 度 为。【燕 山 大 学 1 998 一、4 （1 分】7 .已知一棵度为3的树有2个度为1 的结点，3个度为2的结点，4个度为3的结点，则该树有 个叶子结点。【厦门大学2 0 0 0 六、2 （1 6%/3 分】8.深度为k的完全二叉树至少有（1）个结点,至多有（2）个结点。【厦门大学2 0 0 1 一、4 （1 4 M 5 分）】【南京理工 大 学 1 9 9 9 二、5 （4 分】9 .深度为H的完全二叉树至少有（1）个 结 点:至 多 有（2）个结 点:H和结点总数N之间的关系是（3）o【中科院计算所1 9 9 8 、3（3 分）1 9 9 9 二、4（3 分）】【中国科技大学1 9 9 8 、3（4分】1 0 .在顺序存储的二叉树中，编号为i 和 j的两个结点处在同一层的条件是。【厦门大学2 0 0 2 六、3（4 分】1 1 .在完全二叉树中，编号为i 和 j的两个结点处于同一层的条件是。【合肥工业大学2 0 0 0 三、6 （2分】1 2 .一棵有n个结点的满二叉 树 有（1）个度为1 的结点、有（2）个 分 支（非 终 端）结点 和（3）个叶子,该满二叉树的深度为（4）。【华中理工 大 学 2 0 0 0 、6 （3 分）1 3.假设根结点的层数为1,具有n个 结 点 的 二 叉 树 的 最 大 高 度 是。【北方交通大学2 0 0 1 二、1】1 4.在一棵二叉树中，度为零的结点的个数为N 0,度为2的结点的个数为N 2,则有N 0 =【北方交通大学2 0 0 1 二、6 【南京理工大学1 9 9 9 二、4（2分】1 5 .设只含根结点的二叉树的高度为0,则高度为k的二叉 树 的 最 大 结 点 数 为，最小结点数为。【北京 大 学 1 9 9 7-、1 （4 分】1 6 .设 有 N个结点的完全二叉树顺序存放在向量A 1:N 中，其下标值最大的分支结点为【长沙铁道学院1 9 9 7二、3（2 分）】1 7.高度为K的完全二叉树至少有 个叶子结点。【合肥工业大学1 9 9 9 二、6 （2分】1 8 .高度为8的完全二叉树至少有 个叶子结点。【合肥工业大学2 0 0 1 三、6 （2分】1 9 .已知二叉树有5 0 个叶子结点，则 该 二 叉 树 的 总 结 点 数 至 少 是。【厦门大学2 0 0 2 六、4（4 分】2 0 .一个有2 0 0 1 个 结 点 的 完 全 二 叉 树 的 高 度 为。【南京理工大学1 9 9 7三、2 （1 分】2 1.设 F是由T1,T2,T3三棵树组成的森林，与 F对应的二叉树为B,已知T1,T2,T3的结点数分别为n l,n 2 和 n 3则二叉树B的 左 子 树 中 有（1）个结点,右子树中有（2）个结点。【南京理工大学2 0 0 0 二、9 （3 分】2 2 .一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是（1）；编 号 是 i的结点所在的层次号是 （根所在的层次号规定为1 层）。【南京理工大学2 0 0 1 二、2 （2分】2 3.如某二叉树有2 0 个叶子结点，有 3 0 个结点仅有一个孩子，则该二叉树的总结点数为【南京理工大学2 0 0 1 二、3（2分】2 4.如果结点A 有 3 个兄弟，而且B是 A 的双亲，则 B的度是。【西安电子科技大学1 9 9 9 软 件 一、4（2分）】2 5 .高度为h的 2-3树 中 叶 子 结 点 的 数 目 至 多 为，【西安电子科技大学1 9 9 9 软 件 一、6 （2分】2 6 .完全二叉树中，结点个数为n,则 编 号 最 大 的 分 支 结 点 的 编 号 为。【北京轻工业学院2 0 0 0 一、3（2分）】2 7.设一棵完全二叉树叶子结点数为k,最后一层结点数2,则 该 二 叉 树 的 高 度 为。【北京科技大学1 9 9 8 一、3】2 8 .对于一个具有n个结点的二元树，当它为一棵（1）二元树时具有最小高度,当它为一棵（2）时,具有最大高度。【哈尔滨工业大学2 0 0 1 一、3（2 分）】2 9 .期一 N个结点的二叉树，采用二叉链表存储，共有 个空链域。【重庆大学2 0 0 0 一、8 30.8层完全二叉树至少有 个结点，拥 有 1 0 0 个结点的完全二叉树的最大层数为【西南交通大学2000二 1】3 1.含 4 个度为2的结点和5 个叶子结点的二叉树，可有 个度为1 的结点。【北京工业大学2 0 0 1 一、6 （2分）】32.一棵树T 中，包括一个度为1 的结点，两个度为2的结点，三个度为3 的结点，四个度为 4 的结点和若干叶子结点，则 T 的 叶 结 点 数 为。【山东大学2 0 0 1 三、2 （2分）】33.n （n大 于 1）个结点的各棵树中，其深度最小的那棵树的深度是（1）。它 共 有（2）个叶子结点和（3）个非叶子结点,其中深度最大的那棵树的深度是（4）,它 共 有（5）个叶子结点和（6）个非叶子结点。【山东大学2 0 0 1 三、7（2分）】34.每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是B E F C G D H,对称序列是F E B G C I 1 D,则它的后序序列是（1）。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是（2）。【山东工业大学1 9 9 7二、（6分）】35 .先根次序周游树林正好等同于按（1）周游对应的二叉树,后根次序周游树林正好等同于 按（2）周游对应的二叉树。【山东工业大学1 9 9 9 二、1 （4 分】36 .二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为Q,则 该 二 叉 树 对 应 的 树 林 包 括 棵 树。【北 京 大 学 1 9 9 7 一、2 （4分】37.二 叉 树 的 先 序 序 列 和 中 序 序 列 相 同 的 条 件 是。【合肥工业大学2 0 0 0 三、7（2分】3 8.已知一棵二叉树的前序序列为a b d e c f h g,中序序列为d b e a h f c g,则该二叉树的根为，左子树中有（2）,右子树中有（3）。【南京理工大学1 9 9 6 二、1 （6分】3 9.设二叉树中每个结点均用一个字母表示，若个结点的左子树或右子树为空，用.表示，现前序遍历二叉树，访问的结点的序列为AB D.G.C E.H.F.,则中序遍历二叉树时，访问的结点序列为（1）;后序遍历二叉树时,访问的结点序列为（2）。【南京理工大学1 9 9 9 二、3（4 分】40 .已知二叉树前序为AB D E G C F,中序为D B G E AC F,则 后 序 一 定 是。【青岛大学2 0 0 0 六、3（2 分 41 .现有按中序遍历二叉树的结果为a b c,问 有（1）种不同的二叉树可以得到这一遍历结果，这些二叉树分别是（2）。【中国矿业大学2 0 0 0 、5 （3分】4 2 .一个无序序列可以通过构造一棵 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。【西安电子科技大学1 9 9 9 软 件 一、4 (2 分】4 3 .利用树的孩子兄弟表示法存储，可 以 将 一 棵 树 转 换 为。【重庆大学2 0 0 0 一、9 4 4 .若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的 序列中的最后一个结点。【武汉 大 学 2 0 0 0 一、2 4 5 .先根次序周游树林正好等同于按 周游对应的二叉树；后根次序周游树林正好等同于 周游对应的二叉树。【山东大学1 9 9 9 二、1 (4 分)】4 6 .在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则 这 个 结 点 在 后 序 遍 历 中 的 后 继 结 点 是。【中国人民大学2 0 0 1 一、4 (2分)】4 7 .一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：o【厦门大学2 0 0 2 六、1 (4 分】4 8 .具有n 个结点的满二叉树，其 叶 结 点 的 个 数 是。【北京 大 学 1 9 9 4 4 9 .设一棵后序线索树的高是5 0,结 点 x是树中的一个结点，其双亲是结点y,y的右子树高度是3 1,x是 y的左孩子。则确定x的后继最多需经过 中间结点(不含后继及x本身)【南京理工大学2 0 0 0 二、8 (1.5 分】5 0 .线索二元 树 的 左 线 索 指 向 其,右 线 索 指 向 其。【哈尔滨工业大学2 0 0 0 二、3 (2 分)】5 1 .设 y 指向二叉线索树的一叶子，x 指向一待插入结点，现 x作为y的左孩子插入，树中标志域为I ta g 和 r ta g,并规定标志为1 是线索，则下面的一段算法将x 插入并修改相应的线索，试补充完整：(l c h i l d,r c h i l d 分别代表左，右孩子)x.l ta g:=(1);x.l c h i l d:=(2)：y.l ta g:=(3);y-.l c h i l d:=(4);x.r ta g:=(5);x .r c h i l d:=(6);I F (x*.I c h i l d O N I L)A N D(x l c h i l d.r ta g=l)T H E N x.I c h i l d .r c h i I d:=(7);【南京理工大学1 9 9 7 三、7 (9 分】5 2 .哈 夫 曼 树 是。【北京理工大学2 0 0 1 七、4 (2)长沙铁道学院1 9 9 8 二、3 (2分)】5 3 .若以 4,5,6,7,8 作为叶子结点的权值构造哈夫曼树，则 其 带 权 路 径 长 度 是。【西安电子科技大学2 0 0 1 软 件 一、3 (2 分)】【厦门大学2 0 0 2 六、2 (4 分】5 4 .有数据WG=7,1 9,2,6,3 2,3,2 1,1 0 ,则所建H u f f m a n 树的树高是(1),带权路径长度WP L 为。【南京理工大 学 1 9 9 9三、6 (4 分】5 5 .有一份电文中共使用6个字符:冉1),(;,(1,6,它们的出现频率依次为2,3,4,7,8,9,试构造一棵哈夫曼树，则其加权路径长度W P L 为(1),字符c 的 编 码 是(2)。【中国矿业大学2 0 0 0 一、7 (3 分】56.设 n。为哈夫曼树的叶子结点数目，则该哈夫曼树共有 个结点。【西安电子科技大学1 9 9 9 软 件 一、2 (2 分】57 .二叉树用来表示表达式，因为需要保存各子树的值，修改二叉树的结点结构为(L chil d,D a t a,V a l,R chil d)其中L chil d,R chil d的意义同前，V a i用来存放以该结点为根的子树的值，值的类型依具体情况而定。为了简便起见，算法假定所考虑的表达式只有+,*，/四种二目运算，且已表示成相应的二叉树。算法所计算的表达式值放在根结点的V a i域中。P R O C P o s t o r der-ev a l(t:p t r T y p e)B E G I N I F (t!=N U L L)B E G I N (1);(2);C A S E t da t a:+:t二 V a i:=t L chil d*.V a i+t 二R chil d V a i;B R E A K;V a i:=t.L chil d.V a i-R chil d 二 V a i;B R E A K;，*:V a i:=t.L chil d.V a i*R chil d 二 V a i;B R E A K;t V a l:=t L chil d.V a i/t R chil d 二 V a i;B R E A K;o t her w is e:;B R E A K;E N D C A S E E N DE N D;P R O C D el et e(x:da t a t y p e,A:t r ee)B E G I N t em p A-(4);W H I L E (t em p A I t em!=x)A N D (t em p A!=N U L L)D OI F (x t em p A it em)B E G I N r:=t em p A;t em p A:=(5);E N DE L S E B E G I N r:=t em p A;t em p A:=t em p A R chi 1 d;E N D;/1 em p A 为耍删结点，r 为t em p A的父亲I F r et u r n(x);I F (t em p A .L ehi I d!=N U L L)A N D (t em p A .r chil d!=N U L L)B E G I N t:=t em p A;q:=t em p A R chil d;W H I L E (q,L ehi I d!=N U L L)D O B E G I N t:=q;q:=q L chil d;E N D;t L chil d：=(7);删去 qq L ehi I d:=t em p A .L ehi I d;R chil d:=t em p A二 R chil d;I F (t em p A .it em r it em)r*.L chil d:=(8)E L S E r*.R chil d:=q /用q代 替t em p AE N D;E L S E I F(t em p A L chil d!=N U L L)I F(t em p A it em r it em)r L ehi I d:=t em p A二 L chil dE L S E r R chil d:=t em p A L chil dE L S E I F(t em p A R chil d!=N U L L)I F(t em p A.it em r c h i l d=M)_；0_=q；i f(p-l c h i l d)(4);i f(p-r c h i l d)(5):)/【北京科技大学2000二、(10分)】60.设 t是给定的一棵二叉树，下面的递归程序c o u n t(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数NO。N2、NL、NR、NO都是全局量，且在调用c o u n t (t)之前都置为0.t y p e d e f s t r u c t n o d e i n t d at a;s t r u c t n o d e *1c h i Id,*r c h i l d;n o d e;i n t N2,NL,NR,NO;v o i d c o u n t(n o d e *t)i f (t-l c h i l d!=NU LL)i f 3_ _ _ N2+;e l s e NL+;e l s e i f (2)NR+;e l s e 0)_ ；i f(t-l c h i l d!=NU LL)14);i f (t-r c h i l d!=NU LL)1 5);/*c al l f o r m :i f(t!-NU LL)c o u n t(t);*/【上海大学2000 一、3(10分)】61.下面是求二叉树高度的类PASC AL(注：编者略)及类C写的递归算法试补充完整 说明(1)考生可根据自己的情况任选一个做(都选不给分)(2)二叉树的两指针域为Ic h i l d 与 r c h i l d,算法中p为二叉树的根，l h 和 r h分别为以P 为根的二叉树的左子树和右子树的高，h i 为以p为根的二叉树的高，h i 最后返回。h e i g h t(p)i f (0)i f(p-l c h i l d=n u l l)lh=(2);e l s e lh=(3);i f(p-r c h i l d=n u l l)r h=(4)：e l s e rh=(5);i f (l h r h)h i=(6)；e l s e hi=(7);e l s e hi=(8);r e t u r n h i;/【南京理工大学1997三、8(15分】62.二叉树以链方式存储，有三个域，数 据 域 d at a,左右孩子域Ic h i l d,r c h i l d,树根由t r e e 指 向。现要求按层次从上到下，同层次从左到右遍历树。下面算法中用到ad d x (p),将指针P 进队，d e l x()将队头元素返回并退队，n o t e m p t y 在队不空时返回t r u e,否则为f al s e,将算法补充完整：PROC p r o c e s s n o d e(p);IF(1)T HEN w r i t e (p 人.d at a);(2)ENDP;PROC t r av e(t r e e);w r i t e(t r e e 人.d at a);(3);W HILE n o t e m p t y O DO r:=d e l x();p r o c e s s n o d e(r .Ic h i l d);p r o c e s s n o d e(4)E N D P;【南京理工大学1999三、5(4分】6 3 阅读下列程序说明和程序，填充程序中的【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示(编者略)。本程序采用非递归的方法，设 立 个堆 栈 s t ac k 存放还没有转换过的结点，它的栈顶指针为t p o 交换左、右子树的算法为：(1)把根结点放入堆栈。(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。(3)重 复(2)直到堆栈为空时为止。type d e f stru c t nod e *tre e;stru c t nod e(i nt d a ta;tre e I c h i ld,rc h i ld;)e xc h a ng e(tre e t)tre e r,p;tre e sta c k 500;i nt tp=0;(1)w h i le (tp=0)12)_ _ _ _ _ _ _i f(1 3)r=p-lc h i ld;p-lc h i ld=p-rc h i I d;p-rc h i ld=rsta c k (4)=p-lc h i ld;sta c k +tp=p-rc h i 1d;)【中科院自动化研究所1994二、2(15分】6 4.下面使用类pa sc a l语言写的对二叉树进行操作的算法，请仔细阅读T Y P E poi nte r=tnod e tp;tnod e tp=RECO RD d a ta:c h a r;lli nk,rli nk:poi nte r；EN D;1 i nk sta c k 二 i nk nod e t;1i nk nod e t=RECO RD d a ta:poi nte r；ne xt;li nk sta c k；EN D;P RO C u nk now n(VAR t:poi nte r);VAR p,te mp：poi nte r;BEGI N p:=t;I F p N I L T H EN te mp:=p lli nk ；p lli nk:=p rli nk;；p rli nk:=te mp;u nk now n(p*.lli nk);u nk now n(p rli nk);EN D;指出该算法完成了什么功能用栈将以上算法改为非递归算法u nk now ns其中有若干语句或条件空缺请在空缺处填写上适当的语句或条件P RO C i ni sta c k(VAR s:li nk sta c k);(1);s*.ne xt:=N I L;EN DP;FUN C e mpty(s:li nk sta c k):b oole a n;I F(2)THE N e mpty:=tru e EL S E e mpty:=f a lse;EN DF;FUN C g e ttop(s:li nk sta c k):poi nte r;g e ttop:=(3);EN DF;FUN C pop(VAR s:li nk sta c k)：poi nte r;VAR p:1 i nk sta