计算机专业（基础综合）模拟试卷64

计算机专业(基础综合)模拟试卷64

一、单选题(本题共40题，每题1.0分，共40分。)

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

j»intm){inti»temp；if(j<m){for(i=j»i<=n；i++)if(a[i]<a[j]){temp=a[i]；

a[j]=tcmp；}j++；order。，m)；//递归调用}}

A、0(n)

O(nlog2n)

C、O(n2)

D、0(i?)

标准答案：C

知识点解析：order。函数是一个递归排序过程，设T(n)是排序n个元素所需要的时

间。在排序n个元素时，算法的计算时间主要花费在递归调用。rder()上。第一次调

用时，处埋的元素序列个数为n―1,也就是对余下的n―1个元素进行排序，所

需要的计算时间应为T(n—1)。又因为在其中的循环中，需要n—l次比较，所以

排序n个元素所需要的时间为T(n)=T(n—l)+n-1,n>l这样得到如下方程：

T(l)=0T(n)=T(n—l)+n—1n>l求解过程为T(n)=|T(n-2)+(n-2)]+(n—1)=[T(n

-3)+(n-3)]+(n-2)+(n—1)=[T(l)+l]+2+...+n—1=0+l+2+...+n-1=n(n—1)/2

=0(n2)

2、在顺序表的动态存储定义中需要包含的数据成员是()。I.数组指针*data

II.表中元素个数n川.表的大小maxSizeW.数组基址base

A、I、口

B、I>n、w

c、i、口、m

D、全都需要

标准答案：C

知识点解析：首先，表的大小和表的元素个数是肯定需要的。其次，在顺序表的动

态存储定义中，它的存储空间是通过执行malloc或new动态分配的，所以不包括

数组基址。最后，数组的首地址需要数组指针data来存储。可能疑问点：数组首

址和数组基址貌似〜样，有什么区别？提示：数组基址指数组首地址在内存中的真

实地址，即物理地址”既然是动态分配，自然就无法确定，所以就没有必要纳入其

数据成员。数组首址就是数组第一个元素的下标，通常情况下都是0。换句话说：

数组基址是一个全局的概念，首址是一个局部的概念。

3、向一个栈顶指针为head的带头结点的链栈中插入指针L所指的结点时，应该执

行()。

A、head一next=L

B、L—>next=head

C^L—*next=head;hcad—>next=L

D、L—next=head一next：head—next=L

标准答案：D

知识点解析•：此题表面上考查的是链栈的插入，其实与单链表的插入没有什么两

样。既然是栈的插入，那么就是在栈顶进行操作，即考查的就是在单链表的头结点

（指针head所指结点）后播入一个新的结点。该知识点在《数据结构高分笔记》中

IInot

②heM-EI

己经详细地讲解过了，操作如图2-5所示。图2.5fit枝的瓶入注

意：①和②的顺序千万不可颠倒，否则将断链，导致操作失败。

4、栈S和队列Q的初始状态皆为空，元素al、a2、a3、a4、a5和a6依次通过S

栈，一个元素出栈后即进入队列Q,若6个元素出队列的顺序是a3、a4、a2、al、

a5、a6,则栈S至少应该容纳（）个元素。

A、6

B、4

C、3

D、2

标准答案：C

知识点解析：模拟一下入栈、出栈过程，如表2-5所示。选取模拟过程中栈内元素

个数最大的值，便为该题答案，因此本题选C。

5、某平衡二叉树的树高为3,其根结点A左孩子的平衡因子为一1,右孩子的度

为0。在该平衡二叉树口插入一个结点后造成了不平衡，则应该进行（）型旋转以使

其平衡。

A、LL或者RL

B、LR或者LL

C、RL或者RR

D、RR或者LL

标准答案：C

知识点解析：由题意可知，树的结构如图2-6所示。由图2—6可知，插入一个结

点造成根结点A的左孩子结点不平衡，说明这个结点一定是插在根结点A的左孩

子的右孩子上，如图2-7所示。所以需要进行RL型或者RR型旋转。

re2-7捅入一个针，点后的义利

6、在由4棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为

30、10、20、5,当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结

点个数为（）。

A、64

B、29

C、30

D、4

标准答案：B

知识点解析：当森林转於成二叉树后，根结点的左子树其实就是原来第一棵树除了

根结点的所有结点，所以二叉树中根结点的左子树中结点个数为29,故选B。

7、若一棵深度为6的完全二叉树的第6层有3个叶子结点，则该二义树共有（）个

叶子结点。

A、16

B、17

C、18

D、19

标准答案：B

知识点解析：首先根据每一层最多叶子结点的计算公式可知，完全二叉树的第五层

有16（2、个叶子结点，题目说第6层有3个叶子结点，那么这3个叶子结点肯定要

占据第五层的2个叶子结点，第五层就只有14个叶子结点，然后再加上第六层的

3个叶子结点，所以一共有14+3=17个叶子结点。

8、用有向无环图描述表达式(A+B)*((A+B)/A),至少需要顶点的数目为()。

A、5

B、6

C、8

D、9

标准答案：A

知识点解析：用图2—8可以表示表达式，图2-8中顶点表示参与运算的一种操作

数和运算符(注意是一种而不是一个)，用边来确定各种运算以及运算优先顺序。

(A+B)*((A+B)/A)表达式中的运算符有3种,即操作数有两种,

即“A”、“B”，因此图2-8中顶点数至少为5o图2-8中A与B结合运算符“+”做运

算，将所得结果与结合运算符做运算，上两步的结果再结合运算符“”做运

算得到最终结果。本题比较灵活，属于在掌握基础后的能力扩展。

9、下列关于AOE网的叙述中，错误的是()。

