【考研类试卷】计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编14及答案解析.doc

1、计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 14及答案解析(总分：58.00，做题时间：90 分钟)一、设计题(总题数：29，分数：58.00)1.用 C 语言描述树的孩子兄弟链表结构，并编写递归程序求树中叶子结点数。【北京交通大学 2004 八(10分)】（分数：2.00）_2.设二叉树用二指针结构存储(可以是动态存储结构)，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶子结点。【华南理工大学 200323(2)(232 分)】（分数：2.00）_3.用类 Pascal 语言编写一非递归算法，求二叉树上叶子结点的数量。二叉树

2、用二叉链表存储，左指针定义为 lchild，右指针定义为 rchild。【燕山大学 2000 七、2(8 分)】（分数：2.00）_4.一棵二叉树以二叉链表来表示，求其指定的某一层 k(k1)上的叶子结点的个数。【上海大学 1999 三、1(18 分)】（分数：2.00）_5.已知二叉树采用二叉链表方式存放，要求对二叉树从 1 开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，请回答采用什么次序的遍历方式实现编号?并给出在二叉树中结点的数据域部分填写实现如上要求编号的非递归算法。【西北大学 2003 五(13 分)】（分数：2.

3、00）_6.设树 T 采用孩子兄弟链表表示，编写程序，计算树 T 的度，并写出算法思想。【南京航空航天大学2005 七(10 分)】（分数：2.00）_7.树的存储结构如下： #define MAX 一 TREESIZE 100 typedef struct CTNode 孩子结点 int child； struct CTNode *next ; *childPtr; typedef struct E1emtype data； childPtr *firstchild; 孩子链表头的指针 *CTBox; Typedef struct CTBox nodesMAX_rREESIZE； int n

4、; n 为结点数 *CTree 写出求树的度的算法。【南京理工大学 2004 四(5 分)】（分数：2.00）_8.设 i 是一棵按后序遍历方式构成的线索二叉树的根结点指针，试设计一个非递归的算法，把一个地址为x 的新结点插到 t 树中已知地址为 y 的结点右侧作为结点 y 的右孩子，并使插入后的二叉树仍为后序线索二叉树。【东北大学 1996 七(15 分)】（分数：2.00）_9.请用类 C 或用类 Pascal 语言编写算法。请编写在中序全线索二叉树 T 中的结点 P 下插入一棵根为 X 的中序全线索二叉树的算法。如果尸左右孩子都存在，则插入失败并返回 FAI,SE；如果 P 没有左孩子，

5、则X 作为尸的左孩子插入；否则 X 作为 P 的右孩子插入。插入完成后要求二叉树保持中序全线索并返回TRUE。【上海大学 2002 七、1(10 分)】（分数：2.00）_10.有中序线索树 T，结点形式为：(LL，LT, D，RT,RL)，试编写非递归算法找到数据域为 A 的结点，并在其左子树中插入值为 Q 的已知新结点 X： （分数：2.00）_11.编写程序段，利用中序全线索树求其中任意结点 p的前序后继结点，结果仍用 p 指出。要求先描述结构和算法思路。设线索树不带头结点，其中序序列第一结点的左标志和最后结点的右标志皆为 0(非线索)，对应指针皆为空。【北京工业大学 2000 七(10

6、 分)】【哈尔滨工业大学 2004 五、2(8 分)】【上海交通大学 2003 三(15 分)】（分数：2.00）_12.已知一中序线索二叉树，写一算法完成对它的中序扫描。【山东大学 2001 三(8 分)】（分数：2.00）_13.已知指针 p 指向带表头的中根次序线索二又树中的某结点，试写一算法 FFAp，q)，该算法寻找结点 p的父亲结点 g。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAGLLINK，INFO，RLINK，RTAG)，且规定线索树的最左下结点的 LLNK 域和最右下结点的 RLINK 域指向表头。【吉林大学 1999 二、1(16 分)】（分数：2.00）

