2018年北京大学深圳研究生院907计算机专业基础之数据结构考研核心题库
● 摘要
一、算法设计题
1． 设有一个数组中存放了一个无序的关键序列
【答案】算法如下:
2． 以三元组表存储的稀疏矩阵A ，B 非零元个数分别为m 和n 。试用类PASCAL 语言编写时间复杂度为0(m＋n) 的算法将矩阵B 加到矩阵A 上去。A 的空间足够大，不另加辅助空间。要求描述所用结构。
【答案】算法如下:
＝大于非零元素个数的某个常量
//本算法实现以三元组表存储的各有m 和n 个非零元素两个稀疏矩阵相加，结果放到A 中
//L，p 为A ，B 三元组表指针，k 为结果三元组表榫针(下标
)
//行号不等时，行号大者的三元组为结果三元组表中一项
//A中当前项为结
果项
//B中当前项为结果
当前项
第 2 页，共 40 页
。现要求将K n 放在将元素排序后
的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。
//行号相等时，比较列号
//结束行号相等时的处理
//结束行号比较处理
//结果三元组表的指针前移(减
1)
//结束WHILE 循环。
//处理B 的剩余部
分
//处理A 的剩余部
分
//稀疏矩阵相应元素相加时，有和为零的元素，因而元素总数＜m ＋
n
//三元组前移，使第一个三元组的下标
为
1
//修改结果三元组表中非零元素个数
//结束addmatrix
3． 假设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
第 3 页，共 40 页
以存储在数组R 中的n 个关键字，建立一棵初始为空的二叉排序树
不再插入相同值结点
.
申请结点空间
根结点
左子女
右子女
结束算法 (2)算法如下:
以嵌套括号表示结构打印二叉排序树
打印根结点值
左子女和右子女中至少有一个不空
输出左栝号
输出左子树的嵌套括号表示
若右子树不空，输出逗号
输出右子树的嵌套括号表示
输出右括号
4． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。
【答案】算法如下:
//本算法将无符号十进制整数m 转换为十六进制整数
第 4 页，共 40 页
相关内容
相关标签