2018年兰州理工大学计算机与通信学院408计算机学科专业基础综合[专业硕士]之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。
【答案】算法如下:
//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回
//对应字符相等，指针后移
2． 编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意:行、列及总表头结点的形式为:
它们已用val 域链接成循环链表。非零元的结点形式也同上，每一行(列) 的非零元由right(down)域把它们链接成循环链表，该行(列) 的表头结点即为该行(列) 循环链表的表头。
【答案】算法如下:
//输出由Hm 指向的十字链表中每一行的非零元素个数
//数组A 记各行非零元个数，i 记行号
//循环完各行列表头
//P是稀疏矩阵行内工作指针，num 记该行非零个
数
//完成行内非零元的查找
//指针后移
//存该行非零元个数
//移到下一行列表头
//输出各行非零元个数
第
}算法结束
3． 设键盘输入n 个英语单词，输入格式为词个数，试编一程序，建立一个单向链表，实现:
(1)如果单词重复出现，则只在链表上保留一个。
(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k＜＝n) 个单词。
【答案】定义结点数据类型如下:
//频度域，记单词出现的次数
//maxsize是单词中可能含有的最多字母个数
(1)算法如下:
（ ）
//建立有n(n＞0) 个单词的单向链表，若单词重复出现，则只在链表中保留一个
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//p是工作指针，pre 是前驱指针
//单词重复出现，频度增
1
//指针后移
//该单词没出现过，应插入
//将新结点插入到链表最后
//结束for 循环
//结束creat 算法 (2)算法如下:
行非零元个数为
}
//稀疏矩阵非零元个数
其中n 表示随后输入英语单
（ ）
//建立有n 个单词的单向链表，重复单词只在链表中保留一个，最后输出频度最高的k 个单词
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//P是工作指针，pre 是前驱指针
//单词重复出现，频度增
1
//先将P 结点从链表上摘下，再按频度域值插入到合适位置
//将P 结点插入到合适位置
//指针后移
//该单词没出现过，应插入到链表最后
//if新结点插入
//结束for 循环建表
r
(输入要输出单词的个数
//输出频度最髙的k 个单词
(”第
//结束算法
4． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。
【答案】算法如下:
r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储
本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后
) ；
个单词出现次\n”，++i，p ﹣＞data ，p ﹣＞freg) ；