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

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

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

1、若已知一个栈的入栈序列是1,2,3……n,其输出序列为pl,p2,

p3....pn,若pl=n,则pi是（）。

A、i

B、n-i

C、n-i+1

D^不确定

标准答案：C

知识点。析：本题中所叙述的情况，栈的输出序列一定是输入序列的逆序。

2、将一个A[1……100,I……100]的三对角矩阵，按行优先存入一维数组

R[l.-29用中，A中元素A66.65（即该元素下标i=66,j=65）,在R数组中的位置k

为（）。

A、198

B、195

C、197

D、196

标准答案：B

知识点解析：根据三对角对阵压缩方法，将A[l..n][l..n]压缩至B[0..3n

一3]时，aij与bk的对应关系为:k=2i+j-3；将A[L.n][l..n]压缩至

B[1..3n一2]时，叼与bk的对应关系为：k-2i+j—2；根据题目，A中元素

A66,65，在B数组中的位置k为：k=2i+j--2=2x66+65—2=195

3、查找效率最高的二叉排序树是（）。

A、所有结点的左子树都为空的二叉排序树

B、所有结点的右子树都为空的二叉排序树

C、平衡二叉树

D、没有左子树的二叉排序树

标准答案：C

知识点解析：二叉排序树的查找效率取决于二叉排序树的深度，对于结点个数相同

的二叉排序树，平衡二叉树的深度最小。

4、一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0,则该树的

结点数是（）。

A、2k-1-l

B、2kl

C、2k-,+l

D、2卜一1

标准答案：D

知识点解析：一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0,

也就是说每个非终端结点都有左子树和右子树且高度相等。因此，这样的平衡二叉

树即为满二叉树，而高度为k的满二叉树的结点数是2k—1。

5、以下叙述正确的是（LI.对有向图G,如果以任一顶点出发讲行一次深度优先

或广度优先搜索能访问到每个顶点，则该图一定是完全图U.连通图的广度优先

搜索中一般要采用队列来暂存访问过的顶点m.图的深度优先搜索中一般要采用

栈来暂存访问过的顶点

A、I、n

B、口、m

c、I、m

D、I、n、m

标准答案：B

知识点解析：i叙述是错误的，因为如果有向图构成双向有向环时，则从任一顶点

出发均能访问到每个顶点，但该图却非完全图。口、ni叙述显然是正确的。

6、一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中零元素的

个数是（）。

A、e

B、2e

C>n2—e

D、n2—2e-

标准答案：D

知识点解析：由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，即图中的一条

边对应邻接矩阵的两个非零元素。因此一个含有n个顶点和e条边的简单无向图的

邻接矩阵中共有产一2e个零元素。

7、从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序

排列的是（）。

A、二叉排序树

B、大顶堆

C、小顶堆

D、平衡二叉树

标准答案：C

知识之解析：对于一个堆，若堆顶为最小元素，则称为小顶堆；若堆顶为最大元

素，则称为大顶堆。二叉排序树和平衡二叉树不符合。

8、顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索

引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在

等概率的情况下，分块查找成功的平均查找长度为()。

A、21

B、23

C、41

D、62

标准答案：B

知识点解析：分块查找成功的平均查找长度为ASL=(s2+s+n)/2s。在本题中，

n=123,s=123/3=41,故平均查找长度为23。

9、在下列存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射

关系的是()。

A、树形存储结构

B、链式存储结构

C、索引存储结构

D、散列存储结构

标准答案：D

知识点解析：散列存储结构将结点按其关键字的散列地址存储到散列表中。

10、若对27个元素只进行三趟多路归并排序，则选取的归并路数是()。

A、2

B、3

C、4

D、5

标准答案：B

知识点解析：归并就是将两个或两个以上的有序表组合成一个新的有序表。设三趟

归并中每次归并x个有序表，则有27/X3=1,X=3C所以选取的归并路数为3。

11、下列序列中，执行第一趟快速排序的结果是()，

A、[da,ax,eb,de,bb]ff[ha,gc]

B、[cd,eb,ax,da]ff[ha,gc,bb]

C、[gc»ax,eb,cd,bb]ff[da»ha]

D、[ax,bb,cd,da]ff[eb,gc,ha]

标准答案：A

知识点解析：本题要按字典顺序进行排序，前半区间中的所有元素都应小于ff,后

半区间中的所有元素都应大于ffo

12、某工作站采用时钟频率f为15MHz,处理速率为10MIPS的处理机来执行一个

已知混合程序。假定每次存储器存取为1周期延迟，试问此计算机的有效CPI是

()。

A、2.5

B、2

C、1.5

D、1

标准答案：C

知识点解析：CPI=15MHZ/(10X106)=1.5O

13、5位二进制定点小数，用补码表示时，最小负数是()。

A>0.II11

B、1.0001

C、1.1111

D、1

标准答案：D

知识点解析：5位二进制定点小数，用补码表示时，最小负数表示为I.0000。

14、浮点加减中的对阶是()。

A、将较小的一个阶码调整到与较大的一个阶码相同

B、将较大的一个阶码调整到与较小的一个阶码相同

C、将被加数的阶码调整到与加数的阶码相同

D、将加数的阶码调整到与被加数的阶码相同

标准答案：A

知识点解析：对阶的原则是小阶向大阶看齐。

15、若内存按字节编址，用存储容量为32Kx8比特的存储器芯片构成地址编号

A0000H至DFFFFH的内存空间，则至少需要的片数是()。

A、4

B、6

C、8

D、10

标准答案：C

知识点解析：DFFFF—A0000+1=40000,即256KB,需用32Kx8的芯片数

=(256Kx8)/(32Kx8)=8o

16、某计算机的存储系统由Cache一主存系统构成，Cache的存取周期为10ns,主

存的存取周期为50ns。在CPU执行一段程序时，Cache完成存取的次数为4800

次，主存完成的存取次数为200次，该Cache一主存系统的效率是()。

A、0.856

B、0.862

C、0.958

D、0.96

标准答案：B

知识点解析：命中率=4800/(4800+200)=0.96,平均访问时间=0.96x10+(1—

0.96)x50=11.6ns,效率=10/II.6=0.862。

17、对于RISC机和CISC机，以下说法错误的是（）。

A、RISC机的指令条数比CISC机少

B、RISC机指令的平均字长比CISC机指令的平均字长短

C、对大多数计算任务来说，RISC机程序所用的指令条数比CISC机少

D、RISC机和CISC机都在发展

标准答案：C

知识点解析：对于大多数计算任务来说，RISC机编写的程序会比CISC机编写的

程序更长，这是因为RISC的指令都比较简单，CSIC中的一条复杂指令所完成的

功能在RISC中可能要用几条指令才能实现，对于同一个源程序，显然RISC的指

令条数要比CISC的多。

18、微程序在计算机中存放的位置是（）。

A、主存储器

B、控制存储器

C、通用寄存器

D、指令寄存器

标准答案：B

知识点解析：微程序存放在只读的控制存储器中。

19、下列各叙述中正确的命题是（）。I.在取指周期中也可能从内存取到操作数

n.CPU的访存时间是由存储器的容量决定的，存储容量越大，访存时间就越长

m.在主存与Cache之间的直接映射方式下，不采用替换策略也可以实现正确的块

替换IV.动态存储器的读操作也具有刷新的功能

A、I、n、in

B、I、n、w

c、u、m、w

D、I、山、IV

标准答案：D

知识点解析：立即寻址方式就可以在取指周期从内存取到操作数；在直接映射方式

下，一旦发生块冲突是不需要替换策略的；动态存储器的刷新是与读写操作没有关

系的。

20、在菊花链方式中，靠近控制器的设备与远处设备的（）。

A、优先级高

B、优先级相等

C、优先级低

D、不一定

标准答案：A

知识点解析：常见的集中仲裁方式有链式查询（菊花链）、计数器定时查询和独立请

求等3种。链式查询方式的优先次序是由串接部件的先后位置来确定的，在查询链

中离总线控制器最近的设备具有最高优先权。计数器定时查询和独立请求方式的优

先级可以是固定的也可以是不固定的。链式查询方式需要3条控制线、计数器定

时查询方式需要［*］条控制线，而独立请求方式需要2n+l条控制线。

21、RAID利用冗余技术实现高可靠性，其中RAID1的磁盘利用率是()。

A、25%

B、50%

C、75%

D、100%

标准答案：B

知识点解析：RA1D1称为镜象磁盘阵列，数据盘和检测盘的数量是1:1的关系，所

以磁盘利用率为50%。

22、设存储器容量为32字，字长64位，模块数m=4,存储周期T=200ns,数据总

线宽度为64位，总线传送周期i=50ns。用交叉方式进行组织，交叉存储器的带宽

是()。

A、32x1(/位/秒

B、8xl()7位/秒

C、73xl()7位/秒

D、18xl()7位/秒

标准答案：C

知识点解析：顺序存储存储器连续读出4个字需要4个存储周期，而交叉存储存储

器连续读出4个字，由于采用分时启动的方法，只需要一个存储周期加上三个总线

传输周期的时间。现字长为64位，交叉存储器连续读出4个字的信息总量q=64位

x4=256位，交叉存储器连续读出4个字所需的时间t=T+(4—

l)T=200ns+3x50ns=350ns=3.5xl0-7s,所以交叉存储器的带宽W=q/

t=256-(3.5xl0-7)=73xl()7(位/秒)。

23、操作系统为用户提供了多种接口，它们是()。I.计算机高级指令；11.终端

命令：m.图标菜单；IV.汇编语言；V.C语言；VI.系统调用；

A、I；n；v

B、n；皿；vi

c、m；iv：v

D、口；w；w

标准答案：B

知识点解析：本题考查操作系统的接口，操作系统有二种接口，命令输入和系统调

用，而命令输入又可以分为命令行和图形用户界面。命令行是在终端或命令输入窗

口中输入操作和控制计算机的规定的命令，既可以一条一条输入，也可以组织成一

批命令，逐条自动执行，称为批处理命令。图形用户接口是我们熟知的图标和菜单

形式。系统调用是我们编写程序过程中，需要计算机所做的操作，一般要按固定格

式来调用。

24、若一个信号量的初值为3,经过多次PV操作以后当前值为一1,此表示等待

进入临界区的进程数是()。

A、1

B、2

C、3

D、4

标准答案：A

知识点3析：本题考查信号量的意义。信号量是一个整型的特殊变量，只有初始化

和PV操作才能改变其值。通常，信号量分为互斥量和资源量，互斥量的初值一般

为1,表示临界区只运许一个进程进入，从而实现互斥。互斥量可以为0,表示临

界区己经有1个进程进入，临界区外尚无进程等待；当互斥量小于0时，表示临界

区中有1个进程，互斥量的绝对值表示在临界区外等待进入的进程数。同样的道

理，资源信号量初值可以是任意整数，表示可用的资源数，当资源量为0时，表示

所有资源已经用光，但是也没有其它进程等待使用该资源。当资源量小于0时，表

示当前货源已经全部用完，而目.还有进程正在等待使用该资源，等待的进程数就是

资源量的绝对值。

25、利用银行家算法进行安全序列检查时，不需要的参数是()。

A、系统资源总数

B、满足系统安全的最少资源数

C、用户最大需求数

D、用户已占有的资源数

标准答案：B

知识点露析：安全性检查一般要用到进程所需的最大资源数，减去进程占用的资源

数，得到进程为满足进程运行尚需要的可能最大资源数，而系统拥有的最大资源数

减去已经分配掉的资源数得到剩余的资源数，比较剩余的资源数是否满足进程运行

尚需要的可能最大资源数可以得到当前状态是否安全的结论。而满足系统安全的最

少资源数并没有这么一个说法。

26、若有一进程拥有100个线程，这些线程都属于用户级线程，则在系统调度执行

时间上占用的时间片是()。

A、1

B、100

C、1/100

D、0

标准答案：A

知识点解析：本题主要考查关于进程和线程之间资源共享的知识点。在引入线程的

操作系统中，线程是进程中的一个实体，是系统独立调度和分派的基本单位。但是

线程自己基本上不拥有系统资源，所以它不是资源分配的基本单位，它只拥有一部

分在运行中必不可少的与处理机相关的资源，如线程状态、寄存器上下文和栈等，

它同样有就绪、阻塞和执行三种基本状态。它可与同属一个进程的其他线程共享进

程所拥有的全部资源。一个线程可以创建和撤销另一个线程；同一个进程中的多个

线程之间可以并发执行。由于用户线程不依赖于操作系统内核，因此，操作系统内

核是不知道用户线程的存在的，用户线程是由用户来管理和调度的，用户利用线程

库提供的API来创建、司步、调度和管理线程。所以，用户线程的调度在用户程

序内部进行，通常采用非抢先式和更简单的规则，也无须用户态和核心态切换，所

以速度很快。由于操作系统不知道用户线程的存在，所以，操作系统把CPU的时

间片分配给用户进程，再由用户进程的管理器将时间分配给用户线程。那么，用户

进程能得到的时间片即为所有用户线程共享。因此，正确答案应为A。

27、某计算机采用页式存储管理，内存中现有1000个页表项，CPU的cache中可

以存放N个页表项，该系统中，CPU内存访问的时间为KJOns,对cache访问的时

间是5ns,如果希望页表映射的平均时间降到20ns以下，那么cache中的N必须高

于()。

A、850

B、858

C、923

D、842

标准答案：A

知识点露析：本题考查cache与页式存储管理结合下的时间计算。根据题意，页式

寻址方式的过程是这样的：当执行到一个逻辑地址时，MMU首先将页号分离，将

得到的页号与cache中的多个页表项比较(同时进行)，若页表项命中，则取出页表

项与页内地址相加，形成指令或数据的物理地址，花费5ns,据此地址，然后到内

存中取得对应的指令或数据，送到CPU中执行或计算。若不能在cache命中，那

么CPU会启动cache更新程序，将新的页表项从内存复制到cache,花费100ns,

然后，重复上述地址转段过程，又花去5ns,得到物理地址，再去内存取指令或数

据。根据题意，要求得到页框号，也就是物理地址的过程小于20ns,那么设，

cache的命中率为x,列关系式：5*x+(l—x)*(5+100)=20解得x为85%。因此，

装入cache的页表项应大于1000*85%=850项，这样可以保证获得页框号的时间小

于20ns。本题若问，一个指令双字的执行时间是多少时，需要考虑的事情就比较

复杂。例如系统的字长是否是32位，32位的系统执行一个双字的时间是1次寻

址，16位系统就需要2次寻址。8位系统的就需要4次寻址。另外，采用什么内存

管理机制，页式和段式都是执行1次指令寻址需要访问内存2次，段页式需要3

次。还要看cache的容量多大，指令是否在cache中等，所以，内存管理中寻址时

间的计算与CPU结构和cache的运行模式息息相关，考生应结合计算机组成原

理，妥善解决此类问题。

28、分页系统中的页面是()。

A、用户所能感知的

B、操作系统所能感知的

C、编译程序所能感知的

D、链接装配程序所能感知的

标准答案：B

知识点解析：分页系统中由逻辑地址向物理地址的转换是系统借助硬件系统自动实

现的，对用户透明，对编译程序和链接装配程序透明(在相同的系统里)。只有操作

系统可以感知页面的存在，在内存管理过程中，操作系统要为用户进程分配内存，

回收内存。所以操作系统是页面最直接的接触者，它将页面从计算机系统中到用户

进行了隔离。

29、某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有

10项，其中前8项是直接索引项，第9项是一次间接索引项，第10项是二次间接

索引项，假定物理块的大小是1K,每个索引项占用4个字节，则该文件系统日最

大的文件可以达到()。

A、65800K

B、65792K

C、65536K

D、34000K

标准答案：A

知识点解析：多级索引的逻辑并不复杂，本题中一级间接索引表有256张，二级间

接索引表最多有256张，计算时加以仔细小心，一般不会有太多变化，但是对多级

索引的方法一定要掌握。直接索引为8xlK=8K,一级间接索引为(1K/4B)X1

K=256K；二级间接索引为(1K/4B)x(lK/4B)x1K=65536K。共计

65536K+25K+8K=65800K

30、设磁盘的IO请求队列中所要访问的磁道号为:96,184,25,120,12,

126,73,75,当前磁头在96,前一次在90。当采用最短寻道时间优先算法(SSTF)

和电梯算法所要移动的距离是()。

A、618,418

B、306,260

C、306,418

D、618,260

标准答案：B

知识点解析：本题考查考生对最短寻道时间优先算法和电梯算法的理解。最短寻道

时间优先算法(SSTF)：96—75—73—120—126—184—25—12共计306道。电梯算

法，前一次在90,当前在96,表示移动方向为磁道增大方向，故：

96-120—126T184—75—73-25T12共计260道。计算时注意磁头的当前位置和

运行方向。

31、UNIX操作系统中，文件的索引结构存放在()。

A、超级块

B、索引节点

C、目录项

D、空闲块

标准答案：B

知识点解析：在UNIX的文件系统中文件系统是其核心，其功能强大，可扩展性

强。UNIX采用的是树形目录结构，文件的信息存放在索引节点中，索引节点是一

个64字节长的表，含有一个文件的重要信息，包括文件大小，文件所有者，文件

存取许可方式，文件类型(普通文件、目录文件、特殊文件)等信息，但是不包含文

件名，文件名存放在目录中。除了上述信息以外，索引节点在表格的最后设计有

13项文件在外存存放的混合索引表，前10项存放的是直接指针，指向文件存放的

数据块的直接地址，UNIX系统中文件块的大小一般是1024字节。所以文件的大

小不能超过10*1024=10240字节，超过上述大小的文件将在第11项一级间接索引

表中指出，该表项指针指向的一个数据块中，存放了256个索引指针(假设一个指

针为4字节，1024字节的一个存储块可以存放1024/4=256个指针)，可以最多容

纳256*1024=262144字节。再大的文件在第12项的二级间接索引表中指明,二级

索引指针指向的数据块中可以容纳256个指针，这些指针指向的数据块中还是索引

指针，故称为二级间接索引，它可以容纳的文件大小是256*256*1024=67108864

字节。第13项是三级间接索引，可以容纳的文件大小更大，为

256*256*256*1024节。所以文件总的大小是上述各级索引文仁溶

量的总和。即文件最大可以达节的大小。当然，UNIX文件系统

对文件的大小是有限制的，不会让其用完整个三级索引。文件的物理结构中，主

要使用的是顺序结构、链接结构和索引结构(Hash结构实际上与索引结构类似)。在

索引结构的文件中，必须要用专门的存储空问来存放索引指针，表示文件的内容存

放的地址。所以，当访问该文件时，必须首先去读取该文件的索引表，才能知道相

应的逻辑文件块在外存上的存放地址。逻辑文件块与物理文件块是一一对应关系，

不能在一个记录中存放多个地址，而索引表中只存放地址指针，不存放文件内容由

于有额外的索引表，所以它并不节省存储空间。

32、在设备管理中，用来实现设备分配的四个数据结构中，每个设备一张，描述设

备的特性和状态，反映设备的特性、设备和控制器的连接情况的数据结构是()。

A、设备控制表(DCT)

B、系统设备表(SDT)

C、控制器控制表(COCT)

D、通道控制表(CHCT)

标准答案：A

知识点解析：设备控制的数据结构中，系统设备表(SDT)在整个操作系统中只有一

张，记录了系统中所有的外部设备。经系统设备表找到需使用的外部设备，则数据

结构指针指向设备控制表(DCT),这个数据表每个设备一张，记录了设备的特性和

状态。每个设备有可能有不止一个控制器，所以从设备控制表会指向多张(至少一

张)控制器控制表(COCT),里面存放了控制器的控制参数，如果该设备是通道的

话，则会指向多张通道控制表(CHCT)。

33、在OSI参考模型中，第N层和其上的第N+1层的关系是()。

A、第N层为第N+1层提供服务

B、第N+1层将从第N层接收的信息增加了一个头

C、第N层利用第N+1层提供的服务

D、第N层对N+l层没有任何作用

标准答案：A

知识点解析：本题考查OSI模型的层次关系，在协叹的控制下，两个对等实体问的

通信使得本层能够向上一层提供服务，同时要实现本层协议，还需要使用下层所提

供的服务。本层的服务用户只能看见服务而无法看见下面的协议。下层的协议对上

层的服务用户是透明的。也就是下一层要为上一层提供服务，并为上一层数据进行

封装，因此答案为A,这里选项B和C的说法正好相反，应该是第N层将从第

N+1层接收的信息增加了一个头，第N+1层利用第N层提供的服务。

34、设待传送数据总长度为L位，分组长度为P位，其中头部开销长度为H位，

源节点到目的节点之间.的链路数为h,每个链路上的延迟时间为D秒，数据传输

率为Bbps,电路交换建立连接的时间为S秒，则传送所有数据，电路交换需时间

是（）。

A、hD+L/B秒

B、S+hD+L/P秒

C、S+hD+L/B秒

D、S+L/B秒

标准答案：C

知识点解析：本题考查电路交换的原理，电路交换包括三个阶段：建立电路。在传

送数据之前，由发送方发出建立电路请求，交换机根据该请求，设法选择一条空闲

的信道连接到接收方。谖收方收到该呼叫后，返回一应答信号确认本次电路连成，

则本次连接成功。传送数据。建立电路连接后，发送方通过已建立的电路向接收方

发送数据。拆除电路。数据传输完毕，发送方或接收方任一方发出拆线信号，终止

电路连接，释放所占用的信道资源。因此传送所有数据所需的时间是连接建立时

间，链路延迟，发送时间的和，因此是S+hD+L/B,答案是C。

35、若数据链路的发送窗口尺寸WT=4,在发送3号帧、并接到2号帧的确认帧

后,发送方还可连续发送的帧数是（）“

A、2帧

B、3帧

C、4帧

D、1帧

标准答案：B

知识点解析：本题考查滑动窗口的机制，发送方可连续发送K帧而无需对方应

答，但需要将已发出但尚未收到确认的帧保存在发送窗口中，以备由于出错或丢失

而准备重发。接收方按正确的次序接受和递交数据帧，并返回确认信息。接收方可

能因为一帧出错，不能正确接受并递交主机，对后面连续发送来的n帧均丢失，这

就是累积确认的概念。本题收到了2号帧的确认后，即0,1,2号帧已经正确接

收，因此窗口向右移动3个帧，目前已经发送了3号帧，因此可连续发送的帧数是

窗口大小一已经发送的项数，即4—1=3,答案是B。

36、TCP/IP网络中，某主机的IP地址为130.25.3.135,子网掩码为

255.255.255.192,那么该主机所在的子网的网络地址是（）。

A、130.25.0.0

B、130.25.3.0

C、130.25.3.128

D、130.25.3.255

标准答案：C

知识点解析：本题考查子网划分的计算，从掩码可以看出网络地址仅和第四个字节

有关，因此130.25.3.135的二进制为130.25.3.10000111,子网掩码的二

进制为255.255.255.11000000,两者相与，因此网络地址为

130.25.3.10000000,换算为十进制是130.25.3.128,因此答案为C。

37、为了限制路由信息传播的范围，OSPF、协议把网络划分成4种区域（Area）,其

中连接各个区域的传输网络是（）。

A、不完全存根区域

B、标准区域

C、主干区域

D、存根区域

标准答案：C

知识点解析：本题考查层次路由与OSPF路由协议，如果将区域看成一个节点，则

OSPF是以主干区域（area。）为顶点，其他区域为终端的星形拓扑结构。标准区域可

以接收链路更新信息和路由总结。存根区域是不接受自治系统以外的路由信息的区

域。如果需要自治系统以外的路由，它使用默认路由0.0.0.0。完全存根区域

不接受外部自治系统的路由以及自治系统内其他区域的路由总结，需要发送到区域

外的报文则使用默认路由0.0.0.0o不完全存根区域类似于存根区域，但是允

许接收以LSAType7发送的外部路由信息，并且要把LSAType7转换成

LSAType5o因此答案是C。

38、一台主机的IP地址为11.I.1.100,子网掩码为255.0.0.0。现在用户

需要配置该主机的默认路由。经过观察发现，与该主机直接相连的路由器具有如下

4个IP地址和子网掩码：I.IP地址：11.1.1.1,子网掩码：255.0.0.0

n.1P地址：II.1.2.1,子网掩码：255.0.0.0山.IP地址：1

2.1.1.1,子网掩码：255.0.0.0W.IP地址：13.1.2.1,子网掩码：

255.0.0.。请问IP地址和子网屏蔽码可能是该主机的默认路由的是（）。

A、I和口

B、I和m

C>CC和w

D、in和w

标准答案：A

知识点解析：本题考查默认路由的配置，路由器还可采用默认路由以减少路由表所

占用的空间和搜索路由表所用的时间。这种转发方式在一个网络只有很少的对外连

接时是很有用的。本题中主机地址是一个标准的A类地址，其网络地址为

II.0.0.Oo选项I的网络地址为11.0.0.0,选项II的网络地址为

11.0.0.0,选项HI的网络地址为12.0.0.0,选项IV的网络地址为

13.0.0.0,因此和主机在同一个网络是选项I和n,因此答案为A。

39、以太网交换机中的端口/MAC地址映射表是()。

A、是由交换机的生产厂商建立的

B、是交换机在数据转发过程中通过学习动态建立的

C、是由网络管理员建立的

D、是由网络用户利用特殊的命令建立的

标准答案：B

知识点解析：本题考查交换机中地址映射表的原理，主要与路由器的路由表进行区

分，路由表可以由人为配置静态路由，也可以通过动态协议建立，而对于交换机，

映射表只能在数据转发中进行动态学习建立，并且每个表项都有定时器，具体是收

到一帧后先进行自学习。查找转发表中与收到帧的源地址有无相匹配的项目。如没

有，就在转发表中增加一个项目(源地址、进入的接口和时间)。如有，则把原有的

项目进行更新，因此答案为B。

40、下面关于电子邮件的说法中，不正确的是()。

A、电子邮件只能发送文本文件

B、电子邮件可以发送图形文件

C、电子邮件可以发送二进制文件

D、电子邮件可以发送主页形式的文件

标准答案：A

知识点解析：本题考查电子邮件的主要功能，电子邮件不仅仅发送文本文件，注意

邮件统中SMTP不能传送可执行文件或其他的二进制对象。SMTP限于传送7位的

ASCII码，也就是文本文件，因此引入MIME协议，在没有改动SMTP或取代

SMTP的前提下，增加了邮件主体的结构，并定义了传送非ASCII码的编码规

则.因此答案为A.

二、综合应用题(本题共7题，每题1.0分，共7分。)

41、己知二义树采用二义链表方式存放，要求返回二义树T的后序序列中的第一

个结点的指针，是否可不用递归且不用栈来完成?请简述原因。

标准答案：可以。原因：后序遍历的顺序是“左子树一右子树一根结点”。因此，二

叉树最左下的叶子结点是遍历的第一个结点。下面的语句段说明了这一过程(设p

是二叉树根结点的指针)。if(p!=NULL){while(p—>lchild!=NULL||p—>rchild!

-NULL){while(p>lchild!-NULL)p-p>lchild；if(p>ichild!-NULL)p-p

—>rchild：)(return(p)；//返回后序序列第一个结点的指针

知识点解析：本题主要考查后序遍历过程及特点。

42、设有一个带头结点的循环单链表，其结点值均为正整数。试设计一个算法，反

复找出单链表中结点值最小的结点，并输出之，然后将该结点从中删除，直到单链

表空为止，最后再删除表头结点。

标准答案：voiddelall(LinkL5.st&L){LNode*p,*pre,*minp,*minpre；while(L

—*>next!=L){//循环单链表不空时循环p=Lnext：pre=L；minp=p；

minpre=pre；while(p!=L){//从头开始查找最小值的结点if(p

—>datadata){minp=p；minpre=pre；)pre=p；//p>pre同步后移p=p

一〉next；}printf("％c"，minpdata)；//输出最小值结点minpre

—>ncxt=minp—>ncxt；//删除最小值结点frec(minp)；)free(L)；}

知识点解析：对于循环单链表L,在不空时循环：每循环一次查找一个最小结点

(由minp指向最小结点，minpre指向其前趋结点)并删除它。最后释放头结点。

43、什么是单重分组和双重分组跳跃进位链?一个按3,5,3,5分组的双重分组跳

跃进位链(最低位为第0位)，试问大组中产生的是哪几位进位?与4,4,4,4分组

的双重分组跳跃进位链相比，试问产生全部进位的时间是否一致?为什么？

标准答案：单重分组即组内并行、组间串行的进位方式；双重分组即组内并行，组

间也并行。双重分组跳跃进位链中一个按3,5,3,5分组，大组中产生的进位输

出是C4、C7、。2和C5而一个按4,4,4,4分组，大组中产生的进位输出是

C3、C7、Cu和C|5虽然这两种方式小组内的位数不同，但产生全部进位的时间是

一致的。因为两种方式都被分成4个小组，假定一级“与门”、“或门”的延迟时间定

为ly,则每一级进位的延迟时间为2ty。C]经过2ty产生第1小组的进位及所有组

进位产生函数G「和组进位传递函数Pi*；再经过2ty,由大组产生相应的进位；再

经过2ty后，才能产生第2、3、4小组内的其余的进位，所以最长的进位延迟时间

者B为6tyo

知识点解析•：假设最低位为第0位，16位并行加法器均分为4组，最低位的进位

输入为C-],最高位的进位输出为C]5。

44、某机的主要部件如下图所示。

移位器1-1R.MDR

“L-£^JR.

rm1凡Ld

DR,MAR

回函1--------1(1)请补充各部件间的主

要连接线，并注明数据流动方向。(2)拟出指令SUB(Ri),一(R2)的执行流程(含取

指过程与确定后继指令地址)。该指令的含义是进行减法操作，源操作数地址和日

的操作数地址分别在寄存器Ri和R2中，目的操作数寻址方式为自减型寄存器间接

寻址。其中：LA—A输入选择器，LB—B输入选择器，C、D一暂存器。

标准答案：(1)将各部件间的主要连接线补充完后，数据通路下图所示。

CR~凡DR~旦

票机的敷据通路图(2)指令

SUB(Ri),一(R2)的含义为(R2)-1-R2((RI))—(。2))一(R2)指令的执行流程如

下：①(PC)—MAR；取指令②ReadG)M(MAR)-MDR-1R④(PC)+1-PC

