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

一、算法设计题

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

【答案】算法如下:

（ ）

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

//初始化

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

'//数字字符

//字母字符

//输出数字字符的个数

("数字％d 的个数＝

//求出字母字符的个数

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

//算法结束。

2． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。

【答案】算法如下:

在用邻接表方式存储的无向图g 中，删除边(i,

j)

删顶点i 的边结点(i, j) , pre 是前驱指针

释放空间

沿链表继续査找

删顶点j 的边结点(j,

i)

) ；

) ；

释放空间

沿链表继续査找

3． 在一个循环链队中只有尾指针(记为rear ，结点结构为数据域data ，指针域next) ，请给出这种队列的入队和出队操作的实现过程。

【答案】算法如下:

//rear是带头循环链队列的尾指针，本算法将元素X 插入到队尾

//申请结点空间

//将s 结点链入队尾

//rear指向新队尾

//rear是带头结点的循环链队列的尾指针

//本算法执行出队操作，成功输出队头元素；否则给出出错信息

//s指向队头元素

//队头元素出队

//空队列

4． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:

{二叉树根结点的指针}

【答案】算法如下:

生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写

)

是二叉树结点指针的一维数组，容量足够大

一维数组最后元素的下标

元素或虚结点

根结点

双亲结点和子女结点用指针链上

结束

5． 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key 的记录。设此组记录存放于数组

【答案】算法如下:

本句的有无不影响査找结果

中。若查找成功，则输出该记录在r 数组中的位置及其值，否则显示“not

find ”信息。请编写出算法并简要说明算法思想。

二、应用题

6． 快速排序的最大递归深度是多少? 最小递归深度是多少？

【答案】设待排序记录的个数为n ，则快速排序的最小递归深度为

，最大递归深度

n 。

7． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示(如SXSX) 。

(1)试指出判别给定序列是否合法的一般规则；

(2)两个不同合法序列(对同一输入序列) 能否得到相同的输出元素序列? 如能得到，请举列说明。

【答案】(1)通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。

(2)可以得到相同的输出元素序列。例如，输入元素为A ，B ，C ，则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序列BAC ，使用SSXXSX 操作序列。