2015中国科学院大学考研真题之计算机学科综合(专业).pdf
科目名 称: 计算 机学 科综 合(专业) 第 1 页 共 8 页 中国科学 院 大学 2015 年招 收攻读 硕士学 位研究 生入学 统一考 试试题 科目名称 :计算 机学科 综合(专业) 考 生须 知: 1本试卷满分为150 分,全部考试时间总计180 分钟。 2所有答案必须写在答题纸上,写在试题纸上或草稿纸上一律无效。 一、 单项选择题: 第140小题, 每小题2分, 共80分。 下列每题给出的四个选项 中,只有一个选项最符合试题要求。 1 下列数据结构中,( )是非线性数据结构。 A栈 B.队列 C.二叉树 D.堆 2在非空双向循环链表中q所指的结点后插入一个由p所指的链结点的过程依次 为:rlink(p)0)个分支结点的满二叉树的深度是( )。 科目名 称: 计算 机学 科综 合(专业) 第 2 页 共 8 页 An 2-1 B. log2(n+1)+1 C. log2(n+1) D. log2(n-1) 8. 无向图G=(V, E), 其中V=a, b, c, d, e, f, E=(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d), 对该图进行深度优先遍历,得到的顶点序 列正确的是( )。 Aa, b, e, c, d, f B. a, c, f, e, b, d C. a, e, b, c, f, d D. a, e, d, f, c, b 9. 设哈希表长M=14, 哈希函数H(KEY) = KEY mod 7。 表中已有4个结点:ADDR(15) = 1, ADDR(38) = 3, ADDR(61) = 5; ADDR(84) = 0, 其余地址为空。如用二次 探测再哈希法解决冲突,关键字为68的结点的地址是( )。 A. 8 B. 3 C. 5 D. 6 10. 对05,46,13,55 ,94,17,42进行基 数排序, 一趟排序的结果是 ( ): A 05,46,13,55,94,17,42 B. 05,13,17,42,46,55,94 C 42,13,94,05,55,46,17 D. 05,13,46,55,17,42,94 11. 下列序列中,( )是执行第一趟快速排序后所得的序列。 A68,11,18,6923,93,73 B. 68,11,69,2318,93,73 C93,7368,11,69,23,18 D. 73,11,69,23,1893,68 12生产者和消费者问题用于解决( ) 。 A. 多个并发进程共享一个数据对象的问题 B. 多个进程之间的同步和互斥问题 C. 多个进程共享资源的死锁与饥饿问题 D. 利用信号量实现多个进程并发的问题 13.下面的叙述中,正确的是( )。 A. 在一个进程中创建一个新线程比创建一个新进程所需的工作量多 B. 同一个进程中的线程间通信和不同进程中的线程间通信差不多 C. 同一进程中的线程间切换由于许多上下文相同而简化 D. 同一进程中的线程间通信需要调用内核 14磁盘高速缓存设在( )中。 科目名 称: 计算 机学 科综 合(专业) 第 3 页 共 8 页 A. 内存 B. 磁盘控制器 C. Cache D. 磁盘 15位示图可用于( ) 。 A. 实现文件的保护和保密 B. 文件目录的查找 C. 磁盘空间的管理 D. 主存空间的共享 16虚拟设备是通过( )技术实现的。 A. 并行 B. 通道 C. SPOOLING D. 虚拟存储 17 ( )不是操作系统的功能。 A. CPU 管理 B. 存储管理 C. 网络管理 D. 数据管理 18.下面叙述中,错误的是( ) 。 A. 操作系统既能进行多任务处理,又能进行多重处理 B. 多重处理是多任务处理的子集 C. 多任务是指同一时间内在同一系统中同时运行多个进程 D. 一个CPU 的计算机上也可以进行多重处理 19. ( ) 优先级 是在 创建进程 时确定 的,确 定之后在 整个进 程运行 期间不再改 变。 A. 动态 B. 先来先服务 C. 短作业 D. 静态 20.在分时操作系统中,进程调度经常采用( )算法。 A. 时间片轮转 B. 最高优先级 C. 先来先服务 D. 随机 21.死锁产生的四个必要条件是:互斥、 ( ) 、环路等待和不剥夺。 A. 释放和阻塞 B. 请求和阻塞 C. 请求和保持 D. 请求和释放 22.公用电话交换网(PSTN)采用了( )交换方式。 A.分组 B.报文 C.信元 D.电路 23.在连续ARQ 协议中, 当滑动窗口序号位数为n, 则发送窗口最大尺寸为( )。科目名 称: 计算 机学 科综 合(专业) 第 4 页 共 8 页 A.2 n-1B.2 n -1 C.2n D.2 n24.以下哪个是快速以太网的介质访问控制方法( ) A.CSMA/CD B.令牌总线 C.令牌环 D.100VG-AnyLan 25.ARP 协议的功能是( ) A.域名地址到IP 地址的解析 B.IP 地址到域名地址的解析 C.IP 地址到物理地址的解析 D.物理地址到IP 地址的解析 26.IPv6 地址由( )位二进制数值组成。 A.16 B.64 C.32 D.128 27. 决定局域网特性有三个 主要技术,它们是 ( ) 。 A. 传输介质、差错检测方法和网络操作系统 B. 通信方式、同步方式和拓朴结构 C. 传输介质、拓扑结构和介质访问控制方法 D. 数据编码技术、介质访问控制方法和数据交换技术 28.无法隔离冲突域的网络互联设备是( )。 A.路由器 B.交换机 C.集线器 D.网桥 29.不是 IP 数据报操作特点 的 描述说法是( ) A. 每个分组自身携带有足够的信息,它的传送是被单独处理的 B在整个传送过程中,不需建立虚电路 C使所有分组按顺序到达目的端系统 D网 络节点要为每个分组做出路由选择 30. 关于路由器说法正确的是 ( )。 A.路由器处理的信息量比交换机少,因而转发速度比交换机快 B.对于同一目标,路由器只提供延迟最小的最佳路由 C.通常的路由器可以支持多种网络层协议,并提供不同协议之间的分组转换 D.路由器不但能够根据逻辑地址进行转发,而且可以根据物理地址进行转发 31两个二进制有符号数相加,00111111 + 11101111 的十进制结果是( ) 。 A. 302 B. 47 C. 45 D. 46 32根据存储内容来进行存取的存储器称为( ) 。 科目名 称: 计算 机学 科综 合(专业) 第 5 页 共 8 页 A. 双端口存储器 B. 相联存储器 C. 交叉存储器 D. 串行存储器 33在一个容量为128KB 的SRAM 存储器芯片上, 按字长32 位编址, 其 地址范围 可从0000H 到( ) 。 A. 3fffH B. 7fffH C. 7ffffH D. 3ffffH 34连续两次启动同一存储器所需的最小时间间隔称为( ) 。 A. 存储周期 B. 存取时间 C. 存储时间 D. 访问周期 35依赖硬件的数据传送方式是( ) 。 A程序控制 B程序中断 CDMA D无 36在程序执行过程中, ( ) 控制计算机的运行总是处于取指令、 分析指令和执 行指令的循环之中。 A控制器 BCPU C指令存储器 D指令译码器 37需要周期刷新的存储器是( ) 。 ASRAM BDRAM CROM D双稳态存储器 38CPU 的主频是10MHz,机器周期含3 个时钟周期,则机器周期是( )ns。 A100 B300 C33.3 D30 39命中率高且电路实现简单的Cache 与内存映射方式是( )映射方式。 A全相联 B直接 C组相联 D哈希 40只能检测错误而不能纠正错误的编码方法是( ) 。 A卷积码 B循环冗余码 C海明码 D奇偶校验 二、综合应用题:4148 小题,共70 分。 41(8分)设计并编程实现链式存储结构上交换二叉树中所有结点左右子树的 算法。(注:用C/C+,Pascal等编程语言书写) 科目名 称: 计算 机学 科综 合(专业) 第 6 页 共 8 页 42.(12分)假设有下面的有向图: 1) 请给出从顶点 a 出发得到深度优先遍历的顶点序列。 (遍历过程中存在多种 选择时,请以字母表顺序访问) 2) 请给出从顶点 a 出发得到广度优先遍历的顶点序列。 (遍历过程中存在多种 选择时,请以字母表顺序访问) 3) 该图的强连通子图有多少种? 43. (7 分) 假设一个 磁盘驱动器有5000 个柱面, 从0 到4999。 驱动器正在为 柱面153 的一个请求提供服务。 按 FIFO 顺序, 即将到来的请求队列是86,1470, 913 ,1774 ,948 ,1509 ,1022 ,1750 ,130 。从现在磁头位置开始,按照 FCFS 调度算法, 要满足队列中即将到来的请求, 磁头总的移动距离 (按柱面数计) 是 多少? 44. (8 分) 现要对P1P5 五个进程进行调度, 下 表给出了这五个进程的到达时间、 执行时间和优先级,其中,优先级数值越小表示优先级越高。 进程 到达时间 (ms) 执行时间 (ms) 优先级 P1 0 10 5 P2 1 1 1 P3 2 5 3 P4 3 1 2 P5 4 2 4 科目名 称: 计算 机学 科综 合(专业) 第 7 页 共 8 页 请根据该表分别采用先来先服务(FCFS )调度算法、非抢占式短进程优先 (nonpreemptive SPF )调度算法、抢占式优先 权(preemptive priority )调 度算法和时间片为 2ms 的时间片轮转(RR)调度算法对这五个进程进行调度, 画出 CPU 执行进程的时间图。 45. (7 分) 要发送的数据为1101011011。采用 CRC 的生成多项式是P(x)=x4+x+1。 试求应添加在数据后面的余数。 数据在传输过程中最后一个1 变成了0, 问接收 端能否发现?若数据在传输过程中最后两个1 都变成了0, 问接收端能否发现? 46. (8 分) 假定网络中的路由器A 的路由表有如下的项目 (这三列分别表示 “目 的网络” 、 “距离”和“下一跳路由器” ) N1 4 B N2 2 C N3 1 F N4 5 G 现在A 收到从C 发来的路由信息(这两列分别表示“目的网络”和“距离” ) : N1 2 N2 1 N3 3 试求出路由器A 更新后的路由表(详细说明每一个步骤) 。 47.(8分)某磁盘存储器转速为100转/秒,共有2个记录盘面,每毫米10道,每 道记录信息16384B,最小磁道直径为150mm,共有512道,求: 1)磁盘存储器的存储容量; 2)磁盘数据传输率; 3)平均等待时间。 48.(12 分)一个直接映射的Cache 有128 个字块,主机内存包含16K 个字块,科目名 称: 计算 机学 科综 合(专业) 第 8 页 共 8 页 每个块有16 个字,访问Cache 的时间是10ns,填充一个Cache 字块的时间是 200ns,Cache 的初始状态为空。 1)如果按字寻址,请定义主存地址字段格式,给出各字段的位宽; 2)CPU从主存中依次读取位置16-210的字, 循环读取10次, 则访问Cache的命 中率是多少? 3)10次循环中,CPU平均每次循环读取的时间是多少?