A、关键活动延期完成必定影响整个工程的完成时间

B、关键路径是AOE网中从起点到终点的最短路径

C、所有的关键活动提前完成，那么整个工程将会提前完成

D、一个AOE网的关键路径可以有多条

标准答案：B

知识点解析：关键活动组成了关键路径。关键路径是从起点到终点的最长路径，关

键路径的长度代表整个工期的最短完成时间。关键活动延期完成，必将导致关键路

径长度增加，即整个工期的最短完成时间增加，所以A正确。关键路径实际上是

从源点到终点的最长路经，而非最短路径。这点很容易理解.，因为整个工程的工期

就是按照最长路径长度计算出来的，即等于该路径上所有活动的持续时间之和，所

以B错误。只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的

目的，所以C正确。关健路径并不唯一，可以有多条，所以D正确。注意：关键

路径算法是以拓扑排序为基础的。

10、为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好

情况下查找到表中已有元素，需要执行()次关键字比较。

A、10

B、14

C、20

D、21

标准答案：B

知识点解析：首先需要知道折半查找成功的平均查找长度为k)g2(n+l)・l。为使查

找效率最高，可对有65025个元素的有序顺序表分块，每块有两砺=255个元

素。为每一块建立一个索引项，索引表共255个索引项。若对索引表和每一块都采

用折半查找，则查找效率最高，计算可得

ASLindexSeqSearch=ASLindex+ASLBlock=log2(255+1)1l+log2(255+l)―-1=14下面补充

一些关于折半查找的概念。补充(1)：折半查找的时间复杂度为O(log2n)。补充

(2)：折半查找是基于随机存储方式的算法，必须用顺序表而不能用链表。补充

(3)：对于折半查找，假设h表示判定树的高度，如果有n个元素，则判定树的高

度为h=[log2(n+1)]或者h=[log2(n+l)]+l

11、对于序列(32,47,12,8,2,19,30),其堆顶元素最小的初始堆是()。

A、(2,8,12,32,47.19,30)

B、(2,8,12,19,30：32,47)

C、(2,12,8,32,19,47,30)

D、(2,12,8,30,19.32,47)

标准答案：A

所示。图2-9序列对龙的景小雄画U过目因

此，最后结果为(2,8,12,32,47,19,30)。补充：堆调整过程从无序序列所

确定的完全二叉树的第一个非叶子结点开始，从右至左、从下至上，对每个结点进

行调整，最终将得到一个小顶堆。

12、CPU的CPI与下列哪个因素有关？()I.时钟频率H.系统结构m.指令集

A、仅I、n

B、仅I、in

c、仅u、m

D、I、II和in

标准答案：c

知识点解析：CPI是执行一条指令所需要的时钟周期数，系统结构、指令集、计算

机组织等都会影响CPI,而时钟频率并不会影响到CPI,但可以加快指令的执行速

度.如执行一条指令需要5个时钟周期，则主频大的CPU执行这条指令要比主频

小的CPU快。

13、n+I位的定点小数，其补码表示范围是()。

A、-l<x<l-2'n

B、一1<X<1—2-n

C、一1<X<1—2'n

D、一1<X<1—2'n

标准答案：A

知识点解析：各种编码下的数值范围总结如表2-6所示。

囊29各科螭码依值范81总结

崎蚪”式・小但■科・小便Al大伏垢利・大值

Ml0上符号定点❷⑹000...0000Ill-Ill2-'-|

n*l位JL符号堂点小数0.00..0000on...in1-2-0«Sx«l-2"

。1位定点祭故傣研iuio.ni-2,41OIII...Ill2,1

ml位定且小散发叫i.in-inOlli...IllI-2-*•IHWxW卜2f

*1W定6尊数乃科1000000-r0III...III2,12"<»e£r-l

印|付定6小数韩研1000.000-1Olli--tili-r*ICM«I-I',

Ml健证**数辰科1000.000-2**l0111-III2,11

•*1位定点小数反码1000ooo•1*2**OIII...Ill1-2--l*2-Cx<|-2a

**1位企力，户数杼料0000.000ini^in2,1

。八位定点小数移码小散没有将科定义

14、有一主存-Cache层次的存储器，其主存容量为1MB（按字节编址），Cache容量

为16KB,每字块有8个字，每字为32位，采用直接地址映像方式。若主存地址

为35301H,且CPU访问Cache命中,则在Cache的第（）号字块（Cache字块号从0

开始）。

A、152

B、153

C、154

D、151

标准答案：A

知识点解析：首先将主存地址35301H写成二进制，即00110101001100000001,

然后主要分析该主存地址哪些位才是Cache字块地址。低位是块内地址，高位是主

存字块标记位，所以中间的部分就是Cache字块地址；题目中给出每字块有8个

字，每字为32位，所以每字块的大小为32B,故块内地址需要低5位来表示。另

外，要求主存字块标记位，只需求主存包含了多少个Cache即可，1MB/

16KB=64,所以需要6位来表示主存字块标记位，二进制地址就划分为如下格式：

00110101001100000001（主存字块标记位）（Cache字块地址）（块内地址）010011000

的十进制数为152,所以选A。

15、下列的说法正确的是（）。I.高位多体交叉存储器能很好地满足程序的局部

性原理n.高位四体交叉存储器可能在一个存储底期内连续访问4个模块HI.双

端口存储器可以同时对同一区间、同一单元进行写操作

A、仅I、m

B、仅口、出

C、仅皿

D、仅口

标准答案：D

知识点解析：I：高位多体交叉存储器由于是在单个存储器中将字连续存放的，所

以不能保证程序的局部性原理；而低位多体交叉存储器由于是交叉存放的，所以能

