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

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

1设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（　　）。

A．O（log₂n）

B．O（n）

C．O（nlog₂n）

D．O（n₂）

【答案】A

【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语句x＝2×x，设其执行时间为T（n），则有2^T（n）＜n/2即T（n）＜log₂（n/2）＝O（log₂n）。

2元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（　　）。

A．3

B．4

C．5

D．6

【答案】B

【解析】d首先出栈后的状态如下图所示。

此时可有以下4种操作：

（1）e进栈后出栈，出栈序列为decba。

（2）c出栈，e进栈后出栈，出栈序列为dceba。

（3）cb出栈，e进栈后出栈，出栈序列为dcbea。

（4）cba出栈，e进栈后出栈，出栈序列为dcbae。

3已知循环队列存储在一维数组A[0…n－1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（　　）。

A．0，0

B．0，n－1

C．n－1，0

D．n－1，n－1

【答案】B

【解析】题目要求队列非空时front和rear分别指向队头元素和队尾元素，若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则此时front和rear的值都为0。由于进队操作要执行（rear＋1）% n，则初始时front的值为0、rear的值为n－1。

4若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（　　）。

A．257

B．258

C．384

D．385

【答案】C

【解析】由n＝n₀＋n₁＋n₂和n₀＝n₂＋1可知，n＝2n₀－1＋n₁，即2n₀－1＋n₁＝768，显然n₁＝1，2n₀＝768，则n₀＝384，所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个性质：最后一个分支结点的序号为[768/2]，故非叶子结点数为384，而叶子结点的个数为768－384＝384。（［x］表示不大于x的最大整数，比如［3.14］＝3）。

5若一棵二叉树的前序遍历序列和后序遍历序列分别为l，2，3，4和4，3，2，1，则该二叉树的中序遍历序列不会是（　　）。

A．1，2，3，4

B．2，3，4，1

C．3，2，4，1

D．4，3，2，1

【答案】C

【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。

从左至右，这8棵二叉树的中序序列分别为：

（1）4，3，2，1，

（2）3，4，2，1

（3）2，4，3，1

（4）2，3，4，1

（5）1，4，3，2

（6）1，3，4，2

（7）1，2，4，3

（8）1，2，3，4

显然选项C的中序序列不会出现。

6已知一棵有2011个结点的树，其叶结点个数为ll6，该树对应的二叉树中无右孩子的结点个数是（　　）。

A．115

B．116

C．1895

D．1896

【答案】D

【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子），另外，树根结点转换成二叉树后也没有右孩子。题目中树的总结点数是2011，叶结点个数是116，则非终端结点个数是2011－116＝1895，则该树对应的二叉树中无右孩子的结点个数是1895＋1＝1896。

7对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（　　）。

A．95，22，91，24，94，71

B．92，20，91，34，88，35

C．21，89，77，29，36，38

D．12，25，71，68，33，34

【答案】A

【解析】各选项对应的查找过程如下图所示，从中看到选项B、C、D对应的查找树都是二叉排序树，只有选项A对应的查找树不是一棵二叉排序树，因为在以91为根的左子树中出现了比91大的结点94。

8下列关于图的叙述中，正确的是（　　）。

Ⅰ．回路是简单路径

Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间

Ⅲ．若有向图中存在拓扑序列，则该图不存在回路

A．仅Ⅱ

B．Ⅰ、Ⅱ

C．仅Ⅲ

D．Ⅰ、Ⅲ

【答案】C

【解析】第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，所以选项Ⅰ错误。稀疏图用邻接表表示比邻接矩阵节省存储空间，稠密图适合用邻接矩阵的存储表示，所以选项Ⅱ错误。利用拓扑排序算法可以判断图中是否存在回路，即在拓扑排序输出结束后所余下的顶点都有前驱，则说明了只得到了部分顶点的拓扑有序序列，图中存在回路。所以选项Ⅲ正确。

9为提高散列（Hash）表的查找效率，可以采用的正确措施是（　　）。

Ⅰ．增大装填（载）因子

Ⅱ．设计冲突（碰撞）少的散列函数

Ⅲ．处理冲突（碰撞）时避免产生聚集（堆积）现象

A．仅Ⅰ

B．仅Ⅱ

C．Ⅰ、Ⅱ

D．Ⅱ、Ⅲ

【答案】D

【解析】散列表的查找效率（比较次数）取决于：散列函数、处理冲突的方法和散列表的装填因子α。α标志着散列表的装满程度，通常情况下，α越小，发生冲突的可能性越小；反之，α越大，表示已填入的记录越多，再填入记录时，发生冲突的可能性越大。因此选项Ⅰ错误，越是增大装填因子，发生冲突的可能性就越大，查找效率也越低。选项Ⅱ正确。选项Ⅲ正确。采用合适的处理冲突的方法避免产生聚集现象，也将提高查找效率。例如，用拉链法解决冲突时不存在聚集现象，用线性探测法解决冲突时易引起聚集现象。

10为实现快速排序算法，待排序序列宜采用的存储方式是（　　）。

A．顺序存储

B．散列存储

C．链式存储

D．索引存储

【答案】A

【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。

11已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（　　）。

A．1

B．2

C．4

D．5

【答案】B

【解析】对堆插入或删除一个元素，有可能不满足堆的性质，堆被破坏，需要调整为新堆。

（1）为原堆，

（2）为插入18后，

（3）比较10与18，交换后，

（4）比较25与18，不交换，即为调整后的新的大根堆。

因此调整过程中元素之间进行的比较次数为2。

12下列选项中，描述浮点数操作速度指标的是（　　）。

A．MIPS

B．CPI

C．IPC

D．MFLOPS

【答案】D

【解析】MFLOPS（Million Floating-point Operations per Second）表示每秒执行多少百万次浮点运算，用来描述计算机的浮点运算速度，适用于衡量处理机的性能。

MIPS（Million Instructions per Second）表示每秒执行多少百万条指令。对于一个给定的程序，MIPS定义为

这里所说的指令一般是指加、减运算这类短指令。

CPI（Cycles per Instruction）就是每条指令执行所用的时钟周期数。由于不同指令的功能不同，造成指令执行时间不同，也即指令执行所用的时钟数不同，所以CPI是一个平均值。

IPC（Instructions per Cycle）每个时钟周期执行的指令数。

13float型数据通常用IEEE754单精度浮点数格式表示。若编译器将float型变量x分配在一个32位浮点寄存器FRl中，且x＝－8.25，则FR1的内容是（　　）。

A．C104 0000H

B．C242 0000H

C．C184 0000H

D．C1C2 0000H

【答案】A

【解析】首先将十进制数转换为二进制数－1000.01，接着把它写成规格化形式－1.00001×2³（按IEEE754标准），然后计算阶码的移码＝偏置值＋阶码真值＝127＋3＝130，最后短浮点数代码：数符位＝1，阶码＝1000 0010，尾数00 0010 0000 0000 0000 00000，写成十六进制为C104 0000H。选项D是一个很容易被误选的选项，其错误在于没有考虑IEEE754标准中隐含最高位1的情况，偏置值是128。

14下列各类存储器中，不采用随机存取方式的是（　　）。

A．EPROM

B．CDR0M

C．DRAM

D．SRAM

【答案】B

【解析】随机存取方式是指存储器的任何一个存储单元的内容都可以存取，而且存取时间与存储单元的物理位置无关。CDROM是只读的光盘存储器，采用串行存取方式而不是随机存取方式。

15某计算机存储器按字节编址，主存地址空间大小为64MB，现用4M×8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是（　　）。

A．22位

B．23位

C．25位

D．26位

【答案】D

【解析】虽然实际的主存储器（RAM区）只有32MB，但不排除还有ROM区，考虑到存储器扩展的需要，MAR应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB，所以MAR的位数至少需要26位。

16偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是（　　）。

A．间接寻址

B．基址寻址

C．相对寻址

D．变址寻址

【答案】A

【解析】在四种不同的寻址方式中，间接寻址按指令的形式地址从主存中取出操作数的有效地址，然后再按此有效地址从主存中读出操作数。其余三种寻址方式可以统称为偏移寻址。

17某机器有一个标志寄存器，其中有进位/借位标志CF、零标志ZF、符号标志SF和溢出标志OF，条件转移指令bgt（无符号整数比较大于时转移）的转移条件是（　　）。

A．CF＋OF＝0

B．SF＋ZF＝0

C．CF＋ZF＝0

D．CF＋SF＝0

【答案】C

【解析】判断无符号整数A＞B成立，满足的条件是结果不等于0，即零标志ZF＝0，且不发生进位，即进位/借位标志CF＝0。所以正确选项为C。其余选项中用到了符号标志SF和溢出标志OF，显然可以排除掉。

18下列给出的指令系统特点中，有利于实现指令流水线的是（　　）。

Ⅰ．指令格式规整且长度一致

Ⅱ．指令和数据按边界对齐存放

Ⅲ．只有Load/Store指令才能对操作数进行存储访问

A．仅Ⅰ、Ⅱ

B．仅Ⅱ、Ⅲ

C．仅Ⅰ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ

【答案】D

【解析】特点Ⅰ和Ⅲ都是RISC机的特征，而特点Ⅱ则有利于指令和数据的存放，所以以上三个特点都有利于实现指令流水线。

19假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是（　　）。

A．每个指令周期中CPU都至少访问内存一次

B．每个指令周期一定大于或等于一个CPU时钟周期

C．空操作指令的指令周期中任何寄存器的内容都不会被改变

D．当前程序在每条指令执行结束时都可能被外部中断打断

【答案】C

【解析】本题涉及的概念比较多。首先，如果不采用Cache和指令预取技术，每个指令周期中至少要访问内存一次，即从内存中取指令。其次，指令有的简单有的复杂，每个指令周期总大于或等于一个CPU时钟周期。第三，即使是空操作指令，在指令周期中程序计数器PC的内容也会改变（PC值加“1”），为取下一条指令做准备。第四，如果机器处于“开中断”状态，在每条指令执行结束时都可能被新的更高级的中断请求所打断。所以应选择选项C。

20在系统总线的数据线上，不可能传输的是（　　）。

A．指令

B．操作数

C．握手（应答）信号

D．中断类型号型号

【答案】C

【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。

21某计算机有五级中断L₄～L₀，中断屏蔽字为M₄M₃M₂M₁M₀，M_i＝1（0≤i≤4）表示对L_i级中断进行屏蔽。若中断响应优先级从高到低的顺序是L₀→L₁→L₂→L₃→L₄，且要求中断处理优先级从高到低的顺序为L₃→L₀→L₂→L₁→L₃，则L₁的中断处理程序中设置的中断屏蔽字是（　　）。

A．11110

B．01101

C．00011

D．01010

【答案】D

【解析】由于L₂的中断处理优先级下降，屏蔽字中需要3个0，所以可以将选项A、B排除掉。L₁需要对L₄、L₀、L₂开放，所以相应位应该为“0”，即为01010。

22某计算机处理器主频为50MHz，采用定时查询方式控制设备A的I/O，查询程序运行一次所用的时钟周期数至少为500。在设备A工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU用于设备A的I/O的时间占整个CPU时间的百分比至少是（　　）。

A．0.02%

B．0.05%

C．0.20%

D．0.50%

【答案】C

【解析】对于设备A，每秒中查询至少200次，每次查询至少500个时钟周期，总的时钟周期数为100000，又因为处理器主频为50MHz。所以CPU用于设备A的I/O的时间占整个CPU时间的百分比至少为100000/50＝0.20%。

23下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（　　）。

A．先来先服务

B．高响应比优先

C．时间片轮转

D．非抢占式短任务优先

【答案】B

【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，因此首先排除时间片轮转算法；因为作业调度算法中没有时间片轮转的算法。其次，因为问题提到短任务，则先来先服务的算法也可以排除了，它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个？我们可以通过分析得到，非抢占式短任务优先算法不能解决饥饿问题，因为当一个系统短任务源源不断到达是，长任务必然会得不到调度，产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法，并以高响应比值优先调度。这样，无论短任务或长任务，均可以得到调度，而且，较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有高响应比优先算法。

24下列选项中，在用户态执行的是（　　）。

A．命令解释程序

B．缺页处理程序

C．进程调度程序

D．时钟中断处理程序

【答案】A

【解析】题目是问用户态执行，可见是有关操作系统基本概念的问题。四个选项中，用户唯一能面对的是命令解释程序，缺页处理程序和时钟中断都属于中断，在核心态执行，而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口，可以运行在用户态，接受用户的命令操作控制。

25在支持多线程的系统中，进程P创建的若干个线程不能共享的是（　　）。

A．进程P的代码段

B．进程P中打开的文件

C．进程P的全局变量

D．进程P中某线程的栈指针

【答案】D

【解析】现代操作系统中，进程是资源分配的基本单位，线程是处理机调度的基本单位。因此，进程是线程运行的容器，本题中，进程的代码段，进程打开的文件，进程的全局变量等都是进程的资源，唯有进程中某线程的栈指针是属于线程的，那么，属于进程的资源可以共享，属于线程的栈是独享的，不能共享。

26用户程序发出磁盘I/O请求后，系统的正确处理流程是（　　）。

A．用户程序→系统调用处理程序→中断处理程序→设备驱动程序

B．用户程序→系统调用处理程序→设备驱动程序→中断处理程序

C．用户程序→设备驱动程序→系统调用处理程序→中断处理程序

D．用户程序→设备驱动程序→中断处理程序→系统调用处理程序

【答案】B

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

27某时刻进程的资源使用情况如下表所示

此时的安全序列是（　　）。

A．P1，P2，P3，P4

B．P1，P3，P2，P4

C．P1，P4，P3，P2

D．不存在

【答案】D

【解析】典型的死锁避免算法，银行家算法的应用。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到，经过P1，P4的运行以后，可用资源是2，2，1，而P2，P3所需资源分别是1，3，2和1，3，1。所以剩余资源已经不够P2或P3的分配，亦即找不到能够安全运行的序列，因此此时是处于不安全状态，所以不存在这样的安全序列。

28在缺页处理过程中，操作系统执行的操作可能是（　　）。

Ⅰ．修改页表

Ⅱ．磁盘I/O

Ⅲ．分配页框

A．仅Ⅰ、Ⅱ

B．仅Ⅱ

C．仅Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

【答案】D

【解析】首先我们要考虑的是，为什么会发生缺页中断？当然，在一个采用虚拟存储管理技术的系统中，程序是部分装入的，还有部分是处于外存上的，因此，当需要访问那部分位于外存上的代码或数据时，系统会产生缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存，据此，缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页（若没有空闲的页面则要调用页面置换程序找到一处页面，将该页面的内容处理掉，或回写磁盘，或覆盖掉，然后将此页分配给需要访问的页），分配妥当以后，缺页中断处理程序调用设备驱动程序做磁盘I/O，将位于外存（一般是磁盘）上的页面调入内存，调入后转身去修改页表，将页表中代表该页是否在内存的标志位（一般称为存在位或有效位、在位位）修改为“真”，将物理页框号填入相应位置，若必要还需修改其它相关表项等。完成上述任务后，缺页中断处理程序返回，继续程序的执行。从上述过程可以看出，涉及的相关处理非常多，因此，答案就显而易见了。

29当系统发生抖动（thrashing）时，可以采取的有效措施是（　　）。

Ⅰ．撤销部分进程

Ⅱ．增加磁盘交换区的容量

Ⅲ．提高用户进程的优先级

A．仅Ⅰ

B．仅Ⅱ

C．仅Ⅲ

D．仅Ⅰ、Ⅱ

【答案】A

【解析】“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页又很快被访问，必须换入，如此频繁地置换页面，以致操作系统的大部分时间都花在页面置换上，引起系统性能下降甚至崩溃。引起系统抖动现象的原因是对换的信息量过大，内存容量不足，置换算法选择不当。所以解决的办法就是降低交换页面数量，加大内存容量，改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统来讲是不可能的，只能增加内存容量。增加内存容量可以是直接添加物理内存（大型计算机都可以在不关机的情况下增加物理内存条），或者，降低进程数量，相对地增加内存。而增加交换区容量并不能解决物理内存不足的问题，提高用户进程的优先级会使系统的状态更加恶化。

30在虚拟存储管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（　　）。

A．编辑

B．编译

C．链接

D．装载

【答案】B

【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本，不涉及到任何与计算机运行相关的事；编译是由编译程序将用户源代码编译成若干个目标模块，源地址编译成目标程序时，会形成逻辑地址；链接是由链接程序将编译后形成的一组目标模块，以及所需库函数链接，形成完整的装入模块；装入是由装入程序将装入模块装入内存。

31某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读人缓冲区的时间为100μs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。在单缓冲区和双缓冲区结构下，读人并分析完该文件的时间分别是（　　）。

A．1500μs、1000μs

B．1550μs、1100μs

C．1550μs、1550μs

D．2000μs、2000Μs

【答案】B

【解析】这是一个简单的缓冲区的问题。由于缓冲区的访问是互斥的，所以对单一缓冲区，从磁盘写入和读出到用户区的操作必须串行执行，也就是要保证互斥操作。而CPU对数据的分析与从用户区读数据也是需要互斥操作，但是CPU分析与从磁盘写入缓冲区的操作可以并行。从本题看，由于分析所用的时间小于从磁盘写入缓冲区的时间，因此，CPU会空闲。单缓冲区的总时间＝（磁盘写入缓冲区时间＋缓冲区读出时间）×10＋CPU处理最后一块数据的时间＝（100＋50）×10＋50＝1550μs。当采用双缓冲区时，每块缓冲区的操作也必须满足互斥操作，但是，对两块缓冲区的操作却可以并行，所以，当第一个缓冲区写满以后，磁盘紧接着写另一个缓冲区，同时，前一个已经满了的缓冲区被读出到用户区，并立即进行CPU的数据分析。读出操作和数据分析必须互斥进行，故从时间上看，当数据被读出并分析后，恰好另一个缓冲区也写满了，可以立即进行读出数据到用户区并进行数据分析。两块缓冲区交替进行读写，直到数据分析完毕，因此，总时间＝（磁盘写入缓冲区时间）×10＋读出最后一块数据时间＋CPU分析最后一块数据时间＝（100）×10＋50＋50＝1100μs。

32有两个并发执行的进程P1和P2，共享初值为l的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。

两个操作完成后，2的值（　　）。

A．可能为－1或3

B．只能为1

C．可能为0、1或2

D．可能为－1、0、1或2

【答案】C

【解析】这是在数据库中常有的操作。为保证数据的正确，避免产生错误，系统必须保证数据的同步。而保证数据的同步一般采取加锁的方法，让进程P1和P2互斥访问共享变量x。当然用信号量和P、V操作也是可以保证互斥操作，达到数据同步的。本例中，由于没有采取保证数据同步的相应措施，则最后结果就会出现差错。例如，当正常情况下，进程P1和P2先后对x操作，可以看到x值的变化为初始1→2→1的过程，若P2，P1先后操作，则x值的变化为初始1→0→1，这是正确的。若考虑一种并发的情况，进程P1和P2先后执行了取数load的操作，它们得到的x值均为1，运算后，P1和P2的x值分别为2和0，此时要看哪个进程后执行存数store的操作了，哪个进程后操作，结果就是那个进程的x值，所以可能的结果为0或2，加上前面正确的x值1，则可能的结果就有3种了。

33TCP/IP参考模型的网络层提供的是（　　）。

A．无连接不可靠的数据报服务

B．无连接可靠的数据报服务

C．有连接不可靠的虚电路服务

D．有连接可靠的虚电路服务

【答案】A

【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务，因此答案是A。

34若某通信链路的数据传输速率为2400bps，采用4相位调制，则该链路的波特率是（　　）。

A．600波特

B．1200波特

C．4800波特

D．9600波特

【答案】B

【解析】注意无噪声下的码元速率极限值B与信道带宽H的关系：B＝2×H（Baud），而奈奎斯特公式——无噪信道传输能力公式是C＝2×H×log₂N（bps），N为一个码元所取的离散值个数。从而可以得到波特率与数据传输速率的关系，即C＝B×log₂N（bps），在本题中数据传输速率C＝2400，N＝4，因此波特率是1200，答案是B。

35数据链路层采用选择重传协议（SR）传输数据，发送方已发送了0H3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是（　　）。

A．1

B．2

C．3

D．4

【答案】B

【解析】在选择重传协议中，接收方逐个地确认正确接收的分组，不管接收到的分组是否有序，只要正确接收就发送选择ACK分组进行确认。因此选择重传不支持累积确认，要特别注意其与GBN协议的区别。本题收到l号帧的确认，说明1号帧正确接收，0和2号帧依次超时，因此必须重传，然而3号帧尚未超时，是否正确接收未知，故不用重传，因此必须重传0和2号帧，答案是B。

36下列选项中，对正确接收到的数据帧进行确认的MAC协议是（　　）。

A．CSMA

B．CDMA

C．CSMA/CD

D．CSMA/CA

【答案】D

【解析】可采用排除法。CDMA是码分多址复用，是物理层的内容；CSMA/CD即带冲突检测的载波监听多路访问，接收方并不需要确认；CSMA/CD是CSMA的加强版，故CSMA也无确定；CSMA/CD是802.11中的协议，其利用ACK信号来避免冲突的发生，也就是说，只有当客户端收到网络上返回的ACK信号后才确认送出的数据已经正确到达目的地址，因此答案是D。

37某网络拓扑如下图所示，路由器Rl只有到达子网l92.168.1.0/24的路由。为使R1可以将IP分组正确地路由到图中所有子网，则在R1中需要增加一条路由（目的网络，子网掩码，下一跳）是（　　）。

A．192.168.2.0，255.255.255.128，192.168.1.1

B．192.168.2.0，255.255.255.0，192.168.1.1

C．192.168.2.0，255.255.255.128，192.168.1.2

D．192.168.2.0，255.255.255.0，192.168.1.2

【答案】D

【解析】首先从题目给出的路由表项可以确定下一跳肯定是路由器R1直接相连的R2的地址，因此是192.168.1.2，此时可以排除A和B两个选项了。进而分析路由器R2所连接的网络特点，注意其连接了2个网络分别是l92.168.2.0/25和192.168.2.128/25，但答案选项中只有一条信息，因此这里用到了超网的概念，超网是与子网类似的概念——IP地址根据子网掩码被分为独立的网络地址和主机地址。但是，与子网把大网络分成若干小网络相反，它是把一些小网络组合成一个大网络——超网，这里192.168.2.00000000/25和192.168.2.10000000/25前24位是相同的，因此所构成的超网就是l92.168.2.0/24，那么子网掩码就是255.255.255.00000000即255.255.255.0，因此答案是D。

38在子网l92.168.4.0/30中，能接收目的地址为l92.168.4.3的IP分组的最大主机数是（　　）。

A．0

B．1

C．2

D．4

【答案】C

【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址，本题中由于子网的比特数是30，因此用于主机的只有2位，即O0，01，10，11，有效主机地址是2个，这里192.168.4.3显然是其广播地址，因此答案是C。

39主机甲向主机乙发送一个（SYN一1，seq一11220）的TCP段，期望与主机乙建立TCP连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP段可能是（　　）。

A．（SYN＝0，ACK＝0，seq＝11221，ack＝11221）

B．（SYN＝1，ACK＝1，seq＝11220，ack＝11220）

C．（SYN＝1，ACK＝1，seq＝11221，ack＝11221）

D．（SYN＝0，ACK＝0，seq＝11220，ack＝11220）

【答案】C

【解析】TCP是面向连接的，所谓面向连接，就是当计算机双方通信时必需先建立连接，然后数据传送，最后拆除三个过程，也就是客户主动打开TCP传输，服务器被动打开。第一次握手：客户发送SYN＝1，seq＝x给服务器，即客户的TCP向服务器发出连接请求报文段，其首部中的同步位SYN＝1，并选择序号seq＝x，表明传送数据时的第一个数据字节的序号是x。第二次握手：服务器发送SYN＝1，ACK＝l，seq＝y，ack＝x＋1给客户，即服务器的TCP收到连接请求报文段后，如同意则发回确认。服务器在确认报文段中应使SYN＝1，使ACK＝1，其确认号ack＝x＋1，自己选择的序号seq＝y。第三次握手：客户发送ACK＝1，seq＝x＋1，ack＝y＋1给服务器，即客户收到此报文段后向服务器给出确认，其ACK＝1，确认号ack＝y＋1。客户的TCP通知上层应用进程，连接已经建立。服务器的TCP收到主机客户的确认后，也通知其上层应用进程：TCP连接已经建立。因此，本题中x＝11220，y是主机乙自动选取的序号，可以与x相同，也可以不相同，从而主机乙所发出的TCP段应该是SYN＝1，ACK＝1，seq＝y，ack＝x＋1，即SYN＝1，ACK＝1，seq＝y，ack＝11221，从而答案是C。

40主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了3个连续的TCP段，分别包含300字节、400字节和500字节的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是（　　）。

A．300

B．500

C．1200

D．1400

【答案】B

【解析】本题考查TCP的确认机制，TCP首部的序号字段是指本报文所发送的数据的第一个字节的序号。本题中首先根据第3个段的序号为900，可以得出第2个段的序号为500，第l个段的序号为200，这里主机乙仅正确接收了第1段和第3段，这意味着第2段丢失，需要超时重传，因此主机乙发送给主机甲的确认序号，也就是此时接收端期望收到的下一个数据包中第一个字节的序号应该是第二段的第一个字节的序号，也就是500，因此答案是B。

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

41（8分）已知有6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。

要求：

（1）写出图G的邻接矩阵A。

（2）画出有向带权图G。

（3）求图G的关键路径，并计算该关键路径的长度。

解：（1）由题可以画出待定上三角矩阵的结构图如下（图中？为待定元素）：

可以看出，第一行至第五行主对角线上方的元素分别为5，4，3，2，1个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：

将各元素填入各行即得邻接矩阵：

（2）根据第一步所得矩阵A容易做出有向带权图G，如下：

（3）下图中粗线箭头所标识的4个活动组成图G的关键路径。

由上图容易求得图的关键路径长度为：4＋5＋4＋3＝16。

42（15分）一个长度为L（L≥1）的升序序列S，处在第「L/2」个位置的数为S的中位数。例如，若序列S1＝（11，13，15，17，19），则Sl的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2＝（2，4，6，8，20），则Sl和S2的中位数是11。现有两个等长升序序列A和B，试设计一个时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：

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

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

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

解：（1）算法的基本设计思想：分别求两个升序序列A和B的中位数，设为a和b。

①若a＝b，则a或b即为所求的中位数。

②否则，若a＜b，中位数只能出现（a，b）范围内，舍弃a所在序列A的较小一半，同时舍弃b所在序列B的较大一半。若a＞b，中位数只能出现（b，a）范围内，舍弃b所在序列B的较小一半，同时舍弃a所在序列A的较大一半。

③在保留的两个升序序列中求出新的中位数a和b，重复上述过程，直到两个序列中只含一个元素时为止，则较小者即为所求的中位数。

（2）用C语言算法描述如下：

（3）说明算法的复杂性：算法的时间复杂度、空间复杂度分别是O（1og₂n）和O（1）。

43（11分）假定在一个8位字长的计算机中运行下列C程序段：

若编译器编译时将8个8位寄存器Rl～R8分别分配给变量x、y、m、n、z1、z2、k1和k2。请回答下列问题。（提示：带符号整数用补码表示）

（1）执行上述程序段后，寄存器R1、R5和R6的内容分别是什么？（用十六进制表示）

（2）执行上述程序段后，变量m和kl的值分别是多少？（用十进制表示）

（3）上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器及辅助电路实现？简述理由。

（4）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出？上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？

解：（1）无符号整数运算，（R1）＝x＝134＝1000 0110B＝86H、（R5）＝x－y＝246＝1001 0000B＝90H、（R6）＝x＋y＝0111 1100B＝7CH。

（2）m的机器数与x的机器数相同为86H＝1000 0110B，解释为带符号整数（用补码表示）时，其值为－111 1010B＝－112；同理k1＝（m－n）＝（x－y）＝90H＝1001 0000B，解释为带符号整数（用补码表示）时，其值为－111 1010B＝－112；

（3）四种运算可以利用同一个加法器及辅助电路实现，n位加法器实现的是模2ⁿ无符号整数加法运算。对于无符号整数a和b，a＋b可以直接用加法器实现，而a－b＝a＋[－b]_补（mod2ⁿ）实现；对于带符号整数用补码表示，补码加减运算公式为：[a＋b] _补＝[a] _补＋[b] _补（mod2ⁿ），[a－b] _补＝[a] _补＋[－b] _补（mod2ⁿ），所以四种运算都可在n位加法器中实现。

（4）判断溢出的方法有3种：一位符号位、进位位和双符号位。上述程序段中只有int k2＝m＋n语句会发生溢出，因为2个带符号整数均为负数，它们相加之后，结果小于8位二进制所能表示的最小负数。

44（12分）某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB，主存（物理）地址空间大小为1MB，页面大小为4KB；Cache采用直接映射方式，共8行；主存与Cache之间交换的块大小为32B。系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题44-a图、题44-b所示，图中页框号及标记字段的内容为十六进制形式。

题44-a图　页表的部分内容

题44-b图　Cache的部分内容

请回答下列问题。

（1）虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号（物理页号）？

（2）使用物理地址访问Cache时，物理地址应划分哪几个字段？要求说明每个字段的位数及在物理地址中的位置。

（3）虚拟地址001C60H所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否Cache命中？要求说明理由。

（4）假定为该机配置一个4路组相联的TLB，该TLB共可存放8个页表项，若其当前内容（十六进制）如题44-c图所示，则此时虚拟地址024BACH所在的页面是否在主存中？要求说明理由。

题44-c图　TLB的部分内容

解：（1）由于页面大小为4KB，页内地址需要12位，所以虚拟地址24位，其中虚页号占12位；物理地址20位，其中页框号（实页号）占8位。

（2）主存物理地址20位，从左至右应划分3个字段：标记字段、块号字段、块内地址字段。其中标记12位，块号3位，块内地址5位。

（3）虚拟地址001C60H＝0000 0000 0001 1100 0110 0000B，该虚拟地址的虚页号为001H，查页表可以发现，虚页号1对应的有效位为“1”，表明此页在主存中，页框号为04H，对应的20位物理地址是04C60H＝0000 0100 1100 0110 0000B。

访问该地址时，Cache不命中，因为Cache采用直接映射方式，对应的物理地址应该映射到Cache的第3行中，其有效位为1，标记值105H≠04CH（物理地址高12位），故访问该地址时Cache不命中。

（4）虚拟地址024BACH＝0000 0010 0100 1011 1010 1100B，虚页号为024H，TLB中存放8个页表项，采用4路组相联，即TLB分为2组，每组4个页表项。12位虚页号字段中最低位作为组索引，其余11位为标记位。现在最低位为0，表明选择第0组，11位的标记为012H，根据标记可以知道TLB命中，所在的页面在主存中。因为如果在TLB中查到了页表项，即TLB命中，说明所在页一定命中

45（8分）某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：

请添加必要的信号量和P、V（或wait（）、signal（））操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

解：（1）互斥资源：取机号，故设一个互斥信号量mutex。

（2）同步问题：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客为其服务。空座位的有、无影响等待顾客数量，顾客的有、无决定两营业员是否能开始服务。另外，顾客获得空座位后，需要等待叫号和被服务，顾客与营业员就服务何时开始有同步关系。设信号量teller，customer和mutex初值分别为0，0和1，设waiting为整型量，表示排队的储户数量，其初始为0，表示顾客初始时为0，最大不超过10（10把座椅），各进程的具体实现如下所示：

46．（7分）某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。

（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。为定位文件数据块。需要在FCB中设计哪些相关描述字段？

（2）为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。

解：根据题目所给条件，文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储，这与一次刻录光盘的存储方式相似。对于这样的系统，因为不需要随时添加或删除文件的内容，所以一次写入的文件的大小是固定不变的，也是可预知的，而连续存放文件的方式就有其优点。这种方式只需要知道文件的起始地址和文件的大小，便可以通过计算的方法找到文件的任何位置。文件若需要修改，则原文件作废，修改以后的文件以新文件的形式重新写入，不会产生存储碎片，高效，高利用率。所以，如下作答。

（1） 连续的数据块组织方式更合适，因为文件的数据一次性写入磁盘，已写入的文件不可修改，但是可以多次创建新文件，我们得知该文件系统是不能修改原文件的，只能将修改后的文件按新文件来存储。不需要随时添加或删除文件的内容，所以一次写入的文件的大小是固定不变的，也是可预知的。这样，只需要知道文件的起始地址和文件的大小，便可以通过计算的方法访问文件的任意位置。

为定位文件数据块。需要在FCB中设计相关描述字段有：＜起始块号，块数＞或者＜起始块号，结束块号＞。

（2）将所有的FCB集中存放，文件数据集中存放。这样在随机查找文件名时，只需访问FCB对应的块，可减少磁头移动和磁盘I/O访问次数。

47（9分）某主机的MAC地址为00-15-C5-Cl-5E-28，IP地址为10.2.128.100（私有地址）。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80个字节的十六进制及ASCII码内容。

题47-a图　网络拓扑

题47-b图　以太网数据帧（前80字节）

请参考图中的数据回答以下问题。

（1）Web服务器的IP地址是什么？该主机的默认网关的MAC地址是什么？

（2）该主机在构造题47-b图的数据帧时，使用什么协议确定目的MAC地址？封装该协议请求报文的以太网帧的目的MAC地址是什么？

（3）假设HTTP/1.1协议以持续的非流水线方式工作，以此请求一响应时间为RTT，rfc.html页面引用了5个JPEG小图像，则从发出题47-b图中的Web请求开始到浏览器收到全部内容为止，需要多少个RTT？

（4）该帧所封装的IP分组经过路由器R转发时，需修改IP分组头中的哪些字段？注：以太网数据帧结构和IP分组头结构分别如题47-c图、题47-d图所示。

题47-c图　以太网帧结构

题47-d图　IP分组头结构

解：（1）以太网的数据部分是IP数据报，只要找出相应字段所在的字节即可。根据图47-c可知以太网头部有6＋6＋2＝14字节，根据图47-d可知IP地址有16字节，从图47-b第一个字节开始数14＋16＝30字节，得目的IP地址为40.aa.62.20即64.170.98.32。而以太网帧的前6字节00-21-27-21-51-ee是目的MAC地址，即为主机的默认网关10.2.128.1端口的MAC地址。

（2）该主机在构造题47-b图的数据帧时，使用ARP协议确定目的MAC地址。封装该协议请求报文的以太网帧的目的MAC地址是广播地址即FF-FF-FF-FF-FF-FF。

（3）假设HTTP/1.1协议以持续的非流水线方式工作，客户机在收到前一个请求的响应后才能发出下一个请求。第一个RTT用于请求Web页面，客户机收到第一个请求的响应后，每访问一次对象就需一个RTT。rfc.html页面引用了5个JPEG小图像，则从发出题47-b图中的Web请求开始到浏览开始到浏览器受到全部内容为止，故共需1＋5＝6个RTT后浏览器收到全部内容。

（4）私有地址要和Internet上的主机通信时，须由NAT路由器进行网络地址转换，转换为一个全球IP地址。IP数据报没经过一个路由器，生存时间TTL值就减少1，并重新计算首部校验和。所以需修改的信息有源IP地址，头部校验和，生存时间。