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

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

一、单选题（本题共40题，每题1.0分，共40分。）

1、一个栈的入栈序列是1,2,3,4,5,则栈的不可能的输出序列是（）。

A、5,4,3,2,1

B、4,5,3,2,1

C、4,3,5,1,2

D、1,2,3,4,5

标准答案：C

知识点解析：此类问题是常见题型。解答的基本原理是：一串数据依次通过一个

栈，并不能保证出栈数据的次序总是倒置，可以产生多种出栈序列。一串数据通过

一个栈后的次序由每个数据之间的进栈、出栈操作序列决定，只有当所有数据“全

部进栈后再全部出栈”才能使数据倒置…事实上，存在一种操作序列——“进栈、出

栈、进栈、出栈……”——可以使数据通过栈后仍然保持次序不变.［解题技巧］将

一组数据入栈后，判断题目备选项中的不可能的出栈顺序，上述这类题目有一个解

题技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素

的序号）的两个元素。

2、设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a［，］为第

一元素，其存储地址为1,每个元素占一个地址空间，则a8,5的地址是（）。

A、13

B、33

C、18

D、40

标准答案：B

知识点解析：这里数组下标从1开始，只存储其下三角形元素，在5的前面有7

行，第1行有1个元素，第2行有2个元素，…，第7行有7个元素，这7行共有

（1+7）x7/2=28个元素，在第8行中，ag.5的前面有4个元素，所以，a8,5前有

28+4=32个元素，其地址为33。

3、在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。

A、n

B、n—1

C、n+1

D、2n

标准答案：C

知识点解析：在一棵具有n个结点的二叉树中，每个结点可有两棵子树，共有2n

个子树。其中二叉树的总分支数等于总结点数减1,即有n—1棵不空的子树。所

以在一棵具有n个结点的二叉树中，所有结点的空子树个数等于n+lo

4、在常用的描述二叉排序树的存储结构中，关键字值最大的结点是（）。

A、左指针一定为空

B、右指针一定为空

C、左右指针均为空

D、左右指针均不为空

标准答案：B

知识点解析：在二叉排序树的存储结构中，每个结点由三部分构成，其中左（或右）

指针指向比结点的关键值小（或大）的结点。关键字值最大的结点位于二叉排序礴的

最右位置上，因此它的右指针一定为空。

5、由权值为9、2、5、7的四个叶子构造一棵哈夫蛙树，该树的带权路径长度为

（）。

A、23

B、37

C、44

D、46

标准答案：C

知识点解析：由权值为9、2、5、7的四个叶子构造的哈夫曼树可如下图所示。

®⑤该树的带权路径长度=9x1+7x2+2x3+5x3=44。［归纳总结］对哈

夫曼树特征的总结：（1）用n个权值（对应n个叶子结点）构造哈夫曼树，共需要n-

1次合并，即哈夫曼树中非叶子结点的总数为n—L总结点个数为2n—l。（2）哈

夫变树中没有度为1的结点，因为非叶子结点都是通过两个结点合并而来。但是，

没有度为1的二叉树并不一定是哈夫曼树。（3）用n个权值（对应n个叶子结点）构造

的哈夫曼树，形态并不是唯一的。建立哈夫曼树的过程中有以下三种常见的错

误：（1）在合并中不是选取根结点权值最小的两棵二叉树（包括已合并的和未合并

的），而是选取未合并的根结点权值最小的一棵二叉树与己经合并的二叉树合并。

⑵每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树。（3）有时没有

严格按照哈夫曼算法也两造出带权路径长度与哈夫曼树相同的二叉树，但那只是巧

合，没有规律性，而没有规律性的解法不利于用计算机进行处埋。

6、若一个具有n个结点、k条边的非连通无向图是一个森林（n>k）,则该森林中必

有树的数目是（）。

A、k

B、n

C、n—k

D、n+k

标准答案：C

知识点解析：因为一棵具有n个顶点的树有n-l条边，因此设题目中的森林有m

棵树，每棵树具有顶点数为Vi(lgiWm),则V1+V2+…Vm=N&(V|-1)+"2—1)

+...(Vm—1)=K,所以，2=m+ko

7、采用邻接表存储的图的广度优先遍历算法类似于树的()。

A、中根遍历

B、先根遍历

C、后根遍历

D、按层次遍历

标准答案：D

知识点解析：深度优先嗖索遍历类似于树的先根遍历，是树的先根遍历的推广。广

度优先搜索遍历类似于树的按层次遍历的过程。或者说，树的先根遍历是一种深度

优先搜索策略，树的层次遍历是一种广度优先搜索策略。

8、在有向图G的拓扑产列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现

的是()。

A、G中有弧i,Vj>

B、G中有一条从Vi到Vj的路径

C、G中没有弧i,Vj>

D、G中有一条从Vi到Vj的路径

标准答案：D

知识点解析：选项A、B、C都是有可能出现的，但是选项D是不可能出现的，因