很好地满足程序的局部性原理，故I错误。n：高位四体交叉存储器虽然不能满

足程序的连续读取，但是仍然有可能一次连续读出彼此地址相差一个存储体容量的

4个字。虽然概率比较小，但是也非不可能，所以II正确。n：双端口存储器虽然

具有两套独立读/写端口，且具有各自的地址寄存器和译码电路，但是仍然不能同

时对同一区间、同一单元进行写操作。因为当有一方进行写时，忙标志位将会阻止

BUSY^-BUSY”

另一方访问（见图2/0）,所以HI错误。图双浦u存储港扩

展：双端口存储器可以同时对同一区间、同一单元进行读操作。另外，一方读一方

写也不能同时对同一区间、同一单元进行操作，否则将会发生冲突。总之，只要有

写操作，就不能同时进行。

16、地址总线为A15（高位）〜A0（低位），若用1KX4位的存储芯片组成4KB的存储

器，地址总线的高位做片选信号，则以下说法正确的是（）。I.加在各存储芯片

上的地址线是All〜AO口.加在各存储芯片上的地址线是A9〜AODI.一共需要

使用8片1KX4位的存储芯片W.一共需要使用4片1KX4位的存储芯片

A、I、田

B、口、W

c>n>m

D、I、W

标准答案：c

知识点解析：首先要用1KX4位的存储芯片组成4KB（即4K.x8位）的存储器，需

要进行字位一起扩展由公式可知，共需要的芯片数为（4Kx8位）/（1KX4位）=8,所

以m是正确的。另外，加在各存储芯片上的地址线只与存储芯片的存储容量有关，

本题芯片的存储容量为1K,又因为21°=1K,所以选取地址线的10位A9〜A。作

为各个存储芯片上的地址线。

17、下列说法正确的是（）。I.某加法指令，在指令的地址码中给出了存储器地

址，则此指令在执行周期一定访问存储器U.零地址双操作数指令不需要指出操

作数地址HI.在一地址格式的指令中，只有一个操作数

A、仅n、m

B、仅i、n

c、仅i、m

D、i、n和in

标准答案：B

知识点解析：I：既然指令码给出了存储器地址，无论此地址是源操作数地址，还

是目的操作数地址，执行周期都需要根据此地址访问存储器，所以I正确。D：

零地址双操作数指令不需要指出操作数地址，因为操作数的地址隐含在堆栈指针

中，所以n正确。n：一地址指令应该分为两种情况来讨论：（1）进行单目运算（只

需要一个操作数的运算，如白增、求反等操作）的一些操作，也就是说只有目的操

作数的单操作数指令，按指令地址字段给出的地址读取操作数，最后将执行结果存

回源地址。（2）将目的地址隐含的双操作数指令，先按指令地址码给出的地址读取

源操作数，而另一个操作数由AC提供，运算结果也将存放在AC中。综上所述，

在一地址格式的指令中，可能有一个操作数，也可能有两个操作数，所以m错误。

18、为了缩短指令中某个地址段的位数，有效的方法是采取（）。

A、立即寻址

B、变址寻址

C、间接寻址

D、寄存器寻址

标准答案：D

知识点露析：题目要求缩短某个地址段的位数，因此首先想到的就是寄存器寻址。

由于计算机中寄存器的数量一般很少，采用寄存器寻址时可用少量的代码来指定寄

存器，这样可以减少对应地址段的代码位数，也可减少整个指令的代码长度。其余

的立即寻址中地址字段需要存储一个操作数，有可能会增长位数：变址寻址

EA=A+（IX）,其中的A仍然和主存有一定关系；间接寻址中存放的仍然是一个主

存地址。知识点扩展：常见指令寻址方式特点总结。（1）立即寻址：操作数获取便

捷。通常用于给寄存器赋初值。（2）直接寻址：相对于立即寻址，缩短了指令长

度。（3）间接寻址；扩大寻址范围，便于编制程序，易于完成子程序返回。（4）寄存

器寻址：指令字较短，指令执行速度较快。（5）寄存器间接寻址：扩大寻址范围。

（6）基址寻址：扩大操作数寻址范围，适用于多道程序设计，常用于为程序或数据

分配存储空间。（7）变址寻址：主要用于处理数组问题，适合编制循环程序。（8）相

对寻址：控制程序的执行顺序、转移等。（9）基址寻址和变址寻址的区别：两种方

式有效地址的形成都是寄存器内容+偏移地址，但在基址寻址中，程序员操作的是

偏移地址，基址寄存器的内容由操作系统控制，在执行过程中是动态调整的；而在

变址寻址中，程序员操作的是变址寄存器，偏移地址是固定不变的。

19、下列说法正确的是（）。I.微程序控制方式和硬布线方式相比较，前者可以

使指令的执行速度更快U.若采用微程序控制方式，则可用"C取代PCHI.控

制存储器可以用ROM实现W.指令周期也称为CPU周期

A、I、m

B、II、in

c、只有川

D、i、m、w

标准答案：c

知识点解析•：i：可以这样来理解，微程序控制方式是用软件方式来实现指令执

行，而硬布线方式则是采用硬件方式来实现指令执行。当一个命令信号到来时，硬

布线控制器方式下，命令信号只需要通过一些门电路，就可以快速产生有效的控制

信号来控制部件完成操作，因此速度较快，所以I错误。n："c必然无法取代

PC,"C只是在微程序中指向下一条微指令地址的寄存器，只要熟悉微程序的执

行过程，便可以很容易得知：当一条指令执行时，分派给微程序部件来进行具体操

作，而这个操作仅仅是限于这条指令的内部，它无法得知整个程序是什么样，因此

