2018年上海师范大学信息与机电工程学院408计算机学科专业基础综合之数据结构考研冲刺五套模拟题

专注考研专业课13年，提供海量考研优质文档！

第 1 页，共 32 页

目录

2018年上海师范大学信息与机电工程学院408计算机学科专业基础综合之数据结构考研冲刺五

套模拟题（一） ....................................................................................................................... 2 2018年上海师范大学信息与机电工程学院408计算机学科专业基础综合之数据结构考研冲刺五

套模拟题（二） ....................................................................................................................... 9 2018年上海师范大学信息与机电工程学院408计算机学科专业基础综合之数据结构考研冲刺五

套模拟题（三） ..................................................................................................................... 16 2018年上海师范大学信息与机电工程学院408计算机学科专业基础综合之数据结构考研冲刺五

套模拟题（四） ..................................................................................................................... 22 2018年上海师范大学信息与机电工程学院408计算机学科专业基础综合之数据结构考研冲刺五

套模拟题（五） (28)

专注考研专业课13年，提供海量考研优质文档！

第 2 页，共 32 页 2018年上海师范大学信息与机电工程学院408计算机学科专业基础综合之数据结构

考研冲刺五套模拟题（一）

说明：根据本校该考试科目历年考研命题规律，结合考试侧重点和难度，精心整理编写。考研冲刺模考使用。共五套冲刺预模拟预测题，均有详细答案解析，考研冲刺必备资料。

——————————————————————————————————————————

一、算法设计题

1． 给定一个整数数组

b 中连续的相等元素构成的子序列称为平台。试设计算法，求出b 中最长平台的长度。

【答案】算法如下:

//求具有N 个元素的整型数组b 中最长平台的长度。

//局部最长平台

//新平台起点

(“最长平台长度

在b 数组中起始下标为”，1，

k)

2． 给定nxm 矩阵并设

设计一算法判定x 的值是否在A 中，要求时间复杂度

为O(m ＋n)。

【答案】算法如下:

//n*m 矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中

//flag 是成功査到x 的标志

//假定x 为整型

(“矩阵A 中无

元素\n"，x)；

算法search 结束。

专注考研专业课13年，提供海量考研优质文档！

第 3 页，共 32 页 3． 设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为〇(n)。

【答案】算法如下:

//n 个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前

//用类C 语言编写，数组下标从0开始

//交换A[i]与

A[j]

//算法Arrange 结束

4． 编程:假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化(initqueue)，插入(enqueue)和删除(dequeue)元素的操作。

【答案】定义队列:

//循环队列占m 个存储单元

//rear 指向队尾元素，length 为元素个数

(1)设cq 是seQueue 类型变量，则当

时队列空，当时队列满。 (2)队列的初始化:

//cq 为循环队列，本算法进行队列初始化

//算法结束

(3)队列的插入:

//cq 是已如上定义的循环队列，本算法将元素x 入队

//队满

. //计算插入元素位置

//将元素x 入队列

//修改队列长度

//算法结束

(4)队列的删除:

专注考研专业课13年，提供海量考研优质文档！

第 4 页，共 32 页

//cq 是已如上定义的循环队列，本算法是出队算法，且返回出队元素

//队空

；//出队元素位置

//修改队列长度

//返回队头元素

//算法结束

5． 设稀疏矩阵中有t 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M 的转置矩阵N ，要求转置算法的时间复杂度为0(n ＋t)。

【答案】算法如下:

//采用三元组表方式存储，按列序实现矩阵的转置

//行数、列数和非零元素个数

//设置N 中第一个非零元素从下标1开始存储

//按列，共

列

//在

个元素中查找

//转置

//三元组表上实现矩阵的快速转置的算法

//矩阵M 每一列非零元初始化为零

//求矩阵M 每一列的非

零元个数

//第1列第一个非零元在转置后的三元组中下标是

1

//求第j 列第一个非零元在

中的序号

//求转置矩阵N 的三元组表

本文来源：https://www.bwwdw.com/article/3o1e.html