2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解

一、单项选择题：1～40小题。每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

1求整数n（n≥0）阶乘的算法如下，其时间复杂度是（　　）。

A．O（log₂n）

B．O（n）

C．O（nlog₂n）

D．O（n²）

【答案】B

【解析】设fact（n）的运行时间函数是T（n）。

该函数中语句①的运行时间是O（1），语句②的运行时间是T（n－1）＋O（1），其中O（1）为乘法运算的时间。

因此，当n≤1时，T（n）－O（1）；当n＞1时，T（n）＝T（n－1）＋O（1）。则，T（n）＝O（1）＋T（n－1）＝2×O（1）＋T（n－2）＝（n－1）×O（1）＋T（1）＝n×O（1）＝O（n），即fact（n）的时间复杂度为O（n）。

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

A．5

B．7

C．8

D．11

【答案】A

【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级的运算符在栈中的先计算）。表达式a＋b－a*（（c＋d）/e－f）＋g产生后缀表达式的过程如下表所列：

通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。

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

A．只有e

B．有e、b

C．有e、c

D．无法确定

【答案】A

【解析】由题目可知，若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，其中a为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e，而后序遍历的倒数第二个结点为e，说明a的孩子结点只有e。

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

A．12

B．20

C．32

D．33

【答案】B

【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的结点数是多少。N_h表示深度为h的平衡二叉树中含有的最少结点数，有N₀＝0，N₁＝1，N₂＝2……N_h＝N_h－1＋N_h－2＋1。

由此可得N₅＝20。对应的平衡二叉树如下图所示。

5对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（　　）。

A．O（n）

B．O（e）

C．O（n＋e）

D．O（n×e）

【答案】C

【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O（n²），其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O（n＋e）。即可得出正确答案。

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

A．存在，且唯一

B．存在，且不唯一不唯一

C．存在，可能不唯一

D．无法确定是否存在

【答案】C

【解析】图的基本应用——拓扑排序，用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，说明该图为有向无环图，所以其拓扑序列存在，但不一定唯一，如图的邻接矩阵为，则存在两个拓扑序列。

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

题7图　有向带权图

A．d，e，f

B．e，d，f

C．f，d，e

D．f，e，d

【答案】C

【解析】本题主要考查Dijkstra算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。

执行Dijkstra算法过程中各步的状态表，故后续目标顶点依次为f，d，e。

8下列关于最小生成树的叙述中，正确的是（　　）。

Ⅰ．最小生成树的代价唯一

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

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

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

A．仅Ⅰ

B．仅Ⅱ

C．仅Ⅰ、Ⅲ

D．仅Ⅱ、Ⅳ

【答案】A

【解析】当图中存在相同权值的边时，其最小生成树可能是不唯一的，但最小生成树的代价一定是相同的，所以说法Ⅰ正确。从n个顶点的连通图中选取n－1条权值最小的边可能构成回路，所以说法Ⅱ错误。当某个顶点有权值相同的边，使用普里姆（Prim）算法从不同顶点开始得到的最小生成树并不一定相同，所以说法Ⅲ错误。当最小生成树不唯一时，使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树可能相同，也可能不同，所以说法Ⅳ错误。由此可得出正确答案。

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

题9图　3阶二叉树图

A．60

B．60，62

C．62，65

D．65

【答案】D

【解析】本题主要考查B树删除操作。即被删关键字所在的结点中的关键字个数等于[m/2]－1，而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于[m/2]－1，则需将其兄弟结点中最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B树如下，其最右叶结点所含的关键字是65。

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

Ⅰ．简单选择排序

Ⅱ．希尔排序

Ⅲ．快速排序

Ⅳ．堆排

V．二路归并排序

A．仅Ⅰ、Ⅲ、Ⅳ

B．仅Ⅰ、Ⅱ、Ⅲ

C．仅Ⅱ、Ⅲ、Ⅳ

D．仅Ⅲ、Ⅳ、Ⅴ

【答案】A

【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。

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

A．排序的总趟数

B．元素的移动次数

