2012 年全国硕士研究生入学统一考试 计算机科学与技术学科联考 计算机学科专业基础综合试题 一、单项选择题：第 1 40 小题，每小题 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）、执行 /计算有效地址（ EX）、访问存储器（ M）和结果写回寄存器（ WB），流水线采用 “按序发射，按序完成 ”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题： 1）若 int 型变量 x 的值为 -513，存放在寄存器 R1 中，则执行指令 “SHL R1”后， R1 的内容是多少？（用十六进制表示） 2）若某个时间段中，有连续的 4 条指令进入流水线，在其执行过程中没有发生任何阻 塞，则执行这 4 条指令所需的时钟周期数为多少？ 3）若高级语言程序中某赋值语句为 x=a+b， 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） 若高级语言程序中某赋值语句为 x=x*2+a， x 和 a 均为 unsigned int 类型变量，它们的存储单元王道论坛（ www.cskaoyan.com） 原创并 友情分享！ 7 地址分别表示为 x、 a，则执行这条语句至少需要多少个时钟周期？要求模仿题 44 图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。 45 某请求分页系统的局部页面置换策略如下： 系统从 0 时刻开始扫描，每隔 5 个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲 页链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。 假设不考虑 其它进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框 链表中页框 号依次为 32、 15、 21、 41。进程 P 依次访问的 是： 、 、 、 、 、 。请回答下列问题。 1） 访问 时，对应的页框号是什么？ 2） 访问 时，对应的页框号是什么？说明理由。 3） 访问 时，对应的页框号是什么？说明理由。 4） 该策略 是否 适合于时间局部性好的程序？说明理由。 46 某文件系统空间的最大容量为 4TB（ 1TB=240），以磁盘块为基本分配单位。磁盘块大小为 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 表 王道论坛（ www.cskaoyan.com） 原创并 友情分享！ 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 考查时间复杂度的计算。 该程序中使用了递归运算。本题中递归的边界条件是 n<=1，每调用一次 fact()，传入该层 fact()的参数值减 1（注意不是 n 减 1），因此执行频率最高的语句是 return n*fact(n-1)，一共执行了 n-1 次 ， 而每一层 fact(i)运算只包含一次乘法。如果采用递归式来表示时间复杂度，则 ： 王道论坛（ www.cskaoyan.com） 原创并 友情分享！ 9 时间复杂度为 O(n)。 2考查栈的应用、表达式求值。 表达式求值是栈的典型应用。 通常涉及中缀表达式和后缀表达式。中缀表达式不仅依赖运算符的优先级，还要处理括号。后缀表达式的运算符在表达式的后面且没有括号，其形式已经包含了运算符的优先级。所以从中缀表达式转换到后缀表达式需要用运算符栈对中缀表达式进行处理，使其包含运算法优先级的信息，从而转换为后缀表达式的形式。转换过程如下表： 运算符栈 中缀未处理部分 后缀生成部分 # a+b-a*(c+d)/e-f)+g # +b-a*(c+d)/e-f)+g a + b-a*(c+d)/e-f)+g a + -a*(c+d)/e-f)+g ab - a*(c+d)/e-f)+g ab+ - *(c+d)/e-f)+g ab+a -* (c+d)/e-f)+g ab+a -*( c+d)/e-f)+g ab+a -*( +d)/e-f)+g ab+ac -*(+ d)/e-f)+g ab+ac -*(+ )/e-f)+g ab+acd -*( /e-f)+g ab+acd+ -*(/ e-f)+g ab+acd+ -*(/ -f)+g ab+acd+e -*(- f)+g ab+acd+e/ -*(- )+g ab+acd+e/f -* +g ab+acd+e/f- - +g ab+acd+e/f-* # +g ab+acd+e/f-*- + g ab+acd+e/f-*- # ab+acd+e/f-*-g 3考查树的遍历、及由遍历序列确定二叉树的树形。 前序序列 和 后序序列 不能唯一确定一棵二叉树，但 可以确定二叉树中结点的祖先关系：当两个结点的前序序列为 XY 与后序序列为 YX 时， 则 X 为 Y 的祖先。 考虑前序序列 a,e,b,d,c、后序序列 b,c,d,e,a，可知 a 为根结点， e 为 a 的孩子结点 ；此外， a 的孩子结点的前序序列 e,b,d,c、后序序列 b,c,d,e，可知 e是 bcd 的祖先， 故根结点的孩子结点只有 e。 本题答案为 A。 【特殊法】 前序序列和后序序列对应着多棵不同的二叉树树形，我们只需画出满足该条件的任一棵二叉树即 可，任意一棵二叉树必定满足正确选项的要求。 王道论坛（ www.cskaoyan.com） 原创并 友情分享！ 10 ae , b , d , cab , d , cead , ceebaeebdca ） b ） c ） d ）显然选 A，最终得到的二叉树满足题设中前序序列和后序序列的要求。 4考查平衡二叉树的最少结点情况。 所有非叶结点的平衡因子均为 1，即平衡二叉树满足平衡的最少结点情况，如图 xxx 所示。画图时，先画出 T1 和 T2；然后新建一个根结点，连接 T2、 T1 构成 T3；新建一个根结点，连接 T3、 T2 构成 T4；依此类推，直到画出 T6，可知 T6 的结点数为 20。 对于高度为 N 的题述的平衡二叉树，它的左、右子树分别为高度为 N-1 和 N-2 的 所有非叶结点的平衡因子均为 1 的平衡二叉树 。二叉树的结点总数公式为：CN=CN-1+CN-2+1， C2=2， C3=4，递推可得 C6=20。 【排除法】 对于选项 A，高度为 6、结点数为 10 的树怎么也无法达到平衡。对于选项 C，接点较多时，考虑较极端情形，即第 6 层只有最左叶子的完全二叉树刚好有 32 个结点，虽然满足平衡的条件，但显然再删去部分结点，依然不影响平衡，不是最少结点的情况。同理 D 错误。只可能选 B。 5考查不同存储结构的图遍历算法的时间复杂度。 广度优先遍历需要借助队列实现。邻接表的结构包括 ：顶点表 ； 边表（有向图为出边表）。当采用 邻接表存储方式 时 ， 在对图进行广度优先遍历时 每个顶点均需入队一次 （顶点表遍历） ，故时间复杂度为O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为 O(e)，算法总的时间复杂度为 O(n+e)。 6考查拓扑排序、与存储结构和图性质的关系。 对角线以下元素均为零，表明该有向图是一个无环图，因此一定存在拓扑序列。对于拓扑序列是否唯一，我们试举一例：设 有向图 的 邻接矩阵 0 1 1000000，则存在两个拓扑序列。所以该图存在可能不唯一的拓扑排序。 结论： 对于 任一有向 图，如果它的邻接矩阵 中对角线以下（或以上）的元素均为零 ，则存在拓扑序列 （可能不唯一） 。 反正，若图存在拓扑序列，却不一定能满足邻接矩阵中主对角线以下的元素均为零，但是可以通过适当地调整结点编号，使其邻接矩阵满足前述性质。 7考查 Dijkstra 算法 最单源最短路径。 从 a 到各顶点的最短路径的求解过程： 顶点 第 1 趟 第 2 趟 第 3 趟 第 4 趟 对 5 趟 b (a,b) 2 c (a,c) 5 (a,b,c) 3