2018年863回忆版

一、单选题（共80分）

1. 下列选项中，（）可以执行特权指令

A. 普通用户的程序B. 设备驱动程序C. 动态库函数D. 管理员用户的程序

2. 下列选项中，导致创建新进程的操作是（）

1) 管理员启动Web 服务2) 用户启动浏览器程序3) 用浏览器访问新的网页

A. 仅1和2B. 仅2和3C. 仅1和3D. 1、2、3

3. 以下关于进程死锁的表述，错误的是（）

A. 如果每个进程只能同时申请或拥有一个资源，则死锁就不会发生

B. 如果所有资源多个进程都可以无冲突共享访问，则死锁就不会发生

C. 如果所有进程的执行严格区分优先级，则死锁就不会发生

D. 如果进程资源请求之间不存在循环等待，则死锁就不会发生

4. 对于采用虚拟内存的系统，下列哪种做法无法提高虚拟内存的平均访问性能？（）

A. 增加内存总容量B. 提高磁盘读写速度C. 提高内存读写速度D. 增加磁盘的交换分区容量

5. 设备驱动程序在读写磁盘数据时一般采用下列哪种I/O方式？（）

A. DMA B. 可编程I/OC. 中断I/OD. 消息传递

6. 已知某计算机系统虚拟内存系统采用硬件支持的二级页表，页表项位64bit ，页面大小为4KB ，假设程序连续访问长度为1MB 的数组且过程中未发生中断，那么这个过程中最多会访问多少次内存中的页表？（）

A. 128B. 256C. 512D. 1024

7. 下列关于独立冗余磁盘阵列（RAID ）的说法，正确的是（）

A. 相比于单块磁盘，RAID5能减少单次读操作延迟

B. 相比于单块磁盘，RAID0能提高读写带宽

C. 相比于单块磁盘，RAID0能减少单次写操作延迟

D. RAID5能容忍多块磁盘同时失效

8. 日志文件系统（Journaling File System ）相对于传统的文件系统，其优点是（）

A. 对文件系统操作进行严格的审计和记录，提升安全性

B. 可以提高对存在大量文件的目录的查询性能

C. 可以尽量把属于同一文件的磁盘块和索引节点安排在临近的区域，提高I/O性能

D. 可以支持文件系统元数据的事务性修改，减少对磁盘的同步操作

9. 通常用户通过密码验证登陆一个计算机系统，那么操作系统下列保存验证密码信息最安全的方式是（）

A. 明文保存在只有root 可以读的文件中B. 以单向函数生成的密文的方式保存在文件中

C. 保存在一个需要身份验证的数据库系统中D. 明文保存在只有每个用户自己可读的文件中

10. 下列哪种机制不能用于分布式系统中不同节点的信息交互？（）

A. 远程过程调用B. TCP/IPC. 共享内存D. 网络文件系统

11. 下列有关冯·诺依曼计算机结构的叙述，正确的是（）

A. 指令和数据可以从形式上加以区分B. 按地址访问指令并自动按序执行程序C. 运算器用来完成算术运算D. 指令用二进制表示，数据可以用十进制表示

12. 假定某基准测试程序在时钟频率为800MHz 的机器A 上的执行时间为15s 。现在欲设计机器B 使同一程序在B 上的执行时间缩短为10s ，设计时B 的时钟频率获得大幅提高，但在B 上执行该程序所需的时钟周期变为A 的1.5倍。那么，机器B 的时钟频率至少应为（）。

A. 800MHz B. 1.2GHz C. 1.5GHz D. 1.8GHz

13. 在以下情况中，不会引起指令流水线阻塞的是（）

A. 外部中断B. 指令数据相关C. 条件转移D. 数据旁路

14. 采用周期挪用方式进行数据传送时，每传送一个数据要占用一个（）的时间。

A. 指令周期B. 机器周期C. 时钟周期D. 存取周期

15. 考虑以下C 语言代码：short arg=-8197;int i=arg;执行上述程序段后，i 的机器数表示为（）

A. 00009FFBH B. 0000DFFBH C. FFFF 9FFBH D. FFFF DFFBH

16. 某计算机字长为8位，其CPU 中有一个8位加法器。已知有符号数x=-69，y=-38，现要在该加法器中完成x-y 的运算，则该加法器的两个输入端信息和输入的低位进位信息分别是（）

A. 10111011,11011010,0B. 01000101,11011010,1C. 10111011,00100101,1D. 10111011,00100110,1

17. 假定主存按字节编址，Cache 共有64行，采用直接映射方式，主存块大小为32字节，主存块编号从0开始，则主存第2601号单元所在主存块对用的Cache 行号为（）

A.1B. 17C. 34D. 81

18. 假定一个磁盘存储器有4个盘片，全部盘面都可用于记录信息，柱面数为1024，每个磁道上有3072个扇区，每个扇区512字节，则该磁盘存储器的容量该为（）

A. 12MB B. 12GB C. 6MB D. 6GB

19. 设置中断屏蔽字可以动态地改变（）的优先级

A. 中断查询B. 中断响应C. 中断返回D. 中断处理