C．使用辅助空间的数量

D．元素之间的比较次数

【答案】D

【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。折半插入排序的时间复杂度仍为O（n²），所以两者之间的不同只可能是元素之间的比较次数。

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

A．55秒

B．60秒

C．65秒

D．70秒

【答案】D

【解析】CPU速度提高50%，即CPU性能提高比为1.5，改进之后的CPU运行时间＝90÷1.5＝60秒。I/O速度不变，仍维持10秒，所以运行基准程序A所耗费的时间为70秒。

13假定编译器规定int和short类型长度分别为32位和16位，执行下列C语言语句：unsigned short X＝65530；unsigned int y＝X：得到y的机器数为（　　）。

A．0000 7FFAH

B．0000 FFFAH

C．FFFF 7FFAH

D．FFFF FFFAH

【答案】B

【解析】X和y均为无符号数，其中X为16位，y为32位，将16位无符号数转化成32位无符号数，前面要补零。因为X＝65530＝FFFAH，所以y＝0000 FFFAH。

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

A．2¹²⁶－2¹⁰³

B．2¹²⁷－2¹⁰⁴

C．2¹²⁷－2¹⁰³

D．2¹²⁸－2¹⁰⁴

【答案】D

【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短浮点数的真值为：（－1）^S×1.f×2^{（E－127）}，S为符号位，E的取值为1～254，f为23位；故float类型能表示的最大整数是1.111^1×2（254－127）＝2¹²⁷×（2－2^－23）＝2¹²⁸－2¹⁰⁴。

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

若record变量的首地址为0xC008，则地址0xC008中内容及record.c的地址分别为（　　）。

A．0x00、0xC00D

B．0x00、0xC00E

C．0x11、0xC00D

D．0x11、0xC00E

【答案】D

【解析】32位整数a需要占4个字节，16位整数c需要占2个字节，而字符数据b占一个字节。a＝273，转换成十六进制是111H，采用小端方式存放数据，地址0xC008中的内容为11H。由于数据按边界对齐存储，地址0xC008～OxC00B中存放a，地址0xC00C中存放b，地址0xC00D中空闲，地址0xC00E～0xC00F中存放c。

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

A．信息可读可写，并且读、写速度一样快

B．存储元由MOS管组成，是一种半导体存储器

C．掉电后信息不丢失，是一种非易失性存储器

D．采用随机访问方式，可替代计算机外部存储器

【答案】A

【解析】考查闪存的特性，闪存是EEPROM的进一步发展，可读可写，用MOS管的浮栅上有无电荷来存储信息，它依然是ROM的一种，故写速度比读速度要慢不少。闪存是一种非易失性存储器，它采用随机访问方式，现在常见的SSD固态硬盘就是由flash芯片组成的，故答案为A。

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

【答案】C

【解析】Cache有4个行，2路组相联，即Cache被分成2组，每组2行。主存地址为0～1、4～5、8～9可映射到第0组Cache中，主存地址为2～3、6～7可映射到第1组Cache中。Cache初始为空，采用LRU替换算法，当访问主存的10个地址依次为0，4，8，2，0，6，8，6，4，8时，命中Cache的次数共有3次，分别发生在第7、8和10步时。

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

A．5位

B．6位

C．15位

D．33位

【答案】C

【解析】33个微命令分成5个互斥类（即5个字段），根据每个类中微命令的多少可以分别确定字段的长度为3、2、4、3、3位，又因为采用直接编码方式，所以它们之和3＋2＋4＋3＋3＝15也就是操作控制字段的位数。

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

A．20ns

B．40ns

C．50ns

D．80ns

【答案】C

【解析】总线的时钟频率为100MHz，则时钟周期为10ns。数据是128位，总线宽度是32位，所以需要4个时钟周期，而传输地址还需要一个周期，所以传输一个128位的数据至少需要5个时钟周期，所以至少需要10ns*5＝50ns。

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

A．可实现外设的即插即用和热插拔

B．可通过级联方式连接多台外设

C．是一种通信总线，可连接不同外设

