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

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

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

1、下列程序段的时间复杂度是()。inti,j；for(i=m+l；i<=m+n；

i++){A[O]=A[i]；for(j=i-l;A|j]>A[i]；j-){A|J+1>A[J]；)}

A^0(m2)

B、O(n2)

C^O(m*n)

D、O(m+n)

标准答案：C

知识点解析：时间复杂度由m,n共同决定，最坏情况F的时间复杂度为O(mn)。

2、若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个

结点，则下面最节省运算时间的存储方式是()“

A、单链表

B、带有头指针的单循环链表

C、双链表

D、带有尾指针的单循环链表

标准答案：D

知识点解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，

所以，单链表、带有头右针的单循环链表，双链表郁不合适，考虑在带有尾指针的

单循环链表中删除第一个结点，其时间性能是0(1),所以答案是D。

3、将一个A",…,50,1,...»50]的三对角矩阵,按行优先存入一维数组

B[l,...»148]中,A中元素A33,32(即该元素下标i=33,j=32),在B数组中的位置

k为()。

A、98

B、95

C、97

D、96

标准答案：D

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

B[0,...»3n—3]时，的与bk的对应关系为:k=2i+i—3；将A[l,

n][l,...»n]压缩至B[0,…，3n-2]时，aq与bk的对应关系为：k=2i+j—2。根据

题目，A中元素A33,32在B数组中的位置k为：k=2i+j-2=2x33+32—2=96。

4、已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L；中

序序列为：D,J,G,B,E,H,A,C,K,J,L,F。该二叉树的后序序列为

()。

A、J,H,E,B,G,D,K,L,I,F,C,A

B、J,G,E,B,K,L,D,H,I,F,C,A

C>J,C»D>H,E,B,K,L,I,F,C,A

D、J,C,D,H,E,B,K,L,I,F,A,C

标准答案：C

知识点解析：三叉树的形式如下图所示:后序序列为

J,G,D,H,E,B,K,L,I,F,C,A。

5、二又树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是()。

A、先序遍历二叉树

B、判断两个指定位置的结点是否在同….层上

C、层次遍历二叉树

D、根据结点的值查找其存储位置

标准答案:B

知识点解析：选项A、C、D运算的时间复杂度都是0(n),而选项JE｝的运算的时

间复杂度为0(1),因为对于指定位置p和q的两个结点，判断是否在同一层上，

只需判断两者[Iog2p]=[log2q]是否成立。

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

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

A、4

B、5

C、6

D、7

标准答案：B

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

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

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

7、以下关于图的说法正确的是()。I.在一个有向图的拓扑序列中，若顶点a在顶

点b之前，则图中必有一条弧U.若一个有向图的邻接矩阵中对角线以下元素均

为0,则该图的拓扑序列必定存在IH.在AOE网中一定只有一条关键路径

A、I、n

BIT、in

c、I、m

D、仅有n

标准答案：D

知识点解析：说法I是错误的。在一个有向图的拓扑序列中，若顶点a在顶点b之

前，只能说明顶点a到顶点b有一条路径。说法HI是错误的。AOE网中可能有不

止一条关键路径，它们的路径长度相同。说法n是正确的。任意n个顶点的有向

无环图都可以得到一个拓扑序列。设拓扑序列为vc，V),vn-i，证明此时的邻接矩

阵A为上三角矩阵，可用反证法证明。假设此时的邻接矩阵不是上三角矩阵，那

么，存在下标i和使得不等于O，即图中存在从必到力的一条有向

边。由拓扑序列的定义可知，在任意拓扑序列中，置的位置一定在Vj之前，而上

述拓扑序列vo，V|,Vn-1中，由于i>j，即Vj的位置在Vj之后，导致矛盾。因此说

法H是正确的。

