2018年北京林业大学信息学院821计算机综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。
【答案】算法如下:
层次遍历二叉树，并统计度为1的结点的个数
统计度为1的结点的个数
是以二叉树结点指针为元素的队列
出队，访问结点
度为1的
结点
非空左子女入队
非空右子女入队
返回度为1的结点的个数
2． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；
。其中，data 存放结点的值；lc 、rc 为指向左、
右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。
【答案】算法如下:
先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在
设P 指向二叉树的根结点
结束
在中序线索二叉树T 中,, 求给定值为x 的结点的
后继结点
首先在T 树上査找给定值为x 的结点，由p 指向
第 2 页，共 32 页
' 若P 的右标志为1, 则P 的rc 指针指向其后继
结点P 的右子树中最左边的结点是结点P 的中序后继
结库
3． 当一棵有n(
.
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
，值是
设元素类型为
整型
4． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
5． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。
【答案】算法如下:
第 3 页，共 32 页
求左子树表示的子表达式的值
求右子树表示的子表达式的值
//head是带头结点的单链表的头指针
//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间
//循环到仅剩头结点
//pre为元素最小值结点的前驱结点的指针
//P为工作指针
//记住当前最小值结点的前驱
//输出元素最小值结点的数据
//删除元素值最小的结点，释放结点
空间
//释放头结点
二、应用题
6． KMP 算法(字符串匹配算法) 较Brute(朴素的字符串匹配) 算法有哪些改进？
【答案】朴素的模式匹配(Brute.Force)时间复杂度是
，KMP 算法有一定改进，时间复
杂度达到O(m＋n) 。主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP 算法的优点更为突出。
7． 对于后序线索二叉树，怎样查找任意结点的直接后继? 对于中序线索二叉树，怎样查找任意结点的直接前驱？
【答案】(1)后序线索树中结点的后继的方法如下:根结点无后继；当结点的rtag=1时，其右线索指向后继；当结点的rtag=0且是其双亲的右孩子，或是双亲的左孩子且双亲无右孩子时，其双亲是该结点的后继；当结点是其双亲的左孩子且双亲有右孩子时，其双亲结点右子树中最左下的叶结点是其后继。
(2)对中序线索二叉树的某结点，若其左标记等于1，则左孩子为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。
8． 给出模式串在KMP 算法中的next 和nextval 数组。
【答案】模式串的next 函数定义如下:
根据此定义，
可求解模式串
的next 和nextval 值如下:
第 4 页，共 32 页