D．同时可传输2位数据，数据传输率高

【答案】D

【解析】USB总线即通用串行总线，它的特点有：（1）即插即用；（2）热插拔；（3）有很强的链接能力能将所有外设链接起来，且不损失带宽；（4）有很好的可扩展性；（5）高速传输，速度可达480Mbps。所有A，B，C都符合USB总线的特点。对于选项D，USB是串行总线，不能同时传输两位数据，所以答案为D。

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

Ⅰ．I/O接口中的命令字

Ⅱ．I/O接口中的状态字

Ⅲ．中断类型号

A．仅Ⅰ、Ⅱ

B．仅Ⅰ、Ⅲ

C．仅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

【答案】D

【解析】在I/O总线的数据线上传输的信息包括I/O接口中的命令字、状态字以及真正的数据，而中断类型号也是通过数据线传输的。

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

Ⅰ．开关中断

Ⅱ．保存通用寄存器的内容

Ⅲ．形成中断服务程序入口地址并送PC

A．仅Ⅰ、Ⅱ

B．仅Ⅰ、Ⅲ

C．仅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

【答案】B

【解析】中断隐指令完成的操作有3个：①保存断点；②关中断；③引出中断服务程序（形成中断服务程序入口地址并送PC）。而保存通用寄存器内容的操作是由软件来实现，不是由中断隐指令实现的。

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

A．系统调用

B．外部中断

C．进程切换

D．缺页

【答案】C

【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设定了用户态和内核态（可以通过设置软、硬件标志位来实现），在用户态运行用户的程序，在内核运行系统的程序。所以，从选项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler，进程切换是dispather，这体现了现代操作系统策略与机制分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻），必定是在内核态（进程调度）发生的。

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

A．程序计数器

B．程序状态字寄存器

C．通用数据寄存器

D．通用地址寄存器

【答案】B

【解析】中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关，而子程序调用与正在运行的进程有关。中断是要打断处理器的正常工作次序，并要求其去处理某一事件的一种常用手段。因此，除了要保护当前程序的地址，计数器（指针）和数据寄存器以外，还需要保存程序状态字。子程序调用是与当前进程有关，是正在运行的程序有意安排执行的，这一类调用发生的时间以及位置具有确定性，处于同一个进程内，因此不需要保存程序状态字。所以中断处理和子程序调用不同的区别是中断处理程序必定会保存程序状态字寄存器。

25下列关于虚拟存储的叙述中，正确的是（　　）。

A．虚拟存储只能基于连续分配技术

B．虚拟存储只能基于非连续分配技术

C．虚拟存储容量只受外存容量的限制

D．虚拟存储容量只受内存容量的限制

【答案】D

【解析】所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术（例如缺页中断技术），将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中的A，B，C都是错误的，所以答案是D项。

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

A．用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序

B．用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序

C．用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序

D．用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序

【答案】A

【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程序中发起一次系统调用，操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备，即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。因此，I/O软件从上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。

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

题27表　资源分配情况表

A．P0，P2，P4，P1，P3

B．P1，P0，P3，P4，P2

C．P2，P1，P0，P3，P4

D．P3，P4，P2，P1，P0

【答案】D

【解析】典型的死锁避免算法、银行家算法的应用。本题的题型与2011年的27题相似。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到，P3，P4，P2，P1，P0运行是可以的。

本题也可以排除法，T₀时刻可用资源是R1，R2，R3分别为2，3，3，此时刻，P0需要R1，R2，R3分别为2，3，7，故排除A，P1需要R1，R2，R3分别为1，3，3，P2还需要资源R1，R2，R3分别为0，0，6，故C排除，P3需要R1，R2，R3分别为2，2，1。所以正确答案在B，D之间。看B选项，P1之后的可用资源R1，R2，R3分别变为6，3，6，而P0尚需资源2，3，7，故B方案行不通。因而最终答案只有D项。

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

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

Ⅱ．请求read系统调用会导致CPU从用户态切换到核心态；

