2017年陕西师范大学计算机科学学院856数据结构与程序设计考研强化模拟题

时间：2025-07-12

2017年陕西师范大学计算机科学学院856数据结构与程序设计考研强化模拟题（一） .......... 2 2017年陕西师范大学计算机科学学院856数据结构与程序设计考研强化模拟题（二） ........ 15 2017年陕西师范大学计算机科学学院856数据结构与程序设计考研强化模拟题（三） ........ 27 2017年陕西师范大学计算机科学学院856数据结构与程序设计考研强化模拟题（四） ........ 39 2017年陕西师范大学计算机科学学院856数据结构与程序设计考研强化模拟题（五） ........ 55

2017年陕西师范大学计算机科学学院856数据结构与程序设计考研强化模拟题（一）

说明：①本资料为VIP学员内部使用，严格按照2017考研专业课大纲及历年常考题型出题。 ————————————————————————————————————————

一、选择题

1．设无向图的顶点个数为m则该图最多有（）条边。

A.n-1

B.n（n-l）/2

C.n（n+l）/2 D.0 E.n2

【答案】B

【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为n（n-l）/2。

2．假设栈初始为空，将中缀表达式

当扫描到f时，栈中的元素依次是（）

B.C.D.【答案】B

【解析】中缀表达式转后缀表达式遵循以下原则：（1）遇到操作数，直接输出；（2）栈为空时，遇到运算符，入栈；（3）遇到左括号，将其入栈；

（4）遇到右括号，执行出栈操作，并将出桟的元素输出，直到弹出栈的是左括号，左括号不输出；（5）遇到其他运算符运算符入栈；

（6）最终将栈中的元素依次出栈，输出。所以扫描到优先级比优先级比

入栈‘描到

由于

优先级比

低，所以将

弹出，

入栈；扫描到

，

高，入栈；扫描到

入栈;扫描到

将栈中优先级更高的

弹出，入栈;扫描到

时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该

转换为等价后缀表达式的过程中，

高，入栈。所以扫描到f的时候，栈中元素为

3．操作系统的

A.用户级B.用户级C.用户级D.用户级【答案】A。

子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理软件、设备无关软件、设备驱动程序、中断处理程序软件、设备无关软件、中断处理程序、设备驱动程序软件、设备驱动程序、设备无关软件、中断处理程序软件、中断处理程序、设备无关软件、设备驱动程序

的层次组织排列顺序是（）。

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

软件从

上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。

4．对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。

A. B. C. D. 【答案】C。

【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间

为

其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为

其

中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为即可得出正确答案。

5．下列有关接口的叙述中错误的是：（）

A.状态端口和控制端口可以合用同一寄存器 B.

接口中CPU可访问寄存器，称为