它也必然不可能知道这段微程序执行完毕后，下一条是什么指令，所以口错误。

m：由于每一条微指令执行时所发出的控制信号是事先设计好的，不需要改变，所

以存放所有控制信号的存储器应为只读存储器，并将其集成到CPU内，称其为控

制存储器(简称控存)，故in正确。iv：指令周期是从一条指令的启动到下一条指令

启动的间隔时间，CPU周期是机器周期(通常使用内存中读取一个指令字的最短时

间来规定CPU周期)，是指令执行中每一步操作所需的时间，所以w错误。

20、下列部件中属于控制部件的是()。I.指令寄存器n.操作控制器nr.程序

计数器w.状态条件寄存器

A、仅I、m、w

B、仅I、u、m

c、仅I、n、w

D、I、u、in和w

标准答案：B

知识点解析：CPU控制器主要由3个部件组成：指令寄存器、程序计数器和操作

控制器。状态条件寄存器通常属于运算器的部件，保存由算术指令和逻辑指令运行

或测试的结果建立的各种条件码内容，如运算结果进位标志(C)、运算结果溢出标

志(V)、运算结果为零标志(Z)、运算结果为负标志(N)、中断标志⑴、方向标志(D)

和单步标识等。注意；存储器、运算器、外部设备等都属于执行部件。知识点扩

展：操作控制器总结。操作控制器(OC)的功能就是根据指令操作码和时序信号，

产生各种操作控制信号：以便正确地建立数据通路，从而完成取指令和执行指令的

控制。CPU内的每个功能部件都完成一定的特定功能。然而信息怎样才能在各部

件之间传送呢?也就是说，数据的流动是由什么部件控制的呢?通常把许多数字部件

之间传送信息的通路称为“数据通路信息从什么地方开始，中间经过哪个寄存器

或多路开关，最后传到哪个寄存器，都要加以控制。在各寄存器之间建立数据通路

的任务是由称为“操作控制器”的部件来完成的。操作控制器中主要有节拍脉冲发

生器、控制矩阵、时钟脉冲发生器、复位电路和启停电路等控制逻辑。这几个部件

对微处理器设计人员来说很关键，但微处理器用户却可以不必过多关心。

21、下列关于总线仲裁方式的说法中，正确的是()，I.计数器定时查询方式

下，有一根总线请求(BR)线和一根设备地址线，如果每次计数器从。开始计，则设

备号大的优先级高口.计数器定时查询方式下，有一根总线请求(BR)线和一根设

备地址线，如果每次计数器从当前设备开始计，则设备号小的优先级高m.分布

式仲裁控制逻辑分散在总线各部件中，不需要中央仲裁器

仅In

A、、

仅n

B、m

仅I

、、

C仅n

D、IIn

标准答案：B

知识点解析：I和HI：计数器定时模式下，有n个I/O接口，就需要有log2n根

设备地址线，工作原理是：假设有8个I/O设备，此时就需要3根设备地址线，

并且3根设备地址线与这8个设备都相连；当有设备请求总线时（不管有多少个设

备请求），BR线中产生信号，触动计时器，此时计时器从0开始，通过设备地址线

发送一一进制信号，3根线中信号逐步变化：000、001、010、…当设备检测到设备

线中信号与该设备编号相同时，该设备获得总线控制权，进行总线操作；当该设备

操作结束后，若仍有其，’也设备在请求，则计数器要么从。开始重新计数，要么从当

前设备开始计数……依次进行。如果每次计数器从0开始，肯定导致设备号小的

优先级最高。如果每次计数器从当前设备开始计数，则每个设备的优先级是一样

的。所以I、II都错误。m：分布式仲裁控制逻辑分散在总线各部件中，不需要

中央仲裁器，所以HI正确。

22、设CPU与I/O设备以中断方式进行数据传送，当CPU响应中断时，该I/O

设备接口控制器送给CPU的中断向量表（中断向量表存放中断向量）的指针是

0800H,0800H单元中的值为1200H,则该I/0设备的中断服务程序在主存中的

入口地址为（）。

A、0800H

B、0801H

C、1200H

D、1201H

标准答案：C

知识点解析：首先需要明白中断向量就是中断服务程序的入口地址，所以需要找到

指定的中断向量。中断向量是保存在中断向量表中的，而0800H是中断向量表的

地址，所以0800H的内容即是中断向量。

23、在下列操作系统的各个功能组成部分中，一定需要专门硬件配合支持的是（）。

I.地址映射n.进程调度W.中断系统W.系统调用

A、I

B、I、川

C、I、皿、IV

D、口、m

标准答案：B

知识点解析：有人可能会这样理解，任何功能都是在硬件的基础上实现的，所以都

是需要硬件支持的。但这里肯定不是这个意思，这里需要专门硬件支持的意思是，

除了处理机和内存以外，为了实现该功能，需要另外添加的专门用于实现该功能的

硬件。I是，地址映射是需要硬件机构来实现的。例如，在分页储存系统中，需

要一个页表寄存器，在其中存放页表在内存的始址和页表的长度。除此之外，当

进程要访问某个逻辑地址中的数据时，分页地址变换机构（它是硬件）会自动将有效

地址（相对地址）分为页号和页内地址两部分，再以页号为索引去检索页表。查找操

作是由硬件执行的。n不是，进程调度是通过使用一些调度算法来编程实现的，

所以不需要专门硬件支待。HI是，CPU硬件有一条中断请求线（IRL）。CPU在执行

完每条指令后，都将判断IRL。当CPU检测到已经有中断控制器（即中断源）通过中

断请求线发送了信号时，CPU将保留少量状态（如当前指令位置），并且跳转到内存

特定位置的中断处理程序。这里的中断控制器是硬件。中断系统离开中断控制器是