Ⅲ．read系统调用的参数应包含文件的名称

A．仅Ⅰ、Ⅱ

B．仅Ⅰ、Ⅲ

C．仅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

【答案】A

【解析】对于Ⅰ，当所读文件的数据不再内存时，产生中断（缺页中断、缺段中断），原进程进入睡眠等待状态（阻塞状态），直到所需数据从外村调入内存后，将该进程唤醒，使其变为就绪状态。对于Ⅱ，read系统调用CPU将从用户态切换到核心态，从而获取操作系统提供的服务。对于Ⅲ，在操作系统中，要读一个文件首先要open系统调用将该文件打开。Open系统调用的参数需要包含文件的路径名与文件名，而read系统调用只需使用open返回的文件描述符，并不使用文件名作为参数。Read系统调用要求用户提供三个输入参数：①文件描述符；②buf缓冲区首址；③传送的字节数n。read系统调用的功能是试图从fd所指示的文件中读入n个字节的数据，并将它们送至由指针buf所指示的缓冲区中。

29一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达。它们的计算和I/O操作顺序如下：P1：计算60ms，I/O 80ms，计算20ms；P2：计算120ms，I/O 40ms，计算40ms若不考虑调度和切换时间，则完成两个作业需要的时间最少是（　　）。

A．240ms

B．260ms

C．340ms

D．360ms

【答案】B

【解析】考查处理系统的性能计算，由于P2比P1晚5ms到达，P1先占用CPU，根据P1和P2的执行过程，作业运行的甘特图如下所示，故答案为B。

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

A．在进程结束时能进行处理机调度

B．创建新进程后能进行处理机调度

C．在进程处于临界区时不能进行处理机调度

D．在系统调用完成并返回用户态时能进行处理机调度

【答案】C

【解析】对于A、B、D显然是可以进行处理机调度的，对于C，当进程处于临界区时，只要不破坏临界资源的使用规则，是不会影响处理机调度的，比如，通常访问临界资源可能是慢速的外设（如打印机），如果在进程访问打印机时，不能处理机调度，那么系统的性能将是非常低的。几种不进行处理机调度的情况如下：①在处理机中断的过程中；②进程在操作系统内核程序临界区中；③其他需要完全屏蔽中断的原子操作过程中。

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

A．不管系统是否支持线程，进程都是资源分配的基本单位

B．线程是资源分配的基本单位，进程是调度的基本单位

C．系统级线程和用户级线程的切换都需要内核的支持

D．同一进程中的各个线程拥有各自不同的地址空间

【答案】A

【解析】利用排除法来确定正确答案：“线程是资源分配的基本单位，进程是调度的基本单位”这句话说反了，明显错误。“系统级线程和用户级线程的切换都需要内核的支持”也不正确，因为用户级线程的切换由用户编写的Runtime System执行的，内核并不感知。“同一进程中的各个线程拥有各自不同的地址空间”明显错误，引入线程的目的就是为了同一进程的所有线程能共享进程的地址空间，故“不管系统是否支持线程，进程都是资源分配的基本单位”是正确的。

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

A．重排I/O请求次序

B．在一个磁盘上设置多个分区

C．预读和滞后写

D．优化文件物理块的分布

【答案】B

【解析】磁盘I/O性能主要是指其读写速度。相对而言，磁盘的I/O性能是计算机性能提高的一个瓶颈。“重排I/O请求次序”可以优化磁臂调度的算法，减少读写时间，故正确；“预读和滞后写”是利用内存作为磁盘的缓存，使得对磁盘的访问变为对内存的访问，也可以在总体上提高其性能；“优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间，也可以提高磁盘I/O性能，而磁盘分区仅在磁盘空间的组织上进行划分，对磁盘I/O性能的提升没有什么帮助，是不能改善磁盘设备I/O性能的，故答案为B。

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

A．PPP

B．IP

C．UDP

D．TCP

【答案】B