为若是G中有一条从V到Vi的路杼，则在图的拓扑序列中顶点Vi应该在顶点Vi

之前。

9、假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，至少要

进行的探查次数是()。

A、k-1

B、k

C、k+1

D、k(k+l)/2

标准答案：D

知识点解析：假设有k个关键字互为同义词，若用线性探查法把这k个关键字存

入，探查次数最少的情况是第1个关键字通过1次比较后插入，第2个关键字通过

2次比较后插入，……，第k个关键字通过k次比较后插入。总的比较次数=1+2

+......+k=k(k+l)/2。

10、下列序列中，满足堆定义的是（）。

A、（100,86,48,73,35,39,42,57,66,21）

B、（12,70,33,65,24,56,48,92,86,33）

C、（103,97,56,38,66,23,42,12,30,52,6,26）

D、（5,56,20,23,40,38,29,61,36,76,28,100）

标准答案：A

知识点解析：依据堆的定义，将选项中的每个数列分别看成是一棵完全二叉树，则

堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左/

右子树不空时，根结点的值小于（或大于）左/右子树根结点的值。

11、对于一个长度为n的任意表进行排序，至少需要进行的比较次数是（）。

A、O（n）

B、O（n2）

C^0（log

D、O（nlogn）

标准答案：D

知识点解析：在排序过程中，每次比较会有两种情况出现，若整个排序过程中至少

需要t次比较，则显然会有21种情况，由于n个记录总共有出种不同的排列，因而

必须有n!种不同的比较路径，于是有：2（＞n!,即Glog2（n!）。因为

Iog2（n!）-nlog2n,所以Gnlog2n。

12、哈佛（Harvard）结构的基本特点是（）。

A、采用多指令流单数据流

B、程序和数据在不同的存储空间

C、堆栈操作

D、存储器按内容选择地址

标准答案：B

知识点解析：哈佛结构的指令和数据是完全分开的，存储器分为两部分，一个是程

序存储器，用来存放指令，另一个是数据存储器，用来存放数据。［归纳总结］根据

程序（指令序列）和数据的存放形式，存储器设计思想又可以分为冯・诺依曼结构和哈

佛结构。冯・诺依曼结构的存储器设计是指令和数据是不加区别混合存储在同一个

存储器中，共享数据总线；哈佛结构的存储器设计是指令和数据是完全分开的，存

储器分为两部分，一个是程序存储器，用来存放指令，另一个是数据存储器，用来

存放数据。在冯.诺依曼结构中不能同时取指令和取操作数，而哈佛结构允许同时

获取指令字（来自程序存储器）和操作数（来自数据存储器）。

13、若二进制定点小数真值是一0.1101,机器中表示为1.0010,则该数采用的

编码方法是（）。

A、原码

B、补码

C、反码

D、移码

标准答案：C

知识点解析：真值一0.1101,对应的原码表示为1.1101,补码表示为1.0011,

反码表示为1.0010c移码通常用于表示阶码，不用来表示定点小数。［归纳总结］

对于负数，原码、补码和反码各有不同的表示形式。［解题技巧］由于真值是定点小

数，不能用移码表示，所以可立即排除掉选项D。接下来写出真值对应的原码、补

码和反码，即可得出答案。

14、描述流水线CPU基本概念中，正确表述的句子是（）。

A、流水线CPU是以空间并行性为原理构造的处理

B、流水线CPU一定是RISC机器

C、流水线CPU一定是多媒体CPU

D、流水线CPU是一种非常经济而实用的时间并行技术

标准答案：D

知识点解析：在4个选项中唯有选项D是正确的。选项A是指超标量处理机。

Rise机器一定采用流水线技术，而流水线CPU不一定就是RIsC机器。流水线

CPU也不一定是多媒体CPU。［归纳总结］超标量处理机采用的是空间并行性，流

水线处理机采用的是时间并行性。

15、原码乘法时，符号位单独处理，乘积的符号是（）。

A、两个操作数符号相“与”

B、两个操作数符号相“或”

C、两个操作数符号相“异或”

D、两个操作数中绝对值较大数的符号

标准答案：C

知识点解析：原码的符号位为“1”表示负数，为“0”表示正数。原码乘法时，符号位

单独处理，乘积的符号是两个操作数符号相“异或”，同号为正，异号为负。［归纳

总结］凡是原码运算.不论加减乘除,符号位都单独处理•其中乘除运算的结果符

号由参加运算的两个操作数符号“异或”得到。

16、页式存储系统的逻辑地址是由页号和页内地址两部分组成，地址变换过程如下

图所示。假定页面的大小为8K,图中所示的十进制逻辑地址9612经过地址变换

校—■一■*―

――［/-触］［蝴21

J5母筋奔於另

j13~\*理**

后,形成的物理地址a（十进制）是（）。IT?

A、42380

B、25996

C、9612

D、8192

标准答案：B

知识点解析：由于页面大小为8K,则十进制逻辑地址9612处于第1虚页中，页内