⑤(RI)-MAR；取被减数⑥Read⑦M(MAR)TMDR-C⑧(R2)一1-R2:修改

R的地址@(R2)->MAR:取减数⑩Read?M(MAR)-MDR->D?(C)一

(D)一MDR；求差并保存结果？Write?MDR—MM

知识点解析：第44题的图中只给出了计算机的主要部件，但各部件之间的连接线

没有给出，由于LA和LB分别为输入选择器，所以特将数据通路设计为简单的单

总线结构形式。

45、实现一个经典的“读者一写者”算法时，若当前临界区中有读者访问，写者再来

时必须在临界区外面等候，如果其后读者源源不断地到达，按策略他们均可以进入

临界区，始终保持临界区中有读者访问，那么写者可能长时间不能进入临界区而形

成饥饿。为解决此类问题，我们修改访问策略，要求当写者到达时，写者具有优先

权。具体说，写者到达后，已经在临界区内的读者继续读取直到结束，而后来的读

者就不能进入临界区。等所有的读者离开临界区以后让写者先进去访问，然后等写

者离开后再允许读者进入临界区。这所谓“写者优先读者一写者''问题。请用信号

量和PV操作来描述这一组进程的工作过程。

标准答案：第一部分：假设临界区能容纳的最大读者数量为n。贝I：typedefint