7、_14.给出中序线索树的结点结构并画出一个具有头结点的中序线索树，使其树结点至少应有 6 个。写一算法在不使用栈和递归的情况下前序遍历一中序线索树，并分析其时间复杂性。【东南大学 1993 三(20 分)1997 三(1 8 分)1998 六(14 分)】【东北大学 2003 三(20 分)】（分数：2.00）_15.试编写一算法对二叉树按前序线索化。【东南大学 1999 六(1 5 分)】（分数：2.00）_16.写出中序线索二叉树的线索化过程(已知二叉树 T)。【山东大学 2000 五、2(10 分)】【南京邮电学院1999 五(18 分)】（分数：2.00）_17.已知一个二叉树如下图(

8、编者略)，修改结点(node)的连接方式，以致可以不借助辅助堆栈实现中序遍历的非递归方法。画出修改后的结点连接图并写出其实现中序遍历的非递归算法。【浙江大学 2002 五(10分)】（分数：2.00）_18.已知中序线索二叉树 T 右子树不空。设计算法，将 S 所指的结点作为 T 的右子树中的一个叶子结点插入进去，并使之成为 T 的右子树的(中序序列)第一个结点(同时要修改相应的线索关系)。【合肥工业大学2001 五、2(8 分)】（分数：2.00）_19.写出算法，求出中序线索二叉树中给定值为 x 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：(1tag，lc，data，rc，

9、aag)。其中，data 存放结点的值；lc，rc 为指向左、右孩子或该结点前驱或后继的指针；ltag，rtag 为标志域，若值为 0，则 lc，rc 为指向左、右孩子的指针；若值为1，则 1c，rc 为指向其前驱、后继结点的指针。【北京邮电大学 1996 八(20 分)】（分数：2.00）_20.设计算法求中序线索二叉树中指针 P 所指结点的前驱结点的指针。【东南大学 2004 五 (10 分)】（分数：2.00）_21.设后序线索树中结点构造为(Ltag，Lchild，Data，Rchild，Rtag)。其中：Ltag，Rtag 值为 0 时，Lchild、Rchild 分别为儿子指针；否

10、则分别为直接前驱、直接后继的线索。请写出在后序线索树上找给定结点 p的直接前驱 q 的算法。【武汉交通科技大学 1966 四、1(13 分)】（分数：2.00）_22.用算法说明在对称序线索树中，如何对任意给定的结点直接找出该结点的对称序后继。【山东大学1999 六、3(10 分)】（分数：2.00）_23.写出在中序线索二叉树中找指定结点在后序下的前驱结点的算法。【河海大学 1998 七(10 分)】（分数：2.00）_24.设中序线索二又树的结点由五个域构成：info：给出结点的数据场之值。LL：当 LT 为 1 时，则给出该结点的左儿子之地址，当 LT 为 0 时，则给出按中序遍历的前驱

11、结点的地址。LT：标志域，为 1 或为0。RL：当 RT 为 1 时，则给出该结点的右儿子的地址；当 RT 为 0 时，则给出按中序遍历的后继结点地址。RT：标志域为 0 或为 l。请编写程序，在具有上述结点结构的中序线索二叉树上，求某一结点 p 的按后序遍历次序的后继结点的地址 q，设该中序线索二叉树的根结点地址为 r。另外，请注意必须满足：(1)额外空间的使用只能为 O(1)，(2)程序为非递归。【上海交通大学 2000 十(20 分)】（分数：2.00）_25.写出按后序序列遍历中序线索树的算法。【东南大学 2000 六(15 分)】（分数：2.00）_26.从键盘上输入一串正整数，最后

12、输入一 1 作为结束标志。如：8，7，1，22，98，46，75，一 1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设该二叉排序树上的结点结构为： （分数：2.00）_27.给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为Huffman 树。(1)给出构造 Huffman 树的算法。(2)给定项及相应的权如下表，画出执行上述算法后得到的Huffman 树。(3)用 C 语言编写构造 Huffman 树的程序。 （分数：2.00）_28.已知一棵二叉树，该二叉树中结点的形式为(data，left，right)。其中 d

