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

一、算法设计题

1． 对给定关键字序号j(1

中找到关键字从小到大排在第j 位上的记

录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。

例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下；

在后半部分继续进行划分

在前半部分继续进行划分

2． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

【答案】算法如下:

//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表

//pa, pb 分别是链表la 和lb 的工作指针

//la作为结果链表的头指针，先将结果链表初始化为空

//当两链表均不为空时

//将pa 的后继结点暂存于r

第 2 页，共 41 页

//将pa 结点链于结果表中，同时逆置

//恢复pa 为当前待比较结点

//将pb 的后继结点暂存于

r

//将pb 结点链于结果表中，同时逆置

//恢复pb 为当前待比较结点

//避免再对pa 写下面的While 语句

//算法Union 结束

3． 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。

【答案】算法如下:

//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间

//pa、pb 是两链表的工作指针

//监视哨

//pa指针后移

//pb指针后移

//处理交集元素

//删除重复元素

//交集元素并入结果表

//置结果链表尾

4． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，

试写出判断表达式中括号

是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。 【答案】算法如下:

第 3 页，共 41 页

//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配

//s是一维数组，容量足够大，是用于存放括号的栈

//top用作栈顶指针

//'#先入栈，用于和表达式结束符号'#'匹配

//字符数组E 的工作指针

//逐字符处理字符表达式的数组

//读人其他字符，不进行处理

5． 编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A 〜Z 这26个字母和0〜9这10个数字) 。

【答案】算法如下:

（ ）

//统计输入字符串中数字字符和字母字符的个数

//初始化

//’#’表示输入字符串结束

'//数字字符

//字母字符

//输出数字字符的个数

("数字％d 的个数＝

//求出字母字符的个数

("字母字符％c 的个数＝

//算法结束。

) ；

) ；

二、应用题

6． 已知一个整数序列

且又如

, 其中

, 则称x 为A 的主元素。例如

第 4 页，共 41 页

, 若存在

, 则称5为主元素;

则A 中没有主元素。假设A 中的n 个元素保存在一个一维数组中,