2018年广东省培养单位深圳先进技术研究院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。
【答案】算法如下:
（ ）
//统计输入字符串中数字字符和字母字符的个数
//初始化
//’#’表示输入字符串结束
'//数字字符
//字母字符
//输出数字字符的个数
("数字％d 的个数＝
//求出字母字符的个数
("字母字符％c 的个数＝
//算法结束。
2． 假设K1，... ，Kn 是n 个关键词，试解答：
(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn 时，用算法建立一棵以llink —rlink 链接表示的二叉查找树。
(2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立如图所示的二叉查找树。
) ；
) ；
图
该二叉查找树的嵌套括号表示结构为:B(A，D(C，E)) 。
【答案】(1)算法如下:
在二叉排序树bst 上査找值为K 的结点，返回其双亲结点指针
f
以存储在数组R 中的n 个关键字，建立一棵初始为空的二叉排序树
不再插入相同值结点
.
申请结点空间
根结点
左子女
右子女
结束算法 (2)算法如下:
以嵌套括号表示结构打印二叉排序树
打印根结点值
左子女和右子女中至少有一个不空
输出左栝号
输出左子树的嵌套括号表示
若右子树不空，输出逗号
输出右子树的嵌套括号表示
输出右括号
3． 在一个循环链队中只有尾指针(记为rear ，结点结构为数据域data ，指针域next) ，请给出这种队列的入队和出队操作的实现过程。
【答案】算法如下:
//rear是带头循环链队列的尾指针，本算法将元素X 插入到队尾
//申请结点空间
//将s 结点链入队尾
//rear指向新队尾
//rear是带头结点的循环链队列的尾指针
//本算法执行出队操作，成功输出队头元素；否则给出出错信息
//s指向队头元素
//队头元素出队
//空队列
4． 已知一棵高度为K 具有n 个结点的二叉树，按顺序方式存储。
(1)编写用前序遍历树中每个结点的非递归算法；
(2)编写将树中最大序号叶结点的祖先结点全部打印输出的算法。 【答案】(1)算法如下:
全局变量
递妇遍历以顺序方式存储的二叉树bt ，i 是根结点下标(初始调用时为
1)
是桟s 的栈顶指针，栈容量足够大
访问根结点，设虚结点
以0表示
右子女的下标位置入
栈
沿左子女向下
取出栈顶元素
结束
(2)算法如下:
打印最大序号叶结点的全部袓先
找最大序号叶结点，该结点存储时在最后
相关内容
相关标签