不可能工作的。w不是，对于系统调用是否一定需要专门的硬件这个问题，需要

清楚系统调用的过程。在C程序中调用系统调用好像是一般的函数调用，实际上

调用系统调用会引起用户态到核心态的状态变化，这是怎么做到的呢？原来C编译

程序采用一个预定义的函数库（C的程序库），其中的函数具有系统调用的名字，从

而解决了在用户程序中请求系统调用的问题。这些库函数一般都执行一条指令，该

指令将进程的运行方式变为核心态，然后使内核开始为系统调用执行代码，称这个

指令为操作系统陷入（OperatingSystemTrap）。系统调用的接口是一个中断处理程

序的特例。在处理操作系统陷入时：（1）内核根据系统调用号查系统调用入口表，

找到相应的内核子程序的地址。（2）内核还要确定该系统调用所要求的参数个数。

⑶从用户地址空间复制参数到U区（UNIXV）。（4）保存当前卜下文，执行系统调用

代码。（51恢复处理机现场并返回。上述（I）〜（3）过程和（5）过程都不需要专门的硬

件（除了CPU和内存），只有第（4）过程可能需要专门硬件，如显示器输出字符。但

也可以不需要专门硬件，如打开一个已经在缓存中的文件。综上所述，本题选

Bo

24、下列说法中，正确的说法有（）个。I.当进程申请CPU得不到满足时，它将

处于阻塞状态。n.当进程由执行变为就绪状态时，CPU现场信息必须被保存在

PCB中。n.一一个进程的状态发生变化总会引起其他一些进程的状态发生变

化。

A、0

B、1

C、2

D、3

标准答案：B

知识点解析：当进程申请CPU得不到满足时，它处于就绪状态；当因I/O等待

时，处于阻塞状态，因此I错误。当进程由执行变为就绪状态时，为了使下次进

程调度时进程可以继续从暂停的地方开始运行，CPU现场信息必须被保存在PCB

中，因此n正确。一个进程的状态发生变化并非总会引起其他一些进程的状态发

生变化。例如，一个进程等待的I/O数据到来后，它将从阻塞态变为就绪态，但

这时其他进程的状态可能并不会发生变化，因此111错误。综上，正确的说法有1

个，所以本题选B。

25、将“I/O为主”的进程定义为：当此类进程单独运行时，用于I/O处理的时间

远远多于处理机的处理时间。将“计算为主''的进程定义为：当此类进程单独运行

时，处理机的处理时间远远多于处理的时间。若系统中运行的主要是这两类进程，

采用（）调度算法更有利于资源的利用率。

A、先来先服务

B、短作业（进程）优先

C、时间片轮转

D、多级反馈队列

标准答案：D

知识点解析：以I/O为主的进程，如果采片］时间片调度算法，势必导致CPU利

用率的下降。对于计算为主的进程，如果采用纯优先调度算法，可能会导致进程平

均周转时间变长。因此正确答案是采用多级反馈队列轮转法进程调度算法。所谓

多级反馈队列轮转法就是把就绪进程按优先级排成多个队列，并赋给每个队列不同

的时间片，高优先级进程的时问片比低优先级进程的时间片小。调度时先选择高优

先级队列的第一个进程，使其投入运行，当该进程时间片用完后，若高优先级队列

中还有其他进程，则按照轮转法依次调度执行，否则转入低一级的就绪队列。只有

高优先级就绪队列为空时，才从低一级的就绪队列中调度进程执行。此种方法既照

顾了时间紧迫的进程，又兼顾了短进程，同时考虑了长进程，是一种比较理想的进

程调度方法。因此本题选D。

26、在某个十字路口，卷个车道只允许一辆汽车通过，且只允许直行、左拐和右

拐，如图2—1所示。如果把各个方向的车看成进程，则需要对这些进程进行同

步，那么这里临界资源个数应该为（）。

A、1

B、2

C、4

D、不确定

标准答案：C

知识点解析：如图2—11所示，直行的车辆需要获得该方向上的两个邻近的临界

资源。例如，北方开来的车辆需要获得1、2两个临界资源，南方开来的车的需要

获得3、4两个临界资源。图2小十字路口乍退，意图「）北方来车右转的情况需要获得

1这个临界资源，左转的情况需要获得1、2、3临界资源。所以每个方向来车有3

种不同的进程，4个方向有12种不同的进程。也可以用排除法来做该题，该路口

可以有南北方向的车同时直行，所以临界资源个数大于或等于2,排除A。该路口

可以4个方向的车都左转，所以临界资源个数大于或等于4,排除B。D选项一般

不会选，所以选C。

27、考虑一个由4个进程和一个单独资源组成的系统，当前的最大需求矩阵和分配

1

矩阵如下：SI【2J对于安全状态，需要的最小资源数目是（）。

A、1

B、2

C、3

D、5

标准答案：C

知识点解析：依次用P1〜P4来表示4个进程。从矢巨阵可以看出，4个进程还需

要的资源数目为（2,1,6,5）,按所需资源数目从小到大排列，即P2、Pl、P4、

P3。这就是所需最小资源数目的执行顺序。设有x个可用资源。当XN1时，P2可

以执行完成，并释放占用资源，此时资源数为x+l0当乂+自2时,，P1可以执行完

成，并释放占用资源，此时资源数为x+2。当x+2及时，P4可以执行完成，并释

放占用资源，此时资源数为x+4。当x+4次时，P3可以执行完成，并释放占月资

源，此时费源数为（忽略）。剩下的，就是解这个简单的方程组，得出xN3。按这种

方法做题，可以比较有把握不算错，也利于检杳。

