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

一、算法设计题

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

【答案】算法如下:

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

j)

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

释放空间

沿链表继续査找

删顶点j 的边结点(j,

i)

释放空间

沿链表继续査找

2． 写出一个递归算法来实现字符串逆序存储。

【答案】算法如下:

//字符串逆序存储的递归算法

r

//需要使用静态变量

//

规定

是字符串输入结束标志

//字符串逆序存储

//字符串结尾标记

//结束算法InvertStore

3． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。

【答案】算法如下:

按递减次序输出二叉排序树结点的值

是元素为二叉树结点指针的栈，容量足够大

沿右子树向下

结束

4． 已知二叉树采用二叉链表存储，设计算法以输出二叉树T 中根结点到每个叶结点的路径。

【答案】算法如下::

打印从根结点bt 到结点p 之间路径上的所有结点

.

是元素为二叉树结点指针的栈，容量足够大

是数组，元素值为0或1, 访问左、右子树的标志，tag 和s 同

步

根结点就是所找结点

左子女入栈，并置标记

找到结点P , 栈中元素均为结点P 的祖先

从根结点到P 结点的路径为

沿左分支向下

本题不要求输出遍历序列，

这里只出栈

沿右分支向下

结束算法

为叶结点

从根结点到P 结点的路径为

输出从根到叶子q 的路径上的所有袓先

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

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

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

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

出现次数最多的前k(k＜＝n) 个单词。

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

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

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

(1)算法如下:

（ ）

//建立有n(n＞0) 个单词的单向链表，若单词重复出现，则只在链表中保留一个

//申请头结点

//链表初始化

//建立n 个结点的链表

//a是与链表中结点数据域同等长度的字符数组

//p是工作指针，pre 是前驱指针

//单词重复出现，频度增

1

//指针后移

//该单词没出现过，应插入

//将新结点插入到链表最后

//结束for 循环

//结束creat 算法 (2)算法如下:

（ ）

//建立有n 个单词的单向链表，重复单词只在链表中保留一个，最后输出频度最高的k 个单词

//申请头结点

//链表初始化

//建立n 个结点的链表

//a是与链表中结点数据域同等长度的字符数组

//P是工作指针，pre 是前驱指针

//单词重复出现，频度增1