2018年北京市培养单位资源与环境学院864程序设计[专业硕士]之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 2． 设键盘输入n 个英语单词，输入格式为词个数，试编一程序，建立一个单向链表，实现: (1)如果单词重复出现，则只在链表上保留一个。 (2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k＜＝n) 个单词。 【答案】定义结点数据类型如下: //频度域，记单词出现的次数 //maxsize是单词中可能含有的最多字母个数 (1)算法如下: 第 2 页，共 36 页 其中n 表示随后输入英语单 （ ） //建立有n(n＞0) 个单词的单向链表，若单词重复出现，则只在链表中保留一个 //申请头结点 //链表初始化 //建立n 个结点的链表 //a是与链表中结点数据域同等长度的字符数组 //p是工作指针，pre 是前驱指针 //单词重复出现，频度增 1 //指针后移 //该单词没出现过，应插入 //将新结点插入到链表最后 //结束for 循环 //结束creat 算法 (2)算法如下: （ ） //建立有n 个单词的单向链表，重复单词只在链表中保留一个，最后输出频度最高的k 个单词 //申请头结点 //链表初始化 //建立n 个结点的链表 //a是与链表中结点数据域同等长度的字符数组 //P是工作指针，pre 是前驱指针 //单词重复出现，频度增 1 //先将P 结点从链表上摘下，再按频度域值插入到合适位置 //将P 结点插入到合适位置 //指针后移 //该单词没出现过，应插入到链表最后 第 3 页，共 36 页 //if新结点插入 //结束for 循环建表 r (输入要输出单词的个数 //输出频度最髙的k 个单词 (”第 //结束算法 3． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。 【答案】算法如下: //串用一维数组s 存储，本算法求最长重复子串，返回其长度 //index记最长的串在s 串中的开始位置，max 记其长度 //length记局部重复子串长度，i 为字符数组下标 //上一个重复子串结束 //当前重复子串长 度大，则更新 max //初始化下一重复子串的起始位置和长度 (”最长重复子串的长度为 .//算法结束 4． 二路插入排序是将待排关键字序列二路插入。编写实现2-路插入排序算法。 【答案】算法如下: 二路插入排序的算法 第 4 页，共 36 页 ) ； 个单词出现次\n”，++i，p ﹣＞data ，p ﹣＞freg) ； ，在串中的位置，max ，index) ； 时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。 中关键字分二路分别按序插入到辅助向量 前半部和后半部(注.. 向量d 可视为循环表) ，其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分