【解析】首先明确ICMP是网络层的协议，由于服务必须是下一层向上一层提供服务的，因此选项C项中的UDP和选项D项中的TCP属于传输层，在网络层上面，所以显然错误，而PPP协议是广域网数据链路层协议，直接为网络层，也就是IP层提供服务，ICMP协议是封装在网络层，因此PPP不能直接为ICMP提供服务，ICMP报文直接封装在IP分组中，故答案是B。

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

A．机械特性

B．功能特性

C．过程特性

D．电气特性

【答案】C

【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以分析描述事件先后顺序的就是规程，也就是过程特性，答案是C。

35以太网的MAC协议提供的是（　　）。

A．无连接不可靠服务

B．无连接可靠服务

C．有连接不可靠服务

D．有连接可靠服务

【答案】A

【解析】考查以太网MAC协议，考虑到局域网信道质量好，以太网采取了两项重要的措施以使通信更简洁：①采用无连接的工作方式；②不对发送的数据帧进行编号，也不要求对方发回确认。因此，以太网提供的服务是不可靠的服务，即尽最大努力交付，差错的纠正由高层完成。

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

A．5

B．4

C．3

D．237

【答案】B

【解析】GBN的工作原理如下图所示，本题求解的是发送一个帧到接收到这个帧的确认期间最多可以发送多少数据帧，要尽可能多发送帧，应以短的数据帧计算，注意帧的单位是字节，因此首先计算出发送一帧的时间t1＝128×8/16kbps＝64ms，故发送一帧到收到确认为止的总时间为；64＋270*2＋64＝668ms，这段时间总共可以发送668/64＝10.4（帧），为了保证发送帧序号和确认帧序号在此期间不重复，因此帧序号的比特数至少为4，答案为B

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

Ⅰ．运行路由协议，设置路由表；

Ⅱ．监测到拥塞时，合理丢弃IP分组；

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

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

A．仅Ⅲ、Ⅳ

B．仅Ⅰ、Ⅱ、Ⅲ

C．仅Ⅰ、Ⅱ、Ⅳ

D．Ⅰ、Ⅱ、Ⅲ、Ⅳ

【答案】C

【解析】路由器的主要功能是路由和转发，因此Ⅰ和Ⅳ是正确的，而针对Ⅱ和Ⅲ，可以从ICMP协议的差错控制出发，注意检测到拥塞时，合理丢弃IP分组，并回传ICMP源抑制报文，Ⅱ是正确的，而Ⅲ对收到的IP分组头进行差错校验，确保传输的IP分组不丢失，差错校验是正确的，但网络层不保证IP分组不丢失，也就是不可靠的，因此Ⅲ的说法错误，正确的说法仅Ⅰ、Ⅱ、Ⅳ，因此答案是C。

38ARP协议的功能是（　　）。

A．根据IP地址查询MAC地址

B．根据MAC地址查询IP地址

C．根据域名查询IP地址

D．根据IP地址查询域名

【答案】A

【解析】ARP协议是网络层协议，因此只能和传输层和数据链路层有关系，从这一点出发，域名是应用层的范畴，选项C和D是不正确的，根据MAC地址查询IP地址是RARP协议的功能，因此进而得出正确答案是A。

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

【答案】D

【解析】IPv4地址中的特殊地址，直接广播地址，也就是把主机位全部设置为1，这里77的二进制是01001101，子网掩码252的二进制是11111100，由此可以看到77的前6位作为子网位，后四位作为主机位，由此可以知道其广播地址是180.80.01001111.255，也就是180.80.79.255，因此答案是D。

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

题40图　电子邮件发送接收示意图

A．SMTP、SMTP、SMTP

B．POP3、SMTP、POP3

C．POP3、SMTP、SMTP

D．SMTP、SMTP、POP3

【答案】D

【解析】题中电子邮件的工作过程如下：

①用户1调用用户代理来编辑要发送的邮件，用户代理用SMTP将邮件传送给用户1的发送端邮件服务器。

②发送端邮件服务器也就是用户1的邮件服务器将邮件放入邮件缓存队列中，等待发送。

