2018年复旦大学软件学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1. 已知递增有序的单链表A ,B 分别存储了一个集合,请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ,并以同样的形式存储,同时返回该集合的元素个数。
【答案】算法如下:
//A和B 均是带头结点递增有序的单链表,本算法求两集合的差集,*n是结果集合中元素个数,初始为
//p和q 分别是链表A 和B 的工作指针
//pre为A 中p 所指结点的前驱结点的指针
//A
链表中当前结点指针后移
//B链表中当前结点指针后移
//处理A , B 中元素值相同的结点,
应刪除 //删除结点
2. 编写算法,将自然数1〜n 2按“蛇形”填nxn 矩阵中。例(1〜42) 如图所示(用程序实现) 。
图
【答案】算法如下:
//将自然数
,按" 蛇形M 填入n 阶方阵A 中
//i,j 是矩阵元素的下标,k 是要填入的自然数
//从右上向左下填数
//副对角线及以上部分的新i ,j 坐标
//副对角线以下的新的i ,j 坐标
//从左下向右上
//最外层
while
3. 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空,入桟和出找的操作序列可表示为仅由I 和0组成的序列,称可以操作的序列为合法序列,否则称为非法序列。
(1)下面所示的序列中哪些是合法的?
A.
B.
C.
D.
(2)通过对(1)的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true ,否则返回false(假定被判定的操作序列已存入一维数组中) 。
【答案】(1)A和D 是合法序列,B 和C 是非法序列。 (2)设被判定的操作序列已存入一维数组A 中,算法如下:
//判断字符数组A 中的输入输出序列是否是合法序列。
//i为下标
//j和k 分别为I 和字母O 的个数
//入栈次数增
1
//不论A[i]是’I'或’〇' ,指针i 均后移
//算法结束
4. 写算法将单链表11拆成二个链表,其中以11为头的链表保持原来向后的链接,另一个链表的头为12,其链接方向与11相反,11包含原链表的奇数序号的结点,12包含原链表的偶数序号的结点。
【答案】算法如下:
//本算法将链表L1拆成L1和L2两个链表,L2链接方向与L1相反
//空链表
//奇数序号结点在L1中
//偶数序号
结点逆置插入到L2中
//置L1表尾
5. 结点类型和存储结构如下:
试设计一个排序算法,要求不移动结点的存储位置,只在结点的count 字段记录结点在排序中的序号,并将排序结果按升序输出。
【答案】算法如下:
对存储在数组R 中的记录进行排序
初始化
设R[0]作监视哨,Max 是该类型最大元
素
初始假定第一个元素有序
前驱
第一个元素
査找第i 个元素的序号
将笫i 个元素链入静态链表
二、应用题