地址一1420,其对应的实页为第3页，故a=3x8192+1420=25996。［归纳总结］

具体的计算公式有：虚页号=|虚地址/页面大小|页内地址=虚地址一虚页号x页

面大小主存实地址=实页号x页面大小+页内位移量页式虚拟存储器中的页表的

每一行记录了与某个虚页对应的若干信息，包括虚页号、装入位和实页号等。页表

基址寄存器和虚页号拼接成页表索引地址。根据这个索引地址可读到一个页表信息

字，然后检测页表信息字中装入位的状态。若装入位为“1”，表示该页面已在主存

中，将对应的实页号与虚地址中的页内地址相拼接就得到了完整的实地址；若装入

位为“0”,表示该页面不在主存中，于是要启动I/O系统，把该页从辅存中调入主

存后再供CPU使用。［解题技巧］首先，根据题目那给出的虚地址可以计算出虚页

号和页内地址，然后根据所求出的虚页号查页表找出实页号，最后将实页号拼上页

内地址得到相应的主存地址。

17、在指令系统的各种寻址方式中，获取操作数最快的方式是()。

A、直接寻址

B、立即寻址

C、寄存器寻址

D、间接寻址

标准答案：B

知识点露析：立即寻址是一种特殊的寻址方式，指令中在操作码字段后面的部分不

是通常意义上的地址码，而是操作数本身，也就是说数据就包含在指令中，只要取

出指令，也就取出了可以立即使用的操作数，不必再次访问存储器，从而提高了指

令的执行速度。［归纳总结］所谓寻址，指的是寻找操作数的地址或下一条将要执行

的指令地址。各种不同的寻址方式获取操作数的速度是不相同的，在这四种寻址方

式中，获取操作数的速度由快至慢依次为立即寻址、寄存器寻址、直接寻址、间接

寻址。

18、在计算机体系结构中，cPU内部包括程序计数器PC、存储器数据寄存器

MI)R、指令寄存器IR和存储器地址寄存器MAR等。若CPU要执行的指令为：

MOVR0,#100(即将数值100传送到寄存器R0中)，则CPU首先要完成的操作是

()o

A、100—R0

B、IOOTMDR

C、PC一MAR

D、PCTIR

标准答案：c

知识点解析：无论运行什么类型的指令，CPU首先需要取指令，取指令阶段的第

一个操作就是将指令地址(程序计数器PC中的内容)送往存储器地址寄存器。［归纳

总结］取指周期完成的微操作序列是公共的操作，与具体指令无关，取指公操价如

下：(1)将程序计数器PC中的内容送至存储器地址寄存器MAR,记作

(PC)TMAR；(2)向主存发读命令，记作Read：(3)从主存中取出的指令送到存储

器数据寄存：器MDR,记作M（MAR）-MDR；（4）将MDR的内容送至指令寄存

器IR中，记作（MDR）TIR；（5）将PC的内容递增，为取下一条指令做好准备，记

作（PC）+1-PC。［解题技巧］题干中虽然给出了一条具体的指令“MOVRO,

#100"，实际上CPU首先要完成的操作是取指令，与具体指令是没有关系的。

19、在微指令的编码方式中，若微命令数相同，下列叙述中正确的是（）。I.直接

控制方式与编码控制方式的微指令长度相等D.最短编码控制和直接控制方式不

影响微指令字长m.编码控制方式的微指令比直接控制方式的微指令短w.直接

控制的微指令比字段编码的微指令长V.字段直接编码的微指令与字段间接编码的

微指令长度相等VI.字段间接编码的微指令比字段直接编码的微指令长

A、in和w

B、I和m

c、口和川

D、m、w和VI

标准答案：A

知识点解析：微指令的操作控制字段可分为直接控制法、最短编码法和字段编码

法，字段编码法中又可以进一步分为字段直接编码法和字段间接编码法。若微命令

数相同，微指令操作控制字段的长度由短至长依次为：最短编码T字段间接编码T

字段直接编码一直接控制。操作控制字段短则相应的微指令字长就短。［归纳总结］

直接控制法即每个独立的二进制位代表一个微命令，该位为“1”表示这个微命令有

效，为“0”则表示这个微命令无效。最短编码法将所有的微命令统一编码，每条微

指令只定义一个微命令。字段编码法是前述两种编码法的一个折中的方法，将操作

控制字段分为若干组，组内采用最短编码法，组与组之间采用直接控制法。在字

段编码法中，操作控制字段的分组并非是任意的，必须要遵循如下的原则：（1）应

把互斥性的微命令分在同一组内，兼容性的微命令分在不同组内。这样不仅有助于

提高信息的利用率，缩短微指令字长，而且有助于充分利用硬件所具有的并行性，

加快执行的速度。（2）应与数据通路结构相适应。（3）每个小组中包含的信息位不能

太多，否则将增加译码线路的复杂性和译码时间。（4）一般每个小组还要留出一个