28、已知系统为32位实地址，采用48位虚拟地址，页面大小4KB,页表项大小

为8B；每段最大为4GB。假设系统使用纯页式存储，则要采用（），页内偏移为（）

位。

A、3级页表，12

B、3级页表，14

C、4级页表，12

D、4级页表，14

标准答案：C

知识点解析：页面大小为4KB,故页内偏移为12位。系统采用48位虚拟地址，

故虚页号为48-12=36位。当采用多级页表时，最高级页表项不能超出一页大小；

每页能容纳页表项数为4KB/8B=51.2=27,36/9=4故应采用4级页表，最高级

页表项正好占据一页空间，所以本题选C。

29、某系统有4个页框，某个进程页面使用情况如表2-1所示。

»2-1某个迸程页面使用情况

卜.次川用时间R<4)M(ett)

012627900

12302M10

212027211

31602W11

请问采用

FIFO置换算法将会替换的页的页号为（）。采用LRU置换算法将会替换的页的页号

为（）。采用简单CLOCK置换算法将会替换的页的页号为（）。采用改进型CLOCK

置换算法将会替换的页的页号为（）。

A、1、3、2、0

B、3、2、0、1

C、2、1、0、0

D、3、1、0、

标准答案：C

知识点解析•：FIFO置换算法选择最先进入内存的页面进行替换。由表中装入时间

可知，第2页最先进入内存，所以FIFO置换算法选择第2页替换。LRU国换算法

选择最近最长时间未使用的页面进行替换。由表中上次引用时间可知，第1页是最

长时间未使用的页面，所以LRU置换算法将选择第1页替换。简单CLOCK置换

算法从上一次位置开始扫描，选择第一个访问位为0的页面进行替换。由表中

R（读）标志位可知，依次扫描1、2、3、0,页面。未被访问，扫描结束，所以简单

CLOCK置换算法将选搭第。页替换。改进型CLOCK置换算法从上一次位置开始

扫描，首选的置换页面是既未使用过的，又未修改的页面。由表中R（读）标志位和

M（修改）标志位可知，只有页面。满足R=0和M=0,所以改进型CLOCK置换算法

将选择第0页置换。

30、有某个操作系统对外存分配采用混合索引分配方式。在索引节点中包含了文件

的物理结构数组iaddr[12],其中前10项iaddr[O]〜iaddr⑼为直接地址，iaddr[IO]

为一次间接地址，iaddrlll]为二次间接地址。如果系统的块的大小是4KB,磁盘的

每个扇区也为4KB。描述磁盘块的数据项需要4B,其中1B标识磁盘分区，3B标

识物理块号。该文件系统支持的最大文件是（）。

A、4GB

B、8GB

C、40KB+4MB+4GB

D、40KB+4MB+8GB

标准答案：C

知识点解析：磁盘块大小为4KB,每个磁盘块要4B,则一一个磁盘块可以存放

1K个磁盘块号。直接地址的文件长度为10x4KB=40KB；一级间址时的文件长度

1KX4KB=4MB；二级问址时的文件长度为1KX1KX4KB=4GB；所以，该文件系统

支持的最大文件是40KB+4MB+4GB。

31、某个磁盘系统采用最短寻道时间优先(SSTF)磁盘调度算法，假设有一个请求柱

面读写磁盘请求队列如下：7、136、58、100、72,当前磁头位置是80柱面。请

问，磁盘总移动距离是()。

A、80

B、136

C、229

D、244

标准答案：C

知识点解析：表2—7所示是磁盘移动距离。

*2-7磁窗移动距离

。前•道仲农72100IM杵的

♦20

7214q14

5t-51y♦42-42

100qV♦36

1)6・y

l*y129.根据

SSTF磁盘调度算法,相应请求顺序为72、58、100、136、7。因此，总的移动距

离是8+14+42+36+129=229。此类问题的做法是：按照请求磁道的大小顺序排列，

然后算出两个方向上最近磁道的距离，决定磁头移动方向即可。

32、下面关于设备属性的叙述中，正确的是()。

A、字符设备的基本特征是可寻址到字节，即能指定输入的源地址或输出的目标地

址

B、共享设备必须是可寻址的和可随机访问的设备

C、共享设备是指同一时间内允许多个进程同时访问的设备

D、在分配共享设备和独占设备时都可能引起进程死锁

标准答案：B

知识点解析：字符设备的特征是不可寻址，即输入/输出时不能指定数据的输入源

地址及输出的目标地址。因此A错误。B叙述正确。共享设备是指在一段时间内

允许多个进程同时访问的设备，但不是同一时间同时访问，因此C错误。分配共

享设备和独占设备不会引起进程死锁，因此D错误。

33、关于OSI参考模型和TCP/IP模型在网络层和传输层提供的服务，正确的是

()°

A、OSI参考模型在网络层提供无连接和面向连接服务，在传输层仅提供面向连接

服务

B、TCP/IP模型在网络层仅提供无连接服务，在传输层仅提供面向连接服务

C、OSI参考模型在网络层和传输层均可提供无连接和面向连接服务

D、TCP/IP模型在网络层提供无连接和面向连接服务，在传输层仅提供面向连接

服务

标准答案：A

知识点解析：OSI参考模型和TCP/IP模型的特性对比，如表2-8所示。

«24OSI参考模里相TCP/IP模型的特性对比

OSI,号幔年

①，个％咎*急：接口、的或

①&衣明第1“分”务.楂林试

②产生。町收发明2前

③产生在静试发明之何

③（不J6S肥）

④共有?依

同Q层,

同络笈।AR和（屋楼

传・炭，而同遑检和包植

的♦丛：仪有向自残找

