2018年北京市培养单位材料科学与光电技术学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
2． 己知字符串S1中存放一段英文，写出算法format(s1，s2，s3，n) ，将其按给定的长度n 格式化成两端对齐的字符串S2，其多余的字符送S3。
【答案】算法如下:
//将字符串si 拆分成字符串S2和字符串S3，要求字符串S2长度为n 且两端对齐
//滤掉s1左端空格
("字符串s1为空串或空格串\n")；exit(0)；
}
//字符串S1向字符串S2中
复制
(”字符串s1没有
个有效字符\n"，n) ；exit(0)；
}
//若最后一个字符为空格，则需向后找到第一个非空格字符
第 2 页，共 35 页
求左子树表示的子表达式的值
求右子树表示的子表达式的值
//P指针也后退
//往后査找一个非空格字符作为串S2的尾字
符
("s1串没有
//字符串s2最后一个非空字符
//置S2字符串结束标记
//将s1串其余部分送字符串
S3
//置串S3结束标记
3． 假设K1，... ，Kn 是n 个关键词，试解答：
(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn 时，用算法建立一棵以llink —rlink 链接表示的二叉查找树。
(2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立如图所示的二叉查找树。
个两端对齐的字符串exit(0)；
}
图
该二叉查找树的嵌套括号表示结构为:B(A，D(C，E)) 。 【答案】(1)算法如下:
在二叉排序树bst 上査找值为K 的结点，返回其双亲结点指针
f
以存储在数组R 中的n 个关键字，建立一棵初始为空的二叉排序树
不再插入相同值结点
第 3 页，共 35 页
.
申请结点空间
根结点
左子女
右子女
结束算法
(2)算法如下:
以嵌套括号表示结构打印二叉排序树
打印根结点值
左子女和右子女中至少有一个不空
输出左栝号
输出左子树的嵌套括号表示
若右子树不空，输出逗号
输出右子树的嵌套括号表示
输出右括号
4． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。
【答案】算法如下:
在增加双亲指针
和标志域
的二叉树中，不用栈后序遍历二叉树
) 区分在遍
历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍
向左
向右
访问根结点
找被访问结点的双亲
第 4 页，共 35 页