2018年广东省培养单位深圳先进技术研究院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(
【答案】算法如下:
在后半部分继续进行划分
在前半部分继续进行划分
2． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。
【答案】算法如下:
//设整数序列存于数组a 中，共有n 个，本算法求解其最大值
3． 编程:假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化(initqueue)，插入(enqueue)和删除(dequeue)元素的操作。
【答案】定义队列:
第 2 页，共 32 页
) 小元素。
//循环队列占m 个存储单元
//rear指向队尾元素，length 为元素个数
(1)设cq 是seQueue 类型变量，则当(2)队列的初始化:
//cq为循环队列，本算法进行队列初始化
//算法结束 (3)队列的插入:
//cq是已如上定义的循环队列，本算法将元素x 入队
//队满
.
//计算插入元素位置
//将元素x 入队列
//修改队列长度
//算法结束
//cq是已如上定义的循环队列，本算法是出队算法，且返回出队元素
//队空
；//出队元素位置
//修改队列长度
//返回队头元素
//算法结束
4． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)
【答案】算法如下:
//L是带头结点的单链表，本算法删除其最小值结点
//P为工作指针。指向恃处理的结点。假定链表非空
//pre指向最小值结点的前驱
//q指向最小值结点，初始假定第一元素结点是最小值结点
//查最小值结点
第 3 页，共 32 页
时队列空，当 时队列满。
(4)队列的删除:
//指针后移
//从链表上刪除最小值结点
//释放最小值结点空间
//结束算法Delete
5． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径
。
设有向图有n 个顶点
判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径
是队列，容量足够大，元素是顶点编号
人队
到顶点
不存在路径
【答案】算法如下:
二、应用题
6． 解答问题。设有数据逻辑结构为:
(1)画出这个逻辑结构的图示。
(2)相对于关系R ，指出所有的开始结点和终端结点。 (3)分别对关系R 中的开始结点，举出一个拓扑序列的例子。 (4)分别画出该逻辑结构的正向邻接表和逆向邻接表。 【答案】(1)如图1所示:
第 4 页，共 32 页