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

一、算法设计题

1． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。

【答案】算法如下:

//head是带头结点的单链表的头指针

//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间

//循环到仅剩头结点

//pre为元素最小值结点的前驱结点的指针

//P为工作指针

//记住当前最小值结点的前驱

//输出元素最小值结点的数据

//删除元素值最小的结点，释放结点

空间

//释放头结点

2． 设有两个栈S 1，S 2都采用顺序栈方式，并且共享一个存储区的操作算法。

【答案】找的定乂:

两栈共享顺序存储空间所能达到的最多元素数

//假设元素类型为整型

； //栈空间

//top为两个栈顶指针

第 2 页，共 37 页

为了尽量利用

空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S 1，S 2有关入栈和出找

//S是如上定义的结构类型变量，为全局变量

(1)入栈操作:

//入栈操作。i 为栈号，i ＝〇表示左栈Sl ，i ＝l 表示右栈s2，x 是入栈元素。入栈成功返回1，否则返回

(2)出栈操作

//出栈算法。i 代表栈号，i ＝0时为s1栈，i ＝l 时为s2栈。出栈成功返回出栈元素，否则返﹣

1

//算法结束

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

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

【答案】算法如下:

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

初始化

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

素

初始假定第一个元素有序

前驱

第 3 页，共 37 页

第一个元素

査找第i 个元素的序号

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

4． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。

【答案】算法如下:

//串用一维数组s 存储，本算法求最长重复子串，返回其长度

//index记最长的串在s 串中的开始位置，max

记其长度

//length记局部重复子串长度，i 为字符数组下标

//上一个重复子串结束

//当前重复子串长

度大，则更新

max

//初始化下一重复子串的起始位置和长度

(”最长重复子串的长度为

.//算法结束

5． 设键盘输入n 个英语单词，输入格式为词个数，试编一程序，建立一个单向链表，实现:

(1)如果单词重复出现，则只在链表上保留一个。

(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k＜＝n) 个单词。

【答案】定义结点数据类型如下:

//频度域，记单词出现的次数

//maxsize是单词中可能含有的最多字母个数

(1)算法如下:

第 4 页，共 37 页

，在串中的位置，max ，index) ；

时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。

其中n 表示随后输入英语单