2018年北京大学信息科学技术学院907计算机专业基础之数据结构考研核心题库
● 摘要
一、算法设计题
1． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为
【答案】算法如下:
从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素
，其中，2为排序树中所含结点数，m 为输出的关键字个数。
2． 请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。
【答案】算法如下:
//A是的矩阵，本算法求矩阵A 中的马鞍点
//max数组存放各列最大值元素的行号，初始化为行号
//min数组存放各行最小值元素的列号，初始化为列号
0 //选各行最小值元素和各列最大值元素
//修改第j 列最大元素的
行号
" 修改第i 行最小元素的
列号
//第i 行最小元素的列号
是马鞍点，
元素值是
是马鞍点
第 2 页，共 36 页
//
3． 写出按后序序列遍历中序线索树的算法。
【答案】算法如下:
求结点t 最左子孙的左线索
沿左分支向下
求结点t 最右子孙的右线索
沿右分支向下
若t 是
后序遍历中序线索二叉树
bt
沿左分支向下
左孩子为线索，右孩子为链，相当从左返回
P 为叶子, 相当从右返回
访问结点
修改P 指向双亲
是左子女，用最右子孙的右线索找双亲
.
转向当前结点右分支
结束
满足下述性质
:
当且仅当存在某个顶点
4． —个有向图G=(V，E) 的平方图
，使得表示。
【答案】算法如下:
第 3 页，共 36 页
的右孩子，返回1, 否则返回
且
22
。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表
5． 写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。
【答案】算法如下:
//本算法将链表L1拆成L1和L2两个链表，L2链接方向与L1相反
//空链表
//奇数序号结点在L1中
//偶数序号
结点逆置插入到L2中
//置L1
表尾
二、应用题
6． 用单链表保存m 个整数, 节点的结构为(data, link) , 且余绝对值相等的节点。
例如若给定的单链表head 如下表
表
删除节点后的head 为
表
第 4 页，共 36 页
(n为正整数) 。现要求设计一个
时间复杂度尽可能高效地算法, 对于链表中绝对值相等的节点, 仅保留第一次出现的节点而删除其