2022年河北师范大学数学与信息科学学院823计算机专业基础(数据结

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

第 1 页，共 35 页

目录

2018年河北师范大学数学与信息科学学院823计算机专业基础（数据结构）之数据结构考研冲

刺狂背五套题（一） ................................................................................................................ 2 2018年河北师范大学数学与信息科学学院823计算机专业基础（数据结构）之数据结构考研冲

刺狂背五套题（二） ................................................................................................................ 9 2018年河北师范大学数学与信息科学学院823计算机专业基础（数据结构）之数据结构考研冲

刺狂背五套题（三） .............................................................................................................. 16 2018年河北师范大学数学与信息科学学院823计算机专业基础（数据结构）之数据结构考研冲

刺狂背五套题（四） .............................................................................................................. 22 2018年河北师范大学数学与信息科学学院823计算机专业基础（数据结构）之数据结构考研冲

刺狂背五套题（五） (28)

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

第 2 页，共 35 页 2018年河北师范大学数学与信息科学学院823计算机专业基础（数据结构）之数据结

构考研冲刺狂背五套题（一）

说明：本套狂背五套题按照考研侧重点和出题难度，严格筛选提取了历年考试高频核心试题及重点题型，更突出针对性和实战性，适用于考研冲刺最后狂背。

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

一、算法设计题

1． 当一棵有n()个结点的二叉树按顺序存储方式存储在中时，试写一个算法，求出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。

【答案】算法如下:

二叉树顺序存储在数组

中，本算法求结点i 和j 的最近公共祖先结点的值

下标为i 的结点的双亲结点的下标

下标为j 的结点的双亲结点的下标

所査结点的最近公共祖先的下标是，值是设元素类型为整型

2． 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为

，其中，2为排序树中所含结点数，m 为输出的关键字个数。 【答案】算法如下:

从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素

3． 试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法。delete(Linklist&L)

【答案】算法如下:

//L 是带头结点的单链表，本算法删除其最小值结点

//P 为工作指针。指向恃处理的结点。假定链表非空

//pre 指向最小值结点的前驱

//q 指向最小值结点，初始假定第一元素结点是最小值结点

//查最小值结点

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

第 3 页，共 35 页

//指针后移

//从链表上刪除最小值结点

//释放最小值结点空间

//结束算法Delete

4． 以三元组表存储的稀疏矩阵A ，B 非零元个数分别为m 和n 。试用类PASCAL 语言编写时间复杂度为0(m ＋n)的算法将矩阵B 加到矩阵A 上去。A 的空间足够大，不另加辅助空间。要求描述所用结构。

【答案】算法如下:

＝大于非零元素个数的某个常量

//本算法实现以三元组表存储的各有m 和n 个非零元素两个稀疏矩阵相加，结果放到A 中

//L ，p 为A ，B 三元组表指针，k 为结果三元组表榫针(下标

)

//行号不等时，行号大者的三元组为结果三元组表中一项

//A 中当前项为结

果项

//B 中当前项为结果

当前项

//行号相等时，比较列号

//结束行号相等时的处理

//结束行号比较处理

//结果三元组表的指针前移(减

1)

//结束WHILE 循环。

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

第 4 页，共 35 页

//处理B 的剩余部

分

//处理A 的剩余部

分

//稀疏矩阵相应元素相加时，有和为零的元素，因而元素总数＜m ＋

n

//三元组前移，使第一个三元组的下标

为

1

//修改结果三元组表中非零元素个数

//结束addmatrix

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

满足下述性质

:

当且仅当存在某个顶点

，使得且

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

,G 和G 2

可分别用两个邻接表

表示。

【答案】算法如下:

二、应用题

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