状态，表示本组不发出任何微命令。因此当某组的长度为3位时，最多只能表示7

个互斥的微命令，通常用000表示不操作。

20、下列计算机总线属于串行总线的是（）。

A、PCI

B、1394

C、EISA

D、ISA

标准答案：B

知识点解析：1394是高性能的串行总线。［归纳总结IIEEE—1394是由IEEE标准

委员会发布的，它的最初版本传输速率为200.Mbps,高版本有望支持1600Mbps

的传输速率，甚至可达到3200Mbps。IEEE—1394构建在菊花链或树状的拓扑结

构上的，它支持63个节点，每个节点可以支持多达16台设备的菊花链。最新的

高性能外部总线设计的趋势是使用串行结构，这样可以通过一根导线一次发送一位

数据，而无须担心数据的到达时间，如IEEE—1394端口（使用高速串行技术）支持

的传输速率高达400Mbps（约50MB/s）,USB2.0支持的传输速率可以为

480Mbps（约60MB/s）。［解题技巧］选项A、C、D均属于并行总线。

21、某数码相机内置128MB的存储空间，拍摄分辨率设定为1600x1200像素，颜

色深度为24位，若不采用压缩存储技术，使用内部存储器最多可以存储的照片数

是（）。

A、12

B、25

C、13

D、23

标准答案：D

知识点解析：颜色深度为24位（3个字节），每张照片的存储量为

1600x1200x3即5.5MB,128MB/5.5MB=23.3,所以内置的存储空间最多可

存储23张照片。［归纳总结］数码相机内部存储器存放照片数的多少与照片的分辨

率和颜色数有关。

22、中断向量表中保存的是（）。

A、被中断程序的返回地址

B、中断服务程序入口地址

C、中断优先级

D、中断源编码

标准答案：B

知识点解析：中断向量表是用来存放中断服务程序的人口地址的。［归纳总结］许多

计算机中在主存的特定位置设置有中断向量表，在中断向量表的相关单元中存放着

各级中断服务程序的入口地址。中断源给出的向量地址是中断向量表的指针，也就

是中断服务程序入口地址的地址。由向量地址指向一个中断向量表，从中断向量表

的相应单元中再取出中断服务程序的入口地址C

23、对于设计实时操作系统，不是其设计目标的是（）。

A、安全可靠

B、处理机效率

C、及时响应输入

D、快速处理请求

标准答案：B

知识点解析：本题考查实时操作系统的设计目标。实时操作系统要求能对用户的请

求在规定的时间内完成，同时需要保证进程运行的安全性和高可靠性。而处理机的

效率不是实时操作系统没计所关心的。

24、并发进程在运行时，其推进的相对速度是（）。

A、由进程的程序结构决定

B、由进程自己的代码控制

C、与进程调度策略有关

D、在进程创建时确定的

标准答案：C

知识点解析：在进程的一次运行过程中，其代码的执行序列是确定的，即使有循环

或转移，对于进程来讲，其运行的轨迹也是确定的，所以对于这样一个确定的运行

轨迹，进程自身是可以控制自身前进或停止的，例如可以休眠10秒再唤醒等，但

是，当这样的进程存在于一个并发系统中时，这种确定性就被打破了。由于系统中

存在有大量的可运行的进程，操作系统为了提高计算机的效率，会根据用户的需求

和系统资源的数量来自动地进行调度和切换，以保证系统高效地运行。此时，进程

由于被调度，打破了原来的固有执行速度，走走停停，因此，进程的相对速度就不

受进程自己的控制，而是取决于进程调度的策略。不确定性也是并发系统的一个特

征。

25、两个旅行社甲和已为旅客到某航空公司订飞机票，形成互斥资源的是（）。

A、旅行社

B、航空公司

C、飞机票

D、旅行社与航空公司

标准答案：C

知识点解析：本题考查互斥资源的问题，一张飞机票不能售给不同的旅客，因此飞

机票是互斥资源，其它因素只是为完成飞机票订票的中间过程，与互斥资源无关。

26、在进程通信中，消息的一般形式为四个部分组成。是（）。

A、发送进程名、接收进程名、消息标示符、消息正文

B、发送进程名、消息标示符、消息长度、消息正文

C、发送进程名、接收进程名、消息长度、消息当前状态

D、发送进程名、接收进程名、消息长度、消息正文

标准答案：D

知识点解析：在消息传递系统中，进程间的数据交换是以消息（在计算机网络中又

称为报文）为单位的。消息的一般结构形式有发送进程名、接收进程名、消息长

度、消息正文。故正确答案为选项D。

27、某计算机系统中内存保护采用基址、限长寄存器的疗法来实现，那么，判断是

否越界的判别式是（）。

A、0W被访问的逻辑地让（限长寄存器的内容

B、0S被访问的逻辑地址S限长寄存器的内容

C、0W被访问的物理地址＜限长寄存器的内容

D、0W被访问的物理地址W限长寄存器的内容

