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

一、算法设计题

1． 在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L ，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。

顺序存储结构的线性表描述为:

线性表可能达到的最大长度}；

【答案】算法如下:

//在顺序表a 中査找值为x 的元素，査找成功返回0值，否则返回查找失败时的较大下标值

//当査找失败时，low ＝high ＋

1

//结束对分査找函数

//本过程生成顺序表

L

//顺序表L 初始化

//设x ＝9999时退出输入

//去查找x 元素

//不同元素才插入

//插入元素x ，线性表长度增

1

//结束过程creat

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

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

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

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

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

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

(1)算法如下:

（ ）

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

//申请头结点

//链表初始化

//建立n 个结点的链表

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

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

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

1

//指针后移

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

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

//结束for 循环

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

（ ）

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

//申请头结点

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

//链表初始化

//建立n 个结点的链表

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

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

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

1

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

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

//指针后移

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

//if新结点插入

//结束for 循环建表

r

(输入要输出单词的个数

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

(”第

//结束算法

3． 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空，入桟和出找的操作序列可表示为仅由I 和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

(1)下面所示的序列中哪些是合法的？

A.

B.

C.

D.

(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false(假定被判定的操作序列已存入一维数组中) 。

【答案】(1)A和D 是合法序列，B 和C 是非法序列。 (2)设被判定的操作序列已存入一维数组A 中，算法如下:

//判断字符数组A 中的输入输出序列是否是合法序列。

//i为下标

) ；

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