2022年青海师范大学计算机学院408计算机学科专业基础综合[专业硕

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

第 1 页，共 40 页

目录

2018年青海师范大学计算机学院408计算机学科专业基础综合[专业硕士]之数据结构考研冲刺

五套模拟题（一） .................................................................................................................... 2 2018年青海师范大学计算机学院408计算机学科专业基础综合[专业硕士]之数据结构考研冲刺

五套模拟题（二） .................................................................................................................... 8 2018年青海师范大学计算机学院408计算机学科专业基础综合[专业硕士]之数据结构考研冲刺

五套模拟题（三） .................................................................................................................. 15 2018年青海师范大学计算机学院408计算机学科专业基础综合[专业硕士]之数据结构考研冲刺

五套模拟题（四） .................................................................................................................. 22 2018年青海师范大学计算机学院408计算机学科专业基础综合[专业硕士]之数据结构考研冲刺

五套模拟题（五） (33)

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

第 2 页，共 40 页 2018年青海师范大学计算机学院408计算机学科专业基础综合[专业硕士]之数据结构

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

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

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

一、算法设计题

1． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。

串被确认的最大长度

【答案】算法如下:

//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回

//在类C 中，一维数组下标从零开始

//两串相等

//算法结束

2． 试编写一算法对二叉树按前序线索化。

【答案】算法如下:

设置前驱

对以线索链表为存储结构的二叉树BT 进行前序线索化

设置左线索

设置前驱的右线索

为建立右链做准备

前驱后移

左子树前序线索化

右子树前序线索化

结束

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

第 3 页，共 40 页

3． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，

试写出判断表达式中括号

是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法)。 【答案】算法如下:

//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配

//s 是一维数组，容量足够大，是用于存放括号的栈

//top 用作栈顶指针

//'#先入栈，用于和表达式结束符号'#'匹配

//字符数组E 的工作指针

//逐字符处理字符表达式的数组

//读人其他字符，不进行处理

4． 已知一具有n

个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组

和

中(设该二叉树各结点的数据值均不相同)。请写一建立该二叉树的二叉链表结构的非递

归算法。该二叉链表的链结点结构为(lchild ,data ,rchild)，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示)。

【答案】算法如下:

由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树

和分別是中序序列和后序序列第一和最后元素的下标，初始调用时

，

为栈，容量足够大

初始化

取出栈顶数据

在中序序列中査等于

的结点

.

根结点的值

无左子树

将建立左子树的数据入栈

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

第 4 页，共 40 页

无右子树

右子树数据入

结束

:

5． —个有向图G=(V ，E)的平方图

满足下述性质

:

当且仅当存在某个顶点

，使得且

。写一个算法从给定的G 求出G 2

,G 和G 2

可分别用两个邻接表

表示。

【答案】算法如下:

二、应用题

6． 某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时,若有空座位,则到取号机上领取一个号,等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时,通过叫号选取一位顾客,并为其服务。顾客和营业员的活动过程描述如下:

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