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

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

1若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（　　）。

A．d，c，e，b，f，a

B．c，b，d，a，e，f

C．b，c，a，e，f，d

D．a，f，e，d，c，b

【答案】D

【解析】4个选项所给序列的进、出栈操作序列分别为：

选项A：Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop

选项B：Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop

选项C：Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop

选项D：Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop

按照题目要求，不允许连续三次进行退栈操作，所以选项D所给序列为不可能得到的出栈顺序。

2某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是（　　）。

A．b，a，c，d，e

B．d，b，a，c，e

C．d，b，c，a，e

D．e，c，b，a，d

【答案】C

【解析】根据题意，队列两端都可以输入数据元素，但是只能在一端输出数据元素，这种队列为输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队，从而得出不可能的情况。

假设L代表从左端入队，R代表从右端入队，出队都是从左端L出。四个选项所给序列的进队操作序列分别为：

选项A：aL（或aR），bL，cR，dR，eR

选项B：aL（或aR），bL，cR，dL，eR

选项C：不可能出现

选项D：aL（或aR），bL，cL，dR，eL

3下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（　　）。

【答案】D

【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息，解题思路较简单。题中所给二叉树的后序序列为dbca。结点d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b；结点b无左子树，左链域指向其前驱结点d；结点c无左子树，左链域指向其前驱结点b，无右子树，右链域指向其后继结点a。所以正确选项为D。

4在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（　　）。

A．13、48

B．24、48

C．24、53

D．24、90

【答案】C

【解析】题目中，插入48以后，树根结点的平衡因子由－1变为－2，失去平衡。这属于RL（先右后左）型平衡旋转，需做两次（先右旋后左旋转）旋转操作。过程如下图所示：

显然，在调整后的新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是24，53。

5在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（　　）。

A．41

B．82

C．113

D．122

【答案】B

【解析】根据二叉树的性质3的推广公式：N₀＝l＋N₂＋2N₃＋…＋（m－1）N_m可直接在将数据带入公式，即N₀＝l＋N₂＋2N₃＋3N4＝l＋1×1＋2×10＋3×20＝82。树T的叶子结点的个数是82。如果考生不能熟练掌握二叉树的性质3的推广公式，得到本题的正确答案将费时费力。因此，需要熟练掌握二叉树的性质及推广。

6对n（n≥2）个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是（　　）。

A．该树一定是一棵完全二叉树

B．树中一定没有度为1的结点

C．树中两个权值最小的结点一定是兄弟结点

D．树中任一非叶结点的权值一定不小于下一层任一结点的权值

【答案】A

【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A错误；哈夫曼树中没有度为1的结点，选项B正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C正确；哈夫曼树中任一非叶结点P的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P的左右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q，那么结点Q与其兄弟结点中权值较小的一个应该与结点P作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。

7若无向图G＝（V，E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（　　）。

A．6

B．15

C．16

D．21

【答案】C

【解析】要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通。首先需要图G的任意6个结点构成完全连通子图G₁，需n（n－l）/2＝6×（6—1）/2＝15条边，然后再添加一条边将第7个结点与G₁连接起来，共需l6条边。本题非常容易错误地选择选项A，主要原因是对“保证图G在任何情况下都是连通的”的理解，分析选项A，在图G中，具有7个顶点6条边并不能保证其一定是连通图，即有n－1条边的图不一定是连通图。分析选项D，图G有7个顶点21条边，那么图G一定是无向完全图，无向完全图能保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。

8对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（　　）。

A．4

B．3

C．2

D．1

【答案】B

【解析】拓扑排序的步骤为：

（1）在有向图中选一个没有前驱的顶点并且输出它；

（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑排序序列，分别为abced，abecd，aebcd。

9已知一个长度为l6的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多是（　　）。

A．4

B．5

C．6

D．7

【答案】B

【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（log₂n）＋1，在本题中，n＝l6，故比较次数最多为5。

10采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（　　）。

A．递归次数与初始数据的排列次序无关

B．每次划分后，先处理较长的分区可以减少递归次数

C．每次划分后，先处理较短的分区可以减少递归次数

D．递归次数与每次划分后得到的分区的处理顺序无关