标准答案：A

知识点解析：本题考查存储保护的方法。考查基址、限长寄存器方式下是如何进行

越界判断的。在基址、限长寄存器的保护方式下，系统为每个并发进程设置一个基

址寄存器和一个限长寄存器，限长寄存器保存的是进程的长度，所以有关系式：逻

辑地址〈进程长度。在此注意，地址一般是从0开始，故需要包含。一般，对于长

度为100的区域，地址为从0〜99。因此选A。

28、在某个计算机系统中，内存的分配采用按需调页的方式，测得当前CPU的利

用率为8%,硬盘交换空间的利用率为55%,硬盘的繁忙率为97%,其它设备的

利用率可以忽略不计，由此断定系统发生异常，此异常可能会是（），解决办法是

（）oI.Bclady现象；H.抖动；IH.死锁；W.饥饿；V.加大交换空间容

量；VI.增加内存容量；VD.增加CPU数量；VID.增加并发进程数；

A、I和V

B、II和VI

C、HI和皿

D、W和皿

标准答案：B

知识点解析：本题考查按需调页下提高系统效率的措施。首先判断系统异常是属于

什么异常，从测试数据看，CPU不忙，交换空问也不满，就是硬盘的10非常繁

忙，所以不是交换空间不够，系统也没有死锁，主要瓶颈在内外存交换上，因此可

能的最大情况就是抖动，即由于内存紧缺，并发进程数多，采用按需调页而引起的

频繁的换入换出作业。对于抖动问题的解决，最好的办法是增加内存，或减少并发

进程数，单纯地增大交於分区的大小或增加CPU数量或提高CPU处理能力都没有

解决根本问题。

29、若用100个双字（字长32位）组成的位示图管理内存，假定用户归还一个块号

为240的内存块时，它对应的位示图的位置是（）。

A、字号为6,位号为16

B、字号为7,位号为16

C、字号为6,位号为14

D、字号为7,位号为14

标准答案：B

知识点解析：位示图也祢为示位图，是利用二进制的一位来表示内存或磁盘中一个

存储块的使用情况。当其值为“0”时，表示对应的块空闲；为“1”时，表示己分配。

反之亦然。内存或磁盘上的所有块都有一个二进制位与之对应，这样，由所有块所

对应的位构成一个集合，称为位示图。计算方法：字号i=INT（240/32）=7字内

位置j=MOD（240/32）=16

30、通常对文件系统来说，文件名和文件属性可以找到的地方是（）。

A、目录

B、索引

C、字典

D、作业控制块

标准答案：A

知识点解析：在文件系统中，为每个文件建立一个目录（或称文件目录或目录项），

文件目录记录文件的名字，文件长度和文件存放的外存地址以及文件属性、文件创

建时间日期等信息。文件目录在大部分文件系统中乂成为文件控制块，即FCB。

31、为保证文件的安全，操作系统一般采用多种方式来保护文件。为防止未经授权

对文件的访问而造成的篡改或破坏，所采取的方法是（）。

A、访问控制列表

B、转储备份

C、加密数据

D、口令保护

标准答案：A

知识点露析：本题考查的是文件的保护。系统中的文件有些是只能由文件拥有者使

用，有些是可以共享的，独享的文件需要采取保护措施，防止非法用户存取文件。

保护文件的方法可以有多种，定时转储备份可以防止设备故障造成的文件损坏，U

令保护和加密数据可以保护文件被非法窃取时不会泄密，而对于授权用户的使用，

一般采用访问控制列表来对文件的权限进行分配，从而保证文件的安全。

32、CPU输出数据的速度远远高于打印机的打印速度，为解决这一矛盾，可采用

的技术是（）.

A、并行技术

B、通道技术

C、缓冲技术

D、虚存技术

标准答案：C

知识点解析：缓冲技术的引入主要解决cPu速度和外设速度不匹配的问题，它同时

减少了通道数量上的占用，提高了CPU、10和通道的并发性，减少了中断的次

数，放宽了CPU对中断响应的时间要求，例如打印、文件访问，网络收发等场

合.均要用到缓冲技术.

33、在不同网络节点的对等层之间通信需要的是（），

A、模块接口

B、对等层协议

C、电信号

D、传输介质

标准答案：B

知识点解析：本题考查计算机网络体系结构，注意对等层是指在计算机网络协议层

次中，将数据直接传递给对方的任何两个同样的层次，因此对等层之间通信必须需

要对等层之间的协议，这里选项A是相邻层之问通信所必需的，选项C和D属于

物理层，答案是B。

34、关于数据交换，下列叙述不正确的是（）。

A、线路交换面向连接

B、分组交换比报文交换具有更好的网络响应速度

C、报文交换无存储转发过程

D、分组交换有存储转发过程

标准答案：C

知识点解析：该题考查数据交换的原理，要明确报文是一份完整的信息，而分组是

报文分组的简称，乂叫信息包，将报文划分为若干格式化信息单位作为网络层的数

