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

一、算法设计题

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

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

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

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

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

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

(1)算法如下:

（ ）

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

//申请头结点

//链表初始化

//建立n 个结点的链表

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

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

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

1

//指针后移

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

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

//结束for 循环

//结束creat 算法

第 2 页，共 36 页

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

(2)算法如下:

（ ）

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

//申请头结点

//链表初始化

//建立n 个结点的链表

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

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

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

1

//先将P 结点从链表上摘下，再按频度域值插入到合适位置

//将P 结点插入到合适位置

//指针后移

//该单词没出现过，应插入到链表最后

//if新结点插入

//结束for 循环建表

r

(输入要输出单词的个数

//输出频度最髙的k 个单词

(”第

//结束算法

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

【答案】找的定乂:

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

第 3 页，共 36 页

) ；

个单词出现次\n”，++i，p ﹣＞data ，p ﹣＞freg) ；

为了尽量利用

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

//假设元素类型为整型

； //栈空间

//top为两个栈顶指针

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

(1)入栈操作:

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

(2)出栈操作

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

1

//算法结束

3． 设在4地(A, B , C , D) 之间架设有6座桥，如图所示。

要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件是什么？

第 4 页，共 36 页