2012年考研计算机统考408真题(共10页).docx

《2012年考研计算机统考408真题(共10页).docx》由会员分享，可在线阅读，更多相关《2012年考研计算机统考408真题(共10页).docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上2012年考研计算机统考408真题一、 单项选择题1. 求整数n(n=0)阶乘的算法如下，其时间复杂度是1。Int fact(int n)If(n=2）个不等长升序表的合并策略，并说明理由。42. 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，loading和being的存储映像如下图所示。设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在的结点位置p）。要求：1) 给出算法的基本设计思想。2

2、) 根据设计思想，采用C或C+或Java语言描述算法，关键之处给出注释。3) 说明你所设计算法的时间复杂度。43. 假定某计算机的CPU主频为80MHz，CPI为4，平均每条指令访存1.5次，主存与Cache之间交换的块大小为16B，Cache的命中率为99%。存储器总线宽度为32位。请回答下列问题。1) 该计算机的MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMA传送的情况下，主存带宽至少到多少才能满足CPU的访存要求？2) 假定在Cache丢失的情况下访问主存时，存储0.0005%的缺页率，则CPU平均每秒产生多少次缺页异常？若页面大小为4KB，每次缺页都需要访问磁盘，访

3、问磁盘时DMA传送采用周期挪用方式，磁盘I/O接口的数据缓冲寄存器为32位，则磁盘I/O接口平均每秒发出的DMA请求次数至少是多少？3) CPU和DMA控制器同时要求使用存储器总线时，哪个优先级更高？为什么？4) 为了提高性能，主存采用4体低位交叉存储模式，工作时每1/4个存储周期启动一个体。若每个体的存储周期为50ns，则该主存能提供的最大带宽是多少？44. 某16位计算机中，带符号整数用补码表示，数据Cache和指令Cache分离。题44表给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，mem表示存储单地址，(x)表示寄存器x或存储单元x的内容。该计算机采用5段流水方式执行指令，各

4、流水段分别是取指（IF）、译码/读寄存器（D）、执行/计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB），流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写不能在同一个时钟周期内进行。请回答下列问题：1) 若int型变量x的值为-513，存放在寄存器R1中，则执行指令“SHL R1”后，R1的内容是多少？（用十六进制表示）。2) 若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少？3) 若高级语言程序中某赋值语句为x=a+b,x,b和b均为int型变量，它们的存储单元地址分别表

5、示为x,a和b。该语句对应的指令序列及其在指令流水线中的执行过程如下图所示。则这4条指令执行过程中，I3的ID段和I4的IF段被阻塞的原因各是什么？4) 若高级语言程序中某赋值语句为x=x*2+a,x和a均为unsigned int类型变量，它们的存储单元地址分别表示为x,a，则执行这条语句至少需要多少个时钟周期？要求模仿题44图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。45. 某请求分页系统的局部页面转换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描下一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次分配之前不被清

6、空。当发生缺页时，如果该页曾被使用过且不在空闲页链表中，则重新放回进程的驻留集中；否则，从空闲页框链表善取出一个页框。假设不考虑其他进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的是：、。请回答下列问题。1) 访问时，对应的页框号是什么？说明理由。2) 访问时，对应的页框号是什么？说明理由。3) 访问时，对应的页框号是什么？说明理由。4) 该策略是否适合于时间局部性好的程序？说明理由。46. 某文件系统空间的最大容量为4TB（1TB=240B），以磁盘块为基本分配单位。磁盘块大小为1KB。文件控制块（FCB）包含一个512B

7、的索引表区。请回答下列问题。1) 假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？2) 假设索引表区采用如下结构：第07字节采用格式表示文件创建时预分配的连续存储空间，其中起始块号占6B，块数占2B；剩余504字节采用直接索引结构，一个索引项占6B，则可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。47. 主机H通过快速以太网连接Internet，IP地址为192.168.0.8，服务器S的IP地址为211.68.71.8。H与S使用TCP通信时，在H上捕获的其中5个IP分组如题47-a表所示。回答下列问题。1) 题47-a表中的IP分组中，哪几个是由H发送的？哪几个完成了TCP连接建立过程？哪几个在通过快速以太网传输时进行了填充？2) 根据题47-a表中的IP分组，分析S已经收到的应用层数据字节数是什么？3) 若题47-a表中的某个IP分组在S发出时的前40字节如题47-b表所示，则该IP分组到达H时经过了多少个路由器？注：IP分组头和TCP段头结构分别如题47-a图，题47-b图所示。 与H与专心-专注-专业