据传输单元。分组交换方式：将一份完整的报文划分为若干组，每个分组独立的从

源节点发送到目的节点，目的节点收到这些分组后，再组装成源报文。其特点是化

整为零，即将完整的较长的报文划分为较小的分组，以分组单位传输数据。优点是

减少节点缓冲区容量，并有利于差错控制。而存储转发是指每个节点均设有缓冲

区，分组到达某节点后，先存储在缓冲区中，等待输出链路空闲时在转发到下一个

节点。本题中面向连接的只有线路交换，存储转发只有分组和报文，由于分组交

换的灵活性，使其具有更好的响应速度，因此答案是C。

35、当DHCP客户计算机第一次启动或初始化1P时，广播发送给本地子网的消息

是()。

A、DHCPDISCOVER

B、DHCPREQUEST

C、DHCPOFFER

D、DHCPACK

标准答案：A

知识点解析：本题考查DHCP协议的工作原理，需要IP地址的主机在启动时就向

DHCP服务器广播发送发现报文(DHCPDISCOVER),这时该主机就成为DHCP客

户。本地网络上所有主机都能收到此广播报文，但只有DHCP服务器才回答此广

播报文。DHCP服务器先在其数据库中查找该计算机的配置信息。若找到，则返回

找到的信息。若找不到，则从服务器的IP地址池(addresspool)中取一个地址分配

给该计算机。DHCP服务器的回答报文叫做提供报文(DHCPOFFER)。客户计算机

初始化IP的时候，首先要查找DHCP服务器，因此要发送的消息是DHCP

DISCOVER,答案是A。

36、网络由6个路由器互连而成，路由器之间的链路费用如下图所示，从PC机到

服务器的最短路径和通路费用是()。

A、1—3—6,7

1—>4—>5—>6»4

C、1—4—3-6,6

D、12—4—5—6,7

标准答案：B

知识点解析：本题考查链路状态路由算法，将网络看成连通图。每条链路以其“费

用''为权值。通过Dijkstra最短路径算法求出任意两个节点之间的最短距离，本题

中，就是以PC机所连接的路由器1为根节点，计算到达其他网络的最短路径，也

就是费用最小的路径，这样可以直接从选项中得出答案，是B。

37、一个B类网络的子网掩码为255.255.252.0,则该B类网络的主机数目是

()o

A、2046

B、1022

C、510

D、128

标准答案：D

知识点解析：本题考查IPv4字网划分，首先明确B类网络的掩码是

255.255.0.0,而192的二进制是11111100,由此可知可划分？6=64个子网，

每个子网的主机数为22—2=2,因此该B类网络的主机数目是64x2=128,因此

答案是D。

38、在TCP报文段的报头中，窗口字段的作用是

A、报头中32bit字节的数量

B、说明对■方端口的数量

C、控制对方的发送流量

D、说明网络的负荷能力

标准答案：C

知识点》析：本题考查TCP报文段的作用窗口大小：用于流量控制。表示在确认

了的字节之后还可以发送多少字节。窗口大小也允许为0,表示它已经收到了包括

确认号减1在内的所有数据段，但接收方急需暂停接受数据。对于窗口字段，占2

个字节，用来控制对方发送的数据量，并不能说明网络的负荷能力，因此答案是

Co

39、关于以太网交换机，下面的论述中不正确的是()。

A、交换机工作在数据链路层

B、交换机的每个端口形成一个冲突域

C、交换机支持多端口同时收发数据

D、交换机是一种多端口中继器

标准答案：D

知识点解析：本题考查交换机的工作原理和特性，交换机是工作与数据链路层的网

络设备，每个端口是独立的冲突域，交换机的交换结构保证了多端口同时进行数据

交换，多端口的中继器可以认为是集线器，其所有端口处于同一个冲突域内，因此

答案为D。

40、一台主机要解析www.abc.edu.cn的IP地址，如果这台主机配置的域名服

务器为202.120.66.68,因特网顶级域名服务器为11.2.8.6,而存储

WWW.abc.edu.cn与其IP地址对应关系的域名服务器为20的113.16.10,那

么这台主机解析该域名通常首先查询的服务器是（），

A、202.120.66.68域名服务器

B>11.2.8.6域名服务器

C、202.113.16.10域名服务器

D、不能确定，可从这三个域名服务器中任选一个

标准答案：A

知识点解析：本题考查域名解析的过程，一个主机发出DNS查询报文时，这个查

询报文首先被送往该主机的本地域名服务器。当本地域名服务器不能立即回答某个

主机的查询时，该本地域名服务器就以DNS客户的身份向某一根域名服务器查

询。若根域名服务器也没有该主机的信息时（但此时根域名服务器一定知道该主机

的授权域名服务器的IP地址），有两种做法：（1）递归查询：根域名服务器向该主

机的授权域名服务器发送DNS查询报文，查询结果再逐级返回给原主机；（2）递归

