2016年淮北师范大学计算机科学与技术学院数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 在缺页处理过程中，操作系统执行的操作可能是（ ）。
I. 修改页表
II. 磁盘I/O
III. 分配页框
A. 仅 I 、II
B. 仅II
C. 仅III
D.I 、II 和III
【答案】D
【解析】首先我们要考虑的是，为什么会发生缺页中断? 当然，在一个采用虚拟存储管理技术的系统中，程 序是部分装入的，还有部分是处于外存上的，因此，当需要访问那部分位于外存上的代码或数据时，系统会产生 缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存，据此，缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页（若没有空闲的页面则要调用页面置换程序找到一处页 面，将该页面的内容处理掉，或回写
，分配妥当以后，缺页中断处理程序调用设备磁盘，或覆盖掉，然后将此页分配给需要访问的页）
驱动程序做磁盘1/0, 将位于外存（一般是磁盘）上的页面调入内存，调入后转身去修改 页表，将
，将物理页表中代表该页是否在内存的标志位（一般称为存在位或有效位、在位位）修改为“真”
页框号填入相应位置，若必要还需修改其它相关表项等。完成上述任务后，缺页中断处理程序返
回，继续程序的执行。 从上述过程可以看出，涉及的相关处理非常多，因此，答案就显而易见了。
2． 下列关于管道（Pipe ）通信的叙述中，正确的是（ ）
A. —个管道可实现双向数据传输
B. 管道的容量仅受磁盘容量大小限制
C. 进程对管道进行读操作和写操作都可以被阻塞
D. —个管道只能有一个读写进程或一个写进程对其操作
【答案】C
【解析】只有写进程才能对管道写入数据，读进程对管道进行读取数据，只能半双工通信，即某一时刻只能单向传输。管道为空，则读操作被堵塞，而如果有写操作对管道进行写的话那就要堵塞了。那么C 正确
3． 某网络的IP 地址空间为采用定长子网划分，子网掩码为则该网络的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）。
A.32, 8
B.32, 6
C.8, 32
D.8, 30
【答案】B
【解析】子网号为5位，在CIDR 中可以表示个子网，主机号为3位，除去全0和全1的情况可以表示6个主机地址，答案为B 。
4． 假定基准程序A 在某计算机上的运行时间为100秒，其中90秒为CPU 时间，其余为间。若CPU
速度提高
A.55秒
B.60秒
C.65秒
D.70秒
【答案】D 。
CPU 速度提高【解析】即CRJ 性能提高比为1.5, 改进之后的CPU 运行时间秒。速度不变，仍维持10秒，所以运行基准程序A 所耗费的时间为70秒。
5． 若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（ ）
速度不变，则运行基准程序A 所耗费的时间是（ ）。 时
A.
B.
C.
D.
【答案】D
【解析】根据广度优先遍历的定义，可知选项A 、B 、C 都为广度优先遍历，而选项D 是深度优先遍历而不是广度优先遍历，故答案为D 。
6． 主机甲和乙已建立了TCP 连接，甲始终以MSS=1KB大小的段发送数据，并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗
口为8KB , 则从t 时刻起，不再发生超时的情况下，经过10个RTT 后，甲的发送窗口是（ ）。
A.10KB
B.12KB
C.14KB
D.15KB
【答案】A
【解析】发送窗口是接受窗口和拥塞窗口的最小值，这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的，取最小值。
7． 设有两个串S1和S2, 求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串
B. 判断是否相等
C. 模型匹配
D. 连接
【答案】C
【解析】常用的串的基本操作有七种，INDEX （s ，t ）是其中的定位函数，这种运算就是所说的模式匹配。
8． 要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n-1
B.n
C.n+1
D.2n
【答案】B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n-1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。
9． 下列措施中，能加快虚实地址转换的是1增大快表（TLB ） 2让页表常驻内存3增大交换区（ ）。
A. 仅1
B. 仅2
C. 仅 1，2
D. 仅 2, 3
【答案】C
【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使cpu 不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响