2018年北京大学软件与微电子学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 已知一个单链表中每个结点存放一个整数，并且结点数不少于2, 请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture ，否则返回false 。
【答案】算法如下:
//la是结点的元素为整数的单链表。本算法判断从第二结点开始
//毎个元素值是否等干其序号的平方减去其前驱的值，如是返回true ；否则，返回
false
//P是工作指针，初始指向链表的第二项
//pre是p 所指结点的前驱指针
//i是la 链表中结点的序号，初始值为
2
//结点值间的关
系符合题目要求
//当前结点的值不等于其序号的平方减去前驱的值
//未查到表尾就结束了
//成功返回
//算法结束
//假设无头结点，初始P 指向第一元素结点
//初始p ﹣＞next 指向第二项
//失败
//成功
2． 试将下列递归过程改写为非递归过程。
【答案】算法如下:
3． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。
【答案】算法如下:
（ ）
//统计输入字符串中数字字符和字母字符的个数
//初始化
//’#’表示输入字符串结束
'//数字字符
//字母字符
//输出数字字符的个数
("数字％d 的个数＝
//求出字母字符的个数
("字母字符％c 的个数＝
//算法结束。
4． 二路插入排序是将待排关键字序列二路插入。编写实现2-路插入排序算法。
【答案】算法如下:
二路插入排序的算法
辅助存储
) ；
) ；
中关键字分二路分别按序插入到辅助向量
前半部和后半部(注.. 向量d 可视为循环表) ，其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分
插人后部
折半査找插入位置
移动元素
插入有序位置
插入前部
移动元素
将序列复制回去
5． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)
【答案】算法如下:
//L是带头结点的单链表，本算法删除其最小值结点
//P为工作指针。指向恃处理的结点。假定链表非空
//pre指向最小值结点的前驱
//q指向最小值结点，初始假定第一元素结点是最小值结点
//查最小值结点
//指针后移
//从链表上刪除最小值结点
//释放最小值结点空间
//结束算法Delete
二、应用题