2018年同济大学建筑与城市规划学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 假设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)算法如下:
以嵌套括号表示结构打印二叉排序树
打印根结点值
左子女和右子女中至少有一个不空
输出左栝号
输出左子树的嵌套括号表示
若右子树不空，输出逗号
输出右子树的嵌套括号表示
输出右括号
2． 设键盘输入n 个英语单词，输入格式为词个数，试编一程序，建立一个单向链表，实现:
(1)如果单词重复出现，则只在链表上保留一个。
(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k＜＝n) 个单词。
【答案】定义结点数据类型如下:
//频度域，记单词出现的次数
//maxsize是单词中可能含有的最多字母个数
(1)算法如下:
（ ）
//建立有n(n＞0) 个单词的单向链表，若单词重复出现，则只在链表中保留一个
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//p是工作指针，pre 是前驱指针
其中n 表示随后输入英语单
//单词重复出现，频度增
1
//指针后移
//该单词没出现过，应插入
//将新结点插入到链表最后
//结束for 循环
//结束creat 算法 (2)算法如下:
（ ）
//建立有n 个单词的单向链表，重复单词只在链表中保留一个，最后输出频度最高的k 个单词
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//P是工作指针，pre 是前驱指针
//单词重复出现，频度增
1
//先将P 结点从链表上摘下，再按频度域值插入到合适位置
//将P 结点插入到合适位置
//指针后移
//该单词没出现过，应插入到链表最后
//if新结点插入
//结束for 循环建表
r
(输入要输出单词的个数
//输出频度最髙的k 个单词
(”第
) ；
个单词出现次\n”，++i，p ﹣＞data ，p ﹣＞freg) ；
相关内容
相关标签