中科院 863计算机学科综合 考研真题下载
2019版中科院863计算机学科综合考研真题、答案、学长笔记、视频课程
中国科学院研究生院
2018年招收攻读硕士学位研究生入学统一考试试题科目名称:计算机学科综合(专业)
一、单选题(共 80 分)
1. 下列选项中,( )可以执行特权指令
A.普通用户的程序 B. 设备驱动程序 C. 动态库函数 D. 管理员用户的程序
2. 下列选项中,导致创建新进程的操作是( )
1)管理员启动 Web 服务 2)用户启动浏览器程序 3)用浏览器访问新的网页
A.仅 1 和 2 B. 仅 2 和 3 C. 仅 1 和 3 D. 1、2、3
3. 以下关于进程死锁的表述,错误的是( )
A. 如果每个进程只能同时申请或拥有一个资源,则死锁就不会发生
B. 如果所有资源多个进程都可以无冲突共享访问,则死锁就不会发生
C. 如果所有进程的执行严格区分优先级,则死锁就不会发生
D. 如果进程资源请求之间不存在循环等待,则死锁就不会发生
4. 对于采用虚拟内存的系统,下列哪种做法无法提高虚拟内存的平均访问性能?( )
A. 增加内存总容量 B. 提高磁盘读写速度
C. 提高内存读写速度 D. 增加磁盘的交换分区容量
5. 设备驱动程序在读写磁盘数据时一般采用下列哪种 I/O 方式?( )
A. DMA B. 可编程 I/O C. 中断 I/O D. 消息传递
6. 已知某计算机系统虚拟内存系统采用硬件支持的二级页表,页表项位 64bit,页面大小为4KB,假设程序连续访问长度为 1MB 的数组且过程中未发生中断,那么这个过程中最多会访问多少次内存中的页表?( )
A. 128 B. 256 C. 512 D. 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/IP C. 共享内存 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. 0000 9FFBH B. 0000 DFFBH
C. FFFF 9FFBH D. FFFF DFFBH
16. 某计算机字长为 8 位,其 CPU 中有一个 8 位加法器。已知有符号数 x=-69,y=-38,现要在该加法器中完成 x-y 的运算,则该加法器的两个输入端信息和输入的低位进位信息分别是( )
A. 1011 1011,1101 1010,0 B. 0100 0101,1101 1010,1
C. 1011 1011,0010 0101,1 D. 10111011,0010 0110,1
17. 假定主存按字节编址,Cache 共有 64 行,采用直接映射方式,主存块大小为 32 字节, 主存块编号从 0 开始,则主存第 2601 号单元所在主存块对用的 Cache 行号为( )
A.1 B. 17 C. 34 D. 81
18. 假定一个磁盘存储器有 4 个盘片,全部盘面都可用于记录信息,柱面数为 1024,每个磁道上有 3072 个扇区,每个扇区 512 字节,则该磁盘存储器的容量该为( )
A. 12MB B. 12GB C. 6MB D. 6GB
19. 设置中断屏蔽字可以动态地改变( )的优先级
A. 中断查询 B. 中断响应 C. 中断返回 D. 中断处理
20. 某机器的指令字长为两个字节,其中第一个字节是操作码,第二个字节是相对位移量, 则该指令可转移的地址范围是( )
A.255 B. 256 C. 128 D. 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,1 B. 1,多 C. 多,1 D. 多,多
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+len2 B. len1*len2 C. min(len1,len2) D. max(len1,len2)
32. 若用一个大小为 5 的数组实现循环队列,且当前 rear 和 front 的值分别为 0 和 3,当从队列中删除一个元素,再加入两个元素,再删除一个元素后,rear 和 front 的值分别为( )
A. 2 和 4 B. 3 和 0 C. 2 和 0 D. 4 和 1
33. 现有字符串 s 为"aabaabaabaac",模式串 t 为"aabaac",那么,采用 KMP 算法,在第( ) 趟匹配时,串 t 在串 s 中匹配成功
A. 3 B. 4 C. 6 D. 7
34. 设某二叉树的先序遍历序列为 ABDGCEFH,中序遍历序列为 DGBAECHF,则其后序遍历序列是( )
A. GDBEFHCA B. GDEFHBCA C. GDBEHFCA D. GBDEFCHA
35. 对下图进行拓扑排序,( )序列不是该图的拓扑序列
A. 123546 B. 125346 C. 231546 D. 213546
36. 设有 n 个关键字(n=2^h-1)构成二叉排序树,假设查找每个关键字的概率相同,那么查找成功的平均搜索长度最大是( )
A. n B. (n+1)/2 C. n/2 D. n+1
37. 下列关于图的说法正确的是( )
A. 存储稀疏图,用邻接矩阵比邻接表更省空间
B. 用邻接表存储图,所占用的空间大小只与图中边数有关,与顶点数无关
C. 对有向图 G,如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点, 则该图一定是完全图
D. 可以用拓扑排序或者深度优先遍历判断有向图是否有回路
38. 设哈希表长 M=14,哈希函数 H(key)=key mod 11,表中已有 4 个元素,其关键字分别是4、27、61、84,如果用二次探测再散列处理冲突,关键字为 49 的结点的地址是( )
A. 9 B. 8 C. 3 D. 2
39. 快速排序在最坏情况下的时间复杂度与下面( )算法最坏情况下的时间复杂度相同。
A. 堆排序 B. Shell 排序 C. 冒泡排序 D. 基数排序
40. 一组关键字为(46,79,56,28,40,88),利用堆排序建立大顶堆的初始堆为( )
A. 79,46,56,28,40,88 B. 88,56,79,40,46,28
C. 88,79,56,46,40,28 D. 88,79,56,28,40,46
二、 问答题(共 70 分)
1. 某多处理器计算机的操作系统需要记录日志信息到一个缓冲区中。假设缓冲区是一个连续的足够大的字节数组,初始位置为 0,同时可能有多个线程并发向缓冲区以追加方式顺序写入日志,且每个日志是一段连续且长度不固定的记录。试设计写日志的接口函数,并编写 该函数伪代码程序。要求保证缓冲区不丢失信息、不浪费空间且执行效率高。同时请给出必要的分析。(可采用 C/C++/Java 语言)(7 分)
2. 某文件系统的磁盘块大小为 1KB,在文件的索引节点中存放直接索引指针 16 个,一级间接索引指针 4 个,二级间接索引指针 1 个,每个索引指针占 4 个字节。用户进程欲访问/home/student/course/os/homework/bitmap.dat 文件字节偏移量为第1280 和1280000 处的各128 字节的记录。假设当前除了根目录索引节点在内存外,相关目录和文件数据都不在内存中,且每个目录和索引节点只占一个磁盘块,那么完成数据访问一共需要读取多少个磁盘 块?给出相应的描述过程。(8 分)
3.某机器主频为 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 之间没有访存冲突)
4.以下是计算两个向量点积的 C 语言程序段,假定数据 Cache 采用 2-路组相联映射方式, 数据区容量为 64 字节,每个主存块大小为 16 字节;编译器将变量 sum 和 i 分配再寄存器中, 数组 a 存放在 0000 0040H 开始的 48 字节的连续存储区中,数组 b 则紧跟在 a 后进行存放。请回答下列问题。(10 分)
float dotmultiply(float a[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 一次缺失损失至少为多少个时钟周期?
5.主机 A 向主机 B 连续发送了两个 TCP 报文段,其序号分别为 60 和 110。请回答下列问题。(7 分)
(1) 第一个报文段携带了多少个字节的数据?
(2) 如果主机 B 收到第二个报文段后发回的确认中的确认号是 180,,请问 A 发送的第二个报文段中的数据有多少字节?
(3) 如果主机 A 发送的第一个报文段丢失了,但第二个报文段到达了主机 B。主机 B 在第二个报文段到达后向主机 A 发送确认,在采用累计确认方式时,请问这个确认号应为多少?
(4) 针对上述第 3 个问题描述的情况,主机 B 可以采取选择确认的方式,减少重复数据的发送,请描述选择确认机制的基本原理。
6. RIP 和 OSPF 是两类典型的域内路由协议,他们都是基于自治域内各路由节点之间相互交换信息,通过相应的路由算法计算生成路由表。现假设一个自治域内(域内不再划分为 area 等更小区域)使用 RIP 协议或者 OSPF 协议。请回答下列问题:(8 分)
(1) 各路由节点之间相互交换什么信息?请以一个路由器为例,针对 RIP 和 OSPF 分别进行回答。
(2) 对于一条需要被交换的信息来说,该信息被交换的范围(即该信息会被传送给哪些节点)是什么?请针对 RIP 和 OSPF 分别进行回答。
7. 定一个以二叉链表表示的二叉树,查找值为 x 的结点,并输出该结点的所有祖先。假设值为 x 的结点不多于一个。要求给出算法设计思想,并采用 C/C++/Java 语言描述算法。(10 分)
8. n 个顶点的无向图,其邻接矩阵为 A,请计算矩阵 A 的 m 次方即 A^m,其中 2<=m<=n。要求采用 C/C++/Java 语言描述所采用的数据结构并给出算法。请说明 A^m 的非零元素 aij 所表示的含义。(10 分)