与迭代相结合的方法：取域名服务器把授权域名服务器的IP地址返回给本地域名

服务器，由本地域名服务器再去查询。无论是递归方式，还是迭代方式，主机进

行域名解析的第一步都是向自己的本地域名服务器发起请求，因此答案为Ao

二、综合应用题（本题共7题，每题7.0分，共7分0）

41、采用散列函数H（k）=3xkMOD13并用线性探测开放地址法处理冲突，在数列

地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51；（1）构

造散列表（画示意图）：（2）装填因子：（3）等概率情况下查找成功的平均查找长度：

⑷等概率情况卜查找失败的平均查找长度。

标准答案：（1）各关键字的散列函数值如下：

下标0it1iS67S101112

key224153llI6751关・7225314167uSI

H(key)163803610111212111

⑵装填因子=关键字总数/表长=9/13=0.7。（3）设查找成功在每个关键字上是

等概率的，则查找每个关键字的概率为1/9,各关键字的探查次数分别为：

所以有，ASLwcc=(l+1+1+2+1+2+1

+l+l）/9=ll/9o（4）设不成功的查找在每个地址上发生的概率相同，平均概率

关键字为例，若该关键字不在散列表中，需要将它与从位置3开始向后直至位置5

的关键字相比较，由于关键字5的关键字为空，所以不再向后比较，共比较3次，

其他的类推得到。所以有，ASLunsucc=（3+2+1+3+2+1+4+3+2+1+2+1+

4）/13=29/13o

知识点解析：用线性探测法解决冲突构造散列表，并对查找性能进行分析，具体解

题步骤如上。

42、假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第

一条最长的路径长度以及此路径上各结点的值。

标准答案：voidLongpath（BiTrccb,TElcmTypcpath[],intpathlcn,TElcmTypc

longpath[],intlongpalhlen）{inti；if（b==NULL）（if（pathlen-longpathlen）{//若

当前路径更长，将路径保存在longpath中for（i=pa【hlen—1；i>=0：i-----）

iongpath[i]=path[i]；longpathlen=pathlen；}}else{path[：pathlen]=b—>data；

//将当前结点放入路径中palhlen++；//路径长度增ILongpath（b—>.Ichii

d.pat.h,pathlen,longpath,longpathlen）；//递归扫描左子树Longpath（b

—>rchild.pat.h,pathlen,longpath,longpathlen）；//递归扫描右子树path]en

一一；//环境恢复}}

知识点解析：采用path数组保存扫描到当前结点的路径，pathlen保存扫描到当前

结点的路径长度，longpath数组保存最长的路径，longpathlen保存最长路径长度。

当b为空时，表示当前扫描的一个分支已扫描完毕，将pathlen与longpalhlen进行

比较，将较长路径及路径长度分别保存在longpath和longpathlen中。

43、某微机的寻址范围为64KB,其存储器选择器信号为M,接有8片8KB的存

储器，试完成下列问题。（1）画出选片译码逻辑图。（2）写出每片RAM的寻址范

围。（3）如果运行时发现不论往哪片存储器存放8KB数据，以4000H起始地址的存

储芯片都有与之相同的数据，分析故障原因。（4）如果运行时发现以0000H为起始

地址的一片存储芯片不能读写，分析故障原因。（5）若发现译码器中的地址线A”

与CPU断线，并搭接到低电平的故障，问后果如何？（6）如果发现只能对第1-4片

RAM进行读写，试分析故障原因。

LAl

1•小低言爰：也nm旧疼粗刈「因"小。-———匕（2）8片RAM的寻址

范围分别是：0000H〜IFFFH、2000H〜3FFFH、4000H〜5FFFH、6000H〜

7FFFH、8000H〜9FFFH、A000H〜BFFFH、C000H〜DFfFH和E000H〜FFFFH。

⑶说明译码器有误，凶输出始终为低。因该输出接至第3片RAM的

端，该片对应的地址范围是4000H〜5FFFH,故不沦往哪片RAM存放8K数据，

该存储芯片始终被选中，所以都有与之相同的数据。（4）说明yO输出始终为高。因

RAM的片选信号时低比平有效，故用作片选信号的存储芯片（对应0000H〜1FFFH

地址范围）不能读写，而其他芯片可以读写。（5）若发现A］3与CPU断线，并搭接

到低电平的故障，则信号均不可能输出0,故第2、4、6、8片RAM始终不被选

中。（6）说明译码器的C输入端始终为低，可以检查一下A］5是否搭接到低电平

上。

知识点解析：（3）〜（6）中出现的问题都是由于译码器连接上的问题（短路或断路）造成

的，使得某些片选信号始终被选中或始终不被选中。［归纳总结］全译码法将除片内

寻址外的全部高位地址线都作为地址译码器的输入，译码器的输出作为各芯片的片

选信号，将它们分别接到存储芯片的片选端，以实现对存储芯片的选择。全译码法

的优点是每片（或组）芯片的地址范围是唯一确定的，而日.是连续的，也便于扩展，

不会产生地址重叠的存储区。［解题技巧］首先确定片选电路以及各个芯片的地址分

配，然后分析各种出错情况，分别找出出错的原因。

44、某模型机的通路结沟如下图所示，用寄存器传送语句（如PC-MAR）,拟出下

列指令从读取到执行的完整流程。（1）数据传送指令MOVX（Ro）,Y（Ri）,源和目

的操作数地址均采用变址寻址，第1个参数X为源操作数的形式地址，第2个参

数为目的操作数的形式地址，分别位于指令的第2个和第3个存储字。（2）数据求

反指令COM—（Ro）,采用自减型寄存器间接寻址，结果送回自减后的地由E单

告耳禽］f一"»~~I-->1~K"""MDR

CRTD具禺

标准答案：（l）MOVX（Ro）,Y（R。①PC—MAR,Read；取指令②M—MDR—IR

③PC+ITPC④PCTMAR,Read；取源操作数形式地址&M—MDR—C@PC

+1-PC⑦C+Ro—MAR,Read；形成源操作数有效地址，并取源操作数

⑧M—MDR—C；源操作数暂存C中⑨PC—MAR,Read；取目的操作数形式地

址⑩MTMDR—D⑩PC+1-PC⑩D+Ri-MAR；形成目的操作数有效地址

⑩C-MDR；将源操作数送存储器数据寄存器⑩MDR-M,write；将源操作数

写入目的有效地址中（2jCOM-（Ro）①PC—MAR,Read；取指令

②M—MDR—IR③PC+1-PC④Ro-l-Ro，RO-1->MAR,Read；修改Ro的

内容（源和0的操作数地址）⑤M-MDR—D；取出源操作数⑥D—MDR；将源操

作数取反⑦MDR—M,write；写入目的地址中

知识点解析：数据传送指令占3个字，第1个字是操作码和寄存器编号；第2个字

是参数X,为源操作数的形式地址；第3个字是参数Y,为目的操作数的形式地

址，源和目的操作数地址均采用变址寻址，指令的含义是：（（Ro）+X）一（RD+Y。

求反指令仅占1个字，自减型寄存器寻址是先修改寄存器的内容（一1）,再取数。

［归纳总结］（l）MOVX（Ro）,Y（R］）指令执行流程中的前3步是完成取指令的操作公

操作；接下来的5步是去主存中取源操作数，把取出的数放在暂存器C中；然后

的4步是形成目的操作数地址；最后2步完成传送操作。(2)COM-(Ro)指令执行

流程中的前3步是取指令公操作；接下来的2步是去主存中取源操作数，把取出的

数放在暂存器D中；然后将D的内容取反，写入目的地址中。［解题技巧］根据数

据通路，写出指令执行的微操作序列。使用寄存器传送语句(如PC-MAR),比较

直观。

45、某工厂有一个仓库可以存放甲、乙两种零部件，甲零件可以存放m件，乙零

件可以存放n件，车间A专门生产甲零件，每次1件，每生产1件存放进仓库1

件；车间B专门生产零件乙，每次1件，每生产1件存放进仓库1件。总装车间每

次从仓库取出2件甲零件、1件乙零件组装成成品，车间A、B和总装车间必须互

斥进入仓库。当仓库内甲、乙零件分别达到m、n件时，车间A、B分别停止生

产。而仓库内任何一种零件为。时，总装车间停产。根据上述规则，请利用信号量

机制，没计一个可以让车间A、B和总装车间协调运转的程序，并说明各个信号量

的意义，用类c语言写出整个过程。

标准答案：设信号量mutex用于车间的互斥,positionA>positionBpartA,partB

为资源信号量，分别表示仓库中零件甲、乙的空位数和满位数，positionA+partA

=m；positionB4-partB=n；编程如下：deftypeintsem叩hore；//定义信号量

semaphoremutex=l；//进入仓库的互斥信号量semaphorepositionA=m,

positionB=n；//车间A、B生产的零件甲、乙存放的位置semaphorepartA=

0,partB=0；//零件甲、乙的信号量voidworkshopA()//车间A进程

｛while(TRUE)//并发调度｛intitem；//仓库货架指针item=produce(甲)：/

/生产零件甲P(positior.A)；//查有无零件甲的货位P(mutex)；//仓库可以进

入吗？puton(item)；//放置零件甲V(mutex)；//释放仓库互斥量V(partA)；

//增加零件甲的资源信号量｝//离开｝voidworkshopB()//车间B进程

｛while(TRUE)//并发调度(intitem；//仓库货架指针item=produce(乙):/

/生产零件乙P(positionB)；//查有无零件乙的货位P(mutex)；//仓库可以进

入吗？puton(itcm)；//放置零件乙V(mutex)；//释放仓库互斥量V(panB)；

//增加零件乙的资源信号量)//离开)voidassembleshop()//总装车间进程

(while(TR