2022年上海海洋大学上海农科院408计算机学科专业基础综合[专业学

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

第 1 页，共 35 页

目录

2018年上海海洋大学上海农科院408计算机学科专业基础综合[专业学位]之数据结构考研仿真

模拟五套题（一） .................................................................................................................... 2 2018年上海海洋大学上海农科院408计算机学科专业基础综合[专业学位]之数据结构考研仿真

模拟五套题（二） .................................................................................................................... 8 2018年上海海洋大学上海农科院408计算机学科专业基础综合[专业学位]之数据结构考研仿真

模拟五套题（三） .................................................................................................................. 14 2018年上海海洋大学上海农科院408计算机学科专业基础综合[专业学位]之数据结构考研仿真

模拟五套题（四） .................................................................................................................. 20 2018年上海海洋大学上海农科院408计算机学科专业基础综合[专业学位]之数据结构考研仿真

模拟五套题（五） (27)

专注考研专业课13年，提供海量考研优质文档！ 第 2 页，共 35 页 2018年上海海洋大学上海农科院408计算机学科专业基础综合[专业学位]之数据结构

考研仿真模拟五套题（一）

说明：仿真模拟试题是根据本校该考试科目历年考研真题题型及出题难度，结合常考侧重点，精心整理编写，均含有详细答案解析，是考研必备参考资料。

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

一、算法设计题

1． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数)。

【答案】算法如下:

求以双亲表示法作为存储结构的树的深度

深度加1,并取新的双亲

最大深度更新

返回树的深度

’结束Depth

2． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N

的二叉树的存储结构。和分别指示结点i 的左儿子和右儿子，

)表示i 的左(右)儿子为空。试写一个算法，由L 和R 建立一个一维数组

，使存放结点i 的父亲；然后再写一个判别结点u 是否为结点V 的后代的算法。

【答案】算法如下:

和是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组

本算法据此建立结点i 的双亲数组T ,并判断结点U 是否是结点V 的后代

T 数组初始化

若结点i 的左子女是则结点L 的

双亲是结点

i

若结点i 的右子女是R ,则R 的

双亲是

i

判断U 是否是V 的后代

专注考研专业课13年，提供海量考研优质文档！ 第 3 页，共 35 页 3． 设有两个栈S 1，S 2都采用顺序栈方式，并且共享一个存储区

为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S 1，S 2有关入栈和出找

的操作算法。

【答案】找的定乂:

两栈共享顺序存储空间所能达到的最多元素数

//假设元素类型为整型

； //栈空间

//top 为两个栈顶指针

//S 是如上定义的结构类型变量，为全局变量

(1)入栈操作:

//入栈操作。i 为栈号，i ＝〇表示左栈Sl ，i ＝l 表示右栈s2，x 是入栈元素。入栈成功返回1，否则返回

(2)出栈操作

//出栈算法。i 代表栈号，i ＝0时为s1栈，i ＝l 时为s2栈。出栈成功返回出栈元素，否则返﹣

1

//算法结束

4． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。

【答案】算法如下:

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

第 4 页，共 35 页 //串用一维数组s 存储，本算法求最长重复子串，返回其长度

//index 记最长的串在s 串中的开始位置，max

记其长度

//length 记局部重复子串长度，i 为字符数组下标

//上一个重复子串结束

//当前重复子串长

度大，则更新

max

//初始化下一重复子串的起始位置和长度

(”最长重复子串的长度为

，在串中的位置，max ，index)；

.//算法结束 时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。

5． 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C ,其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点(链表A 的元素类型为整型，要求B 、C 表利用A 表的结点)。

【答案】算法如下:

//本算法将带头结点的单链表A 分解成数据域值小于零和大于零的两个单链表B 和

C

//为C 申请结点空间

//C 初始化为空表

//P 为工作指针

//B 表初始化

//暂存P 的后继

//小于0的放入B 表

//将小于0的结点链人B 表

//P 指向新的待处理结点

//算法结束

二、应用题

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