1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 14 及答案与解析一、设计题1 用 C 语言描述树的孩子兄弟链表结构，并编写递归程序求树中叶子结点数。【北京交通大学 2004 八(10 分)】2 设二叉树用二指针结构存储(可以是动态存储结构)，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶子结点。【华南理工大学 200323(2)(232 分)】3 用类 Pascal 语言编写一非递归算法，求二叉树上叶子结点的数量。二叉树用二叉链表存储，左指针定义为 lchild，右指针定义为 rchild。【燕山大学 2000 七、2(8分)】
2、4 一棵二叉树以二叉链表来表示，求其指定的某一层 k(k1)上的叶子结点的个数。【上海大学 1999 三、1(18 分)】5 已知二叉树采用二叉链表方式存放，要求对二叉树从 1 开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，请回答采用什么次序的遍历方式实现编号?并给出在二叉树中结点的数据域部分填写实现如上要求编号的非递归算法。【西北大学 2003 五(13 分)】6 设树 T 采用孩子兄弟链表表示，编写程序，计算树 T 的度，并写出算法思想。【南京航空航天大学 2005 七(10 分)】7 树的存储结构如下：#define
3、MAX 一 TREESIZE 100typedef struct CTNode 孩子结点int child；struct CTNode *next ;*childPtr;typedef struct E1emtype data；childPtr *firstchild; 孩子链表头的指针*CTBox;Typedef struct CTBox nodesMAX_rREESIZE；int n; n 为结点数*CTree写出求树的度的算法。【南京理工大学 2004 四(5 分)】8 设 i 是一棵按后序遍历方式构成的线索二叉树的根结点指针，试设计一个非递归的算法，把一个地址为 x 的新结点插到 t
4、树中已知地址为 y 的结点右侧作为结点 y的右孩子，并使插入后的二叉树仍为后序线索二叉树。【东北大学 1996 七(15 分)】9 请用类 C 或用类 Pascal 语言编写算法。请编写在中序全线索二叉树 T 中的结点P 下插入一棵根为 X 的中序全线索二叉树的算法。如果尸左右孩子都存在，则插入失败并返回 FAI,SE；如果 P 没有左孩子，则 X 作为尸的左孩子插入；否则 X 作为 P 的右孩子插入。插入完成后要求二叉树保持中序全线索并返回 TRUE。【上海大学 2002 七、1(10 分) 】10 有中序线索树 T，结点形式为：(LL ，LT, D，RT,RL)，试编写非递归算法找到数据域
5、为 A 的结点，并在其左子树中插入值为 Q 的已知新结点 X：注意：可能 A 有左孩子或无左孩子，插入后考虑线索的状态应作何修改。【上海大学 1998 六(1 7 分)】11 编写程序段，利用中序全线索树求其中任意结点 p的前序后继结点，结果仍用p 指出。要求先描述结构和算法思路。设线索树不带头结点，其中序序列第一结点的左标志和最后结点的右标志皆为 0(非线索)，对应指针皆为空。【北京工业大学2000 七(10 分) 】【哈尔滨工业大学 2004 五、2(8 分)】【上海交通大学 2003 三(15分)】12 已知一中序线索二叉树，写一算法完成对它的中序扫描。【山东大学 2001 三(8分)】
6、13 已知指针 p 指向带表头的中根次序线索二又树中的某结点，试写一算法FFAp，q) ，该算法寻找结点 p 的父亲结点 g。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAGLLINK ，INFO，RLINK，RTAG) ，且规定线索树的最左下结点的 LLNK 域和最右下结点的 RLINK 域指向表头。【吉林大学 1999 二、1(16 分 )】14 给出中序线索树的结点结构并画出一个具有头结点的中序线索树，使其树结点至少应有 6 个。写一算法在不使用栈和递归的情况下前序遍历一中序线索树，并分析其时间复杂性。【东南大学 1993 三(20 分)1997 三(1 8 分)1998
7、六(14 分)】【东北大学 2003 三(20 分) 】15 试编写一算法对二叉树按前序线索化。【东南大学 1999 六(1 5 分)】16 写出中序线索二叉树的线索化过程(已知二叉树 T)。【山东大学 2000 五、2(10分)】【 南京邮电学院 1999 五(18 分)】17 已知一个二叉树如下图(编者略)，修改结点(node)的连接方式，以致可以不借助辅助堆栈实现中序遍历的非递归方法。画出修改后的结点连接图并写出其实现中序遍历的非递归算法。【浙江大学 2002 五(10 分)】18 已知中序线索二叉树 T 右子树不空。设计算法，将 S 所指的结点作为 T 的右子树中的一个叶子结点插入进去
8、，并使之成为 T 的右子树的 (中序序列)第一个结点(同时要修改相应的线索关系)。【合肥工业大学 2001 五、2(8 分)】19 写出算法，求出中序线索二叉树中给定值为 x 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：(1tag，lc ，data，rc，aag)。其中，data 存放结点的值；lc，rc 为指向左、右孩子或该结点前驱或后继的指针；ltag ，rtag 为标志域，若值为 0，则 lc，rc 为指向左、右孩子的指针；若值为 1，则 1c，rc 为指向其前驱、后继结点的指针。【北京邮电大学 1996 八(20 分)】20 设计算法求中序线索二叉树中指针 P 所指结点
9、的前驱结点的指针。【东南大学2004 五 (10 分) 】21 设后序线索树中结点构造为(Ltag，Lchild，Data，Rchild，Rtag)。其中：Ltag， Rtag 值为 0 时，Lchild、Rchild 分别为儿子指针；否则分别为直接前驱、直接后继的线索。请写出在后序线索树上找给定结点 p的直接前驱 q 的算法。【武汉交通科技大学 1966 四、1(13 分)】22 用算法说明在对称序线索树中，如何对任意给定的结点直接找出该结点的对称序后继。【山东大学 1999 六、3(10 分)】23 写出在中序线索二叉树中找指定结点在后序下的前驱结点的算法。【河海大学1998 七(10 分
10、) 】24 设中序线索二又树的结点由五个域构成：info：给出结点的数据场之值。 LL：当 LT 为 1 时，则给出该结点的左儿子之地址，当 LT 为 0 时，则给出按中序遍历的前驱结点的地址。LT：标志域，为 1 或为 0。RL ：当 RT 为 1 时，则给出该结点的右儿子的地址；当 RT 为 0 时，则给出按中序遍历的后继结点地址。 RT：标志域为 0 或为 l。请编写程序，在具有上述结点结构的中序线索二叉树上，求某一结点 p 的按后序遍历次序的后继结点的地址 q，设该中序线索二叉树的根结点地址为 r。另外，请注意必须满足：(1)额外空间的使用只能为 O(1)，(2)程序为非递归。【上海交
11、通大学 2000 十(20 分)】25 写出按后序序列遍历中序线索树的算法。【东南大学 2000 六(15 分)】26 从键盘上输入一串正整数，最后输入一 1 作为结束标志。如：8，7，1，22，98，46，75，一 1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设该二叉排序树上的结点结构为： 其中：data 域为结点的数据场。ltag=0，那么 left 域中存放的是该结点的左儿子结点的地址。ltag=1，那么left 域中存放的是该结点的按中序周游次序的前驱结点的地址。rtag=0，那么 fight域中存放的是该结点的右儿子结点的地址。rtag=1，
12、那么 fight 域中存放的是该结点的按中序周游次序的后继结点的地址。【上海交通大学 2003 二(20 分)】27 给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为 Huffman 树。(1)给出构造 Huffman 树的算法。(2)给定项及相应的权如下表，画出执行上述算法后得到的 Huffman 树。(3)用 C 语言编写构造Huffman 树的程序。【浙江大学2000 七(18 分) 】28 已知一棵二叉树，该二叉树中结点的形式为(data，left，right)。其中 data 域为结点的数据域，且它的数据类型为 int；left 域和 fight
13、 域分别给出本结点的左孩子和右孩子的地址，又已知该排序二叉树的根结点地址为 root。请设计一个非递归的函数，给出该二叉树的前序遍历序列的最后一个结点的地址，另外要求所使用的额外空间必须为 O(1)。【上海交通大学 2006】29 UNIX 的文件目录结构如左图所示，木表示目录，括弧内的数字是文件目录的大小。(1)试设计一种数据结构表达这种关系。(2)设计一种算法，输出如右图所示的结果(次序和数字不能改变)。【浙江大学2004 五(15 分) 】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 14 答案与解析一、设计题1 【正确答案】 孩子兄弟链表表示的树中孩子指针为空的结点是叶子。
14、int Count(CSTree t) 统计以孩子兄弟链表表示的树的叶子结点个数(if(t=null)return(0)；else if(t 一firstlchild=null) return(1+Count(t 一nextsibling)；else return(Count(t-firstchiid)+Count(t-nextsibling)； 子女中叶子+兄弟中叶子2 【正确答案】 首先设计一个函数，使用任何一种遍历方法，查找元素值等于某个给定的整数的结点，返回该结点指针。之后，再在遍历以该结点为根的子树的过程中求叶子结点。3 【正确答案】 以二叉链表为存储结构的二叉树遍历的非递归算法，在
15、“访问根结点”时，加上判断该结点是否是叶子结点的语句，对叶子结点进行计数就行了。4 【正确答案】 对某层上的结点进行运算，采用队列结构按层次遍历最适宜。核心语句段如下：BiTree P=bt，Q ； Q 是队列，元素是二叉树结点指针，容量足够大int front：0，rear ：1，leaf：0； front 和 rear 是队头和队尾指针，leaf 是叶子结点数int last：1，level=1；Q1=P ； last 是同层最右结点的指针， level 是二叉树的层数while(frontIchild p 指向二叉树的根结点，当二叉树为空时，p 指向头结点thrtwhild(p!=thr
16、t)while(p 一ltag=0)p=p 一lchild 沿左子女向下visit(tp) 访问左子树为空的结点while(p 一rtag=l 左子树前序线索化preorderThreat(BT 一rchild); 右子树前序线索化16 【正确答案】 在中序遍历中完成线索化。下面只给对“访问根结点” 进行改造的语句段：if(T 一ichild=null)T 一Itag=1；T 一ichild=pre； 左线索为 preif(pre!=nullpre 一rtag=1)pre 一rchild=T； 给前驱加后继线索if(T 一rchild=null)T 一rtag=1； 置右标记，为右线索作准备p
17、re=T； 前驱指针后移17 【正确答案】 不借助堆栈实现中序遍历，必须解决如何查找后继的问题。使用线索树就可完成。为此，将结点结构修改为(1tag，lchild，data，rchild，rtag)。18 【正确答案】 若使新插入的叶子结点 S 成 T 右子树中序序列的第一个结点，则应在 T 的右子树中最左面的结点(设为 p)处插入，使 S 成为结点 P 的左子女，则 S的前驱是 T，后继是 P。p=T 一rchild； p 指向 T 的右子女while(p 一itag=0)p=p 一Ichild ； P 最终指向 T 的右子树中最左面的结点S 一itag=1； s 一rtag=1； s 是叶
18、子，其左右标记均为 1s 一ichild=T；s 一rchild=p； s 的前驱是根结点 T，后继是结点 PP 一ichild=S；p-itag=0; 将 P 的左子女指向 S，并修改左标志为 019 【正确答案】 首先查找值为 X 的结点，设结点存在，且指针 p 指向该结点。若P 一rtag=1， P 一RC 不为空，则 P 一rc 指向其后继；若 P 一rtag=0 ，P 结点有右子女，则其右子树上按中序遍历的第一个结点是其后继。前面几个题已有涉及找中序后继的内容，这里不再赘述。20 【正确答案】 中序线素二叉树中指针 P 所指结点的前驱结点的特征是：若 P-ltag=l，P-lchil
19、d 指向其前驱，否则，P 的左子树上按中序遍历的最后结点是其中序前驱。if(p 一itag=1)q=p 一ichild； 若 P 的左标志为 1，用其左指针指向前驱else(q=p 一lchild；while(q 一rtag=0)q=q 一rchild； P 的前驱为其左子树中最右下的结点return(q);21 【正确答案】 二叉树的后序遍历是“左右一根” ，因此，若结点有右子女，则右子女是其后序前驱，否则，左子女(或左线索)指向其后序前驱。核心语句如下：if(p 一Rtag=0)return(p-Rchild); 若 P 有右子女，则右子女为其前驱else return(p 一Lchild
20、)； 若 P 无右子女，左子女或左线索就是 P 的后序前驱22 【正确答案】 中序线索树任意给定的结点 P 中序后继的特点是，若 P-rtag=1，则 P-rchild 指向其后继，否则，其右子树最左结点是其中序后继。23 【正确答案】 在后序序列中，若结点 P 有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点 P 左右子女均无，设其中序左线索指向某祖先结点 f(p 是厂右子树中按中序遍历的第一个结点)，若 f 有左子女，则其左子女是结点 P 在后序下的前驱；若厂无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女(这时左子女是 P 的前驱)。还有一种情况，若 P
21、 是中序遍历的第一个结点，结点 P 在中序和后序下均无前驱。24 【正确答案】 在中序线索二叉树中，求某结点 P 的后序后继 g，需要知道 P 的双亲结点 f 的信息。( 中序线索树的性质；若 P 是 f 的左子女，DJf 是 p 的最右子孙的右线索；若 p 是 f 的右子女，则 f 是 p 的最左子孙的左线索。)找到 f 后，若 p是 f 的右子女，则 p 的后继是 f 若 p 是 f 的左子女，且 f 无右子女，则 p 的后继也是 f;若 p 是 f 的左子女，且 f 有右子女，则 f 的右子树中最左边的叶子结点是 p 的后继。因此，算法思路是，先找 p 的双亲 f,根据 p 是 f 的左
22、右子女再确定 p 的后序后继。25 【正确答案】 上题讨论了中序线索树中查找结点 p 的后序后继问题，本题要求在中序线索树上进行后序遍历。因后序遍历是“左一右一根” ，最后访问根结点，即只有从右子树返回时才能访问根结点，为此设一标志 flag，当其为 1 时表示从右侧返回，可以访问根结点。为了找当前结点的后继，需知道双亲结点的信息，在中序线索树中，某结点最左子孙的左线索和最右子孙的右线索均上指双亲或祖先，因此设立两个函数 LeftMost 和 RightMost 求结点的最左和最右子孙，为了判定是否是从右子树返回，再设一函数 IsRightChild。下面是求结点 t 最左子孙的左线索：BiT
23、hrTree p=t；while(p 一Itag=0)p=p 一Ichild； 沿左分支向下if(p-ichild!=null)return(p 一Ichild)；else return(null)；下面是求结点 t 最右子孙的右线索：BiThrTree p=t；while(p 一rtag=0)p=p 一rchild； 沿右分向下if(p-rchild!=null)return(p 一rchild)；else return(null)；下面的函数，若 t 是 father 的右孩子返回 1，否则返回 0int IsRightChild(BiThrTree t，father)(father=Le
24、ftMost(t)；if(father&father 一rchiid=t)return(1)；else return(0)；void PostOrderInThr(BiThrTree bt) 后序遍历中序线索二叉树 btBiThrTree father，p=bt；int flag；while(p!=null)while(p 一itag=0)p=P 一ichild； 沿左分支向下if(p 一rtag=0)flag=0 ； 左孩子为线索，右孩子为链，相 “-3 于从左返回else flag=1 ； lip 为叶子，相当于从右返回while(flag=1)visit(+p)； 访问结点if(IsRi
25、ghtChild(p，father)p=father ；flag=1；)修改 P 指向双亲else p 是左子女，用最右子孙的右线索找双亲p=RightM。st(p) ；if(p&p 一rtag=1)flag=l；else flag=0 ； while(flag=1)if(flag=0&P!=null)p-p 一rchild；转向当前结点右分支结束 PostorderInThr26 【正确答案】 二叉排序树建立过程如下：设输入第一个数据，用二叉排序树根结点指针 bst 指向该结点，根结点的数据域赋值。将左右子女指针和左右标记初始化：bst 一left=-bst 一right=null，bst
26、一ltag=bst 一nag=1。接着对输入数据做如下处理：若该数据小于根结点的数据，则在左子树上查找其插入位置，否则在右子树上查找其插入位置。查找时记住其双亲结点的指针厂。插入的结点一定是叶子，设 p 指向已申请空间的叶子结点。若 p 一dataf-data，则按 f 的左子女插入，否则，按 f 的右子女插入，同时，修改双亲和叶子的线索和标记。核心语句段如下：cinx； 输入数据while(x!=flag) flag 是结束标记if(bst=null) 处理根结点bst=new(BstNode)； 建立根结点，并初始化bst 一 left=bst 一right=null ；bst-itag=
27、bst-rtag=1；bst-data=x；else 非根结点的插入f=null；s=bst ； f 是双亲指针while(s)if(s 一datax)f=s ； s=s 一left； 沿左分支向下else if(S-dataright； 沿右分支向下elsetoutdata=x； 申请结点空间，填入数据if(f 一datax) 插入为左子女p 一 left=f 一left；f 一left=p；f 一ltag=0 ； 修改双亲线索和标记p-itag=p-rtag=l；p-right=f； 建立叶子结点的线索和标记else 插入为右子女p 一 right=f 一right；f-right=p；f
28、 一rtag=0 ；P 一Itag=p 一rtag=l；P 一left=f ；cinx； 输入数据 else 结束非根结点的插入 结束 while(x!=flag)27 【正确答案】 (1)哈夫曼树的构造过程： 根据给定的 n 个权值W1，W 2，W 3，W n构成 n 棵二叉树的集合 F=T1，T 2，T n，其中每棵二叉树 Ti 只有权值为 Wi 的根结点，其左右子树均为空。 在 F 中选取两棵根结点的权值最小的树作左右子树构造一棵新二叉树，新二叉树根结点的权值为其左右子树上根结点的权值之和。 在 F 中删除这两棵树，同时将新得到的二叉树加入F 中。重复和 ，直到 F 中只剩一棵树为止。这
29、棵树便是哈夫曼树。 (2)含有n 个叶子结点的哈夫曼树共有 2n 一 1 个结点，采用静态链表作为存储结构，设置大小为 2n 一 1 的数组。核心语句段如下： for(i=0；i28 【正确答案】 前序遍历的最后一个结点是最右边的叶子结点。核心语句是：p=root；while(p)if(p 一right)p=p 一right；else if(p 一 left)p=p 一left；else return P；29 【正确答案】 用树形结构表示这种文件目录结构。题中的输出是对树进行后根遍历的结果，括号内数字代表文件大小：原文件(*c 和*txt)是叶子结点，其大小照原大小输出，子目录文件的大小是其
30、本身大小和其目录下的文件大小之和。设树用孩子兄弟链表表示。typedef struct CSNodechar namemaxsize； 目录(文件)名，maxsize 为文件名最大长度int byt； 文件大小struct CSNode*fch，*nsib； 第一子女，兄弟CSNode，*CSTree；int num； 计算子目录下的文件大小int ByteNumber(CSTree t)if(t)ByteNumber(t 一fch)；num+=t 一byt ；ByteNumber(t 一nsib ；if 结束void Inorder(CSTree t)(if(t)(Inorder(t 一fch)；if(t 一fch=null)printf(“s( d) n”，t 一name，t 一byt) ；lit 是叶子，直接输出else 计算子目录下文件大小num=0；num=ByteNumber(t)；printf Cs(“d)n”，t 一name，num)； 输出子目录大小InOrder(t-nsib)；
