2018年北京市培养单位生命科学学院866计算机原理之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素
在C 中的存放位置下标的公式。
//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置
//算法结束
2． 当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
【答案】算法如下:
和B 的
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
，值是
设元素类型为
整型
3． 按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点到顶点的路径
。
【答案】算法如下:
设有向图有n 个顶点
判断以邻接矩阵方式存储的有向图中是否存在由顶点到顶点的路径
是队列，容量足够大，元素是顶点编号
人队
到顶点
不存在路径
4． 设键盘输入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
//先将P 结点从链表上摘下，再按频度域值插入到合适位置
//将P 结点插入到合适位置
//指针后移
//该单词没出现过，应插入到链表最后
//if新结点插入
//结束for 循环建表
r
(输入要输出单词的个数
//输出频度最髙的k 个单词
(”第
//结束算法
) ；
个单词出现次\n”，++i，p ﹣＞data ，p ﹣＞freg) ；
相关内容
相关标签