8、已知有向图G=(V,A),其中V={a,b,c,d,e),A={,对该图

进行拓扑排序，下面序列中不是拓扑排序的是().，

A、a,d,c,h,e

B、d,a,b,c,e

C>a,h,d,c,e

D、a,b,c,d,e

标准答案：D

知识点解析：对AOV网进行拓扑排序的方法和步骤是：（1）从AOV网中选择一个

没有前驱的顶点（该顶点的入度为0）,并且输出它；（2）从网中删去该顶点，并且删

去从该顶点发出的全部有向边；（3）重复上述两步，直到剩余的网中不再存在没有

前驱的顶点为止。本题按照拓扑排序方法对该图进行拓扑排序便可得到结果。在

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

要进行的探查次数是（）,

A、9

B、10

C、11

D、66

标准答案：D

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

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

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

=1+2+…+k=k（k+l）/2,将k=10代入得到总的比较次数为66。

10.设关键字序列为：［3,7,6,9,7,1,4,5,20）,对其进行排序的最小交换

次数是（）。

A、4

B、5

C、6

D、7

标准答案：B

知识点解析：由于关键字序列数较小，采用直接插入排序或简单选择排序，直接插

入排序的交换次数更多，选择简单选择排序，最小交换次数为5。

11、设有5个初始归并段，每个归并段有20个记录，采用5路平衡归并排序，若

采用败者树最小的方法，总的比较次数是（）。

A、20

B、300

C、396

D、500

标准答案：B

知识点露析：采用败者何时，5一路归并意味着败者树的外结点有5个，败者树的

高度h为log23向上取整，结果为3。每次在参加比较的记录中选择一个关键字国

小的纪录，比较次数不超过h,总共100个记录，需要的比较次数不超过1

00x3=300次,故选B。

12、下列选项中，描述浮点数操作速度的指标是（），

A、MIPS

B、CPI

C、IPC

D、MFLOP

标准答案：D

知识点解析：衡量计算机系统速度的指标中，CPI表示每条指令平均所需的时钟周

期数；IPC表示每个时钟周期平均执行的指令条数；MIPS表示每秒百万条指令

数；MFLOP常用于衡量浮点运算速度，表示每秒百万条浮点运算数。

13、某浮点机的字长8位，尾数和阶码都采用补码形式，且运算过程中数符和阶符

都采用双符号位，基数为2。则浮点加减运算过程中，当出现下列（）情况时，需要

左舰。

A、尾数相加后，数符为“01”

B、尾数相加后，数符为“10”

C、尾数相加结果为“00.Ixxxxxx”

D、尾数相加结果为“I1.ixxxxxx-

标准答案：D

知识点解析：当尾数运算结果为非规格化形式时，需要左规；基数为2的补码的规

格化形式下最高数值位应与符号位相反，故当尾数相加结果为"11."XXXXX”时，

尾数需要左规。

14、计算机的加法器采用并行进位的原因是（）。

A、增强加法器功能

B、简化加法器设计

C、提高加法器的运算速度

D、保证加法器可靠性

标准答案：C

知识点解析：与串行进位相比，并行进位可以提高运算速度。

15、下列火于主存储器的描述中，正确的是（）1.CPU访存时间由存储器容量决定

n.ROM和RAM在存储器中是统一编址的HI.ROM中任意一一个单元可以随机

访问W.DRAM是破坏性读出，因此需要读后重写

A、I和n

B、II和HI

C、HI和W

D、n,in和w

标准答案：D

知识点解析：兼容性微操作是指那些可以同时产生，共同完成某一任务的微操作，

而互斥性微操作是指在机器中不允许同时出现的微操作。一条机器指令可以分解成

一个微操作序列，这些微操作是计算机中最基本的、不可再分解的操作。微操作有

兼容性和互斥性之分。左同一CPU周期中，可以并行执行的微操作称为兼容性微

操作，不可以并行执行的微操作称为互斥性微操作。所谓兼容和互斥都是相对的，

一个微操作可以和一些微操作兼容，和另一些微操作互斥。对于单独一个微操作，

谈论其兼容和互斥都是没有意义的。

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

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

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

A、0.856

B、0.862

C、0.958

D、0.96

标准答案：B

知识点解析：在一个程序执行期间，设N］为访问Mi的命中次数，N2为访问M2

的次数。M+M,两级存储层次的等效访问时间TA。根据主存的启动时间

有：假设Cache访问和主存访问是同时启动的，TA=HXTAI+（1—H）XTA2，假设

Cache不命中时才启动主存TA=HXTAI+（1一N）X（TAI+TA2）=TAI+（1一H）xTA2,存

储层次的访问效率“TAI/TA。命中率=4800/(4800+200)=0.96,平均访问时

间=0.96x10+(1—0.96)x50=11.6ns,效率：10/11.6=0.862。先求出命中

率，接着求出平均访问时间，最后求出Cache一主存系统的效率。

17、设指令中的地址码为A,变址寄存器为X,程序计数器为PC,则变址间接寻

址方式的操作数有效地址EA是()。

A、((PQ+A)

B、((X)+A)

C、(X)+(A)

D、(X)+A

标准答案：B

知识点解析：变址间接寻址方式就是先变址后间接寻址。在4个选项中，选项A：

((PC)+A)为相对寻址;选项B：((X)+A)变址间接寻址；选项C：(X)+(A)为间接变

址寻址；选项D：(X)+A为变址寻址。

18、以下叙述中，不符合RISC指令系统特点的是()。

A、指令长度固定，指令种类少

B、寻址方式种类丰富，指令功能尽量增强

C、设置大量通用寄存器，访问存储器指令简单

D、选取使用频率较高的一些简单指令

标准答案：B

知识点解析•：RISC即精简指令系统计算机，选项B显然不符合RISC的特点。

RISC的中心思想是要求指令系统简化，尽量使用寄存器〜寄存器操作指令，指令

格式力求一致，大部分RISC具有下列特点：(1)指令总数较少(一般不超过100

条)；(2)基本寻址方式种类少(一般限制在2〜3种)：(3)指令格式少(一般限制在

2〜3种)，而且长度一致；(4)除取数和存数指令(Load/Store)外，大部分指令在单

周期内完成；(5)只有取数和存数指令能够访问存储器，其余指令的操作只限于在

寄存器之间进行；(6)CPU中通用寄存器的数目应相当多(32个以上，有的可达上

千个)；(7)为提高指令执行速度，绝大多数采用硬连线控制实现，不用或少用微程

序控制实现；(8)采用优化的编译技术，力求以简单的方式支持高级语言。

19、通常所说的32位微处理器是指()。

A、地址总线的宽度为32位

B、处理的数据长度只能为32位

C、CPU字长为32位

D、通用寄存器数目为32个

标准答案：c

知识点解扁：通常所说的32位微处理器是指CPU字长为32位。通常将运算器和

控制器合称为中央处理器(CPU)。在由超大规模集成电路构成的微型计算机中，往

往将CPU制成一块芯片，称为微处理器。CPU按照其处理信息的字长可以分为：

8位CPU,16位CPU,32位CPU以及64位CPU等。选项A,B,D均与微处理

器的位数无关。

20、在单发射、按序流动的普通流水线中，可能出现下列哪种数据相关问题（）。

A、写后读相关RAW

B、读后写相关WAR

C、写后写相关WAW

D、以上都有可能

标准答案：A

知识点解析：指令取操作数的动作一定在写回结果之前，故在按序流动的单发射

（普通标量）普通流水线中，先进入流水线的指令取操作数和写回结果的动作一定位

于后续指令写同结果的动作之前，故不可能出现WAR和WAW；唯一可能的数据

相关问题是后续指令在前一指令写回结果之前读相关的操作数，即RAw,写后读

相关。而在非按序流动的流水线中，允许后进入流水线的指令超过先进入流水线的

指令而先流出流水线，故三种数据相关问题都可能出现。

21、“总线忙”信号由（）建立。

A、获得总线控制权的设备

B、发出“总线请求”的设备

C、总线控制器

D、CPU

标准答案：A

知识点解析：在总线控制机制中，准备使用总线的设备向总线控制器发出“总线请

求”由总线控制器进行裁决。如果经裁决允许该设备使用总线，就由总线控制器向

该设备发出一个“总线允许''信号。该设备接收到此信号后，发出一个“总线忙''信号

用来通知其他设备总线已被占用。当该设备使用完总线时，将“总线忙”信号撤销，

释放总线。因此“总线忙”信号是由获得总线控制权的设备建立的。

22、CPU的工作周期为20ns,主存存取周期为10ns,此时DMA接口适合采用（）

方式与CPU共享主存。

A、停I卜CPU访问主存

B、周期挪用

C、DMA与CPU交替访存

D^以上无正确选项

标准答案：C

知识点解析：由于CPU工作周期为主存周期的2倍，故可将其分为两个分周期，

其中一个供DMA接口访存，另一个供CPU访存，即DMA与CPU交替访存，这

样可以在不影响CPU效率的前提下充分利用主存带宽。

23、提高单机资源利用率的关键技术是（）。

A、Spooling技术

B、虚拟技术

C、交换技术

D、多道程序设计技术

标准答案：D

知识点解析：本题考查操作系统的特性。并发性是操作系统的一个最主要的特性，

其他特性都是基于该特性的。多道程序设计技术是实现并发性的基础，由于采用了

多道技术，系统实现了并发，从而提高了资源利用率。而Spooling技术是为解决

独占设备的问题，虚拟技术主要应用在存储管理中来扩大存储空间，交换技术也是

用于存储管理。

24、临界区是指并发进程访问共享变量段的（）。

A、管理信息

B、信息存储

C、数据

D、代码程序

标准答案：D

知识点解析：本题考查对临界区的理解。所谓临界区，并不是指临界资源，例如共

享的数据、代码或硬件设备等，而是指访问这些临界资源的那段代码程序，例如

PV操作、加减锁等。操作系统中对临界区的访问关心的就是临界区的操作过程，

对临界资源作何具体操蚱是应用程序的事，操作系统并不关心。

25、一个正在访问临界资源的进程由于申请等待10操作而被中断时，它是（）。

A,可以允许其他进程进入与该进程相关的临界区

B、不允许其他进程进入任何临界区

C、可以允许其他进程抢占处理机，但不得进入该进程的临界区

D、不允许任何进程抢占处理机

标准答案：C

知识点解析：进程进入临界区必须满足互斥条件，当进程进入临界区但是尚未离开

时就被迫进入阻塞是可以的，系统中经常有这样的情形。在此状态下，只要其他进

程在运行过程中不寻求进入该进程的临界区，就应该允许其运行。该进程所锁定的

临界区是不允许其他进程访问的，其他进程若要访问，必定会在临界区的“锁”上阻

塞,期待该进程下次运行时可以离开并将临界区交给它C所以正确选项为Cc

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

A、系统资源总数

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

C、用户最大需求数

D、用户已占有的资源数

标准答案：B

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

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

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

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

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

27、在请求页式虚拟存储系统中，假设系统为某个进程分配了4个物理页框，页面

的引用串号为0，1,2,4,5,2,3,4,3,0,1,4,5,3,采用固定分配局部

置换，当采用LRU算法时会产生的缺页中断次数是（）。

A、8

B、9

C、10

D、11

标准答案：C

知识点解析：本题考查LRU算法。对于页面置换类的题目，一般只要理解了置换

算法的执行过程，那么计算相对是比较简单的，一般采用表格的方法，以堆栈的顺

序来计算比较方便。如下表所示：

012452343014§

10124523430145PF

110124523430I45

m0i2452243014

IV01145524301

ifaUYYYYYYYYYY

经过计算，缺页次数为10。

28、页式虚拟存储管理的主要特点是（）。

A、不要求将作业装入主存的连续区域

B、不要求将作业同时全部装入主存的连续区域

C、不要求进行缺页中断处理

D、不要求进行页面置换

标准答案：B

知识点解析：本题考查页式存储的概念。

29、下面的叙述中，属于分段式虚拟存储管理的优点的是（）。

A、没有内零头

B、便于处理在进程执行过程中堆栈尺寸的增长问题

C、便于共享内存中数据

D、只需将进程的一部分调入内存，进程即可运行

标准答案：c

知识点3析：如果系统正在向非易失性存储器件硬盘写数据，此时，系统崩溃，写

的数据可能会丢失，或者存储信息不完整。

30、在UNIX系统中，将一个文件卷复制到另一个磁盘上。只复制文件数据，包括

目录之后（）。

A、文件数据能够被访问

B、文件目录能够被访问

C、文件数据和目录都能被访问

D、文件数据和目录都不能访问

标准答案：D

知识点解析：UNIx系统中每个文件卷需要经过安装后才能使用。所以只复制文件

数据，包括目录后，是都不能访问的。即使物理介质本身在工作，但若其上的文件

卷没有安装好，系统也无法存取其中的信息。uNIx需要安装文件卷后才可以被访

问。

31、在某文件系统中，一个文件控制块的大小为128B,一个盘块大小为1KB,

采用一级目录。假定文'牛目录中有1600个目录项，则查找一个文件平均需要（）次

访问磁盘。

A、50

B、100

C、200

D、300

标准答案：B

知识点解析：1600个目录项占用的盘块数=1600x128B/1KB=200个。一级目录

的平均访盘数为1/2盘块数，所以平均访问磁盘的数目为100次。

32,中断向量的地址是（）。

A、子程序入口地址

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

C、中断服务例行程序入口地址的地址

D、例行程序入口地址

标准答案：C

知识点解析：中断向量包括两个字：一个是中断处理程序的入口地址；另一个是中

断处理程序的程序状态字。那么显然，中断向量地址就是中断处理程序的入口地址

的地址了。

33、在OSI参考模型中，服务定义为（）。

A、各层向下层提供的一组原语操作

B、各层间对等实体间通信的功能实现

C、各层向上层提供的一组功能

D、和协议的含义是一样的

标准答案：c

知识点解析•：本题考查OSI参考模型中，服务的定义。

34、有一条无噪声的8KHz信道，每个信号包含8级，每秒采样24K次，那么可

以获得的最人传输速率是（）。

A、24Kbps

B、32Kbps

C、48Kbps

D、72Kbps

标准答案：c

知识点露析•：无噪声的信号应该满足奈奎斯特定理，即最大数据传输率

二2Hxlog2V（位/秒）。将题目中的数据代入，得到答案是48kHz。注意：题目中给

出的每秒采样24kHz是无意义的，因为超过了2H,所以D是错误答案。

35、连接在透明网桥上的一台计算机把一个数据帧发往网络上不存在的一个设备，

网桥将（）。

A、丢弃该帧

B、扩散该帧

C、停止接收其他帧

D、暂存该帧等收到地址信息再转发

标准答案：B

知识点解析：网桥不知道网络上是否存在该设备，它只知道在其转发表中没有这个

设备的MAC地址。因此，当网桥收到这个目的地址未知的帧时，它将扩散该帧，

即把该帧发送到所连接的除输入网段以外的所有其他网段。

36、以太网交换机中的端H/MAC地址映射表是（）o

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

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

C、由网络管理员建立的

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

标准答案：B

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

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

映射表只能在数据转发中进行动态学习建立，并且没有表项都有定时器，因此答案

为Bo

37、在IP数据报的传递过程中，IP数据报报头中保持不变的域是（）。

A、标识和片偏移

B、标志和头部校验和

C、标识和目的地址

D、标志和生存周期

标准答案：C

知识点解析：本题考查IPv4报文格式和传输特性。在数据报传递过程中，如果遇

到长度超过网络MTU的时候，必须分片。因此，片偏移和标志是变化的，生存时

间是随着数据报传递发生变化的。对于校验和，每经过一个结点都要进行重新计

算，因此只有目的地址和标识是不变的。注意：标识是一个计算器，即使发生分片

的情况下，其会把这个值复制到分片后的标识字段，因此答案为C。

38、组播路由过程中（）技术可以避免路由环路。

A、采用了水平分割技术

B、构造组播转发树

C、采用IGMP协议

D、通过生存期（TTL）字段

标准答案：B

知识点解析：由于树具有不存在环路的特性，因此构造一个组播转发树，通过该转

发树既可以将主播分组传送到组内每台主机，又能避免环路。

39、UDP与IP都是不可靠的通信协议，在IP协议的基础上封装UDP报文的原因

是（）。

A、UD1P能够进行流量控制

B、UDP能够进行拥塞控制

C、UDP能够实现路由转发

D、UDP能够实现端口功能

标准答案：D

知识点解析：UDP与IP的最大区别是UDP能够实现端到端的通信，即只是在IP

的基础上增加了端口功能。

40、FTP协议中，客户进程与服务器的连接过程需要打开（）个端U

A、28

B,26

C、23

D、21

标准答案：D

知识点解析：FTP打开熟知端口（端口号为21）,使客户进程能够连接上。

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

41、如下图所示的AOE网，求：（1）每项活动山的最早开始时间c（ai）和最迟开始

时间l（ai）o（2）完成此工程最少需要多少天（设边上权值为天数）？⑶哪些是关键活

动？（4）是否存在某项活动，当其提高速度后能使整个工程缩短工期？

标准答案：⑴所有事件的最早发生时间如下：Ve⑴=0Ve⑵=5Ve⑶=6

Ve(4)=max{ve(2)+3,ve(3)+6)=12Ve(5)=max{ve(3)+3,ve(4)+3)=15

Vc(6)=vc(4)+4=I6Ve(7)=ve(5)+l=16Vc(8)=Vc(5)+4=19Ve(9)=max{vc(7)+5,

Ve(8)+2)=21Ve(10)=max{ve(6)+4,Ve(9)+2}=23所有事件的最晚发生时间如下:

Vl(l0)=23V1(9)=V1(10)-2=21Vl(8)=vl(9)-2=19V1(7)=V1(9)-5=16V1(6)=V1(10)-

4=19VI(5)=min{V1(7)-1,VI(8)-4)=15Vl(4)=min{Vl(6)-4,Vl(5)-3)=12

Vl(3)=rain{Vl(4)-6,Vl(5)-3)=6Vl(2)=Vl(4)-3=9Vl(l)=min{Vl(2)-5,VI⑶-6}=0

因此,所有活动Ai的e(),1(),d()如下：Al：e(l)=Ve(l)：0,l(l)=Vl(2)-5=4,

d(l)=4A2：e(2)=Ve(l)：0,1(2)=V1(3)-6=O,d(2)=DA3：e(3)=Ve(2)=5,

l(3)=Vl(4)-3=8,d(3)=3A4：e(4)=Ve(3)=6,l(4)=Vl(4)-6=6,d(4)=0A5：

e(5)=Ve(3)=6,1(5)=V1(5)-3=12,d(5)=6A6：e(6)=Ve(4)=12,1(6)=V1(5)-3=12,

d(6)=0A7：e(7)=Ve(4)=12,1(7)=V1(6)-4=15,d(7)=3A8：e(8)=Ve(5)=15,

1(8)=V1(7)-1=15,d(8)=0A9：e(9)=Ve(5)=15,1(9)=VI(8)-4=15,d(9)=0A10：

e(10)=Ve(6)=16,1(1O)=V1(9)-5=16,d(10)=0All：e(ll)=Ve(7)=19,1(11)=V1(9)-

2=19,d(10)=0A10：e(l2)=Vc(8)=16,1(12)=V1(1O)-4=19,d(10)=3A10：

e(13)=Ve(9)m=21,1(13)=V1(10)-2=21,d(10)=0(2)经过上面的计算,可以得出：

V12345678910

Ve05612151616192123

VI09612151916192123

d0400030000

完成此工程最少需要23天。(3)从以上计算可知，关键活动为a2，闻，H6，ag,

H9，aio»an，ai3o这些活动构成两条关键路径即：a2>a4>a6，ag,aio，a13和

a2，34，a6»ag,a”，a：3。(4)存在a2，a4>a6，an，活动，当其提高速度后能使

整个工程缩短工期。

知识点解析：暂无解析

42、设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽

可能有效的算法，将R中保有的序列循环左移P(0<PVn)个位汽，即将R中的数

据由(Xi，X2，…,Xn)变换为(Xp,Xp+1，…，XN，XI，Xp.1),要求：(1)给出算

法的基本设计思想。(2)根据设计思想，采用C或C++或JAVA语言表述算法，关

键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。

标准答案：(1)基本设计思想：将数组{ai，a2,a3,ap,ap+1,aQ先进行

全部逆转，然后分别对{ap,…，an-i，an}{ai，a2，a3，…，ap}进行再次逆转。

(2)算法描述:voidsiftjeft(inta[],intn,intp){Reverse(a>0,n-l)；//移动了

3n/2次数据；Reverse(a,0,n-p-1)；//移动了3(n-p)/2次数据；Reverse(a,

n-p,n-l)；}//移动了3P/2次数据；voidReverse(intA[],intleft,

int.right){intn=right-left+l；//设置一个辅助空间;if(n<=l)return0；//数组

为空;for(inti=0；i

知识点解析：暂无解析

43、已知主机A的主频为40MHz,现在用这台主机运行一组标准测试程序A.A

中包含的各种指令和响应所需要的时间如下表所示：

指令类型CPI指令混合比(%)

算术和逻辑160

访问高速缓存218

转移412

访问高速缓存失效810

请回答以下问题：(1)求主机有效的CPI。(2)求主机的MIPS。(3)假设程序A在计

算机上运行的时间为100s,其中90s用于cPu,其余时间为I/O时间。现在CPU

的速度提高了50%,I/O速度不变，那么A的运行耗费了多长时间？

标准答案：(1)计算机的CPI包括四种指令，那么CPI就是这四种指令的数学期

望：CPI=0.6X1+0.18x2+0.12x4+0.1x8=2.24。(2)MIPS=40/CPI=I7.9o

⑶程序A在计算机上运行的时间为100s,90s用于CPU,那么用于I/O的时间

为10ms不会发生改变。CPU的速度提高了50%。程序A的CP[J时间变为90/

1.5=60s,A的运行耗费了60s+l0s=70s。

知识点解析：暂无解析

44、下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑，分取指周

期，取第一操作数周期,取第二操作数周期，执行周期四个机器周期，每个机器周

期有To,Ti，T2三个节拍。试写出如下双操作数运算指令的微操作命令及节扫安

排。ADDRo,(Ri)完成功能(Ro)+((Ri))-Ro

标准答案：各机器周期的微操作命令及节拍安排如下：(1)取指周期To：PC-总线

—MAR—主存，微操作命令形成部件发读信号到主存Ti：M(MAR)TMDR,微操

作命令形成部件发+1信号到PCT2：MDR—总线TIR,OP(IR)一微操作命令形成

部件(2)取第一操作数底期To：Ro—总线—FIRST⑶取第二操作数周期To：R1—

总线-MAR-主存，微操作命令形成部件发读信号到主存：Ti：

M(MAR)—>MDR；T2：MDR一总线一SECOND。(4)执行周期T()：FIRST—总线

一Y；Ti：微操作命令形成部件发.Add信号至ijALU,(Y)+(SECOND)-ALU—Z

T2：Z—总线—>RO。

知识点解析：暂无解析

45、一个系统采用段页式存储方式，有16位虚地址空间，每个进程包含两个段，

并且一页大小为2%字节。段表和页表如下表所示（所有的值为二进制，并且段长

以页为单位）。下列哪些二进制虚地址会产生缺段中断或缺页中断?哪些二进制虚地

址能转换为物理地址?如果可以转换，请写出物理地址。（1）0001010001010111（提

示：产生缺段中断，或缺页中断?）（2）1110010011111111（提示：转换后的物理地址

是什么?）（3）1111010011000111（提示：产生缺段中断,或缺页中断?）

（4）0011001011000111（提示：转换后的物理地址是什么?）（5）请问该系统最大物理内

段友

出号段长页衣地址

0111指向页表0的指针

1110拉向贝米1的指针

页表0

页号存储块状态

0001010111

()010010100

0100010111

0111001101

10000110()0

1011101101

11011101()0

III0111010

页表1

页号存储块状态

(XX)0101000

0011101011

0101101000

011011()010

1001I00II1

101001()010

11000()1011

1111000101

存是多少?

标准答案：由题意可得逻辑地址各字段为：

1位3位12位

段号段内地址页内地址

(1)

0001010001010111

段号为0,页号为001,查看页表0中的001,号页的状态，其状态为0,说明此页

尚未调入内存。故发生缺页中断。(2)

1no0100IIII1III

段号为1,页号为110,段表长度为6,查看页表1中的110号页的状态，其状态

为1,说明此页面已调入内存。则相应的物理地址为:000101010011111111(3)

11111010011000!II

段号为1，页号为111,段表长度为6,发生越界。所以发生缺页中断。(4)

001