2012年计算机408统考考研真题及答案解析.pdf

返回 相似
第1页 / 共18页
第2页 / 共18页
第3页 / 共18页
第4页 / 共18页
第5页 / 共18页
点击查看更多>>
资源描述:
2012 年全国硕士研究生入学统一考试 计算机科学与技术学科联考 计算机学科专业基础综合试题 一、单项选择题第 1~ 40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个 选项最符合试题要求。 1. 求整数 nn≥0阶乘的算法如下,其时间复杂度是 。 int factint n{ if nRd 算术 /逻辑左移 SHL Rd 2*Rd-Rd 算术右移 SHR Rd Rd/2-Rd 取数指令 LOAD Rd, mem mem-Rd 存数指令 STORE Rs, mem Rs-mem 该计算机采用 5 段流水方式执行指令,各流水段分别是取指( IF)、译码 /读寄存器( ID)、执行 /计 算有效地址( EX)、访问存储器( M)和结果写回寄存器( WB),流水线采用 “按序发射,按序完成 ”方 式,没有采用转发技术处理数据相关,并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。 请回答下列问题 1)若 int 型变量 x 的值为 -513,存放在寄存器 R1 中,则执行指令 “SHL R1”后, R1 的内容是多少 (用十六进制表示) 2)若某个时间段中,有连续的 4 条指令进入流水线,在其执行过程中没有发生任何阻 塞,则执行 这 4 条指令所需的时钟周期数为多少 3)若高级语言程序中某赋值语句为 xab, x、 a 和 b 均为 int 型变量,它们的存储单元地址分别表 示为[x] 、 [a]和 [b]。该语句对应的指令序列及其在指令流水线中的执行过程如下图所示。 I1 LOAD R1, [a] I2 LOAD R2, [b] I3 ADD R1, R2 I4 STORE R2, [x] 图 指令序列及其执行过程示意图 则这 4 条指令执行过程中, I3 的 ID 段和 I4 的 IF 段被阻塞的原因各是什么 4) 若高级语言程序中某赋值语句为 xx*2a, x 和 a 均为 unsigned int 类型变量,它们的存储单元 7 地址分别表示为 [x]、 [a],则执行这条语句至少需要多少个时钟周期要求模仿题 44 图画出这条语句对 应的指令序列及其在流水线中的执行过程示意图。 45. 某请求分页系统的局部页面置换策略如下 系统从 0 时刻开始扫描,每隔 5 个时间单位扫描一轮驻留集(扫描时间忽略不计),本轮没有被访 问过的页框将被系统回收,并放入到空闲页框链尾,其中内容在下一次分配之前不被清空。当发生缺页 时,如果该页曾被使用过且还在空闲 页链表中,则重新放回进程的驻留集中;否则,从空闲页框链表头 部取出一个页框。 假设不考虑 其它进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框 链表中页框 号 依次为 32、 15、 21、 41。进程 P 依次访问的是 、 、 、 、 、 、 。请回答下列问题。 1) 访问 时,对应的页框号是什么 2) 访问 时,对应的页框号是什么说明理由。 3) 访问 时,对应的页框号是什么说明理由。 4) 该策略 是否 适合于时间局部性好的程序说明理由。 46. 某文件系统空间的最大容量为 4TB( 1TB240),以磁盘块为基本分配单位。磁盘块大小为 1KB。 文件控制块( FCB)包含一个 512B 的索引表区。请回答下列问题。 1)假设索引表区仅采用直接索引结构,索引表区存放文件占用的磁盘块号 , 索引 表 项中块号最少占 多少字节可支持的单个文件最大长度是多少字节 2)假设索引表区采用如下结构第 07 字节采用 格式表示文件创建时预分配的 连续存储空间 , 其中起始块号占 6B,块数占 2B; 剩余 504 字节采用直接索引结 构,一个索引项占 6B, 则可支持的单个文件最大长度是多少字节为了使单个文件的长度达到最大,请指出起始块号和块数分 别所占字节数的合理值并说明理由。 47. 主机 H 通过快速以太网连接 Internet, IP 地址为 192.168.0.8,服务器 S 的 IP 地址为 211.68.71.80。 H 与 S 使用 TCP 通信时,在 H 上捕获的其中 5 个 IP 分组如 题 47-a 表所示。 题 47-a 表 编号 IP 分组的前 40 字节内容(十六进制) 1 45 00 00 30 01 9b 40 00 80 06 1d e8 c0 a8 00 08 d3 44 47 50 0b d9 13 88 84 6b 41 c5 00 00 00 00 70 02 43 80 5d b0 00 00 2 43 00 00 30 00 00 40 00 31 06 6e 83 d3 44 47 50 c0 a8 00 08 13 88 0b d9 e0 59 9f ef 84 6b 41 c6 70 12 16 d0 37 e1 00 00 3 45 00 00 28 01 9c 40 00 80 06 1d ef c0 a8 00 08 d3 44 47 50 0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 f0 43 80 2b 32 00 00 4 45 00 00 38 01 9d 40 00 80 06 1d de c0 a8 00 08 d3 44 47 50 0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 18 43 80 e6 55 00 00 5 45 00 00 28 68 11 40 00 31 06 06 7a d3 44 47 50 c0 a8 00 08 13 88 0b d9 e0 59 9f f0 84 6b 41 d6 50 10 16 d0 57 d2 00 00 回答下列问题。 1)题 47-a 表中的 IP 分组中,哪几个是由 H 发送的哪几个完成了 TCP 连接建立过程哪几个在 通过快速以太网传输时进行了填充 2)根据题 47-a 表中的 IP 分组,分析 S 已经收到的应用层数据字节数是多少 3)若题 47-a 表中的某个 IP 分组在 S 发出时的前 40 字节如题 47-b 表所示,则该 IP 分组到达 H 时 经过了多少个路由器 题 47-b 表 8 来自 S 的分组 45 00 00 28 68 11 40 00 40 06 ec ad d3 44 47 50 ca 76 01 06 13 88 a1 08 e0 59 9f f0 84 6b 41 d6 50 10 16 d0 b7 d6 00 00 注 IP 分组头和 TCP 段头结构分别如题 47-a 图,题 47-b 图所示。 题 47-a 图 IP 分组头结构 题 47-b 图 TCP 段头结构 2012 年计算机学科专业基础综合试题参考答案 一、单项选择题 ( 一 ) 单选题答案 1. B 2. A 3. A 4. B 5. C 6. C 7. C 8. A 9. D 10. A 11. D 12. D 13. B 14. D 15. D 16. A 17. C 18. C 19. C 20. D 21. D 22. B 23. C 24. B 25. B 26. A 27. D 28. A 29. B 30. C 31. A 32. B 33. B 34. C 35. A 36. B 37. C 38. A 39. D 40. D ( 二 ) 单选题答案解析 1. 考查时间复杂度的计算。 该程序中使用了递归运算。本题中递归的边界条件是 nn,则使 p 指向链表 中的第 m-n1 个结点;若 mlen2;len1-- //使 p 指向的链表与 q 指向的链表等长 pp-next; forqstr2;len1next; whilep-nextNULL //两个指针同步向后移动 qq-next; } return p-next; //返回共同后缀的起始点 } 【 1) 2)的评分说明】 ①若考生所给算法实现正确,且时间复杂度为 Omn,可给 12 分;若算法 正确,但时间复杂度超过 Omn,则最高可给 9 分。 ②若在算法的基本设计思想描述中因文 字表达没有非常清晰反映出算法思路,但在算法实现中能够 清晰看出算法思想且正确的,可参照①的标准给分。 ③若算法的基本设计思想描述或算法实现中部分正确,可参照①中各种情况的相应给分标准酌情给 分。 ④参考答案中只给出了使用 C 语言的版本,使用 C/JAVA 语言的答案视同时用 C 语言。 3)时间复杂度为 Olen1len2或 Omaxlen1,len2,其中 len1、 len2 分别为两个链表的长度。 【 3)的评分说明】 若考生所估计的时间复杂度与考生所实现的算法一致,可给 1 分。 43. 解答 1)平均 每秒 CPU 执行的指令数为 80M/420M,故 MIPS 数为 20;(1 分) 平均每条指令访存 1.5 次,故 平均每秒 Cache 缺失的次数 20M1.51-99300k; ( 1 分) 17 当 Cache 缺失时, CPU 访问主存,主存与 Cache 之间以块为传送单位,此时,主存带宽为 16B300k/s 4.8MB/s。在不考虑 DMA 传输的情况下,主存带宽至少达到 4.8MB/s 才能满足 CPU 的访存要求。( 2 分) 2)题中 假定在 Cache 缺失的情况下访问主存 ,平均 每秒产生缺页中断 3000000.00051.5 次 。 因 为存储器总线宽度为 32 位,所以每传送 32 位数据,磁盘控制器发出一次 DMA 请求,故 平均每秒 磁盘 DMA 请求 的 次数至少 为 1.54KB/4B1.5K1536。 ( 2 分) 3) CPU 和 DMA 控制器同时要求使用存储器总线时, DMA 请求优先级更高;( 1 分) 因为 DMA 请求得不到及时响应, I/O 传输数据可能会丢失 。 ( 1 分) 4) 4 体交叉存储模式能提供的最大带宽为 44B/50ns320MB/s。 ( 2 分) 44. 解答 1) x 的机器码为 [x]补 1111 1101 1111B,即指令执行前 R1FDFFH,右移 1 位后为 1111 1110 1111 1111B,即指令执行后 R1FEFFH。( 2 分) 【评分说明】仅正确写出指令执行前的 R1可给 1 分。 2)至少需要 45-18 个时钟周期数。 ( 2 分) 3) I3 的 ID 段被阻塞的原因因为 I3 与 I1 和 I2 都存在数据相关,需等到 I1 和 I2 将结果写回寄存器 后,I 3 才能读寄存器内容,所以 I3 的 ID 段被阻塞。 ( 1 分) I4 的 IF 段被阻塞的原因因为 I4 的前一条指令 I3 在 ID 段被阻塞,所以 I4 的 IF 段被阻塞。 ( 1 分) 4)因 2*x 操作有左移和加法两种实现方法,故 xx*2a 对应的指令序列为 I1 LOAD R1, [x] I2 LOAD R2, [a] I3 SHL R1 //或者 ADD R1, R1 I4 ADD R1, R2 I5 STORE R2, [x] 【评分说明】指令正确给 2 分;其他正确答案同样给分;部分正确,酌情给分。 这 5 条指令在流水线中执行过程如下图所示。 ( 3 分) 时间单元 指令 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 I1 IF ID EX M WB I2 IF ID EX M WB I3 IF ID EX M WB I4 IF ID EX M WB I5 IF ID EX M WB 故执行 xx*2a 语句最少需要 17 个时钟周期。 ( 1 分) 45. 解答 1)页框号为 21。( 1 分)理由因为起始驻留集为空,而 0 页对应的页框为空闲链表中的第三 个空 闲页框( 21),其对应的页框号为 21。( 1 分) 2)页框号为 32。( 1 分)理由因 1110 故发生第三轮扫描,页号为 1 的页框在第二轮已处于空闲 页框链表中,此刻该页又被重新访问,因此应被重新放回驻留集中,其页框号为 32。( 1 分) 3)页框号为 41。( 1 分)理由因为第 2 页从来没有被访问过,它不在驻留集中,因此从空闲页框 链表中取出链表头的页框 41,页框号为 41。( 1 分) 4)合适。( 1 分)理由如果程序的时间局部性越好,从空闲页框链表中重新取回的机会越大,该 18 策略的优势越明显。( 1 分) 46. 解答 1)文件系统中所能容纳的磁盘块总数为 4TB/1KB232。 要完全表示所有磁盘块,索引项中的块号最 少要占 32/84B。( 2 分) 而 索引表区仅采用直接索引结构 ,故 512B 的索引表区能容纳 512B/4B27 个索引项。每个索引项对 应一个磁盘块,所以该系统 可支持的单个文件最大长度是 1281KB128KB。( 2 分) 【评分说明】过程描述正确,但计算结果不正确,可酌情给分。 2)块号占 6B、 块数占 2B 时,共可以表示 216 个磁盘块,即 22664MB;直接索引区共 504B/6B84 个索引项。所以该系统 可支持的单个文件最大长度是 226B84KB65620KB。( 2 分) 合理的起始块号和块数所占字节数分别为 4,4(或 1,7 或 2,6 或 3,5)。( 1 分)理由块数占 4B 或以 上,就可表示 4TB 大小的文件长度,达到文件系统的空间上限。( 1 分) 【评分说明】过程描述正确,但计算结果不正确,可酌情给分。只要答出起始块号和块数所占字节数 的任何合理值,均可得 1 分;理由说明正确得 1 分。 47. 解答 1)由于题 47-a 表中 1、 3、 4 号分组的源 IP 地址(第 1316 字节)均为 192.168.0.8( c0a8 0008H), 因此可以判定 1、 3、 4 号分组是由 H 发送的。( 3 分) 题 47-a 表中 1 号 分组封装的 TCP 段的 FLAG 为 02H(即 SYN1, ACK0), seq846b 41c5H, 2 号 分组封装的 TCP 段的 FLAG 为 12H(即 SYN1, ACK1), seqe059 9fefH, ack846b 41c6H, 3 号分组 封装的 TCP 段的 FLAG 为 10H(即 ACK1), seq846b 41c6H, ack e059 9ff0H,所以 1、 2、 3 号分组 完成了 TCP 连接建立过程。( 1 分) 由于快速以太网数据帧有效载荷的最小长度为 46 字节,表中 3、 5 号分组的总长度为 40( 28H)字 节,小于 46 字节, 其余分组总长度均大于 46 字节。所以 3、 5 号分组通过快速以太网传输时进行了填充。 ( 1 分) 2)由 3 号分组封装的 TCP 段可知,发送应用层数据初始序号为 seq846b 41c6H,由 5 号分组封装 的 TCP 段可知, ack 为 seq846b 41d6H,所以 5 号分组已经收到的应用层数据的字节数为 846b 41d6H - 846b 41c6H10H16。( 2 分) 【评分说明】其他正确解答,亦给 2 分;若解答结果不正确,但分析过程正确给 1 分;其他情况酌情 给分。 3)由于 S 发出的 IP 分组的标识 6811H,所以该分组所对 应的是题 47-a 表中的 5 号分组。 S 发出的 IP 分组的 TTL40H64, 5 号分组的 TTL31H49, 64-4915,所以,可以推断该 IP 分组到达 H 时经过 了 15 个路由器。( 2 分) 【评分说明】若解答结果不正确,但分析过程正确给 1 分;其他情况酌情给分。
展开阅读全文

copyright@ 2018-2019 考拉文库网站版权所有
经营许可证编号:陕ICP备18022950号-1