2018年浙江理工大学信息学院991数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。
两个操作完成后, 2的值（ ）。 A. 可能为-1或3 B. 只能为1 C. 可能为0、1或2 D. 可能为-1、0、1或2 【答案】C
【解析】这是在数据库中常有的操作。为保证数据的正确, 避免产生错误, 系统必须保证数据的同步。而保证数据的同步一般采取加锁的方法, 让进程P1和P2互斥访问共享变量X 。当然用信号量和P 、V 操作也是可以保证互斥操作, 达到数据同步的。
本例中, 由于没有采取保证数据同步的相应措施, 则最后结果就会出现差错。例如, 当正常情况下, 进程P1和P2先后对x 操作, 可以看到x 值的变化为初始则x 值的变化为初始
的过程, 若P2, P1先后操作,
, 这是正确的。若考虑一种并发的情况, 进程P1和P2先后执行了取数
load 的操作, 它们得到的x 值均为1, 运算后, P1和P2的x 值分别为2和0, 此时要看哪个进程后执行存数store 的操作了, 哪个进程后操作, 结果就是那个进程的x 值, 所以可能的结果为0或2, 加上前面正确的x 值1, 则可能的结果就有3种了。
2． 下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）.
A. 连续结构 B. 索引结构
C. 链式结构且磁盘块定长 D. 链式结构且磁盘块变长 【答案】B
【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问. 链式结构的优点是文件易于扩展，缺点是不易随机访问. 索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展.
3． 下列关于中断
A. 中断
方式和DMA 方式比较的叙述中, 错误的是（ ）
方式请求的是方式请求的是CPU 处理时间, DMA 方式请求的是总线使用权
B. 中断响应发生在一条指令执行结束后, 中断响应发生在一条指令执行结束后, DMA 响应发生在一个总线事务完成后
C. 中断送由硬件完成
D. 中断设备
【答案】D
【解析】中断处理方式:在与
设备输入每个数据的过程中, 由于无需CPU 干预, 因而可使CPU
设备并行工作。仅当输完一个数据时, 才需CPU 花费极短的时间去做些中断处理。因此中断
设备
方式适用于所有外部设备, 方式适用于所有外部设备, DMA 方式仅适用于快速外部方式下数据传送通过软件完成, 方式下数据传送通过软件完成, DMA 方式下数据传
申请使用的是CPU 处理时间, 发生的时间是在一条指令执行结束之后, 数据是在软件的控制下完成传送。而DMA 方式与之不同。DMA 方式:数据传输的基本单位是数据块, 即在CPU 与之间, 每次传送至少一个数据块, DMA 方式每次申请的是总线的使用权, 所传送的数据是从设备直接送入内存的或者相反; 仅在传送一个或多个数据块的开始和结束时, 才需CPU 干预, 整块数据的传送是在控制器的控制下完成的。答案D 的说法不正确。
4． 最大容量为n 的循环队列，队尾指针是rear ，队头:front ，则队空的条件是（ ）。
A.(rear+1)MODn＝front B.rear ＝front C.rear+1＝front D.(rear-1)MODn＝front 【答案】B
【解析】循环队列队空的条件是:rear ＝front 。循环队列队满的条件，
通常采用(rear+1)%MAXQSIZE＝front 来判定队满，其中MAXQSIZE 表示队列的长度。
5． 若磁盘转速为7200转/分, 平均寻道时间为8ms , 每个磁道包含1000个扇区, 则访问一个扇区的平均存取时间大约是（ ）。
A. B. C. D. 【答案】B
【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms , 平均等待时间与磁盘转速有关, 为
。
磁盘的存取一个扇区的时间为
因此总的时间为:
。
6．
操作系统的
A. 用户级B. 用户级C. 用户级D. 用户级【答案】A 。
【解析】对于一次设备的调用, 操作系统为用户准备了系统调用的接口, 当用户使用设备时, 首先在用户程序中发起一次系统调用, 操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理, 根据调用格式和形参, 再转到相应的设备驱动程序去处理; 大部分设备在运行时是需要时间的, 所以设备驱动程序会以中断方式驱动设备, 即设置好控制寄存器参数和中断向量等参数后阻塞自己; 当设备准备好或所需数据到达后设备硬件发出中断, 设备驱动程序唤醒, 将数据按上述调用顺序逆向回传到用户程序中, 或继续驱动设备执行下一条指令。因此, 为四个层次:用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。
7． 求整数阶乘的算法如下, 其时间复杂度是（ ）。
A. B.0(n) C.
2
D.O(n)
【答案】B 。
【解析】设fact(n)的运行时间函数是T(n)。
该函数中语句①的运行时间是0(1), 语句②的运行时间是算的时间。
因此, 当则,
时
,
;
。
子系统通常由四个层次组成, 每一层明确定义了与邻近层次的接口。其合理软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序 软件、中断处理程序、设备无关软件、设备驱动程序
的层次组织排列顺序是（ ）。
软件从上到下分
, 其中O(1)为乘法运
当11>1时,
相关内容
相关标签