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

一、算法设计题

1． 结点类型和存储结构如下:

试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。

【答案】算法如下:

对存储在数组R 中的记录进行排序

初始化

设R[0]作监视哨，Max 是该类型最大元

素

初始假定第一个元素有序

前驱

第一个元素

査找第i 个元素的序号

将笫i 个元素链入静态链表

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

【答案】算法如下:

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

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

当前元素是红色

第 2 页，共 37 页

当前元素是白色

当前元素是蓝色

3． 假设串的存储结构如下所示，编写算法实现串的置换操作。

【答案】算法如下:

//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结束

//算法结束

第 3 页，共 37 页

4． 设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针) ，data(数据) 和next(后继指针) 域外，还有一个访问频度域freq 。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L，X) 运算时，令元素值为x 的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增(递减) 的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x) 运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

【答案】算法如下:

//L是带头结点的按访问频度递减的双向链表

//本算法先査找数据x ，査找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中

//P为L 表的工作指针，q 为p 的前驱，用于査找插入位置

//查找值为x 的结点

("不存在所査结点\n”) ；exit(0)；

//令元素值为x 的结点的freq 域加

1

//将P 结点从链表上摘下

//以下査找P 结点的插人位置

//将P 结点插人

//返回值为x 的结点的指针

//算法结束

5． 从键盘上输入一串正整数，最后输入-1作为结束标志。如:8，7，1，22，98，46，... ，75，-1。请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设ltag ，data ，rta9，right) 。该二叉排序树上的结点结构为(teft，其中:data 域为结点的数据场。那么left 域中存在的是该结点的左儿子结点的地址。序遍历次序的前驱结点的地址。

【答案】算法如下:

从键盘上输入一串正整数，建立一棵初始为空的二叉排序树，同时也是线索二叉树

第 4 页，共 37 页

，

，那么left 域中存放的是该结点的按中

，那么right

域中存放的是该结点的右儿子结点的地址。

，那么right 域中存放的是该结点的按中序遍历次序的后继结点地址。