34、一个传输数字信号的模拟信道的信号功率是0.62W,噪声功率是0.02W,

频率范围为3.5〜3.9MHz,该信道的最高数据传输速率是（）。

A、1Mbit/s

B、2Mbit/s

C、4Mbit/s

D、8Mbit/s

标准答案：B

知识点解析：首先计算信噪比S/N=0.62/0.02=31；带宽W=3.9MHz一

3.5MHz=0.4MHz,由香农公式可知最高数据传输率V=Wx]og2（l+S/

N）=0.4xlog2（l+31）Mbit/s=2Mbit/s„提示：这道题目题干说得很清楚,是有噪

声的信道，所以第一个想到的应该是香农公式；如果题干说是无噪声信道，则应该

想到奈奎斯特定理。补充知识点：关于香农公式和奈奎斯特定理的总结。提示：

具体的信道所能通过的频率范围总是有限的（因为具体的信道带宽是确定的），所以

信号中的大部分高频分量就过不去了，这样在传输的过程中会衰减，导致在接收端

收到的信号的波形就失去了码元之间的清晰界限，这种现象叫做码间串扰.所以需

要找到在不出现码问串况的前提下，码元传输速率的最大值是多少（因为找到了最

大值既满足了最大传输率，也满足了不出现码问串扰），奈奎斯特就在采样定理和

无噪声的基础上，提出了奈式准则。而奈奎斯特定理的公式为Cmax=f采样

xlog2N=2fxlog2N（其中f表示带宽）介绍香农定理之前先介绍信噪比，首先要清楚

噪声的影响是相对的，也就是说信号较强，那么噪声的影响就相对较小（两者是同

时变化的，仅考虑两者之一是没有任何意义的），所以求信号的平均功率和噪声的

平均功率之比（记为S/N）才有意义,故引入信噪比=1Oxlogio（S/N）（dB）。引入信

噪比之后就得出香农公式：Cmax二Wxlog2（"S/N）（bil/s）式中，W为信道的带

宽，所以说耍想提高信息的传输速率，应设法提高传输线路的带宽或者设法提高所

传信号的信噪比。

35、CSMA协议可以利用多种监听算法来减小发送冲突的概率，下面关于各种监

听算法的描述中，错误的是（）。I.非坚持型监听算法有利于减少网络空闲时间

口.1一坚持型监听算法有利于减少冲突的概率ni.P—坚持型监听算法无法减少

网络的空闲时间IV.1一坚持型监听算法能够及时抢占信道

A、I>n、w

B、n5m

C、I、U、IV

D、n、w

标准答案：A

知识点解析：按总线争用协议来分类，CSMA有以下3种类型。（1）非坚持

CSMA：一个站点在发送数据帧之前，先要对信道进行检测。如果没有其他站点在

发送数据，则该站点开始发送数据。如果信道被占用，则该站点不会持续监听信

道，而等待一个随机的延迟时间之后再监听。采用随机的监听延迟时间可以减少冲

突的可能性，但其缺点也是很明显的：即使有多个站点有数据要发送，因为此时所

有站点可能都在等待各刍的随机延迟时间，而信道仍然可能处于空闲状态，这样就

使得信道的利用率较为低下，所以I错误。（2）1-坚持CSMA：当一个站点要发送

数据帧时，它就监听信道，判断当前时刻是否有其他站点正在传输数据。如果信道

忙，该站点将一直等待，直至信道空闲。一旦该站点检测到信道空闲，它就立即发

送数据帧，所以W正确。如果产生冲突，则等待一个随机时间再监听。之所以叫

“1-坚持”，是因为当一个站点发现信道空闲的时候，它传输数据帧的概率是1。1-

坚持CSMA的优点是：只要信道空闲，站点就立即发送；它的缺点是：假如有两

个或两个以上的站点有数据要发送，冲突就不可避免，所以口错误。（3）P-坚持

CSMA：P-坚持CSMA是非坚持CSMA和1-坚持CSMA的折中。P-坚持CSMA应

用于划分时槽的信道，其工作过程是：当一个站点要发送数据帧的时候，它先检测

信道。若信道空闲，则该站点按照概率P的可能性发送数据，而有1-P的概率会把

要发送数据帧的任务延迟到下一个时槽。按照这样的规则，若下一个时槽也是空闲

的，则站点同样按照概率P的可能性发送数据，所以说如果处理得当P坚持型监

听算法还是可以减少网络的空闲时间的，所以HI错误。

36、下面的地址中，属于单播地址的是（）。

A、10.3.2.255/24

B、172.31.129.255/18

C、192.168.24.59/30

D、224,100.57.211

标准答案：B

知识点解析：A选项：10.3.2.255/24所表示的子网掩码是11111111

111111111111111100000000,即后8位为主机号,很明显主机号全为1,所以

10.3.2.255/24是子网10.3.2.0的一个广播地址。B选项：与A选项类

似，可以得到主机号为00000111111111.由此可知，172.31.129.255/18是一

个单播IP地址。C选项：与产选项类似，可以得到主机号为11。由此可知，

192.168.24.59/30属于子网192.168.24.56的一个广播地址。D选项：

224.100.57.211为D类IP地址，即组播地址。

37、以下IP地址中，路由器不进行转发的有（）。I.10.1.32.7

H.192.168.32.2EI.172.30.1.3IV.172.35.32.244

A、仅I、n、in

B、仅口、皿

c、仅I、皿、w

D、仅w

标准答案：A

知识点器析：路由器对于专用网地址（私有地址）是不进行转发的。私有地址总结如

下：A类10.0.0.0-10.255.255.255（记住10开头即可）B类

172.16.0.0-172.31.255.255（这个死记）C类192.168.0.0〜

