2022年北京师范大学地理学与遥感科学学院978数据结构考研强化五

考研专业课资料、辅导、答疑一站式服务平台

第 1 页，共 58 页

目录

2019年北京师范大学地理学与遥感科学学院978数据结构考研强化五套模拟题（一） (2)

2019年北京师范大学地理学与遥感科学学院978数据结构考研强化五套模拟题（二） (13)

2019年北京师范大学地理学与遥感科学学院978数据结构考研强化五套模拟题（三） (25)

2019年北京师范大学地理学与遥感科学学院978数据结构考研强化五套模拟题（四） (38)

2019年北京师范大学地理学与遥感科学学院978数据结构考研强化五套模拟题（五） (49)

考研专业课资料、辅导、答疑一站式服务平台

第 2 页，共 58 页 2019年北京师范大学地理学与遥感科学学院978数据结构考研强化五套模拟题（一） 特别说明：

1-本资料为2019考研学员暑期强化班模拟题，检验强化阶段复习质量及复习效果使用。

2-资料仅供考研复习参考，与目标学校及研究生院官方无关，如有侵权、请联系我们立即处理。

一、填空题

1． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】P ﹣＞next!＝NULL

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

2． VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

3． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。

【答案】n －1

【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。

4． 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

5．

给定一组数据以它构造一棵哈夫曼树，则树高为_____，带权路径长度WPL 的值为_____。

【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树:

6． 已知有序表为(12，18，24，35，47，50，62，83，90，115，134)当用二分法查找90时，需次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。

【答案】2;4;3

【解析】二分法查找元素次数列表

考研专业课资料、辅导、答疑一站式服务平台

第 3 页，共 58 页

查找100是找到115就停止了。

7． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)

【答案】3个

【解析】以3，4先出栈的序列有34521、34215、34251共3个。

8． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

【答案】if(top!＝n)data[++top]＝x ；

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。

9． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0,则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。

10．

模式串

的

next 函数值序列为

_____。

【答案】01122312

11

．以下是用类

C

语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的

Lchild 域作为前链域，指向结点的直接

前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈

stack,栈顶

指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。

考研专业课资料、辅导、答疑一站式服务平台

第 4 页，共 58 页 【答案】

12．下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空

:

(_____i)；

＝

_____.

_____

【答案】a ＋l ；n%10

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

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

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

14．如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。

【答案】69

【解析】二叉树叶结点数为20,则度为2的结点数为19,所以总的结点数为20+19+30=69。

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

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

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

二、单项选择题

考研专业课资料、辅导、答疑一站式服务平台

第 5 页，共 58 页 16．下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是（ ）。

【答案】D

【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息,解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树,左链域空,无右子树,右链域指向其后继结点b ;结点b 无左子树,左链域指向其前驱结点d ;结点c 无左子树,左链域指向其前驱结点b ,无右子树,右链域指向其后继结点a 。所以正确选项为D 。

17．以太网交换机进行转发决策时使用的PDU 地址是（ ）.

A.目的物理地址

B.目的IP 地址

C.源物理地址

D.源IP 地址

【答案】A

【解析】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息(源结点的MAC 地址、目的结点的MAC 地址)，就会得到与每个端口所连接结点的MAC 地址，并在交换机的内部建立一个“

端口地址”映射表.建立映射表后，当某个端口接收到数据帧后，交换机会读取出该帧中的目的结点的MAC 地址，并通过“端口-MAC 地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP 地址的选项是不对的，因此答案为

A.

18．处理外部中断时,应该由操作系统保存的是（ ）。

A.程序计数器(PC)的内容

B.通用寄存器的内容

C.快表(TLB)的内容

D.Cache 中的内容

【答案】B

【解析】外部中断处理过程首先要保护现场,使得中断处理完后能够恢复程序的状态继续执

考研专业课资料、辅导、答疑一站式服务平台

第 6 页，共 58 页 行。保护现场有两个含义:

①由中断隐指令保存程序的断点(程序计数器);

②由中断服务程序保存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。

19．已知三叉树T 中6个叶结点的权分别是2,3,4,5,6,7,T 的带权(外部)路径长度最小是（ ）

A.27

B.46

C.54

D.56

【答案】B

【解析】利用三叉树的6个叶子结点的权构建最小带权生成树,最小的带权路径长度为

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

A.用户级

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

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

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

软件、中断处理程序、设备无关软件、设备驱动程序

【答案】A 。

【解析】对于一次设备的调用,操作系统为用户准备了系统调用的接口,当用户使用设备时,首先在用户程序中发起一次系统调用,操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理,根据调用格式和形参,再转到相应的设备驱动程序去处理;大部分设备在运行时是需要时间的,所以设备驱动程序会以中断方式驱动设备,即设置好控制寄存器参数和中断向量等参数后阻塞自己;当设备准备好或所需数据到达后设备硬件发出中断,设备驱动程序唤醒,将数据按上述调用顺序逆向回传到用户程序中,或继续驱动设备执行下一条指令。因此,软件从上到下分为四个层次:用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。

21．由3个“1”和5个“0”组成的8位二进制补码,能表示的最小整数是（ ）。

A.-126

B.-125

C.-32

D.-3

【答案】B

【解析】能表示的最小整数一定是负数,符号位占用1个“1”;负数的补码和原码的转化是:原码符号位不变,数值部分按位取反,末位加“1”。

因此最小的整数的补码是“10000011”,原码为“111111101”,即

。

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