③运行在发送端邮件服务器的SMTP客户进程，发现在邮件缓存中有待发送的邮件，就向运行在接收端邮件服务器也就是用户2的邮件服务器的SMTP服务器进程发起TCP连接建立。当TCP连接建立后，SMTP客户进程开始向远程的SMTP服务器发送邮件。当所有的待发邮件发完了，SMTP就关闭所建立的TCP连接。

④运行在接收端邮件服务器中的SMTP服务器进程收到邮件后，将邮件放人收信人的用户邮箱中，等待收信人在他方便时进行读取。收信人在打算收信时，调用用户代理，使用POP协议将自己的邮件从接收端邮件服务器的用户邮箱中取回（如果邮箱中有来信的话）。

因此题中1，2，3阶段分别使用的应用层协议可以是SMTP，SMTP，POP3，因此答案是D。SMTP采用“推”的通信方式，用于用户代理向邮件服务器发送邮件、以及邮件服务器之间发送邮件。POP3采用“拉”的通信方式，用于用户从目的邮件服务器上读取邮件。

二、综合应用题：41～47小题。共70分。

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

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

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

解：（1）6个表的合并顺序如下图所示。

对应于合并过程的哈夫曼树

根据上图中的哈夫曼树，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个元素的最终表。

由于合并两个长度分别为m和n的有序表，最坏情况下需要比较m＋n－1次，故最坏情况下比较的总次数计算如下：

第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）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。

解析：本题具有较强的综合性，主要考查了构造哈夫曼树的算法思想和过程、归并排序的过程等。

42（13分）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如题42图所示。

题42图　存储映像示意图

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

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

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

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

解：（1）算法的基本设计思想：

①分别求出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语言算法描述如下：

（3）参考答案的时间复杂度为：O（m＋n）或O（max（m，n））。其中m、n分别为两个链表的长度。

43（11分）假定某计算机的CPU主频为80MHz，CPI为4，并且平均每条指令访存1.5次，主存与Cache之间交换的块大小为168，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，则该主存能提供的最大带宽是多少？

解：（1）平均每秒CPU执行的指令数为：80M/4＝20M，故MIPS数为20；

平均每秒Cache缺失的次数为：20M×1.5×（1－99%）＝300000；

当Cache缺失时，CPU访问主存，主存与Cache之间以块为单位传送数据，此时，主存带宽为：16B×300000/s＝4.8MB/s。在不考虑DMA传输的情况下，主存带宽至少达到4.8MB/s才能满足CPU的访存要求。

（2）平均每秒钟“缺页”异常次数为：300000×0.0005%＝1.5次；

因为存储器总线宽度为32位，所以，每传送32位数据，磁盘控制器发出一次DMA请求，故平均每秒磁盘DMA请求的次数至少为：1.5×4KB/4B＝1.5K＝1536。

（3）CPU和DMA控制器同时要求使用存储器总线时，DMA请求优先级更高；因为若DMA请求得不到及时响应，I/O传输数据可能会丢失。

（4）4体交叉存储模式能提供的最大带宽为：4×4B/50ns＝320MB/s。

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

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

该计算机采用5段流水方式执行指令，各流水段分别是取指（IF）、译码/读寄存器（ID）、执行/计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB），流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。

（1）若int型变量x的值为－513，存放在寄存器R1中，则执行指令“SHR R1”后，R1的内容是多少？（用十六进制表示）

（2）若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少？

（3）若高级语言程序中某赋值语句为x＝a＋b，x、a和b均为int型变量，它们的存储单元地址分别表示为[x]、[a]和[b]。该语句对应的指令序列及其在指令流水线中的执行过程如题44图所示。则这4条指令执行过程中，I₃的ID段和I₄的IF段被阻塞的原因各是什么？

题44图　指令序列及其执行过程示意图

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

解：（1）x的机器码为[x]_补＝1111 1101 1111B，即指令执行前（R1）＝FDFFH，右移1位后为1111 1110 1111 1111B，即指令执行后（R1）＝FEFFH。

（2）至少需要5＋（4－1）＝8个时钟周期数。

