【冲刺】2024年 北京师范大学081202计算机软件与理论《408计算机学科专业基础之数据结构》考研终极预测5套卷

【冲刺】2024 年北京师范大学 081202 计算机软

件与理论《408 计算机学科专业基础之数据结构》

考研终极预测 5 套卷

特别说明

本书严格按照该科目今年考研专业课真题题型、试题数量和考试难度出题，结合本专业考研大纲整理

编写，由考研学长严格审核校对。其内容涵盖了本科目考研常考试题及重点试题，针对性强，是报考本校

该科目考研专业课复习的重要资料。

版权声明

本机构依法对本书享有专有著作权，同时我们尊重知识产权，对本电子书部分内容参考和引用的市面

上已出版或发行图书及来自互联网等资料的文字、图片、表格数据等资料，均要求注明作者和来源。但由

于各种原因，如资料引用时未能联系上作者或者无法确认内容来源等，因而有部分未注明作者或来源，在

此对原作者或权利人表示感谢。若使用过程中对本书有任何异议请直接联系我们，我们会在第一时间与您

沟通处理。

因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生读

者批评指正。

考研专业课资料 学长一对一 诚招加盟

目录

【冲刺】2024 年北京师范大学 081202 计算机软件与理论《408 计算机学科专业基础之数据结构》考研

终极预测 5 套卷（一） ..........................................................................................................................4

【冲刺】2024 年北京师范大学 081202 计算机软件与理论《408 计算机学科专业基础之数据结构》考研

终极预测 5 套卷（二） ........................................................................................................................16

【冲刺】2024 年北京师范大学 081202 计算机软件与理论《408 计算机学科专业基础之数据结构》考研

终极预测 5 套卷（三） ........................................................................................................................28

【冲刺】2024 年北京师范大学 081202 计算机软件与理论《408 计算机学科专业基础之数据结构》考研

终极预测 5 套卷（四） ........................................................................................................................40

【冲刺】2024 年北京师范大学 081202 计算机软件与理论《408 计算机学科专业基础之数据结构》考研

终极预测 5 套卷（五） ........................................................................................................................55

第 3 页，共 64 页

考研专业课资料 学长一对一 诚招加盟

【冲刺】2024 年北京师范大学 081202 计算机软件与理论《408 计算机学科专业基础之数

据结构》考研终极预测 5 套卷（一）

说明：本书按照考试大纲、历年真题、指定参考书等公开信息潜心整理编写，由学长严格审核校对，仅供

考研备考使用，与目标学校及研究生院官方无关，如有侵权请联系我们立即处理。

一、单项选择题

1． 模 式 串

， 该 模 式 串 的 next 数 组 的 值 为 __________， nextval 数 组 的 值 为

__________。

A.01112211123456712

B.01112121124567112

C.01110013101100701

D.01112231123456712

E.01100111011001701

F.01102131011021701

【答案】D、F

2． 下面__________可以判断一个有向图是否有环(回路)。掌↑г心博阅电子书

A.拓扑排序

B.求最短路径

C.求关键路径

D.以上均不可

【答案】A

【解析】(1)拓扑排序有以下特点。

①AOV 网的典型应用。

②有向无环图必存在一个入度为 0 的顶点。

③若有向图内每个顶点的入度皆不为 0,则该有向图存在环。

④结果不唯一。

⑤拓扑排序基于队列的实现过程如下。

a.选中一个入度为 0 的顶点入队。

b.将入队顶点指向的各个结点的入度减 1。

c.继续统计是否有结点入度为 0,若存在这样的结点，则将其入队，如此循环往复，直至所有顶点入队。

(2)最短路径:两个顶点之间权值之和最小的路径。

(3)关键路径:

①AOE 网的典型应用。

②起点到终点最长的路径。

③结果不唯一。

④估计工程的工期以及给出缩短工期的办法。

3． 假设 8 行 10 列的二维数组

同，那么以行序为主序时元素

第 0 列，

A.

分别以行序为主序和列序为主序顺序存储时，其首地址相

的地址与以列序为主序时__________元素相同。(注：A 无第 0 行

表示第 i 行第 j 列的元素)

第 4 页，共 64 页

考研专业课资料 学长一对一 诚招加盟

B.

C.

D.ABC 都不对

【答案】B

【解析】可知以行序为主序的存储结构的地址计算公式：

以列序为主序的存储结构的地址计算公式：

对于该题， 等于 8， 等于 10,又因为以行序为主序的存储结构的首地址与以列序为主序的存储结构

的首地址相同，所以设 i 与 j 为 1。

以行序为主序的存储结构的元素

的地址为

。要求以列序为主序的存储结构元素

的地址与之相同，

即求

的解。即求：

的解。

将选项 A、B、C 依次代入验证，得 B。

4． 若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列__________。

A.存在

B.不存在

【答案】A

【解析】把 V 进行拓扑排序，直观上说，就是把 V 的所有顶点排成一个序列

是 1、2、3…n 的一种排列。)且使得任何

