2018年贵州师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
目录
2018年贵州师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题（一） ... 2 2018年贵州师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题（二） . 12 2018年贵州师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题（三） . 20 2018年贵州师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题（四） . 26 2018年贵州师范大学408计算机学科专业基础综合之数据结构考研强化五套模拟题（五） . 32
一、算法设计题
1． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)
【答案】算法如下:
待排序记录的个数
关键字由d 个分量组成
静态链域
记录的其他数据域
存放n 个记录
.
用队列表示桶，共m 个
进行基数排序，返回收集用的链头指针
将
进行d 趟排序
初始化桶
按关键字的第j 个分量进行分配
k 为桶的序号
将将
链到桶头
链到桶尾
链成一个静态链表
将初始链表的终端结点指针置空，P 指向链表的第一个结点
队列的头、尾指针
对
修改桶的尾指针
扫描下一个记录
找第一个非空的桶
为收集链表的头指针，t 为尾指针
连接非空桶
本趟收集完毕，将链表的终端结点指针置空
2． 设稀疏矩阵中有t 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M 的转置矩阵N ，要求转置算法的时间复杂度为0(n＋t) 。
【答案】算法如下:
//采用三元组表方式存储，按列序实现矩阵的转置
//行数、列数和非零元素个数
//设置N 中第一个非零元素从下标1开始存储
//按列，共
//在//转置
//三元组表上实现矩阵的快速转置的算法
//矩阵M 每一列非零元初始化为零
//求矩阵M 每一列的非
零元个数
//第1列第一个非零元在转置后的三元组中下标是
1
//求
第j 列第一个非零元在
中的序号
列
个元素中查找
//求转置矩阵N 的三元组表
//同列下一非零元
素位置
3． 设线性表存于A[l..size]的前mun 各分量中，且递增有序。请设计一个算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。
【答案】算法如下:
//A是Size 个元素空间但目前仅有num(num＜size}个元素的线性表 //本算法将元素x 插入到线性表中，并保持线性表的有序性
//题目要求下标从1开始
//对分査找元素x 的插入位置
//元素后移
//将元素x 插人
算法结束
设计思想:算法中当查找失败(即线性表中无元素X) 时，变量low 在变量high 的右面(low＝high ＋l) 。移动元素从位置low 开始，直到num 为止。
时间复杂度:查找的复杂度为O (logn)，插入的时间复杂度为O (n)，若用顺序查找，则查找的时间复杂度亦为O(n)。 4． 设键盘输入n 个英语单词，输入格式为词个数，试编一程序，建立一个单向链表，实现:
(1)如果单词重复出现，则只在链表上保留一个。
(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k＜＝n) 个单词。
【答案】定义结点数据类型如下:
//频度域，记单词出现的次数
//maxsize是单词中可能含有的最多字母个数
(1)算法如下:
其中n 表示随后输入英语单