软件水平考试（中级）数据库系统工程师上午（基础知识）试题章节练习试卷22

软件水平考试（中级）数据库系统工程

师上午（基础知识）试题章节练习试卷

22

一、中文选择题（本题共〃题，每题7.0分，共〃

分。）

1、单个磁头在向盘片的磁性涂料层上写入数据时，是以⑶方式写入的。

A、并行

并一串行

C、串行

D、串一并行

标准答案：C

知识点解析：串行通信中，两个设备之间通过一对信号线进行通信，其中一根为信

号线，另外一根为信号地线，信号电流通过信号线到达目标设备，再经过信号地线

返回，构成一个信号回路。并行通信中，基本原理与串行通信没有区别。只不过使

用了成倍的信号线路，从而一次可以传送更多位信号。单磁头可以看做一对信号线

路，所以是以串行方式写入数据。

2、如果主存容量为16M字节，且按字节编址，表示该主存地址至少应需要（6）

位。

A、16

B、20

C、24

D、32

标准答案：C

知识点解析：根据主存容量或芯片的规格求地址的位数，或者是数据线的数量，这

种题型在软考中经常出现，知道规则就很容易解题。求地址线只要把主存的容量

写成2的N次方的形式，这个N就是地址的位数，如题目中的16M=224,所以表

示该主存地址至少需要24位。其实这种规律也是从实践过程中总结出来的，我们

来看几个简单的例子：如果地址线有1根,则可以表示2个地址，即地址0.1,

刚好满足2=2；如果地址线有2根，则可以表示4个地址，即地址00,01,10,

II,满足22=4如果地址线有3根，则可以表示8个地址，即000,001,010,

011,100,101,110,111,满足23=8；依次类推，也就把规律总结出来了。

3、在计算机系统中，构成虚拟存储器(11)。

A、只需要一定的硬件资源便可实现

B、只需要一定的软件即可实现

C、既需要软件也需要硬件方可实现

D、既不需要软件也不需要硬件

标准答案：C

知识点解析：在计算机中，内存空间的分配是由操作系统进行的，程序和数据除了

常驻内存的以外都是以文件的形式存放在硬盘中，需要时从硬盘调到内存，再由

CPU使用。我们把由进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为

虚拟存储器，操作系统必须解决由虚拟存储器到物理存储器的地址变换。这种变换

方法有静态地址重定位和动态地址重定位两种方法。(1)静态地址重定位：静态地

址重定位是在虚空间程序执行之前由装配程序完成地址影射工作。静态地址重定位

的优点是不需要硬件的支持，缺点是无法实现虚拟存储器，必须占用连续的内存空

间且难以做到程序和数据的共享。(2)动态地址重定位：动态地址重定位是在程序

执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换为内存地

址。动态地址重定位依靠硬件地址变换机构完成，其优点主要有：可以对内存进行

非连续分配；提供了虚队存储器的基础；有利于程序段的共享。虚拟存储器只是一

个容量非常大的存储器的逻辑模型，不是任何实际的物理存储器。它借助于磁盘等

辅助存储器来扩大主存容量，使之为更大或更多的程序所使用。它指的是主存一外

存层次。它以透明的方式给用户提供了一个比实际主存空间大得多的程序地址空

间。所以它既需要硬件也需要软件。

4、页式存储系统的逻辑地址由页号和页内地址两部分组成。假定页面的大小为

4K,地址变换过程如图2-1所示，图中逻辑地址用十进制表示。

控制有存笈渡我地址

图2-1地址变换过程图2-1中有效地址经过

变换后，十进制物理地址a应为(12)。

A、33220

B、8644

C、4548

D、2500

标准答案：A

知识点解析：本题考查的是虚拟存储中的页式存储。页式存储组织的基本原理是将

各进程的虚拟空间划分为若干个长度相等的页，把内存空间以与页相等的大小划分

为大小相等的片或页面，采用请求调页或预调页技术实现内外存的统一管理。页式

存储组织的主要优点是利用率高，产生的内存碎片小，内存空间分配及管理简单。

主要缺点是要有相应的硬件支持，增加了系统开销：请求调页的算法如选择不当，

有可能产生抖动现象。页式存储系统的逻辑地址由页号和页内地址两部分组成。题

目已知页面大小为4K,因为4K=2%所以页内地址有12位。现在把逻辑地址

8644转成二进制数得10000111000100,这里的低12位为页内偏移量，最高两

位则为页号，所以逻辑地址8644的页号为10(即十进制数的2),所以物理块号为

8,化为二进制数得1000。把物理块号和页内偏移地址拼合得10000001

11000100,转化为十进制数得33220。

5、在CPU与主存之间设置高速缓冲存储器Cache,其目的是为了(15)。

A、扩大主存的存储容量

B、提高CPU对主存的访问效率

C、既扩大主存容量又提高存取速度

D、提高外存储器的速度

标准答案：B

知识点解析：请参考第5题的分析。

6、若内存地址区间为400011—43ITII,每个存储单元可存储16位二进制数，该内

存区域由4片存储器芯片构成，则构成该内存所用的存储器芯片的容量是(16)。

A、512xl6bil

B、256x8bit

C、256x16bit

D、1024x8bil

标准答案：C

知识点解析：本题的考点是存储容量的计算及其对应所需要的存储器芯片数。从

4000H到43FFH的内存有1024字节，由于每个存储单元可存储16位二进制数，

内存区域由4片存储器芯片构成，因此每片的容量为1024/4xl6bit=256、16bit

7、SCSI是一种通用的系统级标准输入/输出接口，其中(20)标准的数据宽度为16

位，数据传送率达20Mb/s。

A、SCSI-1

B、SCSI-II

C、FASTSCSI-II

D、FAST/WDESCSI-II

标准答案：C

知识点解析：SCSI接口是小型计算机系统接口(SmallComputerSystemInterface)的

简称，它是在美国Shugart公司开发的SASI的基础上，增加了磁盘管理功能而成

的。SCSI接口作为输入/输出接口，主要用于光盘机、磁带机、扫描仪、打印机等

设备。SCSI标准是1986年审议完成的，称为SCSI-1标准，由于SCSI的特点是传

输速度快，支持多I/O任务并行操作，因此在非PC上得到了广泛的应用。1990年

又制定了SCSLH标准。下面是广些SCSI标准的数据。(l)SCSM：数据宽度为8

位，数据传输速率最高达5Mb/s。(2)SCSI-H：数据宽度为16位，数据传输速率最

高达10Mb/s。(3)FastSCSI-II：数据宽度为16位，数据传输速率最高达20Mb&

(4)FastAVideSCSLII：数据宽度为32位，数据传输速率最高达40Mb/s。(5)UItra

SCSI：最高传输速率约为20Mb/s。(6)Ultra-2SCSI：最高传输速率可达80Mb：s。

(7)Ultra160/m：最高传输速率可达160Mb/s。

8、虚存页面调度算法有多种，(47)调度算法不是页面调度算法。

后进先出

B、先进先出

C、最近域少使用

D、随机选择

标准答案：A

知识点解析：虚拟存储器是内存在一定程度上的扩展，它使程序可以在透明的情况

下访问比内存大得多的地址空间，使运行内存需要大于内存实际容量的程序成为可

能，操作系统从硬盘中分配一部分空间作为虚拟存储器，在需要时同内存中的页面

进行相互替换。如果选择的页面被频繁地装入和调出，那么这种现象称为“抖

动”，应减少和避免抖动现象。常用的页面调度算法有以下几种。(1)最优淘汰算法

(OptimalReplacementAlgorithm,OPT)。选择不再使用或最远的将来才被使用的

页，难以实现，常用于淘汰算法的比较。(2)随机选择算法(Randomalgorithm,

RAnd)o随机地选择被淘汰的页，开销小，但是可能选中立即就要访问的页。(3)

先进先出(FirstinFirstout,FIFO)算法,又称轮转法(RR)。选择在内存驻留时间最

长的页，似乎合理，但可能淘汰掉频繁使用的页。另外，使用FIFO算法时，在未

给予进程分配足够的页面数时，有时会出现给予进程的页面数增多，缺页次数反而

增加的异常现象。FIFO算法简单，可采用队列实现。(4)最近最少使用(Least

RecentlyUsed,LRU)算法。选择离当前时间最近的一段时间内使用得最少的页。

这个算法的主要出发点是：如果某个页被访问了，则它可能马上就要被访问；反

之，如果某个页长时间未被访问，则它在最近一段时间也不会被访问。另外，还

有最不经常使用的页面先淘汰(LeastFrequentUsed,LFU)、最近没有使用的页面先

淘汰(NotUsedRecently,NUR)。

9、实存的存储分配算法用来决定输入的程序和数据放到主存中的位置，采用“总是

把程序装入主存中最大的空闲区域”的算法称为(48)。

A、最佳适应算法

B、最差适应算法

C、首次适应算法

D、循环首次适应算法

标准答案：B

知识点解析：实存的可变式动态分区分配在作业执行前并不建立分区，而是在处理

作业过程中按需要建立分区。常使用的4种存储分配算法介绍如下。(1)首次适应

算法：把内存中的可用分区单独组成可用分区表或可用分区自由链，按起始地址递

增的次序排列。每次按潴增次序向后找，一旦找到大于或等于所要求内存长度的分

区，则结束探索，从找到的分区中找出所要求的内存长度分配给用户，并把剩余的

部分进行合并。（2）循环适应算法：上述首次适应法经常利用的是低地址空间，后

面经常是较大的空白区，为使内存所有线性地址空间尽可能轮流使用到，每重新分

配一次，都在当前之后寻找。（3）最佳适应算法：最佳适应算法是指将输入作业放

入主存中与它所需大小最接近的空白区中，使剩下的未用空间最小，该法要求空白

区大小按从小到大的次序组成空白区可用表或自由徒。在进行分配时总是从最小的

一个开始查询，因而找到的一个能满足要求的空白区便是最佳的一个。（4）最差适

应算法：分配时把一个作业程序放入主存中最不适合它的空白区，即最大的空白区

（空闲区）内。

10、在文件存储设备管理中，有三类常用的空闲块管理方法，即位图向量法、空闲

块链表链接法和（49）。

A、一级目录法

B、多级目录法

C、分区法

D、索引法

标准答案：D

知识点解析：在文件存储设备管理中，有三类常用的空闲块管理方法，即位图向量

法、空闲块链表法和索引法。位图向量法中位图的每个字的每一位都对应一个物理

块。空闲块链表法是把所有的空白块链在一起，当创建文件需要一块或几块时，就

从链头上依次取下，反之，回收空间时，把这些空白块依次链接到链头上。索引法

是指在文件存取器上每一个连续的空闲区建立一个索引，这种分配技术适用于建立

连续文件。

11、假设某计算机系统的内存大小为256KB,在某一时刻内存的使用情况表2-4（a）

所示。此时，若进程顺序请求20KB,10KB和5KB的存储空间,系统采用（53）算

法为进程依次分配后的内存情况表2-4（b）所示。

>2-4内存分配情况

如始地址0KB20KB50KB90KB100KB105KB135KB160KB175KB195KB220KB

状专已用未用已用已用未用已用未用已用未用未用已用

20KB30KB40KBI0KB5KB30KB23KB15KB20KB25KB36KB

起始地处0KB20KB40KB50KB90KB100KB105KB115KB145KB160KB175KB19)KB200KB220KB

状态已用未用已期已用*用已用未用未用已用未用已用

容量20KB20KBI0KB40KB10KB5KB30KB10KB15KB1SKB20KB5KB20KB36KB

A、最佳适应

B、最差适应

C、首次适应

D、循环首次适应

标准答案：B

知识点解析：有关分配算法，请读者参考本节练习10的分析。根据本题给出的两

个表格：（1）当进程请求20KB的内存时，可以使用4块内存中的一块（按照先后次

序,分别是30KB、25KB、20KB和25KB）,由表格（b）可知,系统分配的是第1块

(分配20KB,剩下I0KB空闲未用)。(2)当进程请求10KB的内存时，可以使月4

块内存中的一块(按照先后次序，分别是10KB、25KB、20KB和25KB),由表格

(b)可知，系统分配的是第2块(分配10KB,剩下15KB空闲未用)。(3)当进程请求

5KB的内存时，可以使用5块内存中的一块(按照先后次序，分别是10KB、5KB、

15KB、20KB和25KB),由表格(b)可知，系统分配的是最后一块(分配5KB,剩下

20KB空闲未用)。因此，可以看出这里使用的是最差适应法。

二、中文选择题(含2小题)(本题共72题，每题7.0

分，共72分。)

某一非确定性有限自动机(NFA)的状态转换图如图6-1所示，该NFA等价的正规式

是(1),与该NFA等价的DFA是(2)。图6一个NFA

12、某一非确定性有限自动机(NFA)的状态转换图如图6-1所示，该NFA等价的正

规式是(1),与该NFA等价的DFA是(2)。图一个NFA

A、0*|(0|1)0

B、(0|10)*

C、0*((0|1)0)*

D、0*(10)*

标准答案：B

知识点解析：暂无解析

的

C、

0

标准答案：A

知识点解析：我们先介绍有关概念和规则。1.有限状态自动机一个确定的有限状

态自动机M(记做DFA)是一个五元组：M=(Z，Q,qO,F,6)其中：(1)Q是一个

有限状态集合；(2)Z是一个字母表，其中的每个元素称为一个输入符号；

(3)qOEQ,称为初始状态；(4)FUQ,称为终结状态集合；(5)6是一个从Qx£(Q与

Z的笛卡儿乘积)到Q的单值映射：3(q,a尸q，(q,qFQ,a£±)表示当前状态为

q，输入符号为a时，自动机将转换到下一个状态q，称为q的一个后继。若

Q={ql,q2,…，qn),£={al,a2,...,an),则(3(qi，aj))nxm是一个n行m列矩

阵，称为DFA的状态转换矩阵，或称转换表。有限状态自动机可以形象地用状态

转换图表示，设有限状态自动机：DFAM=({S,A,B,C,f},(1,0|,S,

{f},8),其中：5(S,0)=B,S(S,1)=A,6(A,0)=f,6(A,1)=C,6(B,0)=C,

5(B,l)=f,5(C,0)=f,3(C,l)=f其对应的状态转换图如图6・2所示。

图&2状态转换图图6-2中的圈表示状态结点，其中双圈表示终结状态

结点。而边表示状态的转换，代表映射。边上的符号表示此转换需要输入的符号，

代表映射的输入。对于Z上的任何字符串wWg*,若存在一条从初态结点到终态结

点的路径，在这条路径上的所有i力的符号连接成的符号串恰好是w,则w被DFA

所识别(或接受、读出)。DFA所能识别的符号串的全体记为L(M),称为DFA所识

别的语言。如果对所有WWg*,以下述的递归方式扩张6的定义：8(q,E)=q6(q,

wa)=5(5(q,w),a),对，生何尤》qWQ我们则可以把DFA所识别的语言形式定义

为：L(M)=(w|wGl*,若存在qWF,使3(q0,w)=q前面介绍的是确定的有限自

动机，即一个状态对于特定的输入字符有一个确定的后继状态。而当一个状态对于

特定的输入字符有一个以上的后继状态时，我们称该有限自动机为非确定有限自动

机(记做NFA),其形式定义如下。一个非确定的有限自动机M是一个五元组：M

=(Z，Q，qO,F,3)其中Z，Q,qO,F的意义和DFA的定义一样，而6一个从

Qx£到Q的子集的映射，即6：QX£->2Q,其中2Q是Q的幕集，即Q的所有子集

组成的集合。与DFA一样，NFA同样可以用状态转换图表示，所不同的是，在图

中一个状态结点可能有一条以上的边到达其他状态结点。同样，对于任何字符串

WEZ*,若存在一条从初态结点到终态结点的路径，在这条路径上的所有边的符号

连接成的符号串恰好是w,则称w为NFA所识别(或接受或读出)。若qO正儿这时

qO既是初始状态，也是终结状态，因而有一条从初态结点到终态结点的£-路径，

此时空符号串可以被NFA接受。NFA所能识别的符号串的全体记为L(M),称为

NFA所识别的语言。对任何一个NFA,都存在一个DFA，使L(M，)=L(M),这时

我们称M，与M等价。构造与M等价的M，的基本方法是让M，的状态对应于M的

状态集合。即如果有aq,a)={ql,q2,…，qn),则把{ql,q2,…，qn)看做M'

的一个状态，即M，中的状态集合Q，的一个元素。对于一个NFA,如果我们把6

扩展为从QxgU{£}到2Q的映射，则我们称该自动机为带£-转移的非确定有限自

动机。同样，对于带£■转移的非确定有限自动机，我们也可以构造与之等价的不

带转移的非确定有限刍动机。2.正规表达式正规表达式(正规式)是一个十分有

用的概念，它紧凑地表达有限自动机所接受的语言。对正规表达式的递归定义为：

一个正规表达式是按照一组定义规则由一些较简单的正规表达式所组成的。在字母

表Z上的正规表达式可以使用以下规则定义：(1把和①是Z上的正规表达式，它们

所表示的语言分别为{£}和①。(2)如果a是g内的一个符号，则a是一个正规表达

式，所表示的语言为{a},即包含符号串a的集合。(3)如果r和s分别是表示语言

L(r)和L(s)的正规表达式，那么：(r)|(s)是一个表示L(r)UL(s)的正规表达式。(r)(s)

是一个表示L(r)L(s)的正规表达式。(r)*是一个表示(L(r))*的正规表达式。(r)是一

个表示L(r)的正规表达式。通常在正规表达式中，一元运算符“*”具有最高的优先

级，连接运算具有次优先级，运算符具有最低优先级，这三个运算都是左结合

的。每一个正规表达式只都对应一个有限自动机M,使M所接受的语言就是正规

表达式的值。经过以下步骤可以从一个正规表达式R构造出相应的有限自动机

Mo首先定义初始状态S和终止状态f并且组成有向图，如图6-3所示。

图a第一步然后反复应用以下规则：

若@一~则用④―代替：

若⑥心则用④代替;

二一⑥则用。代替.直到所有的边都以z中的字母

或£标记为止。由此产生了一个带。转移的非确定有限自动机，然后可以通过上面

介绍的方法，把该自动叽转换成确定有限状态自动机。3.试题解答从图6-1可以

看出，从qO状态出发，可以只输入若干个0,仍然回到q0状态；也可以只输入若

干个0,经由ql状态后再回到qO状态；还可以输入1后，到达ql,然后再输入

0,回到qO状态。因此，得出其正规式为(0|((0|l)0))T根据正规式之间的代数性质

得0*((0|1)0)*根据图6-1的NFA,下面求与之等价的DFA。T0=8-

closure{qO}={qO},TO未被标记，为子集中唯一成员；令Tl=£・

closure)move(T0,0)}={q0,ql},将T1加入子集：令T2=£-closure{move(T0,

l)[={ql),将T2加入子集：8-closure{move(Tl,0)}={q0,ql),即Tl,已经在

子集中;£-closure{move(TLl))={ql),即T2,已经在字集市；e-

closure{move(T2,0)}={q0},即TO,已经在子集中。因此,构造了三个子集T0

0」

={q0}、Tl={qO,ql}、T2={ql},如图6-4所示，图6YDFA首

先，将图6-4中状态分为终态和非终态两个子集即({TO,Tl),{T2}),再进行子集

划分，观察第一个子集ITO,T1),输入0和1后成为的状态一样。因此，(TO,

T1)两个状态可以合并成为一个状态，变换即得选项A的状态。

某一确定性有限自动机(DFA)的状态转换图如图6-5所示，令d=0|l|2|…|9,则以下

字性串中，不能被该DFA接受的是(3),与该DFA等价的正规式是(4)。(其中，£

表示空字符)①3857②1.2E+5③-123④.576E10

14、某一确定性有限自动机(DFA)的状态转换图如图6-5所示，令d=0|l|2|...[9,则

以下字符串中，不能被咳DFA接受的是(3),与该DFA等价的正规式是(4)。(其

中，£表示空字符)①3857②1.2E+5③-123©.576E10

B、①、②、④

C、②、③、©

D、①、②、③、④

标准答案：B

知识点解析：暂无解析

15、

A、(-d|d)d*E(-d|d)d*|(-d|d)*.d*(e|E(-d|d)d*)

B、(-d|d)dd*(.|8)d*|(e|E(-d|d)d*)

C、(-|d)dd*E(-|d)d*|(-d|d)dd*.d*(e|E(-|d)d*)

D、(-d|d)dd*E(-d|d)d*|(-d|d|)dd*.d*(e|E(-dd*|dd*))

标准答案：A

知识点解析：题目第一问是判断备选答案中有哪些字符串不能被DFA接受。现在

逐个对其进行判别，这样有利于对DFA功能的理解和后面的解题。首先看3857,

这个字符串中的元素全部是数字，从DFA的初态0输入一个数字，进行到状态

1,在状态1输入数字还是回到状态1,如果还想往后走，必须要输入字符“.”或

是字符“E”，但3857中不存在这样的字符，所以无法到达终态，因此①不能被

DFA接受。接着看1.2E+5,这个不用判断就知道不行，因为在此DFA中无法

识别。再看-123.,此串能从始点顺利到达终点(状态0一状态4一状态1-状态1-

状态IT状态5),所以此串可以被DFA接受。最后看•.576E10,第一个字符“.”在

初始状态无法被识别，所以此串也不能被DFA识别。接下来是把DFA转化为正

规式，我们用排除法来解这个题，首先可以排除的是B和D,很明显(・d|d)dd*所表

达的串会比DFA所描述的串多一个do再看C选项(-|d)dd*E(-|d)d*|(-

d|d)dd*.d*(e|E(-|d)d*)o其中的(-|d)dd*E(-|d)d*表示的路径是不经过状态5的路径。

后面的(-d|d)dd*.d*(£|E(-|d)d*)是指经过状态5的路径。这里的(-d|d)dd*,也是多出

了一个d,所以C也可以排除，答案就只能是A了。

⑺是面向对象程序设计语言不同于其他语言的主要特点，是否建立了丰富的(8)是

衡量一个面向对象程序设计语言成熟与否的重要标志之一。

16、(7)是面向对象程序设计语言不同于其他语言的主要特点，是否建立了丰富的

(8)是衡量一个面向对象程序设计语言成熟与否的重要标志之一。

A、继承性

B、消息传递

C、多态性

D、静态联编

标准答案：A

知识点解析：暂无解析

17、

A、函数库

B、类库

C、类型库

D、方法库

标准答案：B

知识点解析：面向对象程序设计语言的特点主耍有继承性、封闭性、多态性。继

承性(Inheritance)是指，在某种情况下，一个类会有“子类子类比原本的类(称为

父类)要更加具体化，子类会继承父类的属性和行为，并且也可包含它们自己的。

它的子类会继承这些成员。这意味着程序员只需要将相同的代码写一次。这是其他

类型的程序语言所不具备的。封装性(Enc叩sulation)是指面向对象程序设计隐藏了

某一方法的具体执行步骤，取而代之的是通过消息传递机制传送消息给它。多态性

(Polymorphism)指方法在不同的类中调用可以实现的不同结果。因此，两个甚至更

多的类可以对同一消息做出不同的反应。是否建立了丰富的类库是衡量一个面向

对象程序设计语言成熟与否的重要标志之一。

在过程式程序设计(①)、数据抽象程序设计(②)、面向对象程序设计(③)、泛型(通

用)程序设计(④)中，C++语言支持(13),C语言支持(14)。

18、在过程式程序设计(①”数据抽象程序设计(②)、面向对象程序设计(③)、泛

型(通用)程序设计(④)中，C++语言支持(13),C语言支持(14)。

A、①

B、②③

C、③④

D、S②③④

标准答案：D

知识点解析：暂无解析

19、

A、①

B、①③

C、@@

D、①②③④

标准答案：A

知识点解析：现代的C++语言支持过程式程序设计，数据抽象，面向对象程序设

计，泛型程序设计等多种程序设计风格，可以充分满足用户和系统对于开放性、高

效率、兼容性和扩展性的各种苛刻需求。C语言只支持过程式程序设计。

一个命题的可判定性是指：存在一种算法能给出该命题成立与否的结论。给定文法

G,只有当G为(26)时，命题“L(G)是空集、有限集或无限集”才是可判定的，当给

出两个不同文法G1和G2,只有当Gl,G2都是(27)时命题“L(G1)=L(G2)”才是可

判定的。

20、一个命题的可判定性是指：存在一种算法能给出该命题成立与否的结论。给定

文法G,只有当G为(26)时\命题“L(G)是空集、有限集或无限集”才是可判定

的，当给出两个不同文法G1和G2,只有当Gl,G2都是(27)时命题“L(G1)=

L(G2)”才是可判定的。

A、1型

B、2型

C、3型

D、0型

E、2型或3型

标准答案：E

知识点解析：暂无解析

21、

A、1型

B、2型

C、3型

D、0型

E、2型或3型

标准答案：c

知识点常析：用计算机对自然语言进行完全自动处理是一件十分困难的事情。这是

因为自然语言歧义性大，用形式化的语法描述起来很困难。为了便于计算机的自动

处理，语言的形式化描述便显得十分重要。现有算法语言在形式上都是形式语言。

在文法G[S]中，如果存在S：a,则称a是文法GF勺一个句型，仅含终结符号的句

型是文法G的一个句子。语言L(G)是由文法G产生的所有句子组成的集合，其形

式定义为：L(G)={a|S：a且此片)。我们称文法G1和文法G2是等价的，如果有

L(Gl)=L(G2)o即有可能不同的文法产生相同的语言。文法G是任意给出的，有

可能出现这样的情况：给定某个文法G,VT中的终止符所组成的任何字符串都无

法识别出它能由G生成，即L(G)是个空集。也可能有某个给定的文法G,其L(G)

无限制。由于VT的终止符可重复出现，字符串长度无限制，因此不可能用列举终

止字符串的方法进行句法分析。那么，如何判断给定G的乙(G)是无限集、有限

集，或是空集呢?我们期望能有一种算法，可直接从G出发，通过有限步运算给出

L(G)是空集、有限集或无限集的结论。若存在这样的算法，就是可判定的，否则就

不是可判定的。研究中发现可否判定L(G)是空集、有限集或无限集与文法G有

关。可以证明，当文法G是2型或3型时，是可判定的。对两个文法G1与G2是

否等价即是否有L(G1)=L(G2),只有当G1和G2都是3型文法时，才是可判定

的。

有限状态自动机可用5元组(VT，Q，3,qO,Qf)来描述，它可对应于(28)。设有一

有限状态自动机M的定义如下：VT={0,1),Q={qO,ql,q2)3定义为：

8(q0,0)=ql5(ql,0)=q26(q2,l)=q28(q2,l)=q2Qf={q2}oM是一个(29)有限状

态自动机，它所对应的状态转换图为(30),它所能接受的语言可以用正则表达式表

示为(31),其含义为(32)。

22、有限状态自动机可用5元组(VT，Q，6,q0,Qf)来描述，它可对应于(28)。设

有一有限状态自动机M的定义如下：VT={0,1),Q={qO,ql,q2)b定义为：

8(q0,0)=ql8(ql,0)=q28(q2,l)=q28(q2,l)=q2Qf={q2}oM是一个(29)有限状

态自动机，它所对应的状态转换图为(30),它所能接受的语言可以用正则表达式表

示为(31),其含义为(32)。

A、0型文法

B、1型文法

C、2型文法

D、3型文法

标准答案：D

知识点解析：暂无解析

23、

A、歧义的

B、非歧义的

C、确定的

D、非确定的

标准答案：C

知识点解析：暂无解析

三、中文选择题(含3小题)(本题共33题，每题7.0

分,共33分。)

在某超市里有一个收银员，且同时最多允许有n个顾客购物，我们可以将顾客和收

银员看成是两类不同的进程，且工作流程如图5-4所示。为了利用P・V操作正确地

协调这两类进程之间的工作，设置了三个信号量SI、S2和心,且初值分别为0,

0和n。这样图中的口应填写(46),图中的bl,b2应分别填写(47),图中的cl,c2

应分别填写(48)。图5Y超市购物流程图

24、在某超市里有一个收银员，且同时最多允许有n个顾客购物，我们可以将顾客

和收银员看成是两类不同的进程，且工作流程如图5-4所示。为了利用P-V操作正

确地协调这两类进程之间的工作，设置了三个信号量SI、S2和Sn，旦初值分别为

0,0和n。这样图中的口应填写(46),图中的bl,b2应分别填写(47),图中的cl,

看客进程…刀)收帙员进田

c2应分别填写(48)。图5Y超市购物流程图

A、P(S1)

B、P(S2)

C、P(Sn)

D、P(Sn),P(S1)

标准答案：C

知识点解析：暂无解析

25、

A、P(Sn)，V(S2)

B、P(Sn)，V(SD

C、P(S2),V(S1)

D、V(S1),P(S2)

标准答案：D

知识点解析：暂无解析

26、

A、P(S1),V(S2)

B、P(Sn),V(S1)

C、P(S2),V(SI)

D、V(S1),P(S2)

标准答案：A

知识点解析：操作系统的重要功能是解决进程间的同步与互斥问题。解决的办法主

要有加锁法、信号量机制、管程机制等。信号量是由一个整型变量和一个等待队列

构成的，对这个整型变量除了做初始化之外，只能实施P-V操作，即P操作和V

操作。P-V操作是原子操作，不可分割使用，必须成对出现，属于低级的进程通信

原语。采用P-V操作实现进程同步的步骤是首先为各并发进程设置私用信号量，

然后为私用信号量赋初值，最后利用P-V原语和私用信号量规定各进程的执行顺

序。采用P-V操作实现进程互斥的步骤是首先为临界资源设置公用信号量，然后

为公用信号量赋初值，最后利用P-V原语和公用信号量实现并发进程的互斥使用

临界资源。在本题中，收银员进程和顾客付款进程类似于生产者和消费者进程，顾

客要想付款必须判断收银员是否忙，忙则等待，不忙则付款。因此，对应的收银员

进程和顾客付款进程私用信号量分别是S1和S2,由于开始时没有顾客去付款，收

银员也没有收费，所以S1和S2的初值为0。这里的公用临界资源是允许进入的

(可容纳的)顾客人数储如果有n+1个顾客想购物，那么第n+1个顾客就得等待，

直到有人购物完毕出来方能进去，所以临界资源的信号量为Sn=n。顾客进入超市

时，允许进入的顾客人数减1,执行P(Sn),购物完毕准备付款时，通知收银员进

程有顾客付款，执行V(S1),此时收银员进程执行P(S1)操作后就可进入收黄，收

费完成后收银员进程执行V(S2),以通知顾客收费完毕，此时顾客执行P(S2)就可

离开收银台，在离开超市时需执行V(Sn),释放资源。

以太网遵循IEEE802.3标准，用粗缆组网时每段不能大于(28)m。超过上述长度

时，要分段，段间用(29)相连。同时，整个网的总长度不能大于(30)m。若总长度

超过上述长度，则需分成两个网，网之间用(31)相连。这是在ISO/OSI模型中(32)

层的连接。

27、以太网遵循IEEE802.3标准，用粗缆组网时每段不能大于(28)m。超过上述

长度时，要分段，段间用(29)相连。同时，整个网的总长度不能大于(30)m。若总

长度超过上述长度，则需分成两个网，网之间用(31)相连。这是在ISO/OSI模型中

(32)层的连接。

A、50

B、100

C、185

D、500

E、1000

标准答案：D

知识点解析：暂无解析

28、

A、网络适配器

B、重发器

C、调制解调器

D、网桥

标准答案：B

知识点解析：暂无解析

29、

A、50

B、100

C、185

D、500

E、1000

标准答案：B

知识点解析：暂无解析

30、

A、网络适配器

B、重发器

C、调制解调器

D、网桥

标准答案：D

知识点解析：暂无解析

31、

A、物

B、数据链路

C、网络

D、运输

标准答案：B

知识点解析：木题需要分析一些传输线缆的技术指标v1.粗缆粗缆传输距离长，

性能高但成本也高，使用于大型网局域干线，连接时两端接重发器(repealer)。在与

粗缆连接时，要外接收发器MAU,收发器与网卡之间用AUI电缆相连，因此网卡

连接时必须有AUI接口。受发送器的功率影响，以及接收器的分辨能力、媒体上

信号传输衰减和畸变的限制，10Basc5标准规定每段同轴电缆的长度不能超过

500mo超过上述长度时，段与段之间要用重发器相连。重发器实际上是把从一段

中接收到的信号放大后，再向另一段发送出去，有时也译为中继器。重发器不能

无限制地使用。由于以太网脉冲检测的需要，全网内端到端最大的信号传播延迟时

间不能超过一定的限制值，这使得整个网的总长度不能大于2500m。若总长度超

过了2500m.则要分成两个网.网之间再用网桥(bridge)来相连.这是在ISO的开

放系统互联(0SI)7层模型中数据链路层的相连。用重发器相连则是物理层的连接。

粗缆组网技术参数如下：.最大的干线段长度：500m.最大网络干线电缆长度：

2.5km.每条干线段支持的最大结点数：100.两站之间的最小距离：2.5m2.细缆

细缆是指直径为5m,特征阻抗为50f2的细同轴电缆。网络中每个结点需要一个提

供BNC接口的以太网，每个结点通过T型连接器与网络连接。T型连接器水平方

向的两个插接头用于连谖两段网线的两端，垂直的插口与网络适配器上的BNC连

接器相连。每个以太网中最多可以使用4个中继器，连接5条干线电缆。细缆组

网的技术参数如下：.最大的干线段长度：185m.最大的网络干线电缆长度：

925m.每条干线段支持的最大结点数：30.BNCT型连接器之间的最小距离：0.5m

3.光纤原理：由光发送机产生光束，将电信号变为光信号，再把光信号导入光

纤，在另一端由光接收机接收光纤上传来的光信号，并把它变为电信号，经解码后

再进行处理。分类：单模光纤和多模光纤。.单模光纤。由激光作为光源，只允许

单一模式的光线穿过光纤，不会发生干扰；传输距离长，2km以上。.多模光纤。

由二极管发光；允许多束光线穿过光纤，高带宽；由于不同光线可能互相干扰，故

只能适用于低速短距离芍输，2km以内。

协议是一组(33),它有助于(34)之间的相互理解和正确通信。协议中有三个关键因

素。其中(35)定义数据的表示形式，(36)则能使数据管理所需的信息得到正确理

解，(37)则规定了通信应答信号之间的间隔和先后关系。

32、协议是一组(33),它有助于(34)之间的相互理解和正确通信。协议中有三个关

键因素,其中(35)定义数据的表示形式，(36)则能使数据管理所需的信息得到正确

理解，(37)则规定了通信应答信号之间的间隔和先后关系。

A、软件

B、外部设备

C、通信实体

D、时钟

E、约定的规则

标准答案：E

知识点解析：暂无解析

33、

A,软件

B、外部设备

C、通信实体

D、时钟

E、约定的规则

标准答案：C

知识点解析：哲无解析

34、

A媒体

、

B语义

、

c文本

、

D语法

、

E时序

、

标及准答案：D

知A识点解析：暂无解析

B

>U媒体

义

语

本

D文

言

>语

E序

>时

嗦

W呼B

知识点解析：暂无解析

36、

A、媒体

B、语义

C、文本

D、语言

E、时序

标准答案：E

知识点解析：协议是对网络中设备以何种方式交换信息的一系列规定的组合，它对

信息交换的速率、传输弋码、代码结构、传输控制步骤、出错控制等许多参数做出

定义。在ARPA网中将协议按功能分成若干层次，分层标准和各层中采用的具体协

议的综合就构成了网络的体系结构。网络协议是为网络数据交换而制定的规则、约

定和标准的集合，是网络中各台计算机进行通信的一种语言基础和规范准则，定义

了计算机之间进行信息交换所必须遵循的规则。一个网络协议由语法、语义、时序

组成。(1)语法：用户数据与控制信息的结构与格式。(2)语义：需要发出何种控制

信息、，以及完成的动作及做出的响应，用于协调和差错的控制信息。(3)时序：对

事件实现顺序的详细说明，包括速度匹配和任务排序。

国际标准化组织(ISO)的开放系统互联(OSI)参考模型共分七层。其中，处理系统之

间用户信息的语法表达形式问题的是(38)层；规定通信双方相互连接的机械、电

气、功能和规程特性的是(39)层：向用户提供各种直接服务，如文件传送、电子邮

件、虚拟终端等的是(4。)层；通过校验和反馈、重发等方法将原始不可靠的物理连

接改造成无差错的数据通道的是(41)层：负责通信子网中从源到目标路径选择的是

(42)层。

37、国际标准化组织(ISO)的开放系统互联(OSI)参考模型共分七层。其中，处理系

统之间用户信息的语法表达形式问题的是(38)层；规定通信双方相互连接的机械、

电气、功能和规程特性的是(39)层；向用户提供各种直接服务，如文件传送、电子

邮件、虚拟终端等的是(40)层；通过校验和反馈、重发等方法将原始不可靠的物理

连接改造成无差错的数据通道的是(41)层：负责通信子网中从源到目标路径选择的

是(42)层。

A、物理层

B、数据链路层

C、网络层

D、运输层

E、表示层

标准答案：E

知识点解析：暂无解析

38、

A、物理层

B、数据链路层

C、网络层

D、运输层

E、会话层

标准答案：A

知识点解析：暂无解析

39、

A、物理层

B、应用层

C、网络层

D、运输层

E、会话层

标准答案：B

知识点解析：暂无解析

40、

A、物理层

B、数据链路层

C,网络层

D、运输层

E、会话层

标准答案：B

知识点解析：暂无解析

41、

A、物理层

B、数据链路层

C、网络层

D、运输层

E、会话层

标准答案：C

知识点解析：开放系统互联参考模型OSI/RM(OpenSystem

Interconnection/ReferenceModel)最初是用来作为开发网络通信协议族的一个工业参

考标准，作为各个层上使用的协议国际标准化的第一步而发展来的。严格遵守0SI

模型，不同的网络技术之间可以轻而易举地实现互操作。整个OSI/RM模型共分七

层，从下往上分别是：物理层、数据链路层、网络层、传输层、会话层、表示层和

应用层。当接收数据时，数据是自下而上传输：当发送数据时，数据是自上而下传

输。七层的主要功能见表7-2。

表7-2OSI/RI模型的七层及主要功能

层次层的名称英文主要功能

7应用层ApplicationLayer处理网络应用

6表示层PresentationLayer故据表示

5会话层SessionLayer互连主机通信

4传输层TransportLayer端到端连接

3掰络层NetworkLayer分组传输和路由选择

2故据链路层DataLinkLayer传送以帧为单位的信息

1胡理层PhysicalLayer二进制传输

在网络数据通信的过程中，每一层要完成特定的任务。当传输数据的时候，每一层

接收上一层格式化后的数据，对数据进行操作，然后把它传给下一层。当接收数据

的时候，每一层接收下一层传过来的数据，对数据进行解包，然后把它传给上一

层。从而实现对等层之间的逻辑通信。OSI模型并未确切描述用于各层的协议和服

务，它仅仅告诉我们每一层该做些什么。1.物理层物理层是OSI的最

低层，提供原始物理通路，规定处理与物理传输介质有关的机械、电气特性和接

口。物理层建立在物理介质上（而不是逻辑上的协议和会话），主要任务是确定与传

输媒体接口相关的一些特性，即机械特性、电气特性、功能特性及规程特性，涉及

到电缆、物理端口和附属设备。双绞线、同轴电缆、接线设备（如网卡等）、RJ-45

接口、串口和并口等在网络中都是工作在这个层次的。物理层数据交换单位为二进

制位bit,因此要定义传输中的信号电平大小、连接设备的开关尺寸、时钟频率、

通信编码、同步方式等。2.数据链路层数据链路层的任务是把原始不可

靠的物理层连接变成无差错的数据通道，并解决多用户竞争，使之对网络层显现为

一条可靠的链路，加强了物理层传送原始比特的功能。该层的传输单位是帧。通过

在帧的前面和后面附加上特殊的二进制编码模式来产生和识别帧边界。数据链路层

可使用的协议有SLIP、PPP、X25和帧中继等。常见的集线器和低档的交换机等网

络设备都是工作在这个层次上的，MODEM之类的拨号设备也是工作在这一层次

上的。在任何网络中数据链路层都是必不可少的，相对于高层而言，此层所有的服

务协议都比较成熟。数据链路层主要包括以下功能。（1）数据链路连接的

建立与释放；（2）构成数据链路的数据单元；（3）数据链路连接的分裂；

（4）帧定界与同步；（5）流量控制和差错的检测与恢复。3.网络层网

络层将数据分成一定长度的分组，负责路由（通信子网到目标路径）的选择。以数据

链路层提供的无差错传输为基础，为实现源设备和目标设备之间的通信而建立、维

持和终止网络连接，并通过网络连接交换网络服务数据单元。它主要解决数据传输

单元分组在通信子网中的路由选择、拥塞控制，以及多个网络互联的问题，通常提

供数据报服务和虚电路服务。网络层建立网络连接为传输层提供服务。在具有开放

特性的网络中，数据终端设备都要配置网络层的功能，主要有网关和路由器。

网络层有以卜主要功能。（1）路由选择和中继；（2）网络连接的激活、终

止；（3）网络连接多路复用；（4）差错检测与恢复；（5）排序、流量控

制；（6）服务选择。4.传输层传输层既是七层模型中负责数据通信

的最高层，又是面向网络通信的低三层和面向信息处理的最高三层之间的中间层，

解决的是数据在网络之间的传输质量问题，它属于较高层次。传输层用于提高网络

层服务质量，提供可靠的端到端的数据传输，如常说的QoS就是这一层的主要服

务。这一层主要涉及的是网络传输协议，它提供的是一套网络数据传输标准，如

TCP协议。本层可在传送数据之前建立连接，并依照连接建立时协商的方式进行

可信赖的资料传送服务。若传输层发现收到的包有误、或送出的包未收到对方的认

可，则可继续尝试数次，直到正确收到或送出包，或是在尝试数次失败之后向上层

报告传送错误的信息。简而言之，传输层能检测及修正传输过程中的错误。传输层

反映并扩展了网络层子系统的服务功能，并通过传输层地址提供给高层用户传输数

据的通信端口，使系统间高层资源的共享不必考虑数据通信方面的问题。本层的最

终目标是为用户提供有效、可靠和价格合理的服务。传输层的主要功能如

下。（I）映像传输地址到网络地址；（2）多路复用与分割：（3）差错控

制及恢复；（4）分段与重新组装；（5）组块与分块；（6）传输连接的建

立与释放；（7）序号及流量控制。5.会话层会话层利用传输层提供

的端到端数据传输服务，具体实施服务请求者与服务提供者之间的通信，属于进程

间通信范畴。管理不同主机进程间的对话，主要针对远程终端访问。会话层使用校

验点使通信会话在通信失效时从校验点继续恢复通信。这种能力对于传送大的文件

极为重要。会话层、表示层、应用层构成开放系统的高三层，面对应用进程提供分

布处理、会话管理、信息表示、恢复最后的差错等。通常，会话层提供服务需要建

立连接、数据传输、释放连接等三个阶段。会话层是最薄的层，常被省略。

会话层的主要功能如下。（1）会话连接到传输连接的映射；（2）数据传送：

（3）会话连接的恢复和释放；（4）对会话参数进行协商；（5）选择合适的

QoS；（6）活动管理；（7）令牌管理。6.表示层表示层处理系统

间用户信息的语法表达形式。每台计算机可能有它自己的表示数据的内部方法，需

要协定和转换来保证不同的计算机可以彼此理解。表示层具有的主要功能如

下。（1）数据语法转换：（2）数据加密和数据压缩；（3）语法表示；

（4）表示连接管理。7.应用层应用层是OSI/RM的最高层，是直接面向

用户的一层，是计算机网络与最终用户间的界面。应用层包含用户应用程序执行通

信任务所需要的协议和功能，如电子邮件和文件传输等。在这一层中，FTP（File

TransferProtocol,文件传输协议）、SMTP（SimpleMailTransferProtocol,简单邮件

传输协议）、POP（PostOfficeProtocol,邮局协议）等协议得到了充分应用。在

实际情况中，常把会话层和表示层归入应用层，成为五层简化的OSI参考模型。

当网络用户通过网络与另一台主机X通信，发现响应太慢时，可运行（43）程序，把

一个分组发向主机X,通过查看所返回的分组首部的（44）,发现问题的所在，并采

取相应的措施。对于一个大中型网络，需要有一个网络管理系统进行管理。当前流

行的各类网管平台软件都支持（45）协议。驻留在（46）上的网管平台软件可通过该协

议软件调阅被管理的网络结点内的管理信息库中的内容。有若干常用的网络平台软

件，但（47）不是网管平台软件。

42、当网络用户通过网络与另一台主机X通信，发现响应太慢时，可运行（43）程

序，把•个分组发向主机X,通过查看所返回的分组首部的（44）,发现问题的所

在，并采取相应的措施。对于一个大中型网络，需要有一个网络管理系统进行管

理。当前流行的各类网管平台软件都支持（45）协议。驻留在（46）上的网管平台软件

可通过该协议软件调阅被管理的网络结点内的管理信息库中的内容。有若干常用的

网络平台软件，但(47)不是网管平台软件。

A、Browser

B、Bitware

C、Ping

D、Handshaking

标准答案：C

知识点解析：暂无解析

43、

A、地址

B、时戳

C、标志码

D、校验码

标准答案：B

知识点解析：暂无解析

44、

A,MAP

B、SNMP

C、MBS

D、FTAM

标准答案：B

知识点解析：暂无解析

45、

A、数据库服务器

B、通信服务器

C、主路由器

D、网络管理工作站

标准答案：D

知识点解析：暂无解析

46、

A、NetManager

B、OpenView

C、SunView

D、NetView

标准答案：C

知识点解析：本题主要测试考生对网络基本概念和常用方法的掌握程度。1.Ping

命令Ping命令的工作过程到底是怎么样的？假定主机A的IP地址是

10.0.0.1,主机B的IP地址是10.0.0.2,在同一子网内。当用户在主机A

上运行“Ping10.0.0.2”后，都发生了些什么呢？首先，Ping命令会构建一个固

定格式的ICMP（InternetControlMessageProtocol）请求数据包，然后由ICMP协议

将这个数据包连同地址10.0.0.2一起交给IP层协议（和ICMP一样，实际上是

一组后台运行的进程），IP层协议将以地址10.0.0.2作为目的地址，本机”地址

作为源地址，加上一些其他的控制信息，构建一个D数据包，并在一个映射表中

查找出IP地址10.0.0.2所对应的物理地址（也叫MAC地址，这是数据链路层

协议构建数据链路层的传输单元，即帧所必需的），一并交给数据链路层。后者构

建一个数据帧，目的地址是IP层传过来的物理地址，源地址则是本机的物理地

址，还要附加上一些控制信息，依据以太网的介质访问规则，将它们传送出去。

主机B收到这个数据帧后，先检查它的目的地址，并和本机的物理地址比对，如

符合，则接收；否则丢弃。接收后检查该数据帧，将IP数据包从帧中提取出来，

交给本机的1P层协议。同样，1P层检查后，将有用的信息提取后交给ICMP协

议，后者处理后，马上陶建一个ICMP应答包，发送给主机A,其过程和主机A

发送ICMP请求包到主机B一模一样。从Ping的工作过程，我们可以知道，主机

A收到主机B的一个应答包，说明两台主机之间的去、回通路均正常。也就是

说，无论从主机A到主机B,还是从主机B到主机A,都是正常的。同时，发送

方可以通过检查返回包首部的时间戳来获得应答时间的长短信息。因此当网络用户

通过网络与另一台主机X通信，发现响应太慢时，可运行Ping程序，把一个分组

发向主机X,通过查看所返回的分组首部的时间戳，发现问题的所在，并采取相应

的措施。IP协议提供的是不可靠非面向连接的数据报服务。为了使网上的计算机

能够检测报告差错，或提供有关意外情况的信息，设计者在IP协议中提供了一种

有特殊作用的报文制，即ICMP。它位于IP数据报的数据部分，同IP数据报的数

据信息一样在网上传输，但其目的地不是目的计算机上的一个用户进程，而是该计

算机上的IP协议软件。当一个有错误的ICMP报文到达时，IP协议软件模块就处

理本身的问题，不再将其提供给高层。2.网络管理协议网络管理系统中最重要的

部分就是网络管理协议，它定义了网络管理器与被管代理间的通信方法。首先开始

研究网络管理通信标准问题的是国际上最著名的国际标准化组织ISO,他们对网络

管理的标潴化工作始于1979年，主要针对OSI七层协议的传输环境而设计。ISO

的成果是CMIS（公共管理信息服务）和CMIP（公共管理信息协议）。CMIS支持管理

进程和管理代理之间的通信要求，CMIP则提供管理信息传输服务的应用层协议，

二者规定了OSI系统的网络管理标准。基于0SI标准的产品有AT&T的

Accumaster和DEC公司的EMA等，HP的OpenView最初也是按OSI标准设计

的。后来，IETF为了管理以几何级数增长的Internet,决定采用基于OSI的