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

一、算法设计题

1． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。

【答案】算法如下:

//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为

//p和q 分别是链表A 和B 的工作指针

//pre为A 中p 所指结点的前驱结点的指针

//A

链表中当前结点指针后移

//B链表中当前结点指针后移

//处理A , B 中元素值相同的结点，

应刪除 //删除结点

2． 已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m)。

【答案】算法如下:

顺序表中记录个数

关键字

该关键字在顺序表中的下标

索引表的一项

关键字

记录中的其他数据

给有m 个记录的顺序表seq 建立索引表

index

监视哨

关键字放入正确位置

第i 个记录的下标

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

【答案】算法如下:

（ ）

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

//初始化

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

'//数字字符

//字母字符

//输出数字字符的个数

("数字％d 的个数＝

//求出字母字符的个数

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

//算法结束。

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

【答案】找的定乂:

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

//假设元素类型为整型

； //栈空间

//top为两个栈顶指针

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

) ；

) ；

为了尽量利用

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

(1)入栈操作:

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

(2)出栈操作

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

1

//算法结束

5． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为

【答案】算法如下:

从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素

，其中，2为排序树中所含结点数，m 为输出的关键字个数。

二、应用题

6． 某博物馆最多可容纳500人同时参观, 有一个出入口, 该出入口一次仅允许个通过。参观者的活动描述如下:

Cobegin

参观者进程i : {

进门;