13、ata 域为结点的数据域，且它的数据类型为 int；left 域和 fight 域分别给出本结点的左孩子和右孩子的地址，又已知该排序二叉树的根结点地址为 root。请设计一个非递归的函数，给出该二叉树的前序遍历序列的最后一个结点的地址，另外要求所使用的额外空间必须为 O(1)。【上海交通大学 2006】（分数：2.00）_29.UNIX 的文件目录结构如左图所示，木表示目录，括弧内的数字是文件目录的大小。(1)试设计一种数据结构表达这种关系。(2)设计一种算法，输出如右图所示的结果(次序和数字不能改变)。（分数：2.00）_计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 14答案解析

14、(总分：58.00，做题时间：90 分钟)一、设计题(总题数：29，分数：58.00)1.用 C 语言描述树的孩子兄弟链表结构，并编写递归程序求树中叶子结点数。【北京交通大学 2004 八(10分)】（分数：2.00）_正确答案：(正确答案：孩子兄弟链表表示的树中孩子指针为空的结点是叶子。 int Count(CSTree t) 统计以孩子兄弟链表表示的树的叶子结点个数 (if(t=null)return(0)； else if(t 一firstlchild=null) return(1+Count(t 一nextsibling)； else return(Count(t-firstchiid

15、)+ Count(t-nextsibling)； 子女中叶子+兄弟中叶子 )解析：2.设二叉树用二指针结构存储(可以是动态存储结构)，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶子结点。【华南理工大学 200323(2)(232 分)】（分数：2.00）_正确答案：(正确答案：首先设计一个函数，使用任何一种遍历方法，查找元素值等于某个给定的整数的结点，返回该结点指针。之后，再在遍历以该结点为根的子树的过程中求叶子结点。)解析：3.用类 Pascal 语言编写一非递归算法，求二叉树上叶子结点的数量。二叉树用二叉链表存储，左指针定义为 lch

16、ild，右指针定义为 rchild。【燕山大学 2000 七、2(8 分)】（分数：2.00）_正确答案：(正确答案：以二叉链表为存储结构的二叉树遍历的非递归算法，在“访问根结点”时，加上判断该结点是否是叶子结点的语句，对叶子结点进行计数就行了。)解析：4.一棵二叉树以二叉链表来表示，求其指定的某一层 k(k1)上的叶子结点的个数。【上海大学 1999 三、1(18 分)】（分数：2.00）_正确答案：(正确答案：对某层上的结点进行运算，采用队列结构按层次遍历最适宜。核心语句段如下： BiTree P=bt，Q； Q 是队列，元素是二叉树结点指针，容量足够大 int front：0，rear：

17、1，leaf：0； front 和 rear 是队头和队尾指针，leaf 是叶子结点数 int last：1，level=1；Q1=P； last 是同层最右结点的指针，level 是二叉树的层数 while(frontIchild *childPtr; typedef struct E1emtype data； childPtr *firstchild; 孩子链表头的指针 *CTBox; Typedef struct CTBox nodesMAX_rREESIZE； int n; n 为结点数 *CTree 写出求树的度的算法。【南京理工大学 2004 四(5 分)】（分数：2.00）_正确

18、答案：(正确答案：这是用孩子表示法存储的树，第 i 个链表中孩子结点的个数是结点 i 的度。对 n个结点，求出每个结点的度，取最大值为树的度。)解析：8.设 i 是一棵按后序遍历方式构成的线索二叉树的根结点指针，试设计一个非递归的算法，把一个地址为x 的新结点插到 t 树中已知地址为 y 的结点右侧作为结点 y 的右孩子，并使插入后的二叉树仍为后序线索二叉树。【东北大学 1996 七(15 分)】（分数：2.00）_正确答案：(正确答案：在线索二叉树上插入结点，破坏了被插入结点的线索。因此，插入结点时，必须修复线索。在结点 y 的右侧插入结点 x，因为是后序线索树，要区分结点 y 有无左子树的

19、情况。本题假定y 结点无右子树。核心语句段如下： if(y 一ltag=0) y 有左子女 p=y 一lchild； if(p 一rtag=1)p 一rchild=x； x 是 y 的左子女的后序后继 x 一ltag=1 ； x 一lchild=p； x 的左线索是 y 的左子女 else y 无左子女 x 一ltag=1 ； x 一lchild=y 一1child； y 的左线索成为 x 的左线索 if(y 一1child 一rtag=1) 若 y 的后序前驱的右标记为 1 y 一1child 一rchild=x； 则将 y 的后序前驱的后继改为 x x 一rtag=1 ； x 一rchil

20、d=y；y 一rtag=0 ； y一rchild=x； x 作 y 的右子树)解析：9.请用类 C 或用类 Pascal 语言编写算法。请编写在中序全线索二叉树 T 中的结点 P 下插入一棵根为 X 的中序全线索二叉树的算法。如果尸左右孩子都存在，则插入失败并返回 FAI,SE；如果 P 没有左孩子，则X 作为尸的左孩子插入；否则 X 作为 P 的右孩子插入。插入完成后要求二叉树保持中序全线索并返回TRUE。【上海大学 2002 七、1(10 分)】（分数：2.00）_正确答案：(正确答案：在中序全线索化 T 树的 P 结点上，插入以 X 为根的中序全线索化二叉树，要对 X有无左右子树进行讨论

21、，并修改 X 左(右)子树上最左结点和最右结点的线索。在中序线索树上查找某结点p 的前驱的规律是：若 p 一ltag=1，则 p 一lchild 就指向前驱，否则，其前驱是 p 的左子树上按中序遍历的最后一个结点；查找某结点 p 的后继的规律是：若 p 一rtag=1，则 p 一rchild 就指向后继，否则，其后继是 p 的右子树上按中序遍历的第一个结点。这里只讨论 P 有左子女，将 X 插为 P 的右子女的情况。核心语句段如下： if(P 一ltag=0) p 有左子女，将 x 插为 p 的右子女 if(x 一l 七 ag=1)x 一lchild=P； 若 x 无左子树， x 的左线索(前

22、驱)是 P else 寻找 x 的左子树上最左(下)边的结点 q=x 一lchild； while(q 一ltag=0) q=q 一lchild； q 一lchild=p； if(X 一rtag=1) x 一rchi1d=P 一rchild； 修改 x 的右线索，将 P 的右线索改为 x 的右线索 else 找 x 右子树最右面的结点 q=x 一rchild； while(q 一rtag=0) q=q 一rchild； q 一rchild=P 一rchild； P一rtag=0 ； p 一rchId=x； 将 x 插入为 P 的右子树 结束将 x 插入为 p 的右子树)解析：10.有中序线索树

23、 T，结点形式为：(LL，LT, D，RT,RL)，试编写非递归算法找到数据域为 A 的结点，并在其左子树中插入值为 Q 的已知新结点 X： （分数：2.00）_正确答案：(正确答案：在中序线索树中，非递归查找数据域为 A 的结点(设该结点存在，其指针为尸)并将数据域为 x 的 Q 结点插入左子树中。若 P 无左子女，则 Q 成为尸的左子女，原 P 的左线索成为 Q 的左线索，Q 的右线索为 P；若 P 有左子树，设 P 左子树中最右结点的右线索是结点 Q，结点 Q 的右线索是 P。 while(p) 初值 p=中序线索二叉树根结点指针 while(P 一LT=0 p 指向二叉树的根结点，当二

24、叉树为空时，p 指向头结点 thrt whild(p!=thrt) while(p 一ltag=0)p=p 一lchild 沿左子女向下 visit(tp) 访问左子树为空的结点 while(p 一rtag=l 左子树前序线索化 preorderThreat(BT一rchild); 右子树前序线索化 )解析：16.写出中序线索二叉树的线索化过程(已知二叉树 T)。【山东大学 2000 五、2(10 分)】【南京邮电学院1999 五(18 分)】（分数：2.00）_正确答案：(正确答案：在中序遍历中完成线索化。下面只给对“访问根结点”进行改造的语句段： if(T一ichild=null)T 一I

25、tag=1；T 一ichild=pre； 左线索为 pre if(pre!=nullpre 一rtag=1)pre 一rchild=T； 给前驱加后继线索 if(T 一rchild=null)T 一rtag=1； 置右标记，为右线索作准备 pre=T； 前驱指针后移)解析：17.已知一个二叉树如下图(编者略)，修改结点(node)的连接方式，以致可以不借助辅助堆栈实现中序遍历的非递归方法。画出修改后的结点连接图并写出其实现中序遍历的非递归算法。【浙江大学 2002 五(10分)】（分数：2.00）_正确答案：(正确答案：不借助堆栈实现中序遍历，必须解决如何查找后继的问题。使用线索树就可完成。为

26、此，将结点结构修改为(1tag，lchild，data，rchild，rtag)。)解析：18.已知中序线索二叉树 T 右子树不空。设计算法，将 S 所指的结点作为 T 的右子树中的一个叶子结点插入进去，并使之成为 T 的右子树的(中序序列)第一个结点(同时要修改相应的线索关系)。【合肥工业大学2001 五、2(8 分)】（分数：2.00）_正确答案：(正确答案：若使新插入的叶子结点 S 成 T 右子树中序序列的第一个结点，则应在 T 的右子树中最左面的结点(设为 p)处插入，使 S 成为结点 P 的左子女，则 S 的前驱是 T，后继是 P。 p=T 一rchild； p 指向 T 的右子女

27、while(p 一itag=0)p=p 一Ichild； P 最终指向 T 的右子树中最左面的结点 S 一itag=1； s 一rtag=1； s 是叶子，其左右标记均为 1 s 一ichild=T；s 一rchild=p； s 的前驱是根结点 T，后继是结点 P P 一ichild=S；p-itag=0; 将 P 的左子女指向S，并修改左标志为 0)解析：19.写出算法，求出中序线索二叉树中给定值为 x 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：(1tag，lc，data，rc，aag)。其中，data 存放结点的值；lc，rc 为指向左、右孩子或该结点前驱或后继的指针；l

28、tag，rtag 为标志域，若值为 0，则 lc，rc 为指向左、右孩子的指针；若值为1，则 1c，rc 为指向其前驱、后继结点的指针。【北京邮电大学 1996 八(20 分)】（分数：2.00）_正确答案：(正确答案：首先查找值为 X 的结点，设结点存在，且指针 p 指向该结点。若 P 一rtag=1，P一RC 不为空，则 P 一rc 指向其后继；若 P 一rtag=0，P 结点有右子女，则其右子树上按中序遍历的第一个结点是其后继。前面几个题已有涉及找中序后继的内容，这里不再赘述。)解析：20.设计算法求中序线索二叉树中指针 P 所指结点的前驱结点的指针。【东南大学 2004 五 (10 分

29、)】（分数：2.00）_正确答案：(正确答案：中序线素二叉树中指针 P 所指结点的前驱结点的特征是：若 P-ltag=l，P-lchild 指向其前驱，否则，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.设后序线索树中结点构造为(Ltag，Lchild，Data，Rchild，Rtag)。其中：Ltag，Rtag 值为 0 时，Lchi

30、ld、Rchild 分别为儿子指针；否则分别为直接前驱、直接后继的线索。请写出在后序线索树上找给定结点 p的直接前驱 q 的算法。【武汉交通科技大学 1966 四、1(13 分)】（分数：2.00）_正确答案：(正确答案：二叉树的后序遍历是“左右一根”，因此，若结点有右子女，则右子女是其后序前驱，否则，左子女(或左线索)指向其后序前驱。核心语句如下： if(p 一Rtag=0)return(p-Rchild); 若 P 有右子女，则右子女为其前驱 else return(p 一Lchild)； 若 P 无右子女，左子女或左线索就是 P 的后序前驱)解析：22.用算法说明在对称序线索树中，如何对

31、任意给定的结点直接找出该结点的对称序后继。【山东大学1999 六、3(10 分)】（分数：2.00）_正确答案：(正确答案：中序线索树任意给定的结点 P 中序后继的特点是，若 P-rtag=1，则 P-rchild指向其后继，否则，其右子树最左结点是其中序后继。)解析：23.写出在中序线索二叉树中找指定结点在后序下的前驱结点的算法。【河海大学 1998 七(10 分)】（分数：2.00）_正确答案：(正确答案：在后序序列中，若结点 P 有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点 P 左右子女均无，设其中序左线索指向某祖先结点 f(p 是厂右子树中按中序遍历的第一

32、个结点)，若 f 有左子女，则其左子女是结点 P 在后序下的前驱；若厂无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女(这时左子女是 P 的前驱)。还有一种情况，若 P 是中序遍历的第一个结点，结点 P 在中序和后序下均无前驱。)解析：24.设中序线索二又树的结点由五个域构成：info：给出结点的数据场之值。LL：当 LT 为 1 时，则给出该结点的左儿子之地址，当 LT 为 0 时，则给出按中序遍历的前驱结点的地址。LT：标志域，为 1 或为0。RL：当 RT 为 1 时，则给出该结点的右儿子的地址；当 RT 为 0 时，则给出按中序遍历的后继结点地址。RT：标志域为 0 或为 l。

33、请编写程序，在具有上述结点结构的中序线索二叉树上，求某一结点 p 的按后序遍历次序的后继结点的地址 q，设该中序线索二叉树的根结点地址为 r。另外，请注意必须满足：(1)额外空间的使用只能为 O(1)，(2)程序为非递归。【上海交通大学 2000 十(20 分)】（分数：2.00）_正确答案：(正确答案：在中序线索二叉树中，求某结点 P 的后序后继 g，需要知道 P 的双亲结点 f 的信息。(中序线索树的性质；若 P 是 f 的左子女，DJf 是 p 的最右子孙的右线索；若 p 是 f 的右子女，则 f是 p 的最左子孙的左线索。)找到 f 后，若 p 是 f 的右子女，则 p 的后继是 f

34、若 p 是 f 的左子女，且 f 无右子女，则 p 的后继也是 f;若 p 是 f 的左子女，且 f 有右子女，则 f 的右子树中最左边的叶子结点是 p的后继。因此，算法思路是，先找 p 的双亲 f,根据 p 是 f 的左右子女再确定 p 的后序后继。)解析：25.写出按后序序列遍历中序线索树的算法。【东南大学 2000 六(15 分)】（分数：2.00）_正确答案：(正确答案：上题讨论了中序线索树中查找结点 p 的后序后继问题，本题要求在中序线索树上进行后序遍历。因后序遍历是“左一右一根”，最后访问根结点，即只有从右子树返回时才能访问根结点，为此设一标志 flag，当其为 1 时表示从右侧返

35、回，可以访问根结点。为了找当前结点的后继，需知道双亲结点的信息，在中序线索树中，某结点最左子孙的左线索和最右子孙的右线索均上指双亲或祖先，因此设立两个函数 LeftMost 和 RightMost 求结点的最左和最右子孙，为了判定是否是从右子树返回，再设一函数 IsRightChild。下面是求结点 t 最左子孙的左线索： BiThrTree 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，否则返回 0 int