2018年第二军医大学训练部408计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。
【答案】算法如下:
//A是的矩阵，本算法求矩阵A 中的马鞍点
//max数组存放各列最大值元素的行号，初始化为行号
//min数组存放各行最小值元素的列号，初始化为列号
0 //选各行最小值元素和各列最大值元素
//修改第j 列最大元素的
行号
" 修改第i 行最小元素的
列号
//第i 行最小元素的列号
是马鞍点，
元素值是
是马鞍点
2． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 // 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 3． 结点类型和存储结构如下: 试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。 【答案】算法如下: 对存储在数组R 中的记录进行排序 初始化 设R[0]作监视哨，Max 是该类型最大元 素 初始假定第一个元素有序 前驱 第一个元素 査找第i 个元素的序号 将笫i 个元素链入静态链表 4． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。 【答案】算法如下: //串用一维数组s 存储，本算法求最长重复子串，返回其长度 //index记最长的串在s 串中的开始位置，max 记其长度 //length记局部重复子串长度，i 为字符数组下标 //上一个重复子串结束 //当前重复子串长 度大，则更新 max //初始化下一重复子串的起始位置和长度 (”最长重复子串的长度为 .//算法结束 ，在串中的位置 ，max ，index) ； 时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。 5． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33) 【答案】算法如下: 待排序记录的个数 关键字由d 个分量组成 静态链域 记录的其他数据域 存放n 个记录 . 用队列表示桶，共m 个 进行基数排序，返回收集用的链头指针 将 进行d 趟排序 初始化桶 按关键字的第j 个分量进行分配 k 为桶的序号 将将 链到桶头 链到桶尾 链成一个静态链表 将初始链表的终端结点指针置空，P 指向链表的第一个结点 队列的头、尾指针 对 修改桶的尾指针 扫描下一个记录