2018年北京市培养单位材料科学与光电技术学院864程序设计之数据结构考研核心题库
● 摘要
一、算法设计题
1． 假设串的存储结构如下所示，编写算法实现串的置换操作。
【答案】算法如下:
//s和t 是用一维数组存储的串，本算法将s 串第i 个字符开始连续j 个字符用t 串置换，操作成功返回1，否则返回0表示失败
//检査参数及置换后的长度的合法性
//若S 串被替换的子串长度小于t 串长度，则S 串部分右移
//S串中被替换子串的长度小于t 串的长度
//将t 串复制到S 串的适当位置
//算法结束
//本算法是串的置换操作，将串S 中所有非空串t 相等且不重叠的子串用V 代替
//判断S 是否有和t 相等的子串
//串S 中包含和t 相等的子串
//creat操作是将串常量(此处为空串) 赋值给
temp
//求串t 和s 的长度
//用串v 替换t 形成部
分结果
//将串s 中串后的部分形成新的s 串
//求串s 的长度
//在新s 串中再找串t 的位置
//将串temp 和剩余的串s 连接后再赋值给s
}//if结束
//算法结束
2． 已知两个链表A 和B 分别表示两个集合，其元素递增排列。编一函数，求A 与B 的交集，并存放于A 链表中。
【答案】算法如下:
//设工作指针pa 和pb ；
//结果表中当前合并结点的前驱的指针
//交集并入结果表中
//释放结点空
间
//释放结点空间
//释放结点空间
//置链表尾标记
//注:本算法中也可对B 表不作释放空间的处理
3． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。
【答案】算法如下:
顺序表中记录个数
关键字
该关键字在顺序表中的下标
索引表的一项
关键字
记录中的其他数据
给有m 个记录的顺序表seq 建立索引表
index
监视哨
关键字放入正确位置
第i 个记录的下标
4． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
r 最小值
("最大值) ；
5． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
【答案】算法如下:
//串用一维数组s 存储，本算法求最长重复子串，返回其长度
//index记最长的串在s 串中的开始位置，max
记其长度
//length记局部重复子串长度，i 为字符数组下标
//上一个重复子串结束
//当前重复子串长
度大，则更新
max
//初始化下一重复子串的起始位置和长度
(”最长重复子串的长度为
，在串中的位置
，max ，index) ；
相关内容
相关标签