semaphore；//定义信号量semaphoremutex=l；//读写的互斥量semaphore

rcadcrs=n；//读者的资源量voidReaders(viod)//读者进程{while(TRUE){/

/调度P(mutex)；//读写互斥P(readers)；//读者资源量减一，为负时等待

V(mutex)；//释放读写互斥read_data(void)；//读者读取数据V(readers)；}

//离开时释放读者数量，加I一}VoidWriters(void)//写者进程

{while(TRUE){P(mutex)；//获取读写互斥量for(inli=l；iv=n；

i++)P(readers)；//将许可读者进入的资源量消耗光writedata(void)；//写入

数据for(inti=l；iv=n；i++)V(readers)；//释放读者的资源量V(mutex)；}//

释放读写互斥量}第二部分：若对读者的数量不加以限制，那么应该如下书写程

序。lypedefintsemaphore；//定义信号量semaphorerwmulex=l；//读写的

互斥量semaphorercmutex=l；//访问读者计数器的互斥量semaphore

nrmutex=1；//写者等待读者退出的互斥量intreaderscount=0；//读者计数器

voidReaders(viod)//读者进程{while(TRUE){//调度P(rwmutex)；//读写

互斥P(rcmutex)；//进入修改读者计数器互斥readerscount++；//读者数量加