20. 某机器的指令字长为两个字节，其中第一个字节是操作码，第二个字节是相对位移量，则该指令可转移的地址范围是（）

A.255B. 256C. 128D. 127

21. 交换机能够识别（）地址。

A. 域名B. IP 地址C. MAC 地址D. UDP 端口号

22. 能从数据信号波形中提取同步信号的典型编码是（）

A. 归零码B. 非归零码C. 差分码D. 曼彻斯特编码

23. 一个频带宽度为3KHz 的信道，其信噪比为30dB ，采用8相位对信号进行调制，可以取得的最大数据速率是（）

A. 14.86kbps B. 29.90kbps C. 89.70kbps D. 118.90kbps

24. 如果本地域名服务器无缓存，当采用递归查询方法解析另一网络中的某主机域名时，用户主机和本地域名服务器发送的域名请求条数分别为（）

A. 1，1B. 1，多C. 多，1D. 多，多

25. 下列关于CSMA/CD的表述，正确的是（）

A. 站点在发送完帧之后再对冲突进行坚持

B. 站点在发送期间，同时对冲突进行检测

C. 发生帧和检测冲突并不是在同一个站点上进行

D. 同一个站点上发送的帧，只有当另一个站点没有收到时，才进行冲突检测

26. 以下关于IPv6地址的表述，错误的是（）

A. 一个拥有多个网络接口的节点可以具有多个IPv6地址

B. 一个单个的接口可以分配多个相同类型或者不同类型的地址

C. 一个单播地址可以同时分配给多个网络接口

D. 一个节点接口的单播地址可用来唯一地标识该接口或该节点

27. 以下关于信道传输速率的表述，正确的是（）

A. 信道的码元传输速率是有上限的

B. 频带宽度越宽的信道，其信息传输速率越大

C. 信噪比越大的信道，其信息传输速率越大

D. 在信道频带宽度和信噪比不变的情况下，可以通过调制方式提高码元极限传输速率

28. 以下关于分组交换原理的表述，正确的是（）

A. 分组交换需要把较长数据划分为较短数据包进行传输

B. 分组交换可降低数据传送延时

C. 分组交换能够以更快的速度将数据传送出去

D. 分组交换中各数据包按照相同的路径传送给目的节点

29. 以下关于IP 数据包在网络中逐跳传输过程的表述，正确的是（）

A. 传输过程中IP 报头中的校验和保持不变

B. 传输过程中IP 报头的源IP 地址和目的IP 地址保持不变

C. 传输过程中数据包的MAC 地址保持不变

D. 传输过程中数据包长度保持不变

30. TCP 是面向字节流的传输协议，关于TCP 报文段长度的表述，正确的是（）

A. TCP 报文段长度根据每次应用进程需要传输的数据块长度决定

B. TCP 报文段长度根据路径上能够传送的最大数据块长度决定

C. TCP 报文段长度根据对端的接受能力和网络状况决定

D. TCP 报文段长度确定后，在本应用进程通信过程中保持不变

31. 将两个长度为len1和len2的升序链表，合并为一个长度为len1+len2的降序列表，采用归并算法，在最坏情况下，比较操作的次数与（）最接近

A. len1+len2B. len1*len2C. min(len1,len2)D. max(len1,len2)

32. 若用一个大小为5的数组实现循环队列，且当前rear 和front 的值分别为0和3，当从队列中删除一个元素，再加入两个元素，再删除一个元素后，rear 和front 的值分别为（）

A. 2和4B. 3和0C. 2和0D. 4和1

33. 现有字符串s 为"aabaabaabaac" ，模式串t 为"aabaac" ，那么，采用KMP 算法，在第（）趟匹配时，串t 在串s 中匹配成功

A. 3B. 4C. 6D. 7

34. 设某二叉树的先序遍历序列为ABDGCEFH ，中序遍历序列为DGBAECHF ，则其后序遍历序列是（）

A. GDBEFHCA B. GDEFHBCA C. GDBEHFCA D. GBDEFCHA 35. 对下图进行拓扑排序，（）序列不是该图的拓扑序列

A. 123546B. 125346C. 231546D. 2135461

2

4

3

5

6

36. 设有n 个关键字（n=2^h-1）构成二叉排序树，假设查找每个关键字的概率相同，那么查找成功的平均搜索长度最大是（）

A. n B. (n+1)/2C. n/2D. n+1

37. 下列关于图的说法正确的是（）

A. 存储稀疏图，用邻接矩阵比邻接表更省空间

B. 用邻接表存储图，所占用的空间大小只与图中边数有关，与顶点数无关

C. 对有向图G ，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图

D. 可以用拓扑排序或者深度优先遍历判断有向图是否有回路

38. 设哈希表长M=14，哈希函数H(key)=keymod 11，表中已有4个元素，其关键字分别是4、27、61、84，如果用二次探测再散列处理冲突，关键字为49的结点的地址是（）

A. 9B. 8C. 3D. 2

39. 快速排序在最坏情况下的时间复杂度与下面（）算法最坏情况下的时间复杂度相同。