（3）I₃的ID段被阻塞的原因：因为I₃与I₁和I₂都存在数据相关，需等到I₁和I₂将结果写回寄存器后，I₃才能读寄存器内容，所以I₃的ID段被阻塞。

I₄的IF段被阻塞的原因：因为I₄的前一条指令I₃在ID段被阻塞，所以I₄的IF段被阻塞。

（4）x＝2*x＋a对应的指令序列为：

这5条指令在流水线中的执行过程如下图所示，执行x＝2*x＋a语句最少需要17个时钟周期。

45（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）该策略是否适合于时间局部性好的程序？说明理由。

解：（1）页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框，其对应的页框号为21。

（2）页框号为32。理由：因11＞10故发生第三轮扫描，页号为1、3的页框32、15在第二轮已处于空闲页框链表中，此刻1页又被重新访问，因此应被重新放回到驻留集中。其页框号为32。

（3）页框号为41。理由：因为第2页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。

（4）适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。

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

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

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

解：（1）文件系统存储空间共有块数2⁴²/2¹⁰＝2³²。为表示2³²个块号，索引表项占32/8＝4B，512B可存放2⁷个索引项，每个索引项对应一个磁盘块，故最大文件长度：2⁷×2¹⁰B＝2¹⁷B＝128KB。

（2）块号占6字节，块数占2字节的情形下，最大文件长度：2¹⁶×2¹⁰＋（504/6）×2¹⁰＝64MB＋84KB＝65620KB。

合理的起始块号和块数所占字节数分别为＜4，4＞（或＜0，8＞或＜1，7＞或＜2，6＞或＜3，5＞）。理由：块数占4B或以上，就可表示4TB大小的文件长度，达到文件系统的空间上限。

47（9分）主机H通过快速以太网连接Internet，IP地址为192.168.0.8，服务器S的IP地址为211.68.71.80。H与S使用TCP通信时，在H上捕获的其中5个IP分组如题47-a表所示。

题47-a表

请回答下列问题。

（1）题47-a表中的IP分组中，哪几个是由H发送的？哪几个完成了TCP连接建立过程？哪几个在通过快速以太网传输时进行了填充？

（2）根据题47-a表中的IP分组，分析S已经收到的应用层数据字节数是多少？

（3）若题47-a表中的某个IP分组在S发出时的前40字节如题47-b表所列，则该IP分组到达H时经过了多少个路由器？

题47-b表

注：IP分组头和TCP段头结构分别如题47-a图、题47-b图所示：

题47-a图　IP分组头结构

题47-b图　TCP段头结构

解：（1）由于题47-a表中1、3、4号分组的源IP地址（第13～16字节）均为192.168.0.8（coa80008H），所以1、3、4号分组是由H发送的。

题47-a表中1号分组封装的TCP段的FLAG为02H（即SYN＝1，ACK＝0），seq＝846b 41c5H，2号分组封装的TCP段的FLAG为12H（即SY＝1，ACK＝1），seq＝e059 9fefH，ack＝846b 41c6H，3号分组封装的TCP段的FLAG为10H（即ACK＝1），seq＝846b 41c6H，ack＝e059 9ff0H，所以1、2、3号分组完成了TCP连接建立过程。

由于快速以太网数据帧有效载荷的最小长度为46字节，表中3、5号分组的总长度为40（28H）字节，小于46字节，其余分组总长度均大于46字节，所以3、5号分组在通过快速以太网传输时进行了填充。

（2）由3号分组封装的TCP段可知，发送应用层数据初始序号为846b 41c6H，由5号分组封装的TCP段可知，ack为846b 41d6H，所以5号已经收到的应用层数据的字节数为846b 41d6H－846b 41c6H＝10H＝16B。

（3）由于S发出的IP分组的标识＝6811H，所以该分组所对应的是题47－a表中的5号分组。S发出的IP分组的TTL＝40H＝64，5号分组的TTL＝31H＝49，64－49＝15。所以，可以推断该IP分组到达H时经过了15个路由器。