-if(readerscount=1)P(nrmutex)；//若是第一个读者，互斥写者V(rcmutex)；/

/释放读者计数器互斥量V(rwmutex)；//及时移放读写互斥量，允许其它进程

申请readdata(void)；//读者读取数据P(rcmutex)；//离开临界区时读者计数

器互斥rcadcrscount--；//读者数量减一if(rcaderscount==0)V(nnnutex)；//所

有读者退出临界区V(rcmutex)；)//离开时释放读者计数器互斥量}Void

writers(void)//写者进程{while(TRUE){P(rwmutex)；//获取读写互斥量

P(nrmutex)；//若临界区有读者，等待其退出writc_data(void)；//写入数据

V(nrmutex)；//允许后续第一个读者进入临界区V(rwmulex)；}//允许新的读

者和写者排队}上述程序不能保证在等待队列中写者更优一点，因为上述约束条件

只能将读者无限制地进入临界区的情况给扉蔽了，而在临界区外，读者和写者还是

按照先来先服务的方式排队。第三部分给出的方法使得访问队列中只要有写者出

现，它必然优先进入临界区。typedefintsemaphore；//定义信号量semaphore

rwmutcx=l；//读写的互斥量semaphorercmutcx=l；//访问读者计数器的互

斥量semaphorewcmutex=l；//访问排队写者计数器的互斥量semaphore

