2018年温州医科大学检验医学院、生命科学学院408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 设键盘输入n 个英语单词，输入格式为词个数，试编一程序，建立一个单向链表，实现:
(1)如果单词重复出现，则只在链表上保留一个。
(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k＜＝n) 个单词。
【答案】定义结点数据类型如下:
//频度域，记单词出现的次数
//maxsize是单词中可能含有的最多字母个数
(1)算法如下:
（ ）
//建立有n(n＞0) 个单词的单向链表，若单词重复出现，则只在链表中保留一个
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//p是工作指针，pre 是前驱指针
//单词重复出现，频度增
1
//指针后移
//该单词没出现过，应插入
//将新结点插入到链表最后
//结束for 循环
//结束creat 算法
第 2 页，共 43 页
其中n 表示随后输入英语单
(2)算法如下:
（ ）
//建立有n 个单词的单向链表，重复单词只在链表中保留一个，最后输出频度最高的k 个单词
//申请头结点
//链表初始化
//建立n 个结点的链表
//a是与链表中结点数据域同等长度的字符数组
//P是工作指针，pre 是前驱指针
//单词重复出现，频度增
1
//先将P 结点从链表上摘下，再按频度域值插入到合适位置
//将P 结点插入到合适位置
//指针后移
//该单词没出现过，应插入到链表最后
//if新结点插入
//结束for 循环建表
r
(输入要输出单词的个数
//输出频度最髙的k 个单词
(”第
//结束算法
2． 给定nxm 矩阵
并设
设计一算法判定x 的值是否在A 中，要求时间复杂度
为O(m＋n) 。
【答案】算法如下:
第 3 页，共 43 页
) ；
个单词出现次\n”，++i，p ﹣＞data ，p ﹣＞freg) ；
//n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中
//flag是成功査到x 的标志
//假定x 为整型
(“矩阵A 中无
算法search 结束。
3． 给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。
【答案】算法如下:
建立有向图的十字链表存储结构
假定权值为整型
建立顶点向量
当输入i 、j 、v 之一为0时，结
束算法运行
申请结点
弧结点中权值域
算法结束
4． 假设在二叉链表的结点中增设两个域:parent 域指示其双亲结点:flag 域(取值为历的递推形式的算法。
【答案】算法如下:
在增加双亲指针
和标志域
的二叉树中，不用栈后序遍历二叉树
) 区分在遍
元素\n"，x) ；
历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍
向左
第 4 页，共 43 页
相关内容
相关标签