【答案】D

【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深度一致。例如：待排序列{48，62，35，77，55，14，35，98），采用快速排序方法，其对应递归调用过程的二叉树如下图所示。

在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。

11对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下：

第一趟：2，12，16，5，10，88

第二趟：2，12，5，10，16，88

第三趟：2，5，10，12，16，88

则采用的排序方法可能是（　　）。

A．起泡排序

B．希尔排序

C．归并排序

D．基数排序

【答案】A

【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”，待序列中的记录“基本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐增多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序列合并为一个大的有序序列，然后“逐趟归并”，直至整个序列为有序为止。基数排序是分配排序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。本题中，很容易看出大值逐渐“沉底”，显然使用的是起泡排序法。

12下列选项中，能缩短程序执行时间的措施是（　　）。

Ⅰ．提高CPU时钟频率

Ⅱ．优化数据通路结构

Ⅲ．对程序进行编译优化

A．Ⅰ、Ⅱ

B．Ⅰ、Ⅲ

C．Ⅱ、Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

【答案】D

【解析】一般说来，CPU时钟频率（主频）越高，CPU的速度就越快；优化数据通路结构，可以有效提高计算机系统的吞吐量；编译优化可得到更优的指令序列。所以Ⅰ、Ⅱ、Ⅲ都是有效措施。

13假定有4个整数用8位补码分别表示为r₁＝FEH，r₂＝F2H，r₃＝90H，r₄＝F8H。若将运算结果存放在一个8位寄存器中，则下列运算会发生溢出的是（　　）。

A．r₁×r₂

B．r₂×r₃

C．r₁×r₄

D．r₂×r₄

【答案】B

【解析】用补码表示时8位寄存器所能表示的整数范围为－128～＋127。现在4个整数都是负数，r₁＝－2，r₂＝－14，r₃＝－112，r₄＝－8，在4个选项中，只有r₂×r₃＝1568，结果溢出，其余3个算式结果都未超过127，不发生溢出。

14假定变量i、f和d的数据类型分为int、float和double（int用补码表示，float和double分别用IEEE754单精度和双精度浮点数格式表示），已知i＝785，f＝1.5678e3，d＝1.5e100。若在32位机器中执行下列关系表达式，则结果为“真”的是（　　）。

Ⅰ．i＝＝（int）（float）i

Ⅱ．f＝＝（float）（int）f

Ⅲ．f＝＝（float）（double）f

IV．（d＋f）－d＝＝f

A．Ⅰ、Ⅱ

B．Ⅰ、Ⅲ

C．Ⅱ、Ⅲ

D．Ⅲ、Ⅳ

【答案】B

【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。Ⅱ中，f的数据类型从float转换为int时，小数点后面4位会丢失，故Ⅱ的结果不为真；Ⅳ中，d＋f时需要对阶，对阶后f的尾数有效位被舍去而变为0，故d＋f仍然为d，再减去d后结果为0，故Ⅳ的结果也不为真。Ⅰ和Ⅱ进行数据类型的转换的时候并没有改变其值。

15假定用若干个2K×4位的芯片组成一个8K×8位的存储器，则地址0B1FH所在芯片的最小地址是（　　）。

A．0000H

B．0600H

C．0700H

D．0800H

【答案】D

【解析】由若干芯片构成存储器，采用字和位同时扩展方法。8片2K×4位的芯片分成4组，每组2个芯片，各组芯片的地址分配分别为：第l组，0000H～07FFH；第2组，0800H～0FFFH；第3组，l000H～17FFH；第4组，l800H～1FFFH。地址0BIFH处于第2组内，其芯片的最小地址为0800H。

16下列有关RAM和ROM的叙述中，正确的是（　　）。

Ⅰ．RAM是易失性存储器，ROM是非易失性存储器

Ⅱ．RAM和ROM都采用随机存取方式进行信息访问

Ⅲ．RAM和ROM都可用作Cache

Ⅳ．RAM和ROM都需要进行刷新

A．Ⅰ、Ⅱ

B．Ⅱ、Ⅲ

C．Ⅰ、Ⅱ、Ⅳ

D．Ⅱ、Ⅲ、Ⅳ

【答案】A

【解析】RAM中的内容断电后即丢失（易失性），ROM中的内容断电后不会丢失（非易失性），同时RAM和ROM都采用随机存取方式（即CPU对任何一个存储单元的存取时间相同），区别在于RAM可读可写，ROM只读不写。而ROM显然不可用作Cache，也不需要刷新，所以Ⅲ和Ⅳ的叙述都是错误的。

17下列命中组合情况中，一次访存过程中不可能发生的是（　　）。

A．TLB未命中，Cache未命中，Page未命中

B．TLB未命中，Cache命中，Page命中

C．TLB命中，Cache未命中，Page命中

D．TLB命中，Cache命中，Page未命中

【答案】D

【解析】TLB（快表）和慢表（页表，Page）构成二级存储系统，若TLB命中，则Page必命中。因此不可能发生的是D选项。

18下列寄存器中，汇编语言程序员可见的是（　　）。

A．存储器地址寄存器（MAR）

B．程序计数器（PC）

C．存储器数据寄存器（MDR）

D．指令寄存器（IR）

【答案】B

【解析】CPU有5个专用寄存器，它们是程序计数器（PC）、指令寄存器（IR）、存储器地址寄存器（MAR）、存储器数据寄存器（MBR）和状态标志寄存器（PSWR），这些寄存器中有些是CPU的内部工作寄存器，对汇编语言程序员来说是透明的，在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC的值，所以程序计数器（PC）对于汇编语言程序员可见的。

19下列选项中，不会引起指令流水线阻塞的是（　　）。

A．数据旁路（转发）

B．数据相关

C．条件转移

D．资源冲突

【答案】A

【解析】由于采用流水线方式，相邻或相近的两条指令可能会因为存在某种关联，后一条指令不能按照原指定的时钟周期运行，从而使流水线断流。有三种相关可能引起指令流水线阻塞：①结构相关，又称资源相关；②数据相关；③控制相关，又称指令相关，主要由转移指令引起。

20下列选项中的英文缩写均为总线标准的是（　　）。

A．PCI、CRT、USB、EISA

B．ISA、CPI、VESA、EISA

C．ISA、SCSl、RAM、MIPS

D．ISA、EISA、PCI、PCI-Express

【答案】D

【解析】选项A中的CRT和USB、选项B中的CPI、选项C中的RAM和MIPS均不是总线标准的英文缩写，只有选项D中的英文缩写均为总线标准。

21单级中断系统中，中断服务程序内的执行顺序是（　　）。

Ⅰ．保护现场；

Ⅱ．开中断；

Ⅲ．关中断；

Ⅳ．保存断点；

Ⅴ．中断事件处理；

Ⅵ．恢复现场；

Ⅶ．中断返回

A．Ⅰ→Ⅴ→Ⅵ→Ⅱ→Ⅶ

B．Ⅲ→Ⅰ→Ⅴ→Ⅶ

C．Ⅲ→Ⅳ→Ⅴ→Ⅵ→Ⅶ

D．Ⅳ→Ⅰ→Ⅴ→Ⅵ→Ⅶ

【答案】A

【解析】程序中断有单级中断和多级中断之分，单级中断在CPU执行中断服务程序的过程中不能被打断，即不允许中断嵌套。保存断点与关中断的任务是由硬件（中断隐指令）完成的，所以在单级中断系统中，中断服务程序内应完成的任务有：①保存现场；②中断事件处理；③恢复现场；④开中断；⑤中断返回。

22假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600×1200，颜色深度为24位，帧频为85Hz，显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（　　）。

A．245Mbps

B．979Mbps

C．1958Mbps

D．7834Mbps

【答案】D

【解析】显存的容量＝分辨率×色深，带宽＝分辨率×色深×帧频，考虑到50%的时间用来刷新屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：1600×1200×24×85×2＝7834Mbps。

23下列选项中，操作系统提供的给应用程序的接口是（　　）。

A．系统调用

B．中断

C．库函数

D．原语

【答案】A

【解析】操作系统提供给用户应用程序的接口只有两种：命令输入和系统调用。其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口（GUI）、自然命令用户接口（NUI）等，而系统调用中除了常规的一些传统的系统调用（例如read（））以外，还有经过扩展的复杂调用（例如多种API），以及包含在Lib库中的各种封装好的过程调用（最终都是通过系统调用陷入到操作系统中去的）等。

24下列选项中，导致创建新进程的操作是（　　）。

Ⅰ．用户登录成功

Ⅱ．设备分配

Ⅲ．启动程序执行

A．Ⅰ、Ⅱ

B．Ⅱ、Ⅲ

C．Ⅰ、Ⅲ

D．Ⅰ、Ⅱ和Ⅲ

【答案】C

【解析】进程创建是需要填写PCB表的，其中唯一不需要的是Ⅱ。考察一个进程创建的过程是这样的：当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock（）时，操作系统首先到PCB表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填写PCB表创建进程。通常填写PCB表的过程有一段时间（主要涉及资源分配需要协调），许多操作系统为此设立了一个中间状态称为“初始化”，也有的操作系统不设这个中间状态。此时操作系统填写进程ID号、处理机参数、进程参数（状态、特权、优先级）、分配内存（若是虚拟存储就分配虚拟地址）、映射文件等，一切就绪，将控制权交给系统进行下一步调度。设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C。

25设与某资源相关联的信号量初值为3，当前为1，若M表示该资源的可用个数，N表示等待该资源的进程数，则M，N分别是（　　）。

A．0、1

B．1、0

C．1、2

D．2、0

【答案】B

【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。

26下列选项中，降低进程优先级的合理时机是（　　）。

A．进程的时间片用完

B．进程刚完成I/O，进入就绪队列

C．进程长期处于就绪队列

D．进程从就绪状态转为运行态

【答案】A

【解析】进程时间片用完可以降低其优先级，完成I/O的进程应该提升其优先级，处于就绪队列等待调度的进程一般不会改变其优先级。进行这样的操作主要是为了改善交互式系统的响应时间，并均衡各个作业的公平性。采用时间片轮转技术主要为改善交互式用户的感受，使其觉得是独享计算机（时间片轮转可以有效地防止计算繁忙型的进程独占计算机），时间片用完后降低其优先级是为了改善新进程的响应时间（新进程优先级较高，老进程降低优先级可以保证新进程具有优先权），对于刚进入就绪队列的新进程，往往在创建时已经根据其特点和要求确定好优先级，不会随意改变。而对于从阻塞状态唤醒的进程，由于阻塞带来了较长时间的等待，一般会根据阻塞队列的不同适当地提高优先级，以改善用户响应时间。

27进程P0和P1的共享变量定义及若进程P0和P1访问临界资源的类C伪代码实现如下：

则并发执行进程P0和P1时产生的情况是（　　）。

A．不能保证进程互斥进入临界区，会出现“饥饿”现象

B．不能保证进程互斥进入临界区，不会出现“饥饿”现象

C．能保证进程互斥进入临界区，会出现“饥饿”现象

D．能保证进程互斥进入临界区，不会出现“饥饿”现象

【答案】D

【解析】这是皮特森算法（Peterson’s Algorithm）的实现，保证进入临界区的进程合理安全。该算法为了防止两个进程为进入临界区而无限期等待，设置变量turn，表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置turn标志，不允许另一个进程进入，这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区。保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入。先到先人，后到等待，从而完成临界区访问的要求。

28某基于动态分区存储管理的计算机，其主存容量为55MB（初始为空闲），采用最佳适配（BestFit）算法，分配和释放的顺序为：分配15MB、分配30MB、释放15MB、分配8MB、分配6MB，此时主存中最大空闲分，区的大小是（　　）。

A．7MB

B．9MB

C．10MB

D．15MB

【答案】B

【解析】对于简单分区内存分配，需要将进程的所有代码和数据装入内存。故55MB先分配15MB余40MB，再分配30MB后余l0MB，释放15MB后出现一个15MB和一个10MB的空闲空间，分配8MB时按最佳适配（BestFit）算法应该使用l0MB的空闲块，余2MB的碎片，分配6MB时占用15MB的空间余9MB的碎片（空闲空间），因此最大空闲区为9MB。

29某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为2¹⁰字节，页表项大小为2字节，逻辑地址结构为：

逻辑地址空间大小为2¹⁶页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（　　）。

A．64

B．128

C．256

D．5l2

【答案】B

【解析】地址空间分为逻辑地址空间和物理地址空间。页的大小为2¹⁰字节，页表项大小为2B，采用二级页表，一页可存放2¹⁰/2＝2⁹个页表项，本题中逻辑地址空间大小为2¹⁶字节，故最少需要2¹⁶/2⁹＝2⁷128个页面来保存页表项，故本题答案为B。

30设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是（　　）。

A．33KB

B．519KB

C．1057KB

D．16513KB

【答案】C

【解析】4个地址项为直接地址索引，其指向的数据块大小4×256B＝1KB，一级间接地址索引可以索引256/4＝64个直接地址索引，故2个一级间接地址索引指向的数据块大小为2×64×256B＝32KB，二级间接地址索引为256/4×256/4＝4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096×256B＝1024KB，共计1KB＋32KB＋1024KB＝1057KB。

31设置当前工作目录的主要目的是（　　）。

A．节省外存空间

B．节省内存空间

C．加快文件的检索速度

D．加快文件的读/写速度

【答案】C

【解析】工作目录只是指出了当前操作的默认目录，使得在每次访问的时候不需要由根目录一层一层地解析，在文件路径比较长时，可以节省许多解析的时间，从而加快了文件的检索速度。

32本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（　　）。

A．命令解释程序

B．中断处理程序

C．系统调用服务程序

D．用户登录程序

【答案】B

【解析】外部设备在与计算机连接时有多种方式，中断技术就是一种常用方式。其工作原理是：利用处理机中断信号线，外部设备在需要服务的时候将该线设置为有效，计算机若同意接受中断则会停止当前进程的运行，转而服务发出中断的物理设备（注意与陷阱，即软中断有区别），那么对不同外部设备进行服务的程序代码是不同的，如何找到这些代码呢？这就要借助中断向量，中断向量一般是由硬件根据中断的类型（不同外设不同）计算所得，或计算机系统在开机配置时所配置的。处理机取得中断向量，其实就是一个物理地址，该地址下存放的是为此中断服务的代码的起始地址。所以，当键盘按下的时候，键盘控制器获得该操作动作，先将键盘扫描码读入键盘缓冲区，再向处理机发出键盘中断，适当的时候（一条指令的末尾或一条原语结束）处理机会响应中断，调用指定服务程序将键盘缓冲区中的键盘扫描码输入到登录进程中去。如此，最先响应键盘的必然是中断处理程序。本题中，像命令解释器（例如cmd窗口）、系统调用服务和用户登录程序都在中断处理程序后面。

33下列选项中，不属于网络体系结构中所描述的内容是（　　）。

A．网络的层次

B．每一层使用的协议

C．协议的内部实现细节

D．每一层必须完成的功能

【答案】C

【解析】体系结构仅规定协议的功能和消息格式，但对具体的实现细节由具体设备厂商来确定，对于网络的层次，以及每一个层次的协议及其功能都是网络体系结构所要描述的内容，因此答案为选项C。

34在下图所示的采用“存储一转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps，分组大小为1000B，其中分组头大小20B，若主机Hl向主机H2发送一个大小为980000B的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（　　）。

A．80ms

B．80.08ms

C．80.16ms

D．80.24ms

【答案】C

【解析】由题设可知，分组携带的数据长度为980B，文件长度为980000B，需拆分为1000个分组，加上头部后，每个分组大小为1000B，总共需要传送的数据量大小为lMB。由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过分组交换机。当t＝1M×8/100Mbps＝80ms时，HI发送完最后一个比特；到达目的地，最后一个分组，需经过两个分组交换机的转发，每次转发的时间为t₀＝lK×8/100Mbps＝0.08ms，所以，在不考虑分组拆装时间和传播延时的情况下，当t＝80ms＋2t₀＝80.16ms时，H2接受完文件，即所需的时间至少为80.16ms。

35某自治系统内采用RIP协议，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量，距离矢量中包含信息“＜net1，16＞”，则能得出的结论是（　　）。

A．R2可以经过R1到达net1，跳数为17

B．R2可以到达net1，跳数为16

C．R1可以经过R2到达net1，跳数为17

D．R1不能经过R2到达net1

【答案】D

【解析】RIP允许一条路径最多只能包含l5个路由器，因此距离等于16时相当于不可达，因此RIP协议里规定16为路由不可达，答案为D。

36若路由器R因为拥塞丢弃IP分组，则此时R可向发出该IP分组的源主机发送的ICMP报文件类型是（　　）。

A．路由重定向

B．目的不可达

C．源抑制

D．超时

【答案】C

【解析】当路由器或主机由于拥塞而丢弃数据报时，就向源点发送源点抑制报文，使源点知道把数据报的发送速率放慢，正确选项为C。

37某网络的IP地址空间为192.168.5.0/24，采用定长子网划分，子网掩码为255.255.255.248，则该网络的最大子网个数、每个子网内的最大可分配地址个数分别是（　　）。

A．32，8

B．32，6

C．8，32

D．8，30

【答案】B

【解析】子网号为5位，在CIDR中可以表示2⁵＝32个子网，主机号为3位，除去全0和全1的情况可以表示6个主机地址，答案为B。

38下列网络设备中，能够抑制广播风暴的是（　　）。

Ⅰ．中继器

Ⅱ．集线器

Ⅲ．网桥

Ⅳ．路由器

A．Ⅰ、Ⅱ

B．仅Ⅲ

C．Ⅲ、Ⅳ

D．仅Ⅳ

【答案】D

【解析】中继器和集线器工作在物理层，不能抑制网络风暴。为了解决冲突域的问题，提高共享介质的利用率，通常利用网桥和交换机来分隔互联网的各个网段中的通信量，以建立多个分离的冲突域。但是，当网桥和交换机接收到一个未知转发信息的数据帧时，为了保证该帧能被目的结点正确接收，将该帧从所有的端口广播出去。于是可以看出，网桥和交换机的冲突域等于端口的个数，广播域为1。因此网桥不能抑制网络风暴。

39主机甲和主机乙之间已建立了一个TCP连接，TCP最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（　　）。

A．1000

B．2000

C．3000

D．4000

【答案】A

【解析】发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，于是此时发送方的发送窗口为min{4000，2000）＝2000字节，由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000－1000＝1000字节，正确选项为A。

40如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（　　）。

A．1条，1条

B．1条，多条

C．多条，1条

D．多条，多条

【答案】A

【解析】所谓递归查询方式就是：如果主机所询问的本地域名服务器不知道被查询域名的IP地址，那么本地域名服务器就以DNS客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询。所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归。正确选项为A。

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

41（10分）将关键字序列（7，8，30，11，18，9，14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组。散列函数是：H（key）＝（key×3）MOD7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。

（1）请画出所构造的散列表。

（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。

解：（1）要求装填因子为0.7，数组的长度应该为7/0.7＝10，数组下标为0～9。各关键字的散列函数值如下表：

采用线性探测法再散列法处理冲突，所构造的散列表为：

（2）查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示：

故查找成功的平均查找长度为（1＋1＋1＋1＋3＋3＋2）/7＝12/7。

在不成功的情况下，由于任意关键字key，H（key）的值只能是0～6之间，H（key）为0需要比较3次，H（key）为1需要比较2次，H（key）为2需要比较l次，H（key）为3需要比较2次，H（key）为4需要比较l次，H（key）为5需要比较5次，H（key）为6需要比较4次，共7种情况，如下表所示：

所以，在等概率下，查找失败的平均查找长度为：（3＋2＋1＋2＋1＋5＋4）/7＝18/7。

42（13分）设将n（n＞1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中存有的序列循环左移P（0＜P＜n）个位置，即将R中的数据由（X₀，X₁，…， X_n－1）变换为（x_p，x_p＋1，…，x_n－1，x₀，x₁，…，x_p－1）。要求：

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

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

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

解：（1）算法的基本设计思想：先将n个数据由x₀，x₁，…，x_p，…，x_n－1原地逆置，得到x_n－1，…，x_p，x_p－1，…，x₀然后再将数组R中的前，n－P个数和后P个数分别原地逆置，最终得到结果x_p，x_p＋1，…，x_n－1，x₀，x₁，…，x_p－1。

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

（3）说明算法的复杂性：上述算法中3个Reverse函数的的时间复杂度分别为O（p/2）、O（（p－2）/2）为O（n/2），故算法的时间复杂度为O（n），算法的空间复杂度为O（1）。

43（11分）某计算机字长16位，主存地址空间大小为128KB，按字编址，采用单字长指令格式，指令各字段定义如下：

转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：

注：（X）表示存储器地址X或寄存器X的内容。请回答下列问题：

（1）该指令系统最多可有多少条指令？该计算机最多有多少个通用寄存器？存储器地址寄存器（MAR）和存储器数据寄存器（MDR）至少各需要多少位？

（2）转移指令的目标地址范围是多少？

（3）若操作码0010B表示加法操作（助记符为add），寄存器R4和R5的编号分别为100B和101B，R4的内容为l234H，R5的内容为5678H，地址1234H的内容为5678H，地址5678H中的内容为1234H，则汇编语句“add（R4），（R5）＋”（逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变？改变后的内容是什么？

解：（1）指令操作码占4位，则指令系统最多可有2⁴＝16条不同的指令；指令操作上占6位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有2³＝8个通用寄存器；主存容量为128KB，计算机字长为16位，故主存有l28KB/2B＝2¹⁶个存储单元，故MDR和MAR至少各需l6位。

（2）由于寄存器字长为l6位，所以转移指令的目标地址范围为0000H～FFFFH。。

（3）汇编语句add（R4），（R5）＋对应的机器码为0010 0011 0001 0101B＝2315H，该指令执行后，寄存器R5和地址为5678H的存储单元的内容会改变，改变后的内容分别为：

（ACC）＝（（R4））＋（（R5））＝5678H＋1234H＝68ACH

（R5）＝（R5）＋1＝5678H＋1＝5679H

（1234H）＝（ACC）＝68ACH

44（12分）某计算机的主存地址空间大小为256MB，按字节编址，指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下所示：程序A：程序B：

假定int类型数据用32位补码表示，程序编译时i，j，sum均分配在寄存器中，数组a按行优先方式存放，首地址320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。

（1）若不考虑用于Cache一致性维护和替换算法的控制位，则数据Cache的总容量为多少？

（2）数组数据a[0][31]和a[1][1]各自所在的主存块对应的Cache行号分别是多少（Cache行号从0开始）？

（3）程序A和B的数据访问命中率各是多少？哪个程序的执行时间更短？

解：

（1）每个Cache行对应一个标记项，标记项包括有效位、脏位、替换控制位以及标记位。由主存空间大小为256M可知地址总长度为28位，其中块内地址为log₂64＝6位，Cache块号为log₂8＝3位，不考虑一致性维护和替换算法的控制位，则Tag的位数为28－6－3＝19位，还需一位有效位，数据Cache共有8行，故Cache的总容量为8*（64＋20/8）B＝532B

（2）数组a在主存的存放位置及其与Cache之间的映射关系如下图所示：

数组按行优先方式存放，首地址为320，数组元素占4个字节。a[0][31]所在的主存块对应的Cache行号为（320＋31*4）/64＝6；a[1][1]所在的主存块对应的Cache行号为（320＋256*4＋1*4）/64%8＝5。

（3）数组a的大小为256*256*4B＝2¹⁸B，占用2¹⁸/64＝212个主存块，按行优先存放，程序A逐行访问数组a，共需访问的次数为2¹⁶次，每个字块的第一个数未面中，因此未面中次数为2¹²次，程序A的数据访问命中率为（2¹⁶－2¹²）/2¹⁶*100%＝93.75%；Cache总容量为64B*8＝512B，数组a一行的大小为1KB正好是Cache容量的2倍，可知不同行的同一列数组元素使用的是同一个Cache单元，而程序B逐列访问数组a的数据时，都会将之前的字块置换出，也即每次访问都不会面中，故程序B的数据访问命中率是0，因此程序A的执行过程更短。

45（7分）假设计算机系统采用CSCAN（循环扫描）磁盘调度策略。使用2KB的内存空间记录16384个磁盘块的空闲状态。

（1）请说明在上述条件下如何进行磁盘空闲状态的管理。

（2）设某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动（如下图所示），磁道号请求队列为50，90，30，120，对请求队列中的每个磁道需要读取1个随机分布的扇区，则读完这4个扇区总共需要多少时间？要求给出计算过程。

（3）如果将磁盘替换为随机访问的Flash半导体存储器（如U盘、SSD等），是否有比CSCAN更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。

解：

（1）采用位示图法管理磁盘空闲块，每一位表示一个磁盘块的状态，共需要16384/32＝512 个字节即2KB的空间，正好可放在系统提供的内存中。

（2）采用CSCAN调度算法，访问磁道的顺序和移动的磁道数如下表所示：

故移动的磁道数为20＋90＋20＋40＝170，所花的时间为170ms。由于转速为6000r/min，则平均旋转延迟为5ms，总的旋转延迟时间为20ms，读取一个扇区的平均时间为0.1ms，故读取4个扇区所花的时间为0.4ms。综上所述，读取磁道上所有扇区所花的总时间为170＋5*4＋0.4＝190.4ms。

（3）采用先来先服务（FCFS）调度策略更高效，因为Flash半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按I/O请求的先后顺序服务。

46（8分）设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框（PageFrame）。在时刻260前的该进程访问情况如下表所示（访问位即使用位）。

当该进程执行到时刻260时，要访问的逻辑地址为17CAH的数据，请回答下列问题：

（1）该逻辑地址对应的页号是多少？

（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。

（3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如图所示）

解：

（1）由题可知计算机的逻辑地址空间和物理地址空间均为64KB＝216B，按字节编址，并且页的大小为1K＝210，故逻辑地址和物理地址的地址格式均为:

地址17CA＝0001 0111 1100 1010B，故可知其逻辑页号为000101B＝5。

（2）根据FIFO算法，需要替换出最早装入的页，故需置换0号页，将5号页装入7号页框中，所以物理地址为0001 1111 1100 1010B＝1FCAH。

（3）根据CLOCK算法，如果当前指针所指页框的使用位为0，则替换该页，否则将使用位清零，并将指针指向下一个页框，继续查找。由题可知，将从2号页框开始，前4次查找页框号的顺序为2、4、7、9，并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位已经为0，故将2号页框的页将5号装入2号页框，并将其对应使用位设置为1，所以对应的物理地址为0000 1011 1100 1010B＝0BCAH。

47（9分）某局域网采用CSMA/CD协议实现介质访问控制，数据传输率为10Mbps，主机甲和主机乙之间的距离为2km，信号传播速度是200000km/s。请回答下列问题，要求说明理由或写出计算过程。

（1）若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间？最长需经过多长时间？（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）

（2）若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1518字节）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧，此时主机甲的有效数据传输速率是多少？（不考虑以太网帧的前导码）

解：（1）当甲乙两台主机同时向对方发送数据时，两台主机均检测到冲突的时间最短：T_min＝（1km/200000km/s）×2＝10μs；当一台主机发送的数据就要到达另一台主机时，另一台主机才发送数据，两台主机均检测到冲突的时间最长：T_min＝（2km/200000km/s）×2＝20μs

（2）有效数据传输速率＝发送的有效数据/发送有效数据所用的总时间。发送的有效数据＝l500B＝1500×8bit＝12000bit；发送l518B的发送时间＝l518×8/10Mbps＝1214.4μs；数据帧的传播时间＝2km/200000km/s＝10μs；确认帧的发送时间＝64×8/10Mbps＝51.2μs ；确认帧的传播时间＝2km/200000km/s＝10μs ；发送l518B所用的总时间为1214.4μs＋10μs＋10μs＋51.2μs＝1285.6μs主机甲的有效数据传输率为l2000bit/1285.6μs＝9.33Mbps。