(其中

，

，则在序列中 排在 之前。

这个有向图的邻接矩阵 A 主对角线以下的元素均为零，则说明对于

，且 i＞j，

，即

到

不存在有向边。所以按顶点号从小到大排列顶点，而得到的序列一定能满足拓扑有序序列的要求。

5． 若 G 是一个具有 36 条边的非连通无向图(不含自回路和多重边)，则图 G 至少有__________个顶点。

A.11

B.10

C.9

D.8

【答案】B

【解析】因为 G 为非连通图，所以，G 中至少含有两个连通子图，而且该图不含有回路和多重边。题

目问的是至少有多少个顶点，因此，一个连通图可看成是只有 1 个顶点，另一个连通图可看成是一个完全

图(因为完全图在最少顶点的情况下能得到的边数最多)，这样，该问题就转化为“36 条边的完全图有多少

个顶点”，因为具有 n 个顶点的无向完全图的边的条数为

，可以算出 n=9 满足条件。再加上另一

个连通图(只有一个点)，则图 G 至少有 10 个顶点。

6． 如图所示的平衡二叉树中插入关键字 48 后得到一棵新平衡二叉树，在新平衡二叉树中，关键字 37 所

在节点的左、右子节点中保存的关键字分别是__________。

A.13,48

B.24,48

C.24,53

第 5 页，共 64 页

考研专业课资料 学长一对一 诚招加盟

D.24,90 青岛掌а心博阅电子书

图

【答案】C

【解析】在平衡二叉树中插入关键字 48 后，进行 RL 调整，如图 B.11 所示。本题答案为 C。

7． 关键路径是 AOE 网中__________。

A.从源点到终点的最短路径

B.从源点到终点的最长路径

C.从源点到终点的边数最多的路径

D.从源点到终点边数最少的路径

【答案】B

8． 下列关于最小生成树的叙述中，正确的是__________。

I.最小生成树的代价唯一

Ⅱ.所有权值最小的边一定会出现在所有的最小生成树中

Ⅲ.使用普里姆

算法从不同顶点开始得到的最小生成树一定相同

IV.使用普里姆算法和克鲁斯卡尔

算法得到的最小生成树总不相同

A.仅 I

B.仅Ⅱ

C.仅 I、Ⅲ

D.仅Ⅱ、IV

【答案】A

9． 设串长为 n，模式串长为 m，则 KMP 算法所需的附加空间为__________。

A.

B.

C.

D.

E.其它

【答案】A

【解析】KMP 算法所需的附加空间就是模式串的串长。

二、填空题

10．有 n 个顶点的有向图，至少需要__________条弧才能保证是连通的。

【答案】n 青岛掌й心博Т阅电子书

第 6 页，共 64 页

考研专业课资料 学长一对一 诚招加盟

图 3 回收空闲块得可利用空间状态图

19．设有 13 个初始归并段，其长度分别为 28、16、37、42、5、9、13、14、20、17、30、12 和 18。试画

出 4 路归并时的最佳归并树，并计算它带权路径长度 WPL。

【答案】最佳归并树如下图所示：

图

WPL=(5+9+12+13+14+16+17+18+20+28+23+37)x2+42=480

20．有一种简单的排序算法，叫做计数排序(Count Sorting)。这种排序算法对一个待排序的表(用数组表示)

进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计

数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键

码小。假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即

为 c。

①给出适用于计数排序的数据表定义。掌ч心博阅电子书

②编写实现计数排序的算法。

③对于有 n 个记录的表，关键码比较次数是多少？

④与简单选择排序相比较，这种方法是否更好？为什么？

【答案】①可以用一个数组来表示计数排序的数据表。

排好序的表，Data 为关键码的数据类型，n 为待排序表的长度。

②

第 21 页，共 64 页

，其中

为待排序表，

为

考研专业课资料 学长一对一 诚招加盟

根据以上算法描述可知，该算法的时间复杂度为

，空间复杂度为

。

24．已知一个带头结点的单链表，假如该链表只给出了头指针 L，在不改变链表的前提下，设计一个算法：

查找链表中“倒数”第 K(K 为正整数)个结点，若查找成功，输出该结点的 data 值，并返回 1,否则，返回 0。

链表结点如下所示。掌ш心博阅电子书

要求：

二、描述算法的详细实现步骤。

【答案】一、算法思想

(1)从头结点开始遍历单链表，并用指针 P 指向当前结点的前 K 个结点。

(2)遍历到链表的最后一个结点时，指针 P 所指向的结点即为待查找结点。

(1)增加两个指针变量 P 和 P1。P1 指向当前遍历的结点，P 指向 P1 所指结点的前 K 个结点。如果 P1

之前没有 K 个结点，则 P 指向表头结点。

(2)增加一个整型变量 i：表示当前遍历的结点个数。

(3)从链表头结点开始，沿指针域向后遍历，同时修改 P、i 的值。

(4)遍历完成时，P 或指向表头结点，或指向链表倒数第 K 个位置的结点。

25．写出从哈希表中删除关键字为 K 的一个记录的算法，设哈希函数为 h,解决冲突的方法为链地址法。

【答案】算法描述如下：

第 36 页，共 64 页

考研专业课资料 学长一对一 诚招加盟

27．试编一循环队列的出队操作和入队操作的算法。掌ㅎ心博阅电子书

【答案】(1)入队过程

：

(2)出队过程 DEQUE(sq):

28．从左到右及从右到左遍历一个单链表是可能的，其方法是在从左到右遍历的过程中将连接方向逆转，

如下图所示。在图中的指针 p 指向当前正在访问的结点，指针 pr 指向指针 p 所指结点的左侧的结点。此时，

指针 p 所指结点左侧的所有结点的连接方向都已逆转。

图

(1)使用 Pascal 或 C 语言编写一个算法，从任一给定位置

开始，将指针 p 右移一个结点。如果 p

移出链表，则将 p 置为 NULL，并让 pr 停留在链表最右边的结点上。

(2)使用 Pascal 或 C 语言编写一个算法，从任一给定位置

开始，将指针 p 左移一个结点。如果 p

移出链表，则将 p 置为 NULL，并让 pr 停留在链表最左边的结点上。

【答案】(1)算法描述如下：

(2)算法描述如下：

第 51 页，共 64 页

试读已结束

激活后可查看剩余未读页数！