2012年全国研究生考试计算机统考真题

（9 分）主机 H 通过快速以太网连接 Internet，IP 地址为 192.168.0.8，服务器 S 的 IP 地址为 211.68.71.80。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 时经过了多少个路由器？

（8 分）某文件系统空间的最大容量为 4TB（1TB=240），以磁盘块为基本分配单位。磁盘块大小为 1KB。文件控 制块（FCB）包含一个 512B 的索引表区。请回答下列问题。

（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？ 可支持的单个文件最大长度是多少字节？

（2）假设索引表区采用如下结构：第 0~7 字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储 空间。其中起始块号占 6B，块数占 2B，剩余 504 字节采用直接索引结构，一个索引项占 6B，则可支持的单个文件 最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理 由。

(7 分)某请求分页系统的页面置换策略如下：

从 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）这种方法是否适合于时间局部性好的程序？说明理由。

（12 分）某 16 位计算机中，带符号整数用补码表示，数据 Cache 和指令 Cache 分离。题 44 表给出了指令系统 中部分指令格式，其中 Rs 和 Rd 表示寄存器，mem 表示存储单元地址，（x）表示寄存器 x 或存储单元 x 的内容。

题 44 表指令系统中部分指令格式

该计算机采用 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]。该语句对应的指令序列及其在指令流中的执行过程如题 44 图所示。

则这 4 条指令执行过程中 I3 的 ID 段和 I4 的 IF 段被阻塞的原因各是什么？

（4）若高级语言程序中某赋值语句为 x=x*2+a，x 和 a 均为 unsigned int 类型变量，它们的存储单元地址分别表示 为[x]、[a]，则执行这条语句至少需要多少个时钟周期？要求模仿题 44 图画出这条语句对应的指令序列及其在流水 线中的执行过程示意图。

（13 分）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，

例如，“loading”和“being”的存储映像如下图所示。

设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为

，请设计一个时间上尽 可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在结点的位置 p）。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用 C 或 C++或 JAVA 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度。

（11 分）假设某计算机的 CPU 主频为 80MHz，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，则主存能提供的最大带宽是多少？

（10 分）设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据元素，各表中元素 按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。

请问答下列问题。

（1）给出完整的合并过程，并求出最坏情况下比较的总次数。

（2）根据你的合并过程，描述 n（n≥2）个不等长升序表的合并策略，并说明理由。

若用户 1 与用户 2 之间发送和接收电子邮件的过程如下图所示，则图中①、②、③阶段分别使用的应用层协议 可以是

下列关于 IP 路由器功能的描述中，正确的是

运行路由协议，设备路由表

II.监测到拥塞时，合理丢弃 IP 分组

III.对收到的 IP 分组头进行差错校验，确保传输的 IP 分组不丢失

IV.根据收到的 IP 分组的目的 IP 地址，将其转发到合适的输出线路上

某主机的 IP 地址为 180.80.77.55，子网掩码为 255.255.252.0。若该主机向其所在子网发送广播分组，则目的地 址可以是

ARP 协议的功能是

两台主机之间的数据链路层采用后退 N 帧协议（GBN）传输数据数据传输速率为 16 kbps，单向传播时延为 270ms， 数据帧长度范围是 128~512 字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序列的 比特数至少为

以太网的 MAC 协议提供的是

在 TCP/IP 体系结构中，直接为 ICMP 提供服务协议的是

在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是

下列关于进程和线程的叙述中，正确的是

下列选项中，不能改善磁盘设备 I/O 性能的是

若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中错误的是

若一个用户进程通过 read 系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是

若该文件的数据不在内存，则该进程进入睡眠等待状态

II. 请求 read 系统调用会导致 CPU 从用户态切换到核心态

III. read 系统调用的参数应包含文件的名称

一个多道批处理系统中仅有 P1 和 P2 两个作业，P2 比 P1 晚 5ms 到达，它的计算和 I/O 操作顺序如下：

P1：计算 60ms，I/O 80ms，计算 20ms

P2：计算 120ms，I/O 40ms，计算 40ms

若不考虑调度和切换时间，则完成两个作业需要的时间最少是

假设 5 个进程 P0、P1、P2、P3、P4 共享三类资源 R1、R2、R3，这些资源总数分别为 18、6、22。T0 时刻的 资源分配情况如下表所示，此时存在的一个安全序列是

操作系的 I/O 子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口，其合理的层次组织排列顺序 是

中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是

下列关于虚拟存储器的叙述中，正确的是

下列选项中，不可能在用户态发生的事件是

响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括

关中断

II.保存通用寄存器的内容

III.形成中断服务程序入口地址并送 PC

下列选项中，在 I/O 总线的数据线上传输的信息包括

I/O 接口中的命令字

II. I/O 接口中的状态字

III.中断类型号

某同步总线的时钟频率为 100MHz，宽度为 32 位，地址/数据线复用，每传送一次地址或者数据占用一个时钟 周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输 128 位数据所需要的时间至少是

下列关于 USB 总线特性的描述中，错误的是

假设某计算机按字编址，Cache 有 4 个行，Cache 和主存之间交换的块为 1 个字。若 Cache 的内容初始为空， 采用 2 路组相联映射方式和 LRU 替换算法。当访问的主存地址依次为 0,4,8,2,0,6,8,6,4,8 时，命中 Cache 的次数是

某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有 33 个微命令， 构成 5 个互斥类，分别包含 7、3、12、5 和 6 个微命令，则操作控制字段至少有

下列关于闪存（Flash Memory）的叙述中，错误的是

某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定 int 和 short 型长度分别为 32 位和 16 位， 并且数据按边界对齐存储。某 C 语言程序段如下：

struct{

int a;

char b;

short c;

} record;

recorD．a=273;

若 record 变量的首地址为 0Xc008，则低至 0Xc008 中内容及 recorD．c 的地址分别为

float 类型（即 IEEE754 单精度浮点数格式）能表示的最大正整数是

假定编译器规定 int 和 short 类型长度占 32 位和 16 位，执行下列 C 语言语句

unsigned short x = 65530;

unsigned int y = x;

得到 y 的机器数为

假定基准程序 A 在某计算机上的运行时间为 100 秒，其中 90 秒为 CPU 时间，其余为 I/O 时间。若 CPU 速度 提高 50%，I/O 速度不变，则运行基准程序 A 所耗费的时间是

在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排 序结束都至少能够确定一个元素最终位置的方法是

简单选择排序

II. 希尔排序

III. 快速排序

IV 堆排序

二路归并排序

对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是

下列关于最小生成树的说法中，正确的是

最小生成树树的代价唯一

II. 权值最小的边一定会出现在所有的最小生成树中

III. 用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同

IV. 普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同

设有一棵 3 阶 B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是

若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是

对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求源点 a 到其他各顶点的最短路径，则得到的第一条最 短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是

对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是

若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点

若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为

求整数 n(n≥0)阶乘的算法如下，其时间复杂度是

int fact(int n)

{

if (n<=1)return 1;

return n*fact(n-1);

}

已知操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。将中缀表达式 a+b-a*((c d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最 大个数是