数据结构与算法 (39).pdf

《数据结构与算法 (39).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法 (39).pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、全国硕士研究生入学统一考试 计算机科学与技术学科联考计算机学科专业基础综合试题 一、单项选择题：第 140 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1求整数 n(n0)阶乘的算法如下，其时间复杂度是。int fact(int 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）、执行/计算有效地址（E

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

3、在指令流水线中的执行过程如下图所示。I1 LOAD R1，a I2 LOAD R2，b I3 ADD R1，R2 I4 STORE R2，x 时间单元 指令 1 2 3 4 5 6 7 8 9 10 11 12 13 14 I1 IF ID EX M WB I2 IF ID EX M WB I3 IF ID EX M WB I4 IF ID EX M WB 图 指令序列及其执行过程示意图 则这 4 条指令执行过程中，I3的 ID 段和 I4的 IF 段被阻塞的原因各是什么？4）若高级语言程序中某赋值语句为 x=x*2+a，x 和 a 均为 unsigned int 类型变量，它们的存储单元地址

4、分别表示为x、a，则执行这条语句至少需要多少个时钟周期？要求模仿题 44 图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。45某请求分页系统的局部页面置换策略如下：系统从 0 时刻开始扫描，每隔 5 个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为 32、15、21、41。进程 P 依次访

5、问的是：、。请回答下列问题。1）访问时，对应的页框号是什么？说明理由。2）访问时，对应的页框号是什么？说明理由。3）访问时，对应的页框号是什么？说明理由。4）该策略是否适合于时间局部性好的程序？说明理由。46某文件系统空间的最大容量为 4TB（1TB=240 B），以磁盘块为基本分配单位。磁盘块大小为 1KB。文件控制块（FCB）包含一个 512B 的索引表区。请回答下列问题。1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？2）假设索引表区采用如下结构：第 07 字节采用格式表示文件创建时预分配的连续存储空间

6、，其中起始块号占 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

7、 08 d3 44 47 50 0b d9 13 88 84 6b 41 c5 00 00 00 00 70 02 43 805d b0 00 00 2 43 00 00 30 00 00 40 00 31 06 6e 83 d3 44 47 50c0 a8 00 08 13 88 0b d9 e0 59 9f ef 84 6b 41 c6 70 12 16 d037 e1 00 00 3 45 00 00 28 01 9c 40 00 80 06 1d ef c0 a8 00 08d3 44 47 50 0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 f0 43

8、 802b 32 00 00 4 45 00 00 38 01 9d 40 00 80 06 1d de c0 a8 00 08d3 44 47 50 0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 18 43 80e6 55 00 00 5 45 00 00 28 68 11 40 00 31 06 06 7a d3 44 47 50c0 a8 00 08 13 88 0b d9 e0 59 9f f0 84 6b 41 d6 50 10 16 d057 d2 00 00 回答下列问题。1）题 47-a 表中的 IP 分组中，哪几个是由 H 发送的？哪几个完成了

9、 TCP 连接建立过程？哪几个在通过快速以太网传输时进行了填充？2）根据题 47-a 表中的 IP 分组，分析 S 已经收到的应用层数据字节数是多少？3）若题 47-a 表中的某个 IP 分组在 S 发出时的前 40 字节如题 47-b 表所示，则该 IP 分组到达H 时经过了多少个路由器？题 47-b 表 来自 S 的分组 45 00 00 2868 11 40 00 40 06 ec ad d3 44 47 50 ca 76 01 06 13 88 a1 08e0 59 9f f0 84 6b 41 d6 50 10 16 d0 b7 d6 00 00 注：IP 分组头和 TCP 段头结构

10、分别如题 47-a 图，题 47-b 图所示。题 47-a 图 IP 分组头结构 题 47-b 图 TCP 段头结构 计算机学科专业基础综合试题参考答案 一、单项选择题 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 二、综合应用题 41解答：本题同时对多个知识点进

11、行了综合考查。对有序表进行两两合并考查了归并排序中的 Merge()函数；对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。1）对于长度分别为 m，n 的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为 m+n-1 次。故最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据哈夫曼树（最佳归并树）思想的启发，可采用如图所示的合并顺序。根据上图中的哈夫曼树，6 个序列的合并过程为：第 1 次合并：表 A 与表 B 合并，生成含有 45 个元素的表AB；第 2 次合并：表 AB 与表 C 合并，生成含有 85 个元素的表 ABC；第 3 次合并：表 D 与表

12、E 合并，生成含有 110 个元素的表DE；第 4 次合并：表 ABC 与表 DE 合并，生成含有 195 个元素的表 ABCDE；第 5 次合并：表 ABCDE 与表 F 合并，生成含有 395 个元素的最终表。由上述分析可知，最坏情况下的比较次数为：第 1 次合并，最多比较次数=10+351=44；第2 次合并，最多比较次数=45+401=84；第 3 次合并，最多比较次数=50+601=109；第 4 次合并，最多比较次数=85+1101=194；第 5 次合并，最多比较次数=195+2001=394。故比较的总次数最多为：44+84+109+194+394=825。2）各表的合并策略是

13、：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。【1）2）评分说明】对于用类似哈夫曼树（或最佳归并树）思想进行合并，过程描述正确，给 5 分。按其他策略进行合并，过程描述正确，给 3 分。正确算出与合并过程一致的总比较次数，给 2 分。若计算过程正确，但结果错误，可给1 分。考生只要说明采用的是类似哈夫曼树（或最佳归并树）的构造方法作为合并策略，即可给 3 分。如果采用其他策略，只要能够完成合并，给 2 分。42解答：顺序遍历两个链表到尾结点时，并不能保证两个链表

14、同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长 k 个结点，我们先在长链表上遍历 k 个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。算法的基本设计思想：分别求出 str1 和 str2 所指的两个链表的长度 m 和 n。将两个链表以表尾对齐：令指针 p、q 分别指向 str1 和 str2 的头结点，若 m=n，则使 p指向链表中的第 m-n+1 个结点；若 mlen2;len1-)/使 p 指向的链表与 q 指向的链表等长p=p-next;for(q=st

15、r2;len1next;while(p-next!=NULL&p-next!=q-next)/查找共同后缀起始点p=p-next;/两个指针同步向后移动q=q-next;return p-next;/返回共同后缀的起始点【1）、2）的评分说明】若考生所给算法实现正确，且时间复杂度为 O(m+n)，可给 12 分；若算法正确，但时间复杂度超过 O(m+n)，则最高可给 9 分。若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照的标准给分。若算法的基本设计思想描述或算法实现中部分正确，可参照中各种情况的相应给分标准酌情给分。3）时间

16、复杂度为：O(len1+len2)或 O(max(len1,len2)，其中 len1、len2 分别为两个链表的长度。【3）的评分说明】若考生所估计的时间复杂度与考生所实现的算法一致，可给 1 分。43解答：本题综合涉及到多个考点：计算机的性能指标、存储器的性能指标、DMA 的性能分析，DMA方式的特点，多体交叉存储器的性能分析。1）平均每秒 CPU 执行的指令数为：80M/4=20M，故 MIPS 数为 20；（1 分）平均每条指令访存 1.5 次，故平均每秒 Cache 缺失的次数=20M1.5(199%)=300k；（1 分）当 Cache 缺失时，CPU 访问主存，主存与 Cache

17、 之间以块为传送单位，此时，主存带宽为 16B300k/s=4.8MB/s。在不考虑 DMA 传送的情况下，主存带宽至少达到 4.8MB/s 才能满足 CPU 的访存要求。（2 分）2）题中假定在 Cache 缺失的情况下访问主存，平均每秒产生缺页中断 3000000.0005%=1.5次。因为存储器总线宽度为 32 位，所以每传送 32 位数据，磁盘控制器发出一次 DMA 请求，故平均每秒磁盘 DMA 请求的次数至少为 1.54KB/4B=1.5K=1536。（2 分）3）CPU 和 DMA 控制器同时要求使用存储器总线时，DMA 请求优先级更高；（1 分）因为 DMA 请求得不到及时响应，

18、I/O 传输数据可能会丢失。（1 分）4）4 体交叉存储模式能提供的最大带宽为 44B/50ns=320MB/s。（2 分）44解答：1）x 的机器码为x补=1111 1101 1111 1111B，即指令执行前(R1)=FDFFH，右移 1 位后位 11111110 1111 1111B，即指令执行后(R1)=FEFFH。（2 分）2）每个时钟周期只能有一条指令进入流水线，从第 5 个时钟周期开始，每个时钟周期都会有一条指令执行完毕，故至少需要 4+(5 1)=8 个时钟周期。（2 分）3）I3的 ID 段被阻塞的原因：因为 I3与 I1和 I2都存在数据相关，需等到 I1和 I2将结果写回

19、寄存器后，I3才能读寄存器内容，所以 I3的 ID 段被阻塞（1 分）。I4的 IF 段被阻塞的原因：因为 I4的前一条指令 I3在 ID 段被阻塞，所以 I4的 IF 段被阻塞（1 分）。注意：要求“按序发射，按序完成”，故第 2 小问中下一条指令的 IF 必须和上一条指令的 ID 并行，以免因上一条指令发生冲突而导致下一条指令先执行完。4）因 2*x 操作有左移和加法两种实现方法，故 x=x*2+a 对应的指令序列为I1 LOAD R1，xI2 LOAD R2，aI3 SHL R1/或者 ADD R1，R1I4 ADD R1，R2I5 STORE R2，x这 5 条指令在流水线中执行过程如

20、下图所示。时间单元 指令 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 故执行 x=x*2+a 语句最少需要 17 个时钟周期。45解答：1）页框号为 21。理由：因为起始驻留集为空，而 0 页对应的页框为空闲链表中的第三个空闲页框 21，其对应的页框号为 21。2）页框号为 32。理由：因 1110 故发生第三轮扫描，页号为 1 的页框在第二轮已处于空闲页框链表中，此刻该页又被重新访问，

21、因此应被重新放回驻留集中，其页框号为 32。3）页框号为 41。理由：因为第 2 页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框 41，页框号为 41。4）合适。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。46解答：1）文件系统中所能容纳的磁盘块总数为 4TB/1KB=232。要完全表示所有磁盘块，索引项中的块号最少要占32/8=4B。而索引表区仅采用直接索引结构，故512B的索引表区能容纳512B/4B=128个索引项。每个索引项对应一个磁盘块，所以该系统可支持的单个文件最大长度是 1281KB=128KB。2）这里的考查

22、的分配方式不同于我们所熟悉的三种经典分配方式，但是题目中给出了详细的解释。所求的单个文件最大长度一共包含两部分：预分配的连续空间和直接索引区。连续区块数占 2B，共可以表示 216个磁盘块，即 226B。直接索引区共 504B/6B=84 个索引项。所以该系统可支持的单个文件最大长度是 226B+84KB。为了使单个文件的长度达到最大，应使连续区的块数字段表示的空间大小尽可能接近系统最大容量 4TB。分别设起始块号和块数分别占 4B，这样起始块号可以寻址的范围是 232个磁盘块，共 4TB，即整个系统空间。同样的，块数字段可以表示最多 232个磁盘块，共 4TB。47解答：【解析】1）由题 4

23、7-a 表看出，源 IP 地址为 IP 分组头的第 1316 字节。在表 5-1 中 1、3、4号分组的源 IP 地址均为 192.168.0.8（c0a8 0008H），所以 1、3、4 号分组是由 H 发送的。题 47-a 表中，1 号分组封装的 TCP 段的 SYN=1，ACK=0，seq=846b 41c5H；2 号分组封装的TCP 段的 SYN=1，ACK=1，seq=e059 9fefH，ack=846b 41c6H；3 号分组封装的 TCP 段的 ACK=1，seq=846b 41c6H，ack=e059 9ff0H，所以 1、2、3 号分组完成了 TCP 连接的建立过程。由于快

24、速以太网数据帧有效载荷的最小长度为 46 字节，表 5-1 中 3、5 号分组的总长度为40（28H）字节，小于 46 字节，其余分组总长度均大于 46 字节。所以 3、5 号分组通过快速以太网传输时需要填充。2）由 3 号分组封装的 TCP 段可知，发送应用层数据初始序号为 seq=846b 41c6H，由 5 号分组封装的 TCP 段可知，ack 为 seq=846b 41d6H，所以 S 已经收到的应用层数据的字节数为 846b 41d6H-846b 41c6H=10H=16 字节。【评分说明】其他正确解答，亦给 2 分；若解答结果不正确，但分析过程正确给 1 分；其他情况酌情给分。3）由于 S 发出的 IP 分组的标识=6811H，所以该分组所对应的是表 5-1 中的 5 号分组。S 发出的 IP 分组的 TTL=40H=64，5 号分组的 TTL=31H=49，64-49=15，所以，可以推断该 IP 分组到达 H 时经过了 15 个路由器。【评分说明】若解答结果不正确，但分析过程正确给 1 分；其他情况酌情给分。