当前位置：问答库＞考研试题

一、算法设计题

1． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。

【答案】算法如下:

r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储

本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后

当前元素是红色

当前元素是白色

当前元素是蓝色

2． 写出一趟快速排序算法。

【答案】算法如下:

一趟快速排序算法，枢轴记录到位，并返回其所在位置

3． —个有向图G=(V，E) 的平方图

，使得表示。

【答案】算法如下:

第 2 页，共 37 页

满足下述性质

:

当且仅当存在某个顶点

且

22

。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表

4． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。

【答案】算法如下:

//d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面

//设链表有头结点

//q指向待处理结点

//P记数据域值最大的结点

//将P 摘下

//插人P 结点

5． 已知两个链表A 和B 分别表示两个集合，其元素递增排列。编一函数，求A 与B 的交集，并存放于A 链表中。

【答案】算法如下:

//设工作指针pa 和pb ；

//结果表中当前合并结点的前驱的指针

//交集并入结果表中

//释放结点空

间

第 3 页，共 37 页

//释放结点空间

//释放结点空间

//置链表尾标记

//注:本算法中也可对B 表不作释放空间的处理

二、应用题

6． 证明:具有n 个顶点和多于n －1条边的无向连通图G —定不是树。

【答案】证明:具有n 个顶点n －1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n －1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。

7． 假设利用边界标识法，并以首次拟合策略分配，已知在某个时刻可利用空间表的状态如图所示(注:存储块头部size 域的值和申请分配的存储量均包括头部和尾部的存储空间)) 请画出:

(1)当系统回收一个起始地址为559大小为45的空闲块之后的链表状态；

(2)系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态

【答案】(1)系统回收一个起始地址为559，大小为45的空闲块后，因右恻起始地址604为空闲块，应与之合并。合并后，成为起始地址为559，大小为167的空闲块。链表状态如图1所示:

图1

(2)系统在接受存储块大小为100的请求后，将大小为117的空闲块分出100给予用户。在回收一个起始地址为515，大小为44的空闲块之后，因左侧起始地址为462、大小为53和右侧起始地址为559、大小为167均为空闲块，应与之合并。合并后，起始地址为462、大小为264的空闲块。链表状态如图2所示:

第 4 页，共 37 页