2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研冲刺五套模拟题

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

第 1 页，共 59 页

目录

2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研冲刺五套模拟题（一）

................................................................................................................................................ 2 2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研冲刺五套模拟题（二）

.............................................................................................................................................. 13 2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研冲刺五套模拟题（三）

.............................................................................................................................................. 25 2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研冲刺五套模拟题（四）

.............................................................................................................................................. 37 2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研冲刺五套模拟题（五）

(48)

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

第 2 页，共 59 页 2018年福建师范大学软件学院842软件工程专业基础综合之数据结构考研冲刺五套

模拟题（一）

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

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

一、填空题

1． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈

【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

2． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为。

3． 设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。

【答案】A[2][3]

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i ＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。

4． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。 【答案】

【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n －1)。又因

为每条边重复出现两次，所有无向完全图的边数为

.。

5． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

6． VSAM(虚拟存储存取方法)文件的优点是:动态地_____，不需要文件进行_____，并能较快地_____进行查找。

【答案】分配和释放存储空间；重组；对插入的记录

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

第 3 页，共 59 页 7． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为_____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

8． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

9． 串是一种特殊的线性表，其特殊性表现在_____；串的两种最基本的存储方式是_____、_____；两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等

10．N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N －1)个非零元素。

11．空格串是指_____，其长度等于_____。

【答案】由空格字符(ASCII 值32)所组成的字符串；空格个数

12．实现字符串拷贝的函数strcpv 为:

(_____)

【答案】s++＝*t++或(*s++＝*t++)!＝'\0?

二、单项选择题

13．就平均性能而言，目前最好的内排序方法是（ ）排序法。

A.起泡

B.希尔插入

C.交换

D.快速

【答案】D

【解析】快速排序的平均时间复杂度是nlogn 所需要的辅助存储为

，虽然堆排序的时

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

第 4 页，共 59 页 间复杂度也是

，所需要的辅助存储为O(1)，看似堆排序比快速排序的性能好，但是需要注意仅仅表示的是一个量级，比如和的量级都为。之所以说快排最好，是在综合考虑的情况下。

14．用户在删除某文件的过程中,操作系统不可能执行是（ ）

A.删除此文件所在的目录

B.删除与此文件关联的目录项

C.删除与此文件对应的控制块

D.释放与此文件关联的内存级冲区

【答案】A

【解析】删除文件不需要删除文件所在的目录,而文件的关联目录项和文件控制块需要随着文件一同删除,同时释放文件的关联缓冲区。

15．向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。

A.h ﹣＞next ＝s ；

B.s ﹣＞next ＝h ；

C.s ﹣＞next ＝h ；h ﹣＞next ＝s ；

D.s ﹣＞next ＝h ﹣next ；h ﹣＞next ＝s ；

【答案】D

【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。

16．下列命中组合情况中,一次访存过程中不可能发生的是（ ）。

A.TLB 未命中,Cache 未命中,Page 未命中

B.TLB 未命中,Cache 命中,Page 命中

C.TLB 命中,Cache 未命中,Page 命中

D.TLB 命中,Cache 命中,Page 未命中

【答案】D

【解析】TLB(快表)和慢表(页表,Page)构成二级存储系统,若TLB 命中,则Page 必命中。因此不可能发生的是D 选项。

17．

操作系统的子系统通常由四个层次组成,每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（ ）。

A.用户级

软件、设备无关软件、设备驱动程序、中断处理程序 B.用户级

软件、设备无关软件、中断处理程序、设备驱动程序 C.用户级软件、设备驱动程序、设备无关软件、中断处理程序

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