2018年复旦大学计算机科学技术学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。
【答案】算法如下:
//head是带头结点的单链表的头指针
//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间
//循环到仅剩头结点
//pre为元素最小值结点的前驱结点的指针
//P为工作指针
//记住当前最小值结点的前驱
//输出元素最小值结点的数据
//删除元素值最小的结点，释放结点
空间
//释放头结点
2． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；
。其中，data 存放结点的值；lc 、rc 为指向左、
右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。
【答案】算法如下:
先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在
设P 指向二叉树的根结点
第 2 页，共 39 页
结束
在中序线索二叉树T 中,, 求给定值为x 的结点的
后继结点
首先在T 树上査找给定值为x 的结点，由p 指向
' 若P 的右标志为1, 则P 的rc 指针指向其后继
结点P 的右子树中最左边的结点是结点P 的中序后继
结库
.
满足下述性质
:
2
3． —个有向图G=(V，E) 的平方图
，使得表示。
【答案】算法如下:
且
当且仅当存在某个顶点
2
。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表
4． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
r 最小值
第 3 页，共 39 页
("最大值
5． 设记录
的关键字为
。
) ； ，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
指示新的胜者
到:_
小数
设置T 中" 败者" 的初值
依次从
出发调整败者
为完全二叉树T 的叶结点，本算法建立败者树
是与题中要求的关键字类型相同的机器最
的双亲结点
二、应用题
6． 假设利用边界标识法，并以首次拟合策略分配，已知在某个时刻可利用空间表的状态如图所示(注:存储块头部size 域的值和申请分配的存储量均包括头部和尾部的存储空间)) 请画出:
(1)当系统回收一个起始地址为559大小为45的空闲块之后的链表状态；
(2)系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态
【答案】(1)系统回收一个起始地址为559，大小为45的空闲块后，因右恻起始地址604为空闲块，应与之合并。合并后，成为起始地址为559，大小为167的空闲块。链表状态如图1所示:
第 4 页，共 39 页