2018年北京师范大学脑与认知科学研究院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
【答案】算法如下:
//串用一维数组s 存储，本算法求最长重复子串，返回其长度
//index记最长的串在s 串中的开始位置，max
记其长度
//length记局部重复子串长度，i 为字符数组下标
//上一个重复子串结束
//当前重复子串长
度大，则更新
max
//初始化下一重复子串的起始位置和长度
(”最长重复子串的长度为
.//算法结束
，在串中的位置
，max ，index) ；
时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。
2． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)
【答案】算法如下:
//L是带头结点的单链表，本算法删除其最小值结点
//P为工作指针。指向恃处理的结点。假定链表非空
//pre指向最小值结点的前驱
//q指向最小值结点，初始假定第一元素结点是最小值结点
//查最小值结点
//指针后移
//从链表上刪除最小值结点
//释放最小值结点空间
//结束算法Delete
3． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，
试写出判断表达式中括号
是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:
//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配
//s是一维数组，容量足够大，是用于存放括号的栈
//top用作栈顶指针
//'#先入栈，用于和表达式结束符号'#'匹配
//字符数组E 的工作指针
//逐字符处理字符表达式的数组
//读人其他字符，不进行处理
4． 在一个循环链队中只有尾指针(记为rear ，结点结构为数据域data ，指针域next) ，请给出这种队列的入队和出队操作的实现过程。
【答案】算法如下:
//rear是带头循环链队列的尾指针，本算法将元素X 插入到队尾
//申请结点空间
//将s 结点链入队尾
//rear指向新队尾
//rear是带头结点的循环链队列的尾指针
//本算法执行出队操作，成功输出队头元素；否则给出出错信息
//s指向队头元素
//队头元素出队
//空队列
5． 以三元组表存储的稀疏矩阵A ，B 非零元个数分别为m 和n 。试用类PASCAL 语言编写时间复杂度为0(m＋n) 的算法将矩阵B 加到矩阵A 上去。A 的空间足够大，不另加辅助空间。要求描述所用结构。
【答案】算法如下:
＝大于非零元素个数的某个常量
//本算法实现以三元组表存储的各有m 和n 个非零元素两个稀疏矩阵相加，结果放到A 中
//L，p 为A ，B 三元组表指针，k 为结果三元组表榫针(下标
)
//行号不等时，行号大者的三元组为结果三元组表中一项
//A中当前项为结
果项
//B中当前项为结果
当前项
//行号相等时，比较列号
//结束行号相等时的处理
//结束行号比较处理
//结果三元组表的指针前移(减
1)
//结束WHILE 循环。