2018年复旦大学计算机科学技术学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
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． 设单链表的表头指针为h ，结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc(h，n) ，判断该链表的前n 个字符是否中心对称。例如xyx ，xyyx 都是中心对称。
【答案】算法如下:
//h是带头结点的n 个字符元素的单链表，本算法判断链表是否中心对称
//i记下结点个数，s 是字符栈
//P是链表的工作指针，指向待处理的当前元素
//链表前一半元素入栈
//恢复最后的i 值
//若n 是奇数，后移过中心结点
//测试
是否中心对称
//链表中心对称
//链表不中心对称
//算法结束
3． 编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。
【答案】算法如下:
全局变量链表头指针
将
若bt 不空
中序遍历左子树
叶结点
第一个叶结点
生成头结点
头结点的左链空，右链指向第一个结点
第一个叶结点左链指向头结点，pre 指向当前叶结点
树中的所有叶结点链成带头结点的双链表
当前叶结点链入双链表
中序遍历右子树
最后一个叶结点的右链置空(链表结束标记
)
结束
；
4． 图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算法。
【答案】算法如下:
利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G 的最小生成
树
数组存放生成树
数组存放顶点是否找到最短路径
初始化, 设顶点信息就是编号
从v0开始，求其最小生成树
是尚未到最小生成树的顶点的集合
循环n －1次
顶点u 已找到最短路径下，下面修改相关顶点的最短路径
算法结束
5． 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。
【答案】算法如下:
//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间
//pa、pb 是两链表的工作指针
//监视哨
//pa指针后移
//pb指针后移
相关内容
相关标签