# 2012年全国硕士研究生入学统一考试 # 计算机科学与技术学科联考 # 计算机学科专业基础综合试题 # 一、单项选择题：第 $1\sim 40$ 小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。 1. 求整数 $n(n \geq 0)$ 阶乘的算法如下，其时间复杂度是 ```c int fact(int n){ if $(n < = 1)$ return 1; return $n^{\star}$ fact(n-1); } ``` A. $\mathrm{O}\left( {{\log }_{2}\mathrm{n}}\right)$ B. $\mathrm{O}\left( \mathrm{n}\right)$ C. $\mathrm{O}\left( {\mathrm{{nlog}}2\mathrm{n}}\right)$ D. $O\left(n^{2}\right)$ 2. 已知操作符包括‘+’、‘-’、‘*’、‘/’、‘(和)’。将中缀表达式 $\mathrm{a + b - a^{*}((c + d) / e - f) + g}$ 转换为等价的后缀表达式 $\mathrm{ab + acd + e / f - * - g + }$ 时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是 A. 5 B. 7 C. 8 D. 11 3. 若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点________。 A. 只有 e B. 有 e、b C. 有 e、c D. 无法确定 4. 若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为 ______。 A. 10 B. 20 C. 32 D. 33 5.对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是 A. $\mathrm{O}\left( \mathrm{n}\right)$ B. $O(e)$ C. $\mathrm{O}\left( {\mathrm{n} + \mathrm{e}}\right)$ D. $\mathrm{O}(\mathrm{n}^{*}\mathrm{e})$ 6. 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是 A. 存在，且唯一 B. 存在，且不唯一 C. 存在，可能不唯一 D. 无法确定是否存在 7. 对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是 ![](https://408.foreverlink.love/images/b15d5301f9581c21e39b282657b34719.jpg) A. d,e,f B. e,d,f C. f,d,e D. f,e,d 8. 下列关于最小生成树的叙述中，正确的是 I. 最小生成树的代价唯一 II．所有权值最小的边一定会出现在所有的最小生成树中 III. 使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同 IV．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同 A. 仅 I B. 仅 II C. 仅 I、III D. 仅 II、IV 9. 已知一棵 3 阶 B-树，如下图所示。删除关键字 78 得到一棵新 B-树，其最右叶结点中的关键字是 ![](https://408.foreverlink.love/images/94cb4139afb5369d5bb7bc9dee182a32.jpg) A. 60 B. 60, 62 C. 62, 65 D. 65 10. 在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是 I. 简单选择排序 II. 希尔排序 III. 快速排序 IV. 堆排序 V. 二路归并排序 A. 仅 I、III、IV B. 仅 I、III、V C. 仅 II、III、IV D. 仅III、IV、V 11．对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是 A. 排序的总趟数 B. 元素的移动次数 C. 使用辅助空间的数量 D. 元素之间的比较次数 12. 假定基准程序 A 在某计算机上的运行时间为 100 秒，其中 90 秒为 CPU 时间，其余为 I/O 时间。若 CPU 速度提高 $50\%$ ，I/O 速度不变，则运行基准程序 A 所耗费的时间是 ________。 A. 55秒 B. 60秒 C. 65秒 D. 70秒 13. 假定编译器规定 int 和 short 型长度分别为 32 位和 16 位，执行下列 C 语言语句： $$ \text {u n s i g n e d} x = 6 5 5 3 0; $$ $$ \text {u n s i g n e d} \quad \text {i n t} \quad y = x; $$ 得到y的机器数为 A. 00007FFAH B. 0000 FFFAH C. FFFF 7FFAH D. FFFF FFFAH 14. float 类型（即 IEEE754 单精度浮点数格式）能表示的最大正整数是 ______。 A. $2^{126} - 2^{103}$ B. $2^{127} - 2^{104}$ C. $2^{127} - 2^{103}$ D. $2^{128} - 2^{104}$ 15. 某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定 int 型和 short 型长度分别为 32 位和 16 位，并且数据按边界对齐存储。某 C 语言程序段如下： ```txt struct { int a; char b; short c; } record; record.a=273; ``` 若 record 变量的首地址为 0xC008，则地址 0xC008 中内容及 record.c 的地址分别为 ______。 A. $0 \times {00}$ 、 $0 \times \mathrm{C}{00}\mathrm{D}$ B. $0 \times {00}$ 、 $0 \times \mathrm{C}{00}\mathrm{E}$ C. $0 \times 11$ 、 $0 \times C 0 0 D$ D. $0 \times 11$ 、 $0 \times C 0 0 E$ 16. 下列关于闪存（Flash Memory）的叙述中，错误的是 A. 信息可读可写，并且读、写速度一样快 B. 存储元由MOS管组成，是一种半导体存储器 C. 掉电后信息不丢失, 是一种非易失性存储器 D. 采用随机访问方式, 可替代计算机外部存储器 17. 假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为1个字。若Cache的内容初始为空，采用2路组相联映射方式和LRU替换策略。访问的主存地址依次为0,4,8,2,0,6,8,6,4,8时，命中Cache的次数是________。 A. 1 B. 2 C. 3 D. 4 18. 某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有________。 A. 5 位 B. 6 位 C. 15 位 D. 33 位 19. 某同步总线的时钟频率为 $100\mathrm{MHz}$ ，宽度为 32 位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输 128 位数据所需要的时间至少是 ________。 A. 20ns B. 40ns C. 50ns D.80ns 20. 下列关于 USB 总线特性的描述中，错误的是 A. 可实现外设的即插即用和热拔插 B. 可通过级联方式连接多台外设 C. 是一种通信总线，连接不同外设 D. 同时可传输 2 位数据, 数据传输率高 21. 下列选项中，在 I/O 总线的数据线上传输的信息包括 ______。 I. I/O接口中的命令字 II. I/O接口中的状态字 III. 中断类型号 A. 仅 I、II B. 仅 I、III C. 仅 II、III D. I、II、III 22. 响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括 I．关中断 II. 保存通用寄存器的内容 III. 形成中断服务程序入口 A. 仅 I、II B. 仅 I、III C. 仅 II、III D. I、II、III 23. 下列选项中，不可能在用户态发生的事件是 A. 系统调用 B. 外部中断 C. 进程切换 D. 缺页 24. 中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是________。 A. 程序计数器 B. 程序状态字寄存器 C. 通用数据寄存器 D. 通用地址寄存器 25. 下列关于虚拟存储器的叙述中，正确的是 A. 虚拟存储只能基于连续分配技术 B. 虚拟存储只能基于非连续分配技术 C. 虚拟存储容量只受外存容量的限制 D. 虚拟存储容量只受内存容量的限制 26. 操作系统的 I/O 子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是________。 A. 用户级 I/O 软件、设备无关软件、设备驱动程序、中断处理程序 B. 用户级 I/O 软件、设备无关软件、中断处理程序、设备驱动程序 C. 用户级 I/O 软件、设备驱动程序、设备无关软件、中断处理程序 D. 用户级 I/O 软件、中断处理程序、设备无关软件、设备驱动程序 27. 假设 5 个进程 P0、P1、P2、P3、P4 共享三类资源 R1、R2、R3，这些资源总数分别为 18、6、22。T0 时刻的资源分配情况如下表所示，此时存在的一个安全序列是
进程已分配资源资源最大需求
R1R2R3R1R2R3
P03235510
P1403536
P24054011
P3204425
P4314424
A. P0, P2, P4, P1, P3 B.P1,P0,P3,P4,P2 C.P2,P1,P0,P3,P4 D.P3,P4,P2,P1,P0 28．若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是 I．若该文件的数据不在内存，则该进程进入睡眠等待状态 II．请求read系统调用会导致CPU从用户态切换到核心态 III. read 系统调用的参数应包含文件的名称 A. 仅 I、II B. 仅 I、III C. 仅 II、III D. I、II 和 III 29. 一个多道批处理系统中仅有 P1 和 P2 两个作业，P2 比 P1 晚 5ms 到达，它们的计算和 I/O 操作顺序如下： P1：计算60ms，I/O80ms，计算20ms P2：计算120ms，I/O40ms，计算40ms 若不考虑调度和切换时间，则完成两个作业需要的时间最少是 A. ${240}\mathrm{{ms}}$ B. $260 \mathrm{~ms}$ C. ${340}\mathrm{\;{ms}}$ D. ${360}\mathrm{\;{ms}}$ 30. 若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是________。 A. 在进程结束时能进行处理机调度 B. 创建新进程后能进行处理机调度 C. 在进程处于临界区时不能进行处理机调度 D. 在系统调用完成并返回用户态时能进行处理机调度 31. 下列关于进程和线程的叙述中，正确的是 A. 不管系统是否支持线程，进程都是资源分配的基本单位 B. 线程是资源分配的基本单位，进程是调度的基本单位 C. 系统级线程和用户级线程的切换都需要内核的支持 D. 同一进程中的各个线程拥有各自不同的地址空间 32. 下列选项中，不能改善磁盘设备 I/O 性能的是________。 A. 重排 I/O 请求次序 B. 在一个磁盘上设置多个分区 C. 预读和滞后写 D. 优化文件物理块的分布 33. 在TCP/IP体系结构中，直接为ICMP提供服务的协议是 A. PPP B. IP C. UDP D. TCP 34. 在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是________。 A. 机械特性 B. 功能特性 C. 过程特性 D. 电气特性 35. 以太网的 MAC 协议提供的是 A. 无连接不可靠服务 B. 无连接可靠服务 C. 有连接不可靠服务 D. 有连接可靠服务 36. 两台主机之间的数据链路层采用后退N帧协议（GBN）传输数据，数据传输速率为16kbps，单向传播时延为270ms，数据帧长度范围是128~512字节，接收方总是以与数据帧等长的帧进行确认。 为使信道利用率达到最高，帧序号的比特数至少为 A. 5 B. 4 C. 3 D. 2 37. 下列关于 IP 路由器功能的描述中，正确的是________。 I．运行路由协议，设备路由表 II. 监测到拥塞时，合理丢弃IP分组 III. 对收到的 IP 分组头进行差错校验，确保传输的 IP 分组不丢失 IV. 根据收到的 IP 分组的目的 IP 地址，将其转发到合适的输出线路上 A. 仅III、IV B. 仅 I、II、III C. 仅 I、II、IV D. I、II、III、IV 38. ARP协议的功能是 A. 根据 IP 地址查询 MAC 地址 B. 根据 MAC 地址查询 IP 地址 C. 根据域名查询 IP 地址 D. 根据 IP 地址查询域名 39. 某主机的 IP 地址为 180.80.77.55，子网掩码为 255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是 ________。 A. 180.80.76.0 B. 180.80.76.255 C. 180.80.77.255 D. 180.80.79.255 40. 若用户 1 与用户 2 之间发送和接收电子邮件的过程如下图所示，则图中①、②、③阶段分别使用的应用层协议可以是 ![](https://408.foreverlink.love/images/9ca8886b705c567b135516a0ad1b815e.jpg) A. SMTP、SMTP、SMTP B. POP3、SMTP、POP3 C. POP3、SMTP、SMTP D. SMTP、SMTP、POP3 # 二、综合应用题：第 $41\sim 47$ 题，共70分。 41. 设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。请问答下列问题。 1）给出完整的合并过程，并求出最坏情况下比较的总次数。 2）根据你的合并过程，描述 $\mathrm{N}(\mathrm{N} \geqslant 2)$ 个不等长升序表的合并策略，并说明理由。 42. 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。 ![](https://408.foreverlink.love/images/cb3a3b6259be9e9127aa44d136dc6840.jpg) 设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 data next，请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在结点的位置 p）。要求： 1）给出算法的基本设计思想。 2）根据设计思想，采用C或 $\mathbf{C} + +$ 或JAVA语音描述算法，关键之处给出注释。 3）说明你所设计算法的时间复杂度。 43. 假定某计算机的CPU主频为 $80\mathrm{MHz}$ ，CPI为4，平均每条指令访存1.5次，主存与Cache之间 交换的块大小为16B，Cache的命中率为 $99\%$ ，存储器总线宽带为32位。请回答下列问题。 1)该计算机的MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMA传送的情况下，主存带宽至少达到多少才能满足CPU的访存要求？ 2）假定在Cache缺失的情况下访问主存时，存在 $0.0005\%$ 的缺页率，则CPU平均每秒产生多少次缺页异常？若页面大小为4KB，每次缺页都需要访问磁盘，访问磁盘时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 的内容。 表 指令系统中部分指令格式
名称指令的汇编格式指令功能
加法指令ADD Rs, Rd(Rs)+(Rd)->Rd
算术/逻辑左移SHL Rd2*(Rd)->Rd
算术右移SHR Rd(Rd)/2->Rd
取数指令LOAD Rd, memmem)->Rd
存数指令STORE Rs, mem(Rs)->mem
该计算机采用5段流水方式执行指令，各流水段分别是取指（IF）、译码/读寄存器（ID）、执行/计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB），流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题： 1）若int型变量 $\mathbf{X}$ 的值为-513，存放在寄存器R1中，则执行指令“SHLR1”后，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]
时间单元
指令1234567891011121314
\(I_1\)IFIDEXMWB
\(I_2\)IFIDEXMWB
\(I_3\)IFIDEXMWB
\(I_4\)IFIDEXMWB
图指令序列及其执行过程示意图 则这4条指令执行过程中， $\mathrm{I}_3$ 的ID段和 $\mathbf{I}_4$ 的IF段被阻塞的原因各是什么？ 4）若高级语言程序中某赋值语句为 $\mathrm{x} = \mathrm{x}^{*}2 + \mathrm{a}$ ，x和a均为unsigned int类型变量，它们的存储单元 地址分别表示为[x]、[a]，则执行这条语句至少需要多少个时钟周期？要求模仿题44图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。 # 45. 某请求分页系统的局部页面置换策略如下： 系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。 假设不考虑其它进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的<虚拟页号，访问时刻>是： $< 1,1>$ 、 $< 3,2>$ 、 $< 0,4>$ 、 $< 0,6>$ 、 $< 1,11>$ 、 $< 0,13>$ 、 $< 2,14>$ 。请回答下列问题。 1）访问 $<0,4>$ 时，对应的页框号是什么？ 2）访问 $< 1,11>$ 时，对应的页框号是什么？说明理由。 3）访问 $< 2,14>$ 时，对应的页框号是什么？说明理由。 4）该策略是否适合于时间局部性好的程序？说明理由。 46. 某文件系统空间的最大容量为 $4\mathrm{TB}$ （ $1\mathrm{TB} = 2^{40}$ ），以磁盘块为基本分配单位。磁盘块大小为 $1\mathrm{KB}$ 。文件控制块（FCB）包含一个512B的索引表区。请回答下列问题。 1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？ 2）假设索引表区采用如下结构：第0~7字节采用<起始块号，块数 $>$ 格式表示文件创建时预分配的连续存储空间，其中起始块号占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字节内容（十六进制）
145 00 00 3001 9b 40 0080 06 1d e8c0 a8 00 08d3 44 47 50
0b d9 13 8884 6b 41 c500 00 00 0070 02 43 805d b0 00 00
243 00 00 3000 00 40 0031 06 6e 83d3 44 47 50c0 a8 00 08
13 88 0b d9e0 59 9f ef84 6b 41 c670 12 16 d037 e1 00 00
345 00 00 2801 9c 40 0080 06 1d efc0 a8 00 08d3 44 47 50
0b d9 13 8884 6b 41 c6e0 59 9f f050 f0 43 802b 32 00 00
445 00 00 3801 9d 40 0080 06 1d dec0 a8 00 08d3 44 47 50
0b d9 13 8884 6b 41 c6e0 59 9f f050 18 43 80e6 55 00 00
545 00 00 2868 11 40 0031 06 06 7ad3 44 47 50c0 a8 00 08
13 88 0b d9e0 59 9f f084 6b 41 d650 10 16 d057 d2 00 00
回答下列问题。 1）题47-a表中的IP分组中，哪几个是由H发送的？哪几个完成了TCP连接建立过程？哪几个在通过快速以太网传输时进行了填充？ 2）根据题47-a表中的IP分组，分析S已经收到的应用层数据字节数是多少？ 3）若题47-a表中的某个IP分组在S发出时的前40字节如题47-b表所示，则该IP分组到达H时经过了多少个路由器？
来自S的分组45 00 00 2868 11 40 0040 06 ec add3 44 47 50ca 76 01 06
13 88 a1 08e0 59 9f f084 6b 41 d650 10 16 d0b7 d6 00 00
注：IP分组头和TCP段头结构分别如题47-a图，题47-b图所示。 ![](https://408.foreverlink.love/images/b2d0e2c5a835589326f33e71d6a9fc43.jpg) 题47-a图 IP分组头结构 ![](https://408.foreverlink.love/images/40a9da4609d051da3585b450cfad7e89.jpg) 题47-b图TCP段头结构 # 2012年计算机学科专业基础综合试题参考答案 # 一、单项选择题 # （一）单选题答案
1.B2.A3.A4.B5.C6.C7.C8.A
9.D10.A11.D12.D13.B14.D15.D16.A
17.C18.C19.C20.D21.D22.B23.C24.B
25.B26.A27.D28.A29.B30.C31.A32.B
33.B34.C35.A36.B37.C38.A39.D40.D
# （二）单选题答案解析 # 1. 考查时间复杂度的计算。 该程序中使用了递归运算。本题中递归的边界条件是 $n <= 1$ ，每调用一次 fact()，传入该层 fact() 的参数值减 1（注意不是 n 减 1），因此执行频率最高的语句是 return n * fact(n-1)，一共执行了 n-1 次，而每一层 fact(i) 运算只包含一次乘法。如果采用递归式来表示时间复杂度，则： $$ T (n) = \left\{ \begin{array}{c c} 0 (1) & n \leq 1 \\ T (n - 1) + 1 & n > 1 \end{array} \right. $$ 时间复杂度为 $O(n)$ # 2. 考查栈的应用、表达式求值。 表达式求值是栈的典型应用。通常涉及中缀表达式和后缀表达式。中缀表达式不仅依赖运算符的优先级，还要处理括号。后缀表达式的运算符在表达式的后面且没有括号，其形式已经包含了运算符的优先级。所以从中缀表达式转换到后缀表达式需要用运算符栈对中缀表达式进行处理，使其包含运算法优先级的信息，从而转换为后缀表达式的形式。转换过程如下表：
运算符栈中缀未处理部分后缀生成部分
#a+b-a*((c+d)/e-f)+g
#+b-a*((c+d)/e-f)+ga
+b-a*((c+d)/e-f)+ga
+-a*((c+d)/e-f)+gab
-a*((c+d)/e-f)+gab+
-*( (c+d)/e-f)+gab+a
-*((c+d)/e-f)+gab+a
-*((c+d)/e-f)+gab+a
-*((+d)/e-f)+gab+ac
-*((+d)/e-f)+gab+ac
-*((+)/e-f)+gab+acd
-*((/e-f)+gab+acd+
-*((e-f)+gab+acd+
-*((-f)+gab+acd+e
-*(-f)+gab+acd+e/
-*(-) + gab+acd+e/f
-*+gab+acd+e/f-
-+gab+acd+e/f-*
#+gab+acd+e/f-*-
+gab+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。 【特殊法】前序序列和后序序列对应着多棵不同的二叉树树形，我们只需画出满足该条件的任一棵二叉树即可，任意一棵二叉树必定满足正确选项的要求。 ![](https://408.foreverlink.love/images/687762c57b6ef20c481526f717af1b23.jpg) a) ![](https://408.foreverlink.love/images/2ba07042f0767994c6955fc11793ee35.jpg) b） ![](https://408.foreverlink.love/images/6afb3ac4943f11ff9199a22de71452f8.jpg) c） ![](https://408.foreverlink.love/images/52a20531cccb1358114a59ad399a2383.jpg) d) 显然选A，最终得到的二叉树满足题设中前序序列和后序序列的要求。 # 4. 考查平衡二叉树的最少结点情况。 所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况，如图xxx所示。画图时，先画出 $\mathrm{T}_{1}$ 和 $\mathrm{T}_{2}$ ；然后新建一个根结点，连接 $\mathrm{T}_{2} 、 \mathrm{T}_{1}$ 构成 $\mathrm{T}_{3}$ ；新建一个根结点，连接 $\mathrm{T}_{3} 、 \mathrm{T}_{2}$ 构成 $\mathrm{T}_{4}$ ；依此类推，直到画出 $\mathrm{T}_{6}$ ，可知 $\mathrm{T}_{6}$ 的结点数为20。对于高度为N的题述的平衡二叉树，它的左、右子树分别为高度为N-1和N-2的所有非叶结点的平衡因子均为1的平衡二叉树。二叉树的结点总数公式为： $\mathrm{C}_{\mathrm{N}} = \mathrm{C}_{\mathrm{N - 1}} + \mathrm{C}_{\mathrm{N - 2}} + 1$ ， $C_{2} = 2$ ， $C_3 = 4$ ，递推可得 $C_6 = 20$ 。 ![](https://408.foreverlink.love/images/83f07391ad382e8968ffd6c2ef9091c0.jpg) ![](https://408.foreverlink.love/images/4e58cb6ce68c3e6944ee9d5c1fbfb2d0.jpg) ![](https://408.foreverlink.love/images/5b3a505bf213c3f8c9498afba24b7ec7.jpg) ![](https://408.foreverlink.love/images/2b30fc1fb59557a396ea9ad68cc84680.jpg) ![](https://408.foreverlink.love/images/42acdc50f0ff502debb4c237a3df7ca4.jpg) 【排除法】对于选项A，高度为6、结点数为10的树怎么也无法达到平衡。对于选项C，接点较多时，考虑较极端情形，即第6层只有最左叶子的完全二叉树刚好有32个结点，虽然满足平衡的条件，但显然再删去部分结点，依然不影响平衡，不是最少结点的情况。同理D错误。只可能选B。 # 5. 考查不同存储结构的图遍历算法的时间复杂度。 广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为 $O(n)$ ，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为 $O(e)$ ，算法总的时间复杂度为 $O(n + e)$ 。 # 6. 考查拓扑排序、与存储结构和图性质的关系。 对角线以下元素均为零，表明该有向图是一个无环图，因此一定存在拓扑序列。对于拓扑序列是否唯一，我们试举一例：设有向图的邻接矩阵 $\begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$ ，则存在两个拓扑序列。所以该图存在可能不唯一 的拓扑排序。 结论：对于任一有向图，如果它的邻接矩阵中对角线以下（或以上）的元素均为零，则存在拓扑序列（可能不唯一）。反正，若图存在拓扑序列，却不一定能满足邻接矩阵中主对角线以下的元素均为零，但是可以通过适当地调整结点编号，使其邻接矩阵满足前述性质。 # 7. 考查 Dijkstra 算法最单源最短路径。 从a到各顶点的最短路径的求解过程：
顶点第1趟第2趟第3趟第4趟对5趟
b(a,b) 2
c(a,c) 5(a,b,c) 3
d∞(a,b,d) 5(a,b,d) 5(a,b,d) 5
e∞∞(a,b,c,f) 4
f∞∞(a,b,c,e) 7(a,b,c,e) 7(a,b,d,e) 6
集合 S{a,b}{a,b,c}{a,b,c,f}{a,b,c,f,d}{a,b,c,f,d,e}
后续目标顶点依次为f,d,e， 【排除法】对于A，若下一个顶点为d，路径a,b,d的长度5，而a,b,c,f的长度仅为4，显然错误。同理可以排除B。将f加入集合S后，采用上述的方法也可以排除D。 8. 考查最小生成树、及最小生成树算法的性质。 对于I，最小生成树的树形可能不唯一（这是因为可能存在权值相同的边），但是代价一定是唯一的，I正确。对于II，如果权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，II错误。对于III，设N个结点构成环，N-1条边权值相等，则从不同的顶点开始普里姆算法会得到N-1中不同的最小生成树，III错误。对于IV，当最小生成树唯一时（各边的权值不同)，普里姆算法和克鲁斯卡尔算法得到的最小生成树相同，IV错误。 9. 考查B-树的删除操作。 对于上图所示的3阶B-树，被删关键字78所在结点在删除前的关键字个数 $= 1 = \lceil 3 / 2\rceil -1$ ，且其左兄弟结点的关键字个数 $= 2\geqslant \lceil 3 / 2\rceil$ ，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。 ![](https://408.foreverlink.love/images/1ef79bb8c1e5ead50df1bbaf3be329c1.jpg) 10. 考查各种内部排序算法的性质。 对于I，简单选择排序每次选择未排序列中的最小元素放入其最终位置。对于II，希尔排序每次是对划分的子表进行排序，得到局部有序的结果，所以不能保证每一趟排序结束都能确定一个元素的最终位置。对于III，快速排序每一趟排序结束后都将枢轴元素放到最终位置。对于IV，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。对于V，二路归并排序每趟对子表进行两两归并从而得到若干个局部有序的结果，但无法确定最终位置。 11. 考查折半插入和直接插入的区别。 折半插入排序与直接插入排序都是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查找法，而折半插入排序是采用折半查找法。排序的总趟数取决于元素个数 $n$ ，两者都是 $n - 1$ 趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是 $O(1)$ 。折半插入排序的比较次数与序列初态无关，为 $O(n\log 2n)$ ；而直接插入排序的比较次数与序列初态有关，为 $O(n)\sim O(n2)$ 。 12. 考查计算机性能指标的计算。 程序A的运行时间为100秒，除去CPU运行时间90秒，剩余10秒为I/O时间。CPU提速后运行基准程序A所耗费的时间是 $\mathrm{T} = 90 / 1.5 + 10 = 70$ 秒。 【误区】 CPU 速度提高 $50\%$ ，则 CPU 运行时间减少一半。错误！ 13. 考查 C 语言中的类型转换。 将一个16位unsigned short转换成一个32位的 unsigned int，新表示形式的所有附加位都用0进行填充。X的16进制表示为 FFFA，所以y的十六进制表示为 0000 FFFA。 14.考查IEEE754浮点数的性质。 IEEE754标准的单精度浮点数，是尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短浮点数的真值为： $(-1)^{\mathrm{S}}\times 1.\mathrm{f}\times 2^{\mathrm{E - }127}$ ，S为符号位，E的取值为 $1\sim 254$ （8位表示），f为23位；故float类型能表示的最大整数是 $1.111\dots 1\times 2^{254 - 127} = 2^{127}\times (2 - 2^{-23}) = 2^{128} - 2^{104}$ 。 15. 考查字符串的存储方式。 计算机存储器按字节编址，采用小端方式存放数据，即以数据的最低有效字节地址表示数据地址。在存储器中，数据结构按边界对齐方式顺序存储，因此int型数据的地址必须是4的倍数，short型数据地址必须是2的倍数。所以record.c的地址不可能为0xC00D。而273的十六进制表示为0x00000111，故地址0xC008中内容应为低字节0x11，如下表所示。
地址0xC0080xC0090xC00A0xC00B
内容record.a (0x11)record.a (0x01)record.a (0x00)record.a (0x00)
地址0xC00C0xC00D0xC00E0xC00F
内容record.b-record.crecord.c
16. 考查闪存（Flash Memory）的性质。 闪存是EEPROM的进一步发展，可读可写，用MOS管的浮栅上有无电荷来存储信息，它依然是ROM的一种，故写速度比读速度要慢不少（硬件常识）。闪存是一种非易失性存储器，它采用随机访问方式。现在常见的SSD固态硬盘，即由Flash芯片组成。 17. 考查组相联映射的 Cache 置换过程。 地址映射采用2路组相联，则主存地址为 $0\sim 1,4\sim 5,8\sim 9$ 可映射到第0组Cache中，主存地址为 $2\sim 3$ 、 $6\sim 7$ 可映射到第1组Cache中。Cache置换过程如下表所示。
走向0482068648
第0组块0044880084
块1\u\u\u8\u0\u*8\u\u*
第1组块222222
块3\u2\u6\u*66
注：*表示本次访问命中。 18. 考查微指令的编码方式。 操作控制字段采用字段直接编码法，将微命令字段分成若干个小字段，互斥类微命令可组合在同一字段。根据微命令字段分段的原则：①互斥性微命令分在同一段内，相容性微命令分在不同段内；②一般每个小段要留出一个状态，表示本字段不发出任何微命令。5个互斥类分别需要3、2、4、3、3共15位。 19. 考查总线传输性能的计算。 总线频率为 $100\mathrm{MHz}$ ，则时钟周期为10ns。总线宽度与存储字长都是32位，故每次传送一个32位存储字。猝发式发送可以连续传送地址连续的数据。故总的传送时间为：传送地址10ns，传送128位数据40ns，共需50ns。 20. 考查USB总线的特性（常识）。 USB总线（通用串行总线）的特点有：①即插即用；②热插拨；③有很强的连接能力，采用菊花链形式将所有外设连接起来，且不损失带宽；④有很好的可扩充性，一个USB控制器可扩充高达127个外部周边USB设备；⑤高速传输，速度可达480Mbps。所以A、B、C都符合USB总线的特点。对于选项D，USB是串行总线，不能同时传输两位数据。 21. 考查 I/O 总线的特点。 I/O接口与CPU之间的I/O总线有数据线、命令线和地址线。命令线和地址线都是单向传输的，从CPU传送给I/O接口，而I/O接口中的命令字、状态字以及中断类型号均是由I/O接口发往CPU的，故 只能通过I/O总线的数据线传输。 # 22. 考查中断隐指令。 在响应外部中断的过程中，中断隐指令完成的操作包括：①关中断；②保护断点；③引出中断服务程序（形成中断服务程序入口地址并送PC)，所以只有I、III正确。II中的保存通用寄存器的内容是在进入中断服务程序后首先进行的操作。 # 23. 考查用户态和和心态。 本题关键在于对“在用户态发生”（不是“完成”）的理解。对于A，系统调用是操作系统提供给用户程序的接口，调用程序发生在用户态，被调用程序在核心态下执行。对于B，外部中断是用户态到核心态的“门”，也是发生在用户态，在核心态完成中断过程。对于C，进程切换属于系统调用执行过程中的事件，只能发生在核心态；对于D，缺页产生后，在用户态发生缺页中断，然后进入核心态执行缺页中断服务程序。 # 24. 考查中断处理和子程序调用的区别。 子程序调用只需保护断点，即该指令的下一条指令的地址；中断调用子程序不仅要保护断点，还要保护程序状态字寄存器的内容PSW（有些机器也称标志寄存器FLAGS）。 # 25. 考查虚拟存储器的特点。 虚拟内存的实现需要建立在离散分配的内存管理方式的基础上，有以下三种实现方式：①请求分页存储管理；②请求分段存储管理；③请求段页式存储管理。虚拟存储器容量既不受外存容量限制，也不受内存容量限制，而是由CPU的寻址范围决定的。 # 26. 考查 I/O 子系统的层次结构。 输入/输出软件一般从上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。与设备无关的软件层也就是系统调用的处理程序。 # 27.考查安全序列的计算。 首先求得各进程的需求矩阵 Need 与可利用资源矢量 Available:
进程Need
R1R2R3
P0237
P1133
P2006
P3221
P4110
AvailableR1R2R3
233
初始时进程P1与P3可满足需求，排除A、C。尝试给P1分配资源，则P1完成后Available将变为(6,3,6)，无法满足P0的需求，排除B。尝试给P3分配资源，则P3完成后Available将变为（4,3,7），该向量能满足其他所有进程的需求。所以，以P3开头的所有序列都是安全序列。 # 28. 考查 read 系统调用的过程与特点。 对于I，当所读文件的数据不在内存时，产生中断（缺页中断、缺段中断），原进程进入阻塞状态（睡眠等待状态)，直到所需数据从外存调入进入内存后，将该进程唤醒，使其变为就绪状态。对于II，read系统调用通过陷入将CPU从用户态切换到核心态，从而获取操作系统提供的服务。对于III，在操作系统中，要读一个文件首先要用open系统调用将该文件打开。open系统调用的参数需要包含文件的路径名与文件名，而read系统调用只需要使用open返回的文件描述符，并不使用文件名作为参数。read系统调用要求用户提供三个输入参数：①文件描述符fd；②buf缓冲区首址；③传送的字节数n。read系统调用的功能是试图从fd所指示的文件中读入n个字节的数据，并将它们送至由指针buf所指示的缓冲区中。 # 29. 考查批处理系统的性能计算。 由于P2比P1晚5ms到达，P1先占用CPU，作业运行的甘特图如下： ![](https://408.foreverlink.love/images/b07bc64a62d2da130a50fee7e3621e83.jpg) 30. 考查处理机调度的时机。 选项A、B、D显然是可以进行处理机调度的情况。对于C，当进程处于临界区时，说明进程正在占用处理机，只要不破坏临界资源的使用规则，是不会影响处理机调度的，比如，通常访问临界资源可能是慢速的外设（如打印机），如果在进程访问打印机时，不能处理机调度，那么系统的性能将是非常低的。几种不适合进行处理机调度的情况：①在处理中断的过程中；②进程在操作系统内核程序临界区中；③其他需要完全屏蔽中断的原子操作过程中。 31. 考查进程与线程的区别与联系。 在用户级线程中，有关线程管理的所有工作都由应用程序完成，无需内核的干预，内核意识不到线程的存在。关于进程和线程的其他区别见下表所示：
进程线程
资源分配进程是资源分配和拥有的基本单位线程自己基本不拥有系统资源，但它可访问所属进程所拥有的全部资源。
调度在没有引入线程的操作系统中，进程是独立调度和分派的基本单位。引入线程后的操作系统中，线程是独立调度和分派的基本单位。
地址空间进程的地址空间之间互相独立。同一进程的各线程间共享进程的地址空间。
32.考查影响磁盘设备I/O性能的因素。 对于A，重排I/O请求次序也就是进行I/O调度，从而使进程之间公平地共享磁盘访问，减少I/O完成所需要的平均等待时间。对于C，缓冲区结合预读和滞后写技术对于具有重复性及阵发性的I/O进程改善磁盘I/O性能很有帮助。对于D，优化文件物理块的分布可以减少寻找时间与延迟时间，从而提高磁盘性能。 33.考查ICMP协议的特点。 ICMP是网络层协议，ICMP报文作为数据字段封装在IP分组中。 34. 考查物理层的接口特性。 过程特性定义了各条物理线路的工作过程和时序关系。 35. 考查以太网MAC协议。 考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简便：①采用无连接的工作方式；②不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力交付。差错的纠正由高层完成。 36.考查GBN协议。 本题主要求解的是从发送一个帧到接收到这个帧的确认为止的时间内最多可以发送多少数据帧。要尽可能多发帧，应以短的数据帧计算，因此首先计算出发送一帧的时间： $128*8 / (16*10^{3}) = 64\mathrm{ms}$ ；发送一帧到收到确认为止的总时间： $64 + 270*2 + 64 = 668\mathrm{ms}$ ；这段时间总共可以发送 $668 / 64 = 10.4$ （帧），发送这么多帧至少需要用4位比特进行编号。 37.考查IP路由器的功能。 I、IV显然是IP路由器的功能。对于II，当路由器监测到拥塞时，可合理丢弃IP分组，并向发出 该IP分组的源主机发送一个源点抑制的ICMP报文。对于III，路由器对收到的IP分组首部进行差错检验，丢弃有差错首部的报文，但不保证IP分组不丢失。 38.考查ARP协议的功能。 在实际网络的数据链路层上传送数据时，最终必须使用硬件地址，ARP协议是将网络层的IP地址解析为数据链路层的MAC地址。 39. 考查 IP 地址的特点。 由于网掩码可知前22位为子网号、后10位为主机号。IP地址的第3个字节为01001101（下划线为子网号的一部分），将主机号全置为1，可得广播地址为180.80.79.255。 40. 考查电子邮件中的协议。 SMTP采用“推”的通信方式，用于用户代理向邮件服务器发送邮件、以及邮件服务器之间发送邮件。POP3采用“拉”的通信方式，用于用户从目的邮件服务器上读取邮件。 # 二、综合应用题 # 41. 解答： 本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中的Merge()函数；对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。 1）对于长度分别为 $\mathfrak{m}$ ， $\mathfrak{n}$ 的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为 $\mathrm{m + n - 1}$ 次。故，最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据哈夫曼树（最佳归并树）思想的启发，可采用如图所示的合并顺序。 ![](https://408.foreverlink.love/images/9925bd5d94ce4b605ff441668733cc06.jpg) 根据上图中的哈夫曼树，6个序列的合并过程为： 第1次合并：表A与表B合并，生成含有45个元素的表AB； 第2次合并：表AB与表C合并，生成含有85个元素的表ABC； 第3次合并：表D与表E合并，生成含有110个元素的表DE； 第4次合并：表ABC与表DE合并，生成含有195个元素的表ABCDE； 第5次合并：表ABCDE与表F合并，生成含有395个元素的最终表。 由上述分析可知，最坏情况下的比较次数为：第1次合并，最多比较次数 $= 10 + 35 - 1 = 44$ ；第2次合并，最多比较次数 $= 45 + 40 - 1 = 84$ ；第3次合并，最多比较次数 $= 50 + 60 - 1 = 109$ ；第4次合并，最多比较次数 $= 85 + 110 - 1 = 194$ ；第5次合并，最多比较次数 $= 195 + 200 - 1 = 394$ 。 故，比较的总次数最多为： $44 + 84 + 109 + 194 + 394 = 825$ 2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。 【1）2）评分说明】 (1)对于用类似哈夫曼树（或最佳归并树）思想进行合并，过程描述正确，给5分。按其他策略进行 合并，过程描述正确，给3分。 ②正确算出与合并过程一致的总比较次数，给2分。若计算过程正确，但结果错误，可给1分。 ③考生只要说明采用的是类似哈夫曼树（或最佳归并树）的构造方法作为合并策略，即可给3分。如果采用其他策略，只要能够完成合并，给2分。 # 42. 解答： 1）顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长 $\mathbf{k}$ 个结点，我们先在长链表上遍历 $\mathbf{k}$ 个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。算法的基本设计思想： ① 分别求出 str1 和 str2 所指的两个链表的长度 m 和 n; ② 将两个链表以表尾对齐：令指针 p、q 分别指向 str1 和 str2 的头结点，若 $m >= n$ ，则使 p 指向链表中的第 $m - n + 1$ 个结点；若 $m < n$ ，则使 q 指向链表中的第 $n - m + 1$ 个结点，即使指针 p 和 q 所指的结点到表尾的长度相等。 ③ 反复将指针 p 和 q 同步向后移动，并判断它们是否指向同一结点。若 p 和 q 指向同一结点，则该点即为所求的共同后缀的起始位置。 # 2）算法的C语言代码描述： ```txt LinkNode \*Find_1st/Common(LinkList strl,LinkList str2){ int len1=Length(str1),len2=Length(str2); LinkNode \*p,\*q; for(p=str1;len1>len2;len1--） //使p指向的链表与q指向的链表等长 p=p->next; for(q=str2;len1next; while(p->next!=NULL&&p->next!=q->next){//查找共同后缀起始点 p=p->next; //两个指针同步向后移动 q=q->next; } return p->next; //返回共同后缀的起始点 ``` 【1）2）的评分说明】 $①$ 若考生所给算法实现正确，且时间复杂度为 $\mathrm{O(m + n)}$ ，可给12分；若算法正确，但时间复杂度超过 $\mathrm{O(m + n)}$ ，则最高可给9分。 ②若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。 ③若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。 ④参考答案中只给出了使用C语言的版本，使用 $\mathrm{C} + + /$ JAVA语言的答案视同时用C语言。 3）时间复杂度为：O(len1+len2)或O(max(len1, len2))，其中len1、len2分别为两个链表的长度。 【3）的评分说明】 若考生所估计的时间复杂度与考生所实现的算法一致，可给1分。 # 43. 解答： 1）平均每秒CPU执行的指令数为： $80\mathrm{M} / 4 = 20\mathrm{M}$ ，故MIPS数为20；（1分） 平均每条指令访存1.5次，故平均每秒Cache缺失的次数 $= 20\mathrm{M}\times 1.5\times (1 - 99\%) = 300\mathrm{k}$ ；（1分） 当 Cache 缺失时，CPU 访问主存，主存与 Cache 之间以块为传送单位，此时，主存带宽为 $16\mathrm{B} \times 300\mathrm{k/s} = 4.8\mathrm{MB/s}$ 。在不考虑 DMA 传输的情况下，主存带宽至少达到 $4.8\mathrm{MB/s}$ 才能满足 CPU 的访存要求。（2 分） 2）题中假定在Cache缺失的情况下访问主存，平均每秒产生缺页中断 $300000 \times 0.0005\% = 1.5$ 次。因为存储器总线宽度为32位，所以每传送32位数据，磁盘控制器发出一次DMA请求，故平均每秒磁盘DMA请求的次数至少为 $1.5 \times 4\mathrm{KB} / 4\mathrm{B} = 1.5\mathrm{K} = 1536$ 。（2分） 3）CPU和DMA控制器同时要求使用存储器总线时，DMA请求优先级更高；（1分） 因为DMA请求得不到及时响应，I/O传输数据可能会丢失。（1分） 4）4体交叉存储模式能提供的最大带宽为 $4\times 4\mathrm{B} / 50\mathrm{ns} = 320\mathrm{MB / s}$ 。（2分） # 44. 解答： 1） $\mathbf{x}$ 的机器码为 $[\mathbf{x}]_{\text{补}} = 111111011111B$ ，即指令执行前 $(R1) = FDFFH$ ，右移1位后为111111101111111B，即指令执行后 $(R1) = FEFFH$ 。（2分） 【评分说明】仅正确写出指令执行前的(R1)可给1分。 2）至少需要 $4 + (5 - 1) = 8$ 个时钟周期数。（2分） 3） $\mathrm{I}_3$ 的ID段被阻塞的原因：因为 $\mathbf{I}_3$ 与 $\mathbf{I}_1$ 和 $\mathbf{I}_2$ 都存在数据相关，需等到 $\mathbf{I}_1$ 和 $\mathbf{I}_2$ 将结果写回寄存器后， $\mathbf{I}_3$ 才能读寄存器内容，所以 $\mathbf{I}_3$ 的ID段被阻塞。（1分） $\mathrm{I}_4$ 的 IF 段被阻塞的原因：因为 $\mathbf{I}_4$ 的前一条指令 $\mathrm{I}_3$ 在 ID 段被阻塞，所以 $\mathrm{I}_4$ 的 IF 段被阻塞。（1 分） 4）因 $2^{*}\mathbf{x}$ 操作有左移和加法两种实现方法，故 $\mathrm{x = x^{\ast}2 + a}$ 对应的指令序列为 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分）
时间单元
指令1234567891011121314151617
I1IFIDEXMWB
I2IFIDEXMWB
I3IFIDEXMWB
I4IFIDEXMWB
I5IFIDEXMWB
故执行 $\mathrm{x} = \mathrm{x}^{*}2 + \mathrm{a}$ 语句最少需要17个时钟周期。（1分） # 45. 解答： 1）页框号为21。（1分）理由：因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框（21），其对应的页框号为21。（1分） 2）页框号为32。（1分）理由：因 $11 > 10$ 故发生第三轮扫描，页号为1的页框在第二轮已处于空闲页框链表中，此刻该页又被重新访问，因此应被重新放回驻留集中，其页框号为32。（1分） 3）页框号为41。（1分）理由：因为第2页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。（1分） 4）合适。（1分）理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该 策略的优势越明显。（1分） # 46. 解答： 1）文件系统中所能容纳的磁盘块总数为 $4\mathrm{TB} / 1\mathrm{KB} = 2^{32}$ 。要完全表示所有磁盘块，索引项中的块号最少要占 $32 / 8 = 4\mathrm{B}$ 。（2分） 而索引表区仅采用直接索引结构，故512B的索引表区能容纳 $512\mathrm{B} / 4\mathrm{B} = 2^{7}$ 个索引项。每个索引项对应一个磁盘块，所以该系统可支持的单个文件最大长度是 $128\times 1\mathrm{KB} = 128\mathrm{KB}$ 。（2分） 【评分说明】过程描述正确，但计算结果不正确，可酌情给分。 2）块号占6B、块数占2B时，共可以表示 $2^{16}$ 个磁盘块，即 $2^{26} = 64\mathrm{MB}$ ；直接索引区共 $504\mathrm{B} / 6\mathrm{B} = 84$ 个索引项。所以该系统可支持的单个文件最大长度是 $2^{26}\mathrm{B} + 84\mathrm{KB} = 65620\mathrm{KB}$ 。（2分） 合理的起始块号和块数所占字节数分别为4,4（或1,7或2,6或3,5)。（1分）理由：块数占4B或以上，就可表示4TB大小的文件长度，达到文件系统的空间上限。（1分） 【评分说明】过程描述正确，但计算结果不正确，可酌情给分。只要答出起始块号和块数所占字节数的任何合理值，均可得1分；理由说明正确得1分。 # 47. 解答： 1）由于题47-a表中1、3、4号分组的源IP地址（第 $13\sim 16$ 字节）均为192.168.0.8（c0a80008H），因此可以判定1、3、4号分组是由H发送的。（3分） 题47-a表中1号分组封装的TCP段的FLAG为02H（即 $\mathrm{SYN} = 1$ ，ACK $= 0$ )，seq $= 846\mathrm{b}41\mathrm{c}5\mathrm{H}$ ，2号分组封装的TCP段的FLAG为12H（即 $\mathrm{SYN} = 1$ ，ACK $= 1$ )，seq $=$ e0599fefH，ack $= 846\mathrm{b}41\mathrm{c}6\mathrm{H}$ ，3号分组封装的TCP段的FLAG为 $10\mathrm{H}$ （即 $\mathrm{ACK} = 1$ )，seq $= 846\mathrm{b}41\mathrm{c}6\mathrm{H}$ ，ack $=$ e0599ff0H，所以1、2、3号分组完成了TCP连接建立过程。（1分） 由于快速以太网数据帧有效载荷的最小长度为46字节，表中3、5号分组的总长度为40（28H）字节，小于46字节，其余分组总长度均大于46字节。所以3、5号分组通过快速以太网传输时进行了填充。（1分） 2）由3号分组封装的TCP段可知，发送应用层数据初始序号为seq=846b 41c6H，由5号分组封装的TCP段可知，ack为seq=846b 41d6H，所以5号分组已经收到的应用层数据的字节数为846b 41d6H-846b 41c6H=10H=16。（2分） 【评分说明】其他正确解答，亦给2分；若解答结果不正确，但分析过程正确给1分；其他情况酌情给分。 3）由于S发出的IP分组的标识 $= 6811\mathrm{H}$ ，所以该分组所对应的是题47-a表中的5号分组。S发出的IP分组的 $\mathrm{TTL} = 40\mathrm{H} = 64$ ，5号分组的 $\mathrm{TTL} = 31\mathrm{H} = 49$ ， $64 - 49 = 15$ ，所以，可以推断该IP分组到达H时经过了15个路由器。（2分） 【评分说明】若解答结果不正确，但分析过程正确给1分；其他情况酌情给分。