A. 堆排序B. Shell 排序C. 冒泡排序D. 基数排序

40. 一组关键字为(46,79,56,28,40,88)，利用堆排序建立大顶堆的初始堆为（）

A. 79,46,56,28,40,88B. 88,56,79,40,46,28C. 88,79,56,46,40,28D. 88,79,56,28,40,46

二、问答题（共70分）

41. 某多处理器计算机的操作系统需要记录日志信息到一个缓冲区中。假设缓冲区是一个连续的足够大的字节数组，初始位置为0，同时可能有多个线程并发向缓冲区以追加方式顺序写入日志，且每个日志是一段连续且长度不固定的记录。试设计写日志的接口函数，并编写该函数伪代码程序。要求保证缓冲区不丢失信息、不浪费空间且执行效率高。同时请给出必要的分析。（可采用C/C++/Java语言）（7分）

42. 某文件系统的磁盘块大小为1KB ，在文件的索引节点中存放直接索引指针16个，一级间接索引指针4个，二级间接索引指针1个，每个索引指针占4个字节。用户进程欲访问/home/student/course/os/homework/bitmap.dat文件字节偏移量为第1280和1280000处的各128字节的记录。假设当前除了根目录索引节点在内存外，相关目录和文件数据都不在内存中，且每个目录和索引节点只占一个磁盘块，那么完成数据访问一共需要读取多少个磁盘块？给出相应的描述过程。（8分）

43. 某机器主频为500MHz ，平均指令执行速度时100MIPS 。假定某外设的数据传输率为0.5MB/S，采用中断方式与主机进行数据传送，传送单位为32位，对应的中断服务程序包含16条指令，中断响应等其他开销相当于4条指令的执行时间，请回答下列问题，并给出必要的计算过程（10分）。

（1）若该机器采用独立编址对外设端口进行编号，则CPU 需要增加什么支持来访问I/O端口？

（2）在中断方式下，CPU 用于该外设I/O的时间与整个CPU 的时间的百分比是多少？

（3）当该外设的数据传输率达到5MB/S时，改用DMA 方式来传送数据。假定每次DMA 传送的块大小为5000B ，DMA 预处理和后处理的总开销为400个时钟周期，则CPU 用于该外设的I/O的时间占整个CPU 时间的百分比又变为多少？（假设DMA 与CPU 之间没有访存冲突）

44. 以下是计算两个向量点积的C 语言程序段，假定数据Cache 采用2-路组相联映射方式，数据区容量为64字节，每个主存块大小为16字节；编译器将变量sum 和i 分配再寄存器中，数组a 存放在00000040H 开始的48字节的连续存储区中，数组b 则紧跟在a 后进行存放。请回答下列问题。（10分）

float dotmultiply(floata[12],float b[12]){

float sum=0.0;

int i;

for(i=0;i<12;i++)

sum+=a[i]*b[i];

return sum;

}

（1）说明访问数组a 和b 的局部性？

（2）该程序数据访问的命中率是多少？

（3）若CPU 通过存储总线读取数据的过程为：发送地址和读命令需要1个时钟周期，存储器准备1个数据需要6个时钟周期，总线上每传送1个数据需要1个时钟周期，存取宽度和总线宽度都为4字节，则Cache 一次缺失损失至少为多少个时钟周期？

45. 主机A 向主机B 连续发送了两个TCP 报文段，其序号分别为60和110。请回答下列问题。（7分）

（1）第一个报文段携带了多少个字节的数据？

（2）如果主机B 收到第二个报文段后发回的确认中的确认号是180，，请问A 发送的第二个报文段中的数据有多少字节？

（3）如果主机A 发送的第一个报文段丢失了，但第二个报文段到达了主机B 。主机B 在第二个报文段到达后向主机A 发送确认，在采用累计确认方式时，请问这个确认号应为多少？

（4）针对上述第3个问题描述的情况，主机B 可以采取选择确认的方式，减少重复数据的发送，请描述选择确认机制的基本原理。

46. RIP 和OSPF 是两类典型的域内路由协议，他们都是基于自治域内各路由节点之间相互交换信息，通过相应的路由算法计算生成路由表。现假设一个自治域内（域内不再划分为area 等更小区域）使用RIP 协议或者OSPF 协议。请回答下列问题：（8分）

（1）各路由节点之间相互交换什么信息？请以一个路由器为例，针对RIP 和OSPF 分别进行回答。

（2）对于一条需要被交换的信息来说，该信息被交换的范围（即该信息会被传送给哪些节点）是什么？请针对RIP 和OSPF 分别进行回答。

47. 给定一个以二叉链表表示的二叉树，查找值为x 的结点，并输出该结点的所有祖先。假设值为x 的结点不多于一个。要求给出算法设计思想，并采用C/C++/Java语言描述算法。（10分）

48. n 个顶点的无向图，其邻接矩阵为A ，请计算矩阵A 的m 次方即A^m，其中2<=m<=n。要求采用C/C++/Java语言描述所采用的数据结构并给出算法。请说明A^m的非零元素aij 所表示的含义。（10分）