192.168.255.255（记住192.168开头即可）

38、假如一台连接到网络上的计算机的网络配置为：IP地址为136.62.2.55,

子网掩码为255.255.192.0,网关地址为136.62.89.I。这台计算机在网络

中不能与其他主机进行通信，可能是由（）造成的。

A、子网掩码

B、网关地址

C、IP地址

D、其他配置

标准答案：c

知识点露析：首先采用反证法，即假设如果能通信，应该满足什么条件?先要判断

网关地址和IP地址是否在一个网络中。主要看IP地址的第三个字节。2的二进制

是00000010,89的二进制是01011001,因此要使得这两个IP地址属于同一个网

络（只有取第三字节的第一位为子网号，到了第二位已经不同了），子网掩码必须为

255.255.128.0。问题是如果子网掩码为255.255.128.0,说明从主机号只

拿出了1位作为子网号，这样所允许的有效子网数为21-2=0,所以网关地址和IP

地址必须有一个是错的。对于子网掩码为255.255.192.0,其第三个字节192

的二进制表示为11000000,表示的含义是所划分的网络包括2?—2=2个子网，子

网号分别为01和10。因此，两个子网的主机地址范围分别为：

（1）136.62.01000000.1-136.62.01111111.254,即136.62.64.1〜

136.62.127.254o（2）136.62.10000000.1—136.62.10111111.254,即

136.62.128.1-136.62.191.254。注意：加了下画线的01和10表示子网

号，加粗的0和1表示主机号，主机号不能全。和全1,所以从开始到254。综上

所述。可以看出，网关地址包含在里面的，而IP地址不在。

39、RI、R2是一个自治系统中采用RIP路由协议的两个相邻路由器，R1的路由表

如表2-2所示，当R1收到R2发送的（V,D）报文（见表2.3）后，R1更新的3个路

由表项中距离值从上到下依次为（）。

«2-2R1的路由衰*2-3R2发送的报文

日的村络加・用图H的网绢我离

0直称3

200007R220.00.04

500004R230.00.03

A、0、4、3

B、0、4、4

C、0、5、3

D、0、5、4

标准答案：D

知识点解析：当R1收到R2发送的报文后，按照以下规律更新路由表的信息、。（1）

如果R1的路由表没有某项路由记录，则R1在路由表中增加该项，由于要经过R2

转发，所以距离值要在R2提供的距离值基础上加I。（2）如果R1的路由表中的表

项路由记录比R2发送的对应项的距离值加1还要大，则R1在路由表中修改该

项，距离值根据R2提供的值加1。可见，对于路由器距离值为O的直连网络，则

无需进行更新操作，其路由距离保持为0。对比表2-2和表2-3发现，R1到达目的

网络20.0.0.0的距离为7,而表2-3中R2到达目的网络20.0.0.0的距离

为4。由于7>4+1,此时R1经过R2到达目的网络20.0.0.0的路由距离变短

了，所以R1要根据R2提供的数据修改相应路由项的距离值为5。R1到达目的网

络30.0.0.0的距离为4,而表2-3中R2到达目的网络30.0.0.0的距离为

3o由于4=3+1,显然R1经过R2到达目的网络30.0.0.0,并不能得到更短的

路由距离，所以R1无需进行更新操作，将保持该路由条目原来的参数。因此，经

过RIP路由重新计算后的R1路由表3个路由表项距离值从上到下依次为0、5、

4o

40、以下应用层协议采用无连接的是（）。I.SMTPn.FTPm.SNMP

IV.HTTP

A仅

、

B仅

、i、n

c仅

、

仅I>IV

D

、i、m、w

标准答案：A

知识点解析：SMTP、FTP、HTTP等协议使用的都是TCP,所以采用有连接。而

SNMP采用的是UDP,所以采用无连接。表2-9列出了常用的应用层协议与传输

表29常用的应用层侨议与传愉层的议

咫川M梅似传・层的议

DNSUDPmT

nn>UDP

网络看照SNMPVW

斛中通界总议RIPUDP

DI1CPUDP

•HrtrnWKITPTCP

AHIMWWWHTTPTCP

FTFTCP

层协议对应的关系。*2空」TELNETKT

二、综合应用题(本题共27题，每题7.0分，共27

分。)

有一结点的关键字序列F={129,72,180,105,147,96,45,69},散列函数为

H(k)=kmodll,其中k为关键字，散列地址空间为D〜10。要求：

41、画出相应的散列表。当发生冲突时，以线性探测法解决。该散列表的装填因子

是多少?计算在等概率情况下，查找成功和查找不成功时的平均查找长度ASLc

标准答案：采用线性探测法处理冲突建立的散列表如下：H(129)=129modll=8

H(72)=72modll=6H(180)=180mod11=4H(105)=105mod11=6冲突

Hi(105)=(l05+l)mod11=7H(147)=147modH=4冲突Hi(l47)=(147+l)mod11=5

H(96)=96modll=8冲突Hi(96)=(96+l)modl1=9H(45)=45modl1=1

H(69)=69modl1=3综上所述，散列表如表4—7所示。

表4.7雄性除试法处"油窑罐方的数科褰

卜k0I23454k78910

*4569IMM772105129%

愣例内数

1t121212

装填因子

a=8/11oASLSUCC=(5X1+2x3)/8=11/8

ASLUNSUCC=(1+2+1+8+7+64-5+4+3+2+1)/11=40/11

知识点解析：暂无解析

42、画出相应的散列表。当发生冲突时，以链地址法解决。计算在等概率情况下,

查找成功和查找不成功时的平均查找长度ASL(只将与关键字的比较次数计算在内

即可)。

标准答案：采用链地址法处理冲突建立的散列表如卜.: