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

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

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

1、在一个双向链表中，在*p结点之后插入结点*q的操作是（）。

A^q—>prior=p；p—>next=q；p—>next—>pior=q；q—>next=p—>next；

—

BNq—>ncxt=p>ncxt；p—>ncxt—>prior=q；p—>ncxt=q；q—>prior=p；

C、p—>next=q；q->prior=p；q->next=p->next；p->next->prior=q；

D、p—>next—>prior=q；q—>next=p->next：q—>prior=p；p—>next=q：

标准答案：B

知识点解析：在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背

线性表的逻辑特征。本题主要考查双向链表的插入算法中的指针的变化过程。虽

然4个选项中的语句相同，但顺序不同，根据双向链表的结构特点可知选项B的

操作顺序是正确的，其他3个选项的指针修改顺序不能完成在*p结点之后插入结

点*q的操作”

2、设线性表中有2n个元素，以下操作中，在单链表上实现要比在顺序表上实现效

率更高的是（）。

A、删除指定元素

B、在最后一个元素的后面插入一个新元素

C、顺序输出前k个元素

D、交换第i个元素和2n—i—1个元素的值（i=0,1,…，n-1）

标准答案：A

知识点解析：在顺序表中删除元素需要移动较多元素，而在单链表上执行同样的操

作不需要移动元素。

3、设数组S［n］作为两个栈S］和S2的存储空间，对任何一个栈只有当S［n］全满时

才不能进行进栈操作。为这两个栈分配空间的最佳方案是（）。

A^Si的栈底位置为0,S2的栈底位置为n—1

B、Si的栈底位置为0,S2的栈底位置为n/2

C、si的栈底位置为0,S2的栈底位置为n

D、S］的栈底位置为0,S2的栈底位置为1

标准答案：A

知识点解析：利用栈底位置不变的特性，可让两个顺序栈共享一个一维数据空间，

以互补余缺，实现方法是：将两个栈的栈底位置分别设在存储空间的两端，让它们

的栈顶各自向中间延伸。这样，两个栈的空间就可以相互调节，只有在整个存储空

间被占满时才发生上溢，这样一来产生上溢的概率要小得多。

4、若用一个大小为6的数组来实现循环队列，且当前rear和from的值分别为。和

3,当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是()1

A、1和5

B、2和4

C、4和2

D、5和1

标准答案：B

知识点解析：出队1个元素后，front=(front+l)%MAXQSIZE,front的值是4：

入队两个元素后，rcar=(rcar+2)%MAXQSIZE,rear的值是2。

5、利用逐点插入建立序列(50,72,43,85,75,20,35,45.,65,30)对应的

二叉排序树以后，要查找元素30要进行元素间的比较次数是()。

A、4

B、5

C、6

D、7

标准答案：B

知识点》析：利用逐点插入法建立二叉排序树是从空树开始，通过查找，将每个结

点作为一个n|子插入。项题目中数据的输入次序建立的二叉排序树如下图所示，查

找元素30的比较次数为5次。哼

6、将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度

是()。

A、4

B、5

C、6

D、7

标准答案：C

知识点解析：将二叉树的性质4推广到完全三叉树即可得出正确答案。［归纳总结］

含有n个结点的完全三叉树的高度是［log3⑵1+1)］。

7、在一个具有n(n>0)个顶点的连通无向图中，至少需要的边数是()。

A、n

B、n+l

C、n—1

D、n/2

标准答案：C

知识点解析：在无向图中，如果从一个顶点Vi到另一个顶点Vj(iKj)有路径，则称顶

点党和Vj是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。所以

具有n个顶点的连通无向图至少有n—l条边。［归纳总结］具有n个顶点的连通无

向图至少有n-1条边，具有n个顶点的强连通有向图至少有n条弧。

8、已知一个线性表(38,25,74,63,52,48),假定采用散：列函数h(key)=

key%7计算散列地址，并散列存储在散列表A［0..6］中，若采用线性探测方法解

决冲突，则在该散列表上进行等概率成功查找的平均查找长度为()。

A、1.5

B、1.7

C、2

D、2.3

标准答案：C

知识点解析•：按照散列函数h(key)=key%7和线性探测方法解决冲突，将线性表

(38,25,74,63,52,48)散列存储在散列表A［0.•6］中，如下图所示。

IAIAIXI

比0仄・II1124

■和AS-

9、有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概

率情况下，查找失败时所需的平均比较次数是()。

A、37/12

B、62/13

C、39/12

D、49/13

标准答案：B

知识点解析：长度为12的折半查找判定树中有13个外结点，如下图所示。

用于长度力序&.折隼食我失01H的平均代表长度为；

ASL-<4X3^5X|O)/|S-«213对于长度为12的有序表，折半查

找失败时的平均查找长度为：ASL=(4x3+5xlO)/13=62/13

10、下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是

()。

A、快速排序

B、希尔排序

朴A机厩欢的$・次・构!I［解题技巧］将多个级别从上向下或从下

向上排出顺序，即可得出正确结果。

13、已知定点整数x的补码为lx3X2Xixo，且x>-8,则必是（）。

A、X3=l,X2~xo至少有一个1

B、X3=0,X2〜X0至少有一个1

C、X3=l，X2〜X0任意

D、X3=0，X2〜Xo任意

标准答案：A

知识点解析：这是一个负数，x>-8,意味着0>x>—8。x=-8的补码表示为

11000,应将一8排除在外。［归纳总结］写出相应定点整数的补码表示形式：11001

一7.......11111—1发现规律为：X3=l，X2~X0至少有一个1。［解题技巧］注意负

数的补码表示，代码越大，其绝对值越小。

14、在规格化浮点运算中，若某浮点数为22x1.10101,其中尾数为补码表示，则

该数是（）。

A、不需规格化

B、需右移规格化

C、需将尾数左移一位规格化

D、需将尾数左移两位规格化

标准答案：C

知识点解析•：浮点数25x1.10101的尾数不是规格化数，需要进行左规。［归纳总

结］对于诸如0.Oxx…x和1.Ixx…x这类非规格化数，需要使尾数左移以实现规

格化，这个过程称为左规。尾数每左移一位，阶码相应减1,直至成为规格化数为

止。［解题技巧］由于左规一次之后尾数就成为规格化数了，所以只需左移一位。

15、汉字“啊”的十进制区位码为它的十六进制机内码是（）。

A、160IH

B、9081H

C、BOAIH

D、B081H

标准答案：C

知识点解析:区位码16—01（十进制）=1001H,国标码=1001H+2020H=3021H,

机内码=3021H+8080H=BOAIH。［归纳总结］汉字的区位码长4位，前两位表示

区号，后两位表示位号，区号和位号用十进制数表示。汉字国标码和汉字机内码都

是两字节长的代码，汉字机内码是在相应国标码的每个字节最高位上加“1”。3种

汉字编码的关系：汉字国标码=汉字区位码（十六进制）+2020H汉字机内码=汉字

国标码+8080H汉字机内码=汉字区位码（十六进制）+A0A0H通常，汉字的国标

码和机内码都用十六进制数表示，而汉字区位码用十进制数表示，所以在3种汉字

编码的转换时，千万不要忘记先将十进制的区位码变成十六进制之后，再利用上述

关系式进行转换。［解题技巧］首先将十进制的区位码转换成十六进制，然后直接加

AOAOH即可。

16、在一个按字节编址的计算机中，若数据在存储器中以小端方案存放。假定int

型变量i的地址为08000000H,i的机器数为01234567H,地址08000000H单元的

内容是（）。

A、01H

B、23H

C、45H

D、67H

标准答案：D

知识点解析：小端方案是将最低有效字节存储在最小地址位置。在数01234567H

中，最低有效字节为67H。［归纳总结］一个多字节的数据在按字节编址的主存中通

常由两种排序方案一大端次序和小端次序。大端次序方案将最高有效字节存储在

最小地址位置，小端次序方案将最低有效字节存储在最小地址位置。

17、在CPU的状态寄存器中，若符号标志为表示运算结果是（）。

A、正

B、负

C、零

D、不一定

标准答案：B

知识点解析：符号标志位SF=0,表示为正数，符号标志位SF=1,表示为负数。

I归纳总结］状态标志寄存器用来存放程序状态字（PSW）。程序状态字的各位表征程

序和机器运行的状态，是参与控制程序执行的重要依据之一。它主要包括两部分内

容：一是状态标志，如进位标志（C）、结果为零标志（Z）等，大多数指令的执行洛会

影响到这些标志位；二是控制标志，如中断标志、陷阱标志等。

18、在微程序控制器设计中，假设微命令采用最短编码法，需产生N种微操作。

则微命令控制字段要设置的位数是（）。

A、Uog2（N+l）］

B、N

C>［logaN］

D、［log2N］+l

标准答案：c

知识点解析：由于微命令控制字段必须是一个整数，所以在最短编码法中为

［log2N］fio［归纳总结］最短编码法将所有的微命令统一编码，每条微指令只定义

一个微命令。若微命令的总数为N,操作控制字段的长度为L,则最短编码法应满

足下列关系式：L>log2N

19、下列是有关冯.诺依曼结构计算机中指令和数据存放位置的叙述，其中正确的

是（）。

A、指令存放在内存中，数据存放在外存中

B、指令和数据任何时候都存放在内存中

C、指令和数据任何时候都存放在外存中

D、程序被启动前指令和数据都存放在外存中，而启动后指令和数据被装入内存

标准答案：D

知识点解析：计算机关机状态时，计算机中指令和数据存放在外存中，但是CPU

不能直接和外存交互信息，因此启动后的指令和数据被装入内存。［归纳总结］外存

设置在主机外部，它的存储容量大，价格较低，但存取速度较慢，一般用来存放暂

时不参与运行的程序和数据，CPU不可以直接访问外存，外存中的程序和数据在

需要时才传送到内存，因此它是内存的补充和后援。［解题技巧］冯.诺依曼结构计

算机中指令和数据存放在同一存储器中。

20、在读写硬盘的一个物理记录块时，不需要的参数是（）。

A、柱面（磁道）号

B、盘片（磁头）

C、簇号

D、扇区号

标准答案：C

知识点解析：在读写硬盘的一个物理记录块时，需要的参数是磁道号、磁头号和扇

区号。［归纳总结］主机向磁盘控制器送出有关寻址信息，磁盘地址一般表示为：

驱动器号、圆柱面（磁道）号、记录面（磁头）号、扇区号

21、有效容量为128KB的Cache,每块16字节，8路组相联。字节地址为

1234567H的单元调入该Cache,其Tag应是（）。

A、1234H

B、2d68H

C、048DH

D、12345H

标准答案：C

知识点解析：因为块的大小为16字节，所以块内地址字段为4位；又因为Cache

容量为128KB,八路组相联，所以可以分为1024纽，128KB;(16x8)=1024,对应

的组号字段10位；剩下为标记字段。1234567H=

0001001000110100010101100111,标记字段为其中高14位,00010010001101=

048DH［归纳总结］在组相联映射方式下，主存地址分为3部分，依次为标记

(Tag)、组号(Index)和块内地址(Offset)。［解题技巧］将十六进制的主存地址写成二

进制，取前14位就是标记字段。

22、中断的概念是()。

A、哲停正在运行的程序

B、暂停对内存的访问

C、暂停CPU运行

D、I/O设备的输入或输出

标准答案：A

知识点解析：程序中断的实质是程序切换，由现行程序切换到中断服务程序，再由

中断服务程序返回到现行程序。所以中断只是暂停正在运行的程序，而不会暂停

CPU的运行，也不会暂停对内存的访问。［归纳总结］程序中断是指计算机执行现

行程序的过程中，出现某些急需处理的异常情况和特殊请求，CPU暂时中止现行

程序，而转去对随机发生的更紧迫的事件进行处理，在处理完毕后，CPU将在动

返回原来的程序继续执行。［解题技巧］此题容易误选D,其错误在于中断不仅用于

I/O设备的输入输出，还用于对计算机内部的故障和错误进行处理。

23、在操作系统的以下功能中，不需要硬件支持的是()。

A、中断系统

B、时钟管理

C、地址映射

D、页面调度

标准答案：D

知识点解析：中断系统需要硬件的支持是显而易见的，在中断过程中保存和恢复寄

存器值都需要硬件支持；时钟管理需要硬件计数器保持时钟的运行；地址映射中需

要基地址(或页表)寄存器和地址加法器的支持；页面调度由相关调度算法完成，不

需要硬件支持；注意，页面调度算法仅计算需要调入或置换的目标页面，调入过程

(例如缺页中断处理过程)才是与硬件相关的。

24、在单处理机的多进程系统中，进程什么时候占用处理机以及决定占用时间的长

短是()。

A、进程相应的代码长度

B、进程总共需要运行的时间

C、进程特点和进程调度策略

D、进程完成什么功能

标准答案：C

知识点解析：本题考查进程调度的时机和进程调度的策略。进程调度的时机与进程

特点有关，例如进程是否是CPU繁忙型还是IO繁忙型，自身的优先级等。但是仅

有这些特点是不够的，能否得到调度还取决于进程调度策略，若采用优先级调度算

法，则进程的优先级才起作用。至于占用处理机运行时间的长短，则要看进程自

身，若进程是10繁忙型，运行过程中要频繁访问IO,也就是说，可能会频繁主动

放弃CPU,所以，占用CPU的时间就不会长，一旦放弃CPU,则必须等待下次调

度。若进程是CPU繁忙型，则一旦占有CPU就可能会运行很长时间，但是，运行

时间还取决于进程调度策略，大部分情况下，交互式系统为改善用户的响应时间，

大多采用时间片轮转的算法，这种算法在进程长期占用CPU到一定时间后，会强

制将其换下，以保证其它进程的CPU使用权。所以，本题的正确答案应为选项

C,其它都不是。

25、系统产生死锁的可能原因是（）。

A、共享资源分配不当

B、系统资源不足

C、进程运行太快

D、CPU内核太多

标准答案：A

知识点解析：系统死锁的可能原因主要是时间，和空间，的。时间，由于进程运行

中推进顺序不当，即调度时机不合适，不该切换进程时进行了切换，可能会造成死

锁；空间上的原因是对共享资源分配不当，互斥资源部分分配乂不可剥夺，极易造

成死锁。那么，为什么系统资源不足不是造成死锁的原因呢?系统资源不足只会对

进程造成饥饿，例如，某系统只有3台打印机，若进程运行中要申请4台，显然不

能满足，该进程会永远等待下去。如果该进程在创建时便声明需要4台打印机，那

么操作系统立即就会拒绝，不会创建该进程的。一般，系统由于部分分配，剩余资

源不足时，可能会造成死锁，这实际上是资源分配不当的一种表现。不能以系统资

源不足来描述剩余资源不足的情形。

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

A、进程时间片用完

B、进程刚完成I/O,进入就绪队列

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

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

标准答案：A

知识点解析：进程时间片用完可以降低其优先级，完成I/0的进程应该提升其优

先级，处于就绪队列等待调度的进程一般不会改变其优先级。这类题目一般在采

用多级反馈队列调度算法的系统中应用。其具体算法为：设置多个就绪队列，并为

各个队列赋予不同的优先级。第一个队列的优先级最高，第二队次之，其余队列优

先级依次降低。赋予各个队列中进程运行时间片的大小也各不相同。在优先级越高

的队列中，每个进程的运行时间片就越小。当一个新进程进入内存后，首先将它放

入第一队列的末尾，也就是优先级最高，按先来先服务的原则排队等待调度。当轮

到该进程运行时，如能在该时间片内完成，便可准备撤离系统。如果它在一个时间

片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，此时其优先级降低

了一级，再同样地按先来先服务原则等待调度运行。如果它在第二队列中运行一个

时间片后仍未完成，再以同样方法，将它转入第三队列。它的优先级乂降低了一

级。如此下去，当一个长作业从第一队列降到最后一个队列后，在最后一个队列

中，使用时间片轮转方式运行。此时优先级也就再也无法降低了。仅当第一队列空

闲时，调度程序才调度第二队列中的进程运行。仅当第一至N队列均为空时•，才

会调度第N+1队列中的进程运行。如果处理机正在第J队列中为某进程服务时，

又有新进程进入优先级较高的队列，那么要考虑是否是可抢先式调度算法，若是，

则新进程将抢占正在运行进程的处理机，而由调度程序把正在运行的进程放回到第

J队列，将处理机分配给新进程。若不是，则需要等待直到当前的进程完成它的时

间片再调度，此时会产生优先级翻转的情形，亦即在处理机上运行的进程其优先级

低于就绪队列中的某个进程。这种情形非常糟糕，极易引起死锁。一般应该避免。

27、在某计算机中采用了多级存储体系，设计有cache,主存和磁盘，假设访问

cache一个字需要花费10ns,若该字不在cache中但是存在在主存中，那么需要

100ns载入cache,然后重新开始定位。若该字既不在cache中，也不在主存中，那

么需要10ms的时间装入主存,再化100ns复制到cache,再开始定位。设cache的

命中率为0.90,主存的命中率为0.75,那么，该系统访问一个字的平均时间是

()o

25000ns

B、250023ns

C、250017ns

D、250020ns

标准答案：D

知识点解析：本题考查多级存储层次下的平均访问时间。多级存储是现代计算机为

了获得比较优异的存储器访问性能又比较廉价的一种实现方法。正确的计算需要搞

清楚CPU访问一个字的流程。通常，若需要执行的指令字已经载入到cache中，

那么，仅需要从cache中取出放到指令队列上即可，所花费的时间即是cache的访

问时间。当cache中缺席时，产生中断，调用cache更新程序，将所需的指令字载

入cache,然后返回到中断点继续定位，所需的时间是访问cache的时间和中断服

务程序所花费的时间之和。同理，可以推断出访问不在主存中的指令字所需花费的

时间是磁盘装入时间与内存中断服务程序时间以及cache访问时间的和。根据各自

命中率的不同,可以计算出总时间为：10x0.94-(10+110)x(1-0.9)x0.754-(10

+100+10000000)x(1-0.9)X(l-o.75)=250020ns

28、在一个采用请求式调页的虚拟存储系统中，存放在外存上的程序代码调入内存

的时机是()。

A、在进程创建填写进程表时

B、在进程创建分配内存时

C、在进程被调度占用处理机执行时

D、在每次产生缺页中断时

标准答案：D

知识点解析：本题考查虚拟存储系统中程序调入内存的时刻。在一个采用请求式调

页的虚拟存储系统中，当一个程序需要执行时，首先由进程创建模块为新进程找到

一张空白的进程表，将该进程的基本信息填入这张表，例如进程号，父进程，进程

组，优先级，状态字等，然后分配该进程虚拟内存空间（此时不做任何实际的分

配），打开文件获得句柄，链接到用户活动文件数据表中，分配设备等，做完这些

工作，进程表将被放入就绪队列（假设所有资源均可用，只等CPU调度），等待操

作系统的调度模块调度。调度模块按照规定的调度算法，从就绪队列中选择一个进

程（对于单核处理机），将运行状态赋予该进程，然后切换CPU,使得CPU的程序

计数器指向该进程起首执行处，开始运行。通常，新创建的进程是仅有虚拟地址空

间的，所以，当第一次次行该进程时，代码不在物理内存，于是产生一次缺页中

断。缺页中断机构把对应的页面从外存调入内存，返回到中断点继续运行。对于请

求式调页，每次产生缺页中断一般仅调入相关的一页，若运行过程中所需的页面不

在内存，那么随时可以产生缺页中断，调入内存。若在进程运行过程中，所需的页

面已经在内存了，那么就不需要再将代码调入内存。因此，真正将程序代码和数据

调入内存的是缺页中断处理过程，其它过程不会对内外存的活动进行操作。

29、为了防止各种意外可能破坏文件，文件系统保护文件的方法可以是（）。

A、为文件加密

B、对每个文件规定使用权限

C、建立副本和定时转储

D、为文件设置口令

标准答案：C

知识点解析：本题主要考查文件保护、防止系统故障或人为误操作造成的破坏。文

件的保护是防止文件被破坏，造成文件可能被破坏的原因有时是硬件故障、软件失

误引起的，有时是由于共享文件时引起的错误，应根据不同的情况，采用不用的保

护措施。为了防止各种意外可能破坏文件，文件系统可以采用建立副本和定时转储

的方法，来保护文件。建立副本是指把同一个文件存放到多个存储介质上，当某个

存储介质上的文件被破坏时，可用其他存储介质上的备用副本来替换。这种方法简

单，但系统开销增大，且当文件更新时必须改动所有的副本，也增加了系统的负

担。因此，这种方法适用于容量较小且极为重要的文件。另一种保护方法是定时转

储，即定时地把文件转储到其他的存储介质上。当文件发生故障时，就用转储的文

件来复原，把有故障的文件恢复到某一时刻的状态，仅丢失了自上次转储以来新修

改或增加的信息。UNIX系统就采用定时转储来保护文件，提高文件的可靠性。正

确答案为C。

30、已知某磁盘的平均转速为r秒/转，平均寻道时间为T秒，每个磁道可以存储

的字节数为N,现向该磁盘读写b字节的数据，采用随机寻道的方法，每道的所有

扇区组成一个簇，请问：平均访问时间是（）。

A、b/N*（r+T）

B、b/N*2

C、（b/N+T）*r

D、b*T/N+r

标准答案：A

知识点解析：本题考查磁盘结构和磁盘读写的概念。磁盘是旋转盘式存储设备，每

个盘面划分有若干存储信息的同心圆称为磁道，每个磁道乂划分成多个扇区。木题

中，将每道的所有扇区组成一个簇，意味着可以将一个磁道的所有存储空间组织成

一个数据块组，这样有利于提高存储速度。读写磁盘时，磁头首先要找到磁道，称

为寻道，然后才可以将信息从磁道里读出来或写进去。读写完一个磁道以后磁头会

继续寻找下一个磁道，完成剩余的工作，所以，在随机寻道的情况下，读写一个磁

道的时间要包含寻道时间和读写磁道时间，即T+r秒。由于总的数据量是b字

节，它要占用的磁道数为b/N个，所以总的平均读写时间为b/N*（T+r）秒。如

果不采用随机寻道，而是采用连续读写的方式，那么磁盘的存储方式是这样的，首

先也是寻道，找到一组连续的磁道（用于连续读或写，写入的话磁道总容量必定大

于要写入的信息总数），花费时间T秒，然后再花费r秒将N个字节的信息写入（或

读出），然后磁头移动到下一道（此时，这个磁道与上一个磁道是紧紧挨着的，几乎

可以不花费时间），继续写入（或读出）N字节，循环往复，直到全部信息写入（或读

出）完成。这样的话，总时间可以缩短为b/N*r+T。因为其不需要每次都去寻

道，只需一次寻道即可。所以，考生要注意题目的条件，找出符合题意的正确答

案。

31、文件系统中，当调用open。去打开一个文件时，其主要目的是（）。

A、把文件内容从外存调入内存

B、把文件的控制信息从外存调入内存

C、把文件系统的文件分配表调入内存

D、把文件系统的目录调入内存

标准答案：B

知识点解析：本题考查对文件控制块（FCB）的理解。文件控制块是控制一个文件读

写和管理文件的基本数据结构，当进程需要使用某个文件时，就会调用。pen（）来打

开文件，该调用将文件的文件控制块从外存调入内存，存放在进程表中的用户活动

文件表中，并在系统活动文件表中记录该文件的打开次数，若是共享文件，还需要

将其链接的用户数加一。由于在进程表中存放有该文件的控制块，用户进程才能在

调用read。时找到该文件的位置并对文件的内容进行存取。而文件系统的信息，例

如文件系统的控制信息，文件系统的文件分配表等是在挂载一个文件系统时就读入

内存的，挂载文件系统可以是一个磁盘分区，也可以是一个文件目录。

32、在下列事件中，哪个不是设备分配中应该考虑的问题（）。

A、及时性

B、设备的固有属性

C、设备的无关性

D、安全性

标准答案：A

知识点解析：本题考查没备分配的概念。设备分配的原则是：根据设备的固有属性

（独占、共享还是虚拟）、用户的需求和系统的配置、使用情况，考虑既要充分发挥

设备的使用效率，又应该避免由于不合理的分配方式造成进程死锁（即设备必须处

于安全状态）；同时，要将用户程序所申请使用的设备与具体的物理设备映射起来

（即让用户使用逻辑设备，分配程序将逻辑设备映射到物理设备后，再根据要求的

物理设备号进行分配），保证设备分配和使用。因此及时性在设备分配中并没有考

虑。

33、OSI模型中完成路径选择功能的层次是（）。

A、物理层

B、数据链路层

C、网络层

D、传输层

标准答案：C

知识点解析：本题考查OSI模型中各个层次功能，完成路径选择，也就是路由功

能的是网络层，答案是C。［归纳总结］OSI参考模型各个层次的主要功能：物理

层：在物理媒体上传输原始的数据比特流。数据链路层：检测和纠正物理链路上

的传输错误，流量控制。广播网在这一层上还有共享信道的分配问题，专门有一个

媒体访问控制子层处理这个问题。网络层：将分组穿过通信子网从信源传送到信

宿。主要功能：路由选择，拥塞控制，网络互连。传输层：为上层用户提供不依

赖于具体网络的端一端数据传输服务。传输层是第一个端一端的层次。会话层：

为端一端进程间的会话提供各种服务，如对话控制、令牌管理、同步等。表示

层：为上层用户提供数据或信息语法的表示变换。应用层：包含用户通常所需的

各种协议，如文件传输、电子邮件等。

34、现采用调相与调幅相结合的调制方式，载波有四种相位变化和两种振幅变化，

调制速率是600波特，那么数据速率是（）。

A、1200bps

B、1800bps

C、2400bps

D、3600bps

标准答案：D

知识点解析：本题考查奈奎斯特定理的应用，这里载波有四种相位变化和两种振幅

变化，也就是离散值为8,有公式可得到2x600x］og28=3600bps,因此答案是D。

35、在CSMA/CD协议中，下列指标与冲突时间没有关系的是（）。

A、检测一次冲突所需的最长时间

B、最小帧长度

C、最大帧长度

D、最大帧碎片长度

标准答案：C

知识点解析：本题考查CSMA/CD协议中冲突时间，CSMA/CD属于竞争型协

议，某站点发送的MAC帧可能会冲突。问题是一旦发生冲突，该站点必须知道是

自己发送的帧造成的冲突，以便重发该帧；即在本帧未发送完毕之前检测到冲突信

号。因此每帧的服务时间必须不小于信号的往返传播延迟Ts>2t,如果设MAC帧

为L,信道的速率为C（bps）,总线长度为s,信号传播速度为V,中继器产生的延

迟为tr,则L/O2（s/v+tr）。冲突时间就是能够进行冲突检测的最长时间，其决

定了最小帧的长度和最大帧碎片的长度，对最大帧的长度没有影响，因此答案是

Co

36、CSMA/CD以太网U」，发生冲突后，重发前的退避时间最大是（）。

A、65536个时间片

B、65535个时间片

C、C24个时间片

D、1U23个时间片

标准答案：D

知识点解析：考查CSMA/CD的退避算法，这里的时间片就是基本退避时间：确

定基本退避时间，一般是取力争用期2r。定义重传次数k,k<10,即1<=乂亩［重传

次数，10］从整数集合［0,1,……，（2k（l）］中随机地取出一个数，记为r0重传所

需的时延就是r倍的基本退避时间。当重传达16次仍不能成功时即丢弃该帧，并

向高层报告。本题中重芍次数的最大值为10,退避时间最大就是21°—1=1023个

时间片，因此答案是D。

37、IEEE802.11采用了（2SMA/CA协议，下面关于这个协议的描述中错误的是

（）。

A、各个发送站在两次帧间隔（IFS）之间进行竞争发送

B、每一个发送站维持一个后退计数器并监听网络上的通信

C、各个发送站按业务的优先级获得不同的发送机会

D、CSMA/CA协议适用于突发性业务

标准答案：C

知识点解析：本题考查CSMA/CA协议的工作原理，IEEE802.11标准定义了两

种操作模式，第一种模式是DCF（分布式协调功能），该模式没有中心控制设备，所

有站点都在竞信道：另一种模式是PCF（点协调功能），该模式有基站，作为中心控

制设备通过轮询机制控制决定各个站点的传输顺序。根据IEEE802.11标准，

DCF是必须的而PCF是可选的。CSMA/CA协议应用于DCF下，目的在于解决

在允许竞争的情况下信道如何分配的问题。它支持的操作方式有两种：第一种操作

方式采用延时算法进行访问控制。当一个要发送数据的站点检测到信道空闲时，站

点需继续监听与IFS（interframespace,帧间间隔）相等的一段时间，若此时信道依然

空闲，站点就可以发送喷；如果检测到信道正忙，则发送站点推迟到信道空闲时再

发送数据。若冲突发生，则发生冲突的站点按照截断二进制指数退避算法延迟一段

时间后，再试着重新发送数据。另一种操作方式类似于发收双方的握手过程。它是

基于MACAW（Mi］ltipleAccesswithCollisionAvoidr：nceforwireless.带冲突避免的

无线多路访问），采用虚拟信道监听的方法。CSMA/CA协议利用1FS机制让PCF

和DCF共存在同一个通信单元内。因此答案是C。

38、局域网交换机首先完整地接收数据帧，并进行差错检测。如果正确，则根据帧

目的，则根据目的地址确定输出端口号再转发出去。这种交换方式是（）。

A、直接交换

B、改进直接交换

C、存储转发交换

D、查询交换

标准答案：c

知识点解析：本题考查交换机的三种交换方式，直接交换在输入端口检测到数据帧

时，检查帧头地址，把数据帧直通到相应的端口，实现交换功能。存储转发交换把

输入端口的数据帧先存储起来，然后进行CRC（循环冗余码校验）检查，在对错误包

处理后才取出数据帧的目的地址，通过查找表转换成输出端口送出帧。碎片隔离交

换检查数据包的长度是否够64个字节，如果小于64字节，说明是假包，则丢弃该

包;如果大于64字节，则发送该包。因此答案是C。

39、在TCP协议中，建立连接时被置为1的标志位和所处的字段是（）。

A、保留，ACK

B、保留，SYN

C、偏移，ACK

D、控制，SYN

标准答案：D

知识点解析：本题考查TCP连接的过程，首先服务器方（接收方）始终监听特定的端

口，被动的等待客户方发来的连接请求。客户方发出连接请求数据段，即SYN=

1,ACK=O的数据段，其中指明想要连接的IP地址和端口号，设置TCP数据段最

大值等。该数据段到达目的端后，服务器方的TCP实体检查是否又有进程在监听

目的端口字段指定的端口，如果没有，则返回一个RST=I的数据段作为应答，拒

绝该连接请求。如果某进程正在对该端口进行监听，于是将到达的TCP数据段交

给该进程。它可以接受或拒绝建立连接。如果接受，则返回一个确认数据段（SYN

=1和ACK=1）。客户方发送（SYN=I,ACK=1）TCP数据段。此时，连接建立完

毕。因此在建立连接的时候，必须把控制字段中的SYN位设置为1,答案为D。

40、下列协议中，用于解决电子邮件中传输多语言文字和附件问题的协议是（）。

A、MIME

B、SMTP

C、SNMP

D、POP3

标准答案：A

知识点解析：本题考查邮件协议中MIME的作用，MIME设计的最初目的就是为

了在发送电子邮件时附加多媒体数据，让邮件客户程序能根据其类型进行处理，因

此定义了5个新的邮件首部字段，它们可包含在「RFC822］首部中。这些字段提供

了有关邮件主体的信息。定义了许多邮件内容的格式，对多媒体电子邮件的表示方

法进行了标准化。定义了传送编码，可对任何内容格式进行转换，而不会被邮件系

统改变。因此答案为A。

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

41、已知加权有向图G如下，回答下列问题:⑴画出该有向

图G的邻接矩阵；（2）试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短

路径，并给出求解过程。

'gIS21288OC

000000co688

8888848

8888883

80088g89

888s90OO|0

标准答案：（1）有向图G的邻接矩阵84888ao8⑵

、除X

bCdcfs

12

2(<«c)

(a.b>-

IS12to.

k-JU»C«f|

IS1016

…

Ca«b>

IS16

k-4

(a«b>(■.c.F.d)

ISH

■3{■•cd.e.d.i?

<*.b>(A«€»f»d.C)

15

I'9•eJ・e・d.4・b)

知识点解析：本题是典型的由Dijkstra算法求出单源点的最短路径问题。迪杰斯特

拉（Dijk-stra）算法提出的一个按路径长度递增的次序产生最短路径的算法。算法的

基本思想是：（1）设置两个顶点的集合5和T=丫一S,集合s中存放已找到最短路

径的顶点，集合T存放当前还未找到最短路径的顶点。（2）初始状态时，集合S中

只包含源点v（）,然后不断从集合T中选取到顶点vo路径长度最短的顶点”加入到集

合S中，集合S每加入一个新的顶点“，都要修改顶点vo到集合T中剩余顶点的最

短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度侑与

顶点”的最短路径长度值加上“到该顶点的路径长度值中的较小值。（3）此过程不断

重复，直到集合T的顶点全部加入到S中为止。

42、己知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效

的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整

数。不要求对这些元素徘序。(1)给出算法的基本设计思想；(2)根据设计思想，采

用C或C++或JAVA涪言表述算法，关键之处给出注释；(3)说明你所设计算法

的时间复杂度和空间复杂度。

标准答案：(1)算法的基本设计思想如分析所述。(2)用C语言算法描述如下：void

Adjust(intA[]){//调整数组A,使得A的左边为负整数。右边为正整数inti=

1,j=n,temp；while(iO&&i

知识点解析：本题主要考查线性表的顺序存储结构(这里为数组)的应用。算法的基

本设计思想是先设置好上、下界和轴值，然后分别从数组前端查找正整数和从数组

末端查找负整数，找到方进行交换，直到上、下界相遇。具体做法是：设置两个

指示器i和j,其中i=l,j=n；当A[i]为正整数,A[j]为负整数时，A[i]和A|j]交

换；否则，A[i]为负整数时，则i++；A[j]为正整数时，则j一一o这样，可使算

法的时间复杂度为O(n)。

43、设某计算机有变址寻址、间接寻址和相对寻址等寻址方式，设当前指令的地址

码部分为001AH,正在执行的指令所在地址为1F05H,变址寄存器中的内容为

23AOHo(1)当执行取数指令时，如为变址寻址方式，则取出的数为多少？(2)如为

间接寻址，取出的数为多少？(3)当执行转移指令时，转移地址为多少？已知存储器

*及内#

001AH23ACH

1F0SH28MH

IF1FH250CH

2JA0H

的部分地址及相应内容，见下表。23BAH17aH

标准答案：(1)变址寻址时，操作数S=((Rx)+A)=(23AOH+001AH)=(23BAH)

⑵间接寻址时，操作数S=((A))=((001AH))=(23AOH)=2600H。⑶转移指令使

用相对寻址，转移地址=(PC)+A=1FO5H+OO1AH=1F1FH。因为在本题中没有

指出指令的长度，故此题未考虑PC值的更新。

知识点解析：前两个小题涉及数据寻址，其最终目的是寻找操作数，第3小题涉及

指令寻址，具目的是寻找下一条将要执行的指令地址。I归纳总结」基本寻址方式的

比较见下表。表中列出的偏移寻址包括变址寻址、基址寻址和相对寻址3种方式。

寻城方式r.9V.A

同存wa

*tf■斗*EA-Rw者仿何存

KA=A

■K•，勉EA-«A)4*▼*大$氏必问主存

EA-<R>J*中旭大*s*—次主a

偏华Jki灵信相对寻址方式中的PC值更新问题是一

个需要注意的问题。有些计算机是以当前指令地址为基准的，有些计算机是以下条

指令地址为基准的。这是因为有的机器是在当前指令执行完时，才将PC的内容加

1(或加增量)，而有的机器是在取出当前指令后立即将PC的内容加1(或加增量)，

使之变成下条指令的地址。通常采用第二种方式比较多，如果题目中给出了指令的

长度，则必须考虑PC值的更新问题。

44、四位运算器框图如下图所示，ALU为算术：逻辑单元，A和B为三选一多路

开关，预先己通过多路开关A的sw门向寄存器Ri，R2送入数据如下：R|=

0101,I.......................................上行显示。其运算过程依次

BR

如下：(1)R।(A)+R2(B)TBR(显

示结果1010)；(2)R2(A)+RI(B)—BR(显示结果1111)；(3)Ri(A)+R］(B)-BR(显

示结果1010)；(4)R2(A)+R2(B)->BR(显示结果1111)；(5)R2(A)+BR(B)—BR(显

示结果1111):(6)R|(A)+BR(B)->BR(显示结果1010)：试分析运算器的故障位置

与故障性质(“1”故障还是“(F故障)，说明理由。

标准答案：运算器的故障位置在多路开关B,其输出始终为R］的值。(l)Ri(A)+

R2(B)=1010,输出结果错;(2)R2(A)+R|(B)=1111,结果正确,说明Rz(A),

R1(B)无错；(3)Ri(A)+R|(B)=1010,结果正确,说明R［(A),Ri(B)无错。由此可

断定ALU和BR无错；(4)R2(A)+R2(B)=llllo结果错。由于Rz(A)正确,且

R2(A)=1010,本应R2(B)=1010,但此时推知R2(B)=0101,显然,多路开关B

有问题；(5)R2(A)+BR(B)=1111,结果错。由于Rz(A)=1010,BR(B)=1111,

但现在推知BR(B)=0101,证明开关B输出有错;(6)Ri(A)+BR(B)=1010,结果

错。由于Ri(A)=0101,本应BR(B)=1111,但现在推知BR(B)=0I01,再次证明

开关B出错。综上所述，多路开关B输出有错。故障性质：多路开关B输出始终

为0101。这有两种可能：一是控制信号Bso，BS］始终为01,故始终：选中寄存器

R1；二是多路开关B电平输出始终处于在0101上。

知识点解析：根据已知的6步运算过程一步一步地分析，可知运算器的故障位置在

多路开关B。［归纳总结］A和B为三选一多路开关，当控制信号为01、10和11时

分别选择不同的输入信号。

45、在某一个单处理机的系统中，外接了一台打印机，一台输入设备。当前在系统

中有二个进程P0、P1已经就绪，进程P0首先获得处理机运行，调度算法为先来

先服务，进程PO、PI的运行要求是这样的：P0：计算100ms,打印信息200ms,

继续计算100ms,打印信息200ms,结束。P1：计算100ms,输入数据150ms,继

续计算200ms,结束。请用甘特图画出它们的运行轨迹，并说明：进程PO、P1

在运行时有无等待?若有，请指出时间区间。计算处理机的利用率。

标准答案：根据题意，画出甘特图如下：

从运行的时序廿特图上

可以看出：处理机在200ms到300ms之间是空闲的。因此，处理机的利用率可以

计算出为：(200+300):600=83.3%。进程P0运行过程中无等待现象，进程P1

有等待现象，等待区间为350—400ms之间。

知识点解析：本题考查进程调度的过程。解决这类题目的关键在于画出进程运行的

时序图，若用条形来表示这种时序图就称为甘特图，然后再对其进行分析。绘图和

分析过程中要注意题目适用的调度算法，先来先服务最简单，按先来后到的次序进

行调度，被调度的进程一般会占有处理机运行直到自己主动放弃；短进程优先算法

在选取调度的进程时需要知道进程的预计执行时间，根据进程表里填写的进程预计

执行时间，选取最短的进程调度其运行；高优先级优先的调度算法是根据进程表内

赋予的优先级来调度，当然，优先级的确定可以有各种方法，可以在创建时确定，

也可以根据程序的紧急程度确定，还可以根据收费多少确定，所以优先级的确定有

许多灵活性，现行大部分操作系统均会采用高优先级优先的调度算法；时间片轮转

的调度算法是由硬件时钟确定每一个进程占用处理机的时间的，进程按先来先服务

排队，调度器调度进程队列中最先的进程运行，若分配的时间未到进程就主动放弃

处理机，则会引起下一次调度，若分配的时间到，则不管进程是否运行完成，必须

立即强制地出让处理机。在以上描述的各种调度算法既可以单独使用，也可以组合

使用。不管采用什么算法，能否抢先是另一个调度的非常重要的因素，为适应不同

用户的需求，也为改善计算机的性能，现代许多操作系统均采用抢先式调度算法，

抢先式调度不能单独实施，一定是与上述各种调度算法相结合。处理机的调度相对

较复杂，而IO的调度就简单了，为保证安全，一般10设备是不能抢夺的，一旦

分配，则一定是使用到进程主动放弃。

46、某一个计算机系统采用虚拟页式存储管理方式，当前在处理机上执行的某一个

进程的页表如下所示，所有的数字均为十进制，每一项的起始编号是0,并且所有

的地址均按字节计址，每页的大小为1024字节。

存在停中用&

01109

11113

2000

1001・

<0Q0—

101S(1)计算下列逻辑地址转换为物理地址，并说

明为什么？0793,1197,2099,3320,4188,53为⑵假设程序要访问第2页,页

面置换算法为改进的Clock算法，请问该淘汰哪页”页表如何修改?上述地址的转换

结果是否改变?变成多少？

标准答案：(1)根据题意，计算逻辑地址的页号和页内偏移量，合成物理地址如下

贡值9物理为it

07>30”94

1I9T1173

2。”151一.♦寅中耸

33：031nn

4IM<n—竣置中"

表。S3125112S皿2(2)第2页不在内存，产生缺页中

断，根据改进的Clock算法，第3页为没被引用和没修改的页面