nrmutex=1；//写者等待读者退出的互斥量intreaderscount=0；//读者计数器

intwriterscount=0；//写者计数器voidReaders(viod)//读者进程

{while(TRUE){//调度P(rwmutex)；//读写互斥P(rcmutex)；//进入修改

读者计数器互斥readerscount++；//读者数量加一

if(readerscount==l)P(nrmutex)；//若是第一个读者，互斥写者V(rcmutex)；//

释放读者计数器互斥量V(rwmulex)；//及时释放读写互斥量，允许其它进程申

请read_data(void)；//读者读取数据P(rcnnutex)://离开临界区时读者计数

器互斥readerscount-；//读者数量减一if(readerscounl==0)V(nrmutex)；//所

有读者退出临界区V(rcmulex)；}//离开时释放读者计数器互斥量}Void

writers(void)//写者进程{while(TRUE){P(wcmutex)；//获取写者队列互斥量

writerscount++；//写者队列加一if(writerscount==l)P(ru/mutex)；//第一写者

使用读写互斥量V(wcmurex)；//释放写者计数互斥量P(nrmutex)；//若临界

区有读者，等待其退出write_data(void)；//写入数据V(nimutex)；//释放后

续第一个读者P(wcmutex)；//获取写者队列互斥量writerscount-；//写者队

列减一if(writerscount==0)V(rwmutex)；//最后一个写者退出，释放临界区

V(wcmutex)；)//释放写者计数互斥量}每个读者进程最开始都要申请一下

rwmulex信号量，之后在真正做读操作前即让出(使得写进程可以随时申请到

rwmulex)o而只有第一个写进程需要中请nnnulex,之后就一直占着不放了，直到

所有写进程都完成后才让出。等于只要有写进程提出申请就禁止读进程排队，从而

提高了写进程的优先级。

知识点解析：“写者优先读者一写者''问题也是考试的热点，解决此类问题也分两方

面，一是读者访问临界区的最大数量是有限的，例如说n,那么程序就比较简单，

看解答中第一部分。若是不限的，则必须设定一个排队的信号量，所有到达临界区

的所有读者一写者均需在此排队，按先来先服务使用临界区，一旦进入临界区以后

就释放该信号量。见解答的第二部分。若需要彻底地让后到的写者跨越前面等待

的读者，那么需要设定更多的限制，见解答的第三部分。

46、某32位计算机系统采用段页式虚拟存储管理，现有一个进程被分成5段，其

段号和段长见下表，段内分页，页表见下，存放在内存中，每页的长度为4096B。

进程运行到某一个指令，其地址为（2,3,010）,当前CPU的寄存器和地址加法器

的状态如图所示，当上述指令执行时，操作系统如何工作?CPU