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

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

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

1、下面说法错误的是

A、算法原地工作的含义是指不需要任何额外的辅助空间

B、在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度0（2,的算法

C、所谓时间复杂度是指在最坏情况下，估算算法执行时间的一个上界

D、同一个算法，实现语言的级别越高，执行效率就越低

标准答案：A

知识点解析：算法原地工作是指算法所需的辅助空间是常量。

2、设A是一个已有10个元素的栈，栈中依次是Ai，Al,…,Aio，栈顶是Aio；

B是一个已有10个元素的循环队列，队列中元素依次为B],B2,…，Bn队头

元素为B],A,B均采用顺序结构，现要将栈中元索全部移入队列中，需（）次基本

操作才能使得队列中元素与栈中元素交替排列，即B中排列后的元素为Bi，AH

B2»A?,…,Bio»Aioo（不必考虑存储空间）

A、100

B、1000

C、50

D、20

标准答案：A

知识点解析：操作如下：（1）先将栈中所有元素出栈（10次），入队列（10次），栈为

空，队列中的元素为Bi，B2，…,Bio,Aio,A9，…,Ai；⑵将Bi，B2,

B3,…，Bio出队列（10次）,入队列（10次），则队列变为Aio…,A2,Ai，Bi，

B2，…,Bio;（3）将AQA9,…,Ai出队列（10次），入栈（10次），栈中自栈底至

栈顶依次为Aio，…，A3,A?、Ai，队列中剩下B”B2»...»B10；（4）重复执行

10次B|出队列（1次），入队列（1次），Ai出栈（1次），入队（1次），则最终得到B|,

A],B2，A?,...rBio»Aio。

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

A、5,4,3,2,1

B、4,5,3,2,1

C、4,3,5,I,2

D、1,2,3,4,5

标准答案：C

知识点解析：此类问题解答的基本原理是：一串数据依次通过一个栈，并不能保证

出栈数据的次序总是倒置，可以产生多种出栈序列。一串数据通过一个栈后的次序

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

出栈''才能使数据倒置。事实上，存在一种操作序列一“进栈、出栈、进栈、出

栈……”可以使数据通过栈后仍然保持次序不变。将一组数据入栈后，判断题目备

选项中的不可能的出栈顺序。上述这类题目有一个解题技巧：在输出序列中任意元

索后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。

4、在一棵完全二叉树中，含有15个叶子结点，度为1的结点数为1时，该树的高

度是（）。

A、3

B、4

C、5

D、6

标准答案：C

知识点解析：非空的二叉树中，由度为0和度为2的结点之间的关系N（尸N2+1，

可知N2=No—1o则总结点数N=N2+N।+No=2No=2x15=30,树的高度为log230向

上取整，结果为5。

5、以下关于二叉排序树的说法正确的是（）。I.在二叉排序树中，每个结点的关键

字都比左孩子关键字大，比右孩子关键字小D.每个结点的关键字都比左孩子关

键字大，比右孩子关键字小，这样的二叉树都是二叉排序树m.在二叉排序树

中，新插入的关键字总是处于最底层IV.在二叉排序树中，新结点总是作为吐子

结点来插入的V.二叉排序树的查找效率和二叉排序树的高度有关

A、I、n、w、v

B、口、皿、W

c、I、m、v

D、I、IV、V

标准答案：D

知识点解析：对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键

字：右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子

的关键字进行比较。在二叉排序树中，新插入的关键字总是作为叶子结点来插入

的，但是叶子结点不一定总是处于最底层。对于每一棵特定的二叉排序树，均可按

照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字，构迨所

得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。最

好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和logn

成正比V

6、对于下列关键序列，不能构成某二叉树排序中的一条查找路径的序列是（）。

A、95,22,91,24,94,71

B、92,20,91,34,88,35

C、21,89,77,29,36,38

D、12,25,71,68,33,34

标准答案：A

知识点解析：对于选项A,当查到91后再向24查找，说明这一条路径之后查找的

数都要比91小，后面94就错了。

7、下列关于图的叙述中正确的是()。I.回路是简单路径H.存储稀疏图，用邻

接矩阵比邻接表更省空间皿.若有向图中存在拓扑序列，则该图不存在回路

A、仅I

B、仅I,n

c、仅m

D、仅i,m

标准答案：c

知识点解析：I.几个概念的描述如下：回路：第一个顶点和最后一个顶点相同的

路径称为回路(环)。简单路径：在一条路径中，若没有重复相同的顶点，该路径称

为简单路径。简单回路：在一个回路中，若除第一个与最后一个顶点外，其余顶

点不重复出现的回路称为简单回路(简单环)。回路对应于路径，简单回路对应于简

单路径。n.存储稀疏图时，使用邻接表比邻接矩阵更省空间。n.若有向图中

存在拓扑序列，则说明该图不存在回路。通过以上分析可知只有in的描述是正确

的。

8、下面关于Prim算法和Kmskal算法的时间复杂度正确的是()。

A、Prim算法的时间复杂度与网中的边数有关，适合于稀疏图

B、Prim算法的时间复杂度与网中的边数无关，适合于稠密图

C、Kruskal算法的时间复杂度与网中的边数有关，适合于稠密图

D、Kruskal算法的时间复杂度与网中的边数无关，适合于稀疏图

标准答案：B

知识点解析：Prim算法的时间复杂度为0(/),与网中的边数无关，适合于稠密

图；而Kruskal的算法复杂度为O(eloge),与网中的边数有关，适合于稀疏图。

9、对包含n个关键码的散列表进行检索，平均检索长度为()。

A、O(logn)

B、O(n)

C、O(nlogn)

D、不直接依赖于n

标准答案：D

知识点解析：对散列表进行检索，平均检索长度仅与装填因子a有关，而与关键字

个数n无关。

10、若一组纪录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,

以第一个纪录为基准得到的一次划分结果为()。

A、38,40,46,56,79,84

B、40,38,46,79,56,84

C、40,38,46,56,79,84

D、40,38,46,84,56,79

标准答案：C

知识点解析：根据快速徘序法的算法思想可得本题答案是Co

11、以下排序方法中，不需要进行关键字的比较的是（）。

A、快速排序

B、归并排序

C、基数排序

D、堆排序

标准答案：C

知识点。析：基数排序是采用分配和收集实现的，不需要进行关键字的比较，而其

他几种排序方法都是通过关键字的比较实现的。

12、某计算机的时钟频率为400MHz,测试该计算机的程序使用4种类型的指

令。每种指令的数量及所需指令时钟数（CPI）如下表所示，则该计算机的运算速度

是（）。

指令类型指令数目（条）何条指令需时钟数

11600001

2300002

3240004

4160008

A、106.7

B、169.5

C、207.3

D、216.2

标准答案：C

知识点解析：先计算出平均的CPI,然后再计算出运算速度。平均CPI=（160

000x1+30000x2+24000x4+16000x8）/（160000+30000+24000+16000）=404.000

/230000=207.3MIPS

13、对于长度固定的浮点数，若尾数的位数增加、阶码的位数减少，则（）。

A、可表示浮点数的范围与表示精度不变

B、可表示浮点数的范围与表示精度增加

C、可表示浮点数的范围增加，但表示精度降低

D、可表示浮点数的范围变小，但表示精度提高

标准答案：D

知识点解析：此题考查浮点数格式中尾数位数与所表示数据精度的关系以及阶码位

数所表示数据范围的关系。

14、已知X=-0.875x2］，Y=0.625x22,设浮点数格式为阶符1位，阶码2位，数

符1位，尾数3位，通过补码求出Z=X-Y的二进制浮点数规格化结果是（）。

A、1011011

B、0111011

C、1001011

D、以上者都不是

标准答案：B

知识点解析：将X=-0.875x2,和Y=O.625x22,写成7位浮点数形式，有

X=0011001和Y=010010I,对阶之后，X=0101l00,对阶后尾数做减法，结果需要

进行右规，最终结果ZR111011。浮点数加、减运算一般包括对阶、尾数运算、规

格化、舍入和判溢出等步骤。对阶就是使两数的阶吗相等，对阶原则是小阶向大阶

看齐，即阶码小的数的尾数右移，每右移一位，阶码加1,直到两数的阶码相等为

止。假设7位浮点数中最高位为阶符，只有选项B的阶符为0,即阶码为正，所以

B为正确答案。

15、设CPU地址总线有24根，数据总线有32根，用512Kx8位的RAM芯片构

成该机的主存储器，则咳机主存最多需要（）片这样的存储芯片。

A、256

B、512

C、64

D、128

标准答案：D

知识点解析：地址线为24根，则寻址范围是224,数据线为32根，则字长为32

位。主存的总量=224x32位，因此所需存储芯片数=（224x32位）/（512Kx8

位）二128。

16、若由高速缓存、主存、硬盘构成的三级存储体系，则CPU访问该存储系统时

发送的地址为（）。

A、高速缓存地址

B、虚拟地址

C、主存物理地址

D、磁盘地址

标准答案：C

知识点解析：当CPU访存时，先要到Cache中查看该主存地址是否在Cache中，

所以发送的是主存物理地址。只有在虚拟存储器中，CPU发出的才是虚拟地址，

这里并没有指出是虚拟存储系统。磁盘地址是外存地址，外存中的程序由操作系统

调入主存中，然后在主存中执行的，囚此CPU不可能直接访问磁盘。

17、某指令系统有200条指令，对操作码采用固定长度二进制编码，最少需要用（）

位。

A、4

B、8

C、16

D、32

标准答案：B

知识点解析：因128=27〈200V28=256,故采用定长操作码时，至少需8位。

18、下面（）寻址方式处理数组问题更为方便。

A、间接寻址

B、变址寻址

C、相对寻址

D、基址寻址

标准答案：B

知识点解析：变址寻址便于处理数组问题。

19、在使用流水线的系统中，n个任务顺序完成时间的时间为To,采用k段流水完

成任务所用的时间为TK，那么这条流水线的加速比为（）。

A、S=T（）/TK

B、S=TK/To

C、S=T0/T„

D、S=Tn/T（）

标准答案：A

知识点解析：设To为任务顺序完成时间，改为k段流水完成任务所用的时间，那

么加速比的计算公式为S=T0/Tko

20、下列关于并行微程序控制器的说法正确的是（），

A、现行微指令的执行与取下一条微指令的操作并行

B、现行微指令的执行与取下•条微指令的操作串行

C、两条或更多微指令的执行在时间上并行

D、两条或更多微指令的取微指令操作在时间上并行

标准答案：A

知识点解析：并行微程序控制器中，在执行现行微指令的同时，取下一条微指令，

A选项的描述正确。

21、总线的异步通信方式（）。

A、不采用时钟信号，只采用握手信号

B、既采用时钟信号，又采用握手信号

C、既不采用时钟信号，乂不采用握手信号

D、以上都不对

标准答案：A

知识点解析：总线的同步定时方式是采用公用的时钟信号，以时钟信号来确定每个

信号出现在总线上的时刻。而异步定时方式是建立在应答式或互锁机制基础上的，

不需要统一的公共时钟信号，但需要握手信号，因此选项A正确。

22、磁盘存储器的等待时间是指（）。

A、磁盘旋转1周所需的时间

B、磁盘旋转半周所需的时间

C、磁盘旋转2/3周所需的时间

D、磁盘旋转1/3周所需的时间

标准答案：B

知识点解析：磁盘访问时间包括寻道时间和旋转延迟时间。寻道时间是将磁头定位

到所要求的磁道上所需的时间；旋转延迟时间是指磁盘上需要访问的区域旋转到达

磁头下方所需的时间。这两个时间都与磁头和数据的位置有关，是随机变化的，因

此一般用平均值表示，即将磁盘旋转半周的时间定义为磁盘存储器的等待时间，也

称为磁盘的寻址时间。

23、能够引起用户态和内核态转换的事件是（）。

A、异常

B、系统调用

C、外围设备的中断

D、以上都是

标准答案：D

知识点解析：用户态与核心态的转换：系统调用。用户态进程通过系统调用申请使

用操作系统提供的服务程序完成工作。异常：当CPU执行运行在用户态下的程序

时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常

的内核相关程序中，也就转到了内核态。外围设备的中断：当外围设备完成用户请

求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要

执行的指令转而去执行与中断信号对应的处理程序.如果先前执行的指令是用户态

下的程序，那么这个转爽的过程自然也就发生了由用户态到内核态的切换。

24、共享变量是指（）访问的变量。

A、只能被系统进程

B、只能被多个进程互斥

C、只能被用户进程

D、可被多个进程

标准答案：D

知识点解析：共享变量是指可被多个进程访问的变量。

25、下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）。

A、时间片轮转调度算法

B、短进程优先调度算法

C、先来先服务凋度算法

D、高响应比优先调度算法

标准答案：D

知识点解析：响应比=(等待时间+执行时间)/要求服务的时间。

26、一种哲学家就餐问题的解决方案如下所述：Philosopheri：

do{wait(chopstick[i])；wait(chopstick[(i+1)%5])eatsignal(chopstick[i])；

signal(chopstick[(i+1)%5])；think}vvhilc(l)：上述方法，说法正确的是()。

A、此算法保证每个哲学家都能互斥地使用筷子且不会处于死锁

B、此算法保证每个哲学家都能互斥地使用筷子但是会出现死锁

C、此算法不能保证哲学家互斥地使用筷子且不会处于死锁

D、此算法不能保证哲学家互斥地使用筷子并且系统会死锁

标准答案：B

知识点解析•：假设每个哲学家变得饥饿，同时拿起左边筷子，而右边的筷子为空，

这样永远拿不到右边的筷子，处于死锁的状态。

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

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

A、1

B、10

C、1/10

D、100

标准答案：A

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

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

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

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

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

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

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

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

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

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

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

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

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

28、分页式虚拟存储管理系统中，一般来说页面的大小与可能产生缺页中断的次数

()o

A、成正比

B、成反比

C、无关

D、成固定比值

标准答案：B

知识点解析：页面越小发生缺页中断次数的可能性越大。

29、在一个请求页式的虚拟存储系统中，每个页面的大小分为40%字节。如下某

个程序需要将数组赋值，假设执行代码已经驻留内存，而数据页面尚未分配，数组

按先行后列存放。请计算，其缺页中断次数是（）。inta[1024][1024]；inti,j；

i=0：for（j=0；j<=1023：j++）A[i][j]=j；

A、2

B、1

C、1024

D、512

标准答案：D

知识点解析•：本题考查对C语言程序在使用内存时的分配机制。采用请求页式虚

拟存储管理的基本点的是按需分配内存，仅当使用到该页时才通过缺页中断分配内

存。C语言对数组的存放是先行后列的，整型数组每个占用2个字节。据此，我们

可以计算，40%字节可以存放2行数组，由于程序中并非按行赋值，而是按列赋

值，所以一页只赋值2个数组（是跳跃地赋值）。若每申请一页产生1次缺页中断，

那么总共要产生1024/2=512次缺页中断。

30、在文件的逻辑组织中，不属于记录文件的是（），

A、索引文件

B、分区文件

C、链接文件

D、索引顺序文件

标准答案：B

知识点解析：对于记录型文件，构成文件的基本单位是记录。记录文件是具有符号

名并且在逻辑上具有完整意义的记录序列。用户对记录型文件的访问是以记录为基

本单位的.一个记录由一组在逻辑卜相关的信息项构成°每个文件内部有一个读写

指针，通过系统调用可以将读写指针移动到文件的某一位汽处，以后的读写系统调

用命令将从该指针所确定的位置处开始。因此，索引顺序文件、链接文件和索引文

件都是记录文件。只有分区文件不是记录文件，故正确答案为B。

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

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

A、设备控制表（DCT）

B、系统设备表（SDT）

C、控制器控制表（COCT）

D、通道控制表（C2HCT）

标准答案：A

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

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

针指向设备控制表，这个数据表每个设备一张，记录了设备的特性和状态。每个设

备有可能有不止一个控制器，所以从设备控制表会指向多张（至少一张）控制器及制

表，里面存放了控制器的控制参数。如果该设备是通道的话，则会指向多张通道控

制表。

32、通道又称I/O处理机，它用于实现（）之间的信息传输。

A、主存和外设

B、CPU与外设

C、主存与外设

D、CPU与外存

标准答案：C

知识点解析：通道主要用于主存和外设的信息交换。

33、在OSI参考模型中，下列功能需由应用层的相邻层实现的是（）。

A、对话管理

B、数据格式转换

C、路由选择

D、可靠数据传输

标准答案：B

知识点解析：本题考查的知识点主要是OSI模型及其各层的主要功能.在OSI参

考模型中，应用层的相邻层是表示层。表示层的功能是表示出用户看得懂的数据格

式，实现与数据表示有关的功能，主要完成数据字符集的转换、数据格式化和文本

压缩、数据加密、解密等工作。

34、在带宽为4kHz的信道上，如果有4种不同的物理状态来表示数据，若信噪比

5/1^为30<18,按香农定理，最大限制的数据速率为（）。

A、6kbps

B、16kbps

C、40kbps

D、56kbps

标准答案：C

知识点解析：此题考查的知识点是香农定理。本题中W=4000Hz,S/N=1000,

根据香农定理，最大数据传输率=亚'1。82（1+5/N）-40kbps,因此C正确。

35、网络中的广播信息太多时能使整个网络性能急剧恶化，这种现象称为（）。

A、网络拥塞

B、IP多播

C、广播风暴

D、以上均不是止确答案

标准答案：C

知识点解析：这种现象祢为“广播风暴

36、在IEEE802.3以太网中，碎片帧指的是小于（）字节的帧。

A、64

B、128

C、256

D、512

标准答案：A

知识点解析：小于64字节的帧称为碎片帧。这主要是冲突造成的不完全帧。

37、某公司获得了一个1P地址段，在不分子网的情况下，最多可以容纳65534个

主机，那么这个地址属于（）。

A、A类地址

B、B类地址

C、C类地

D、D类地址

标准答案：B

知识点解析：B类地址的主机号的长度是16位，再去点全“0”和全“1”两个地址，

还可以分配65534个主机。

38、下列关于地址转换技术（NAT）的叙述，不正确的是（）。

A、地址转换技术可以使用私有IP地址的内部主机访问.Internet

B、地址转换技术能够确保内部主机正常使用所有Internet服务

C、地址转换技术能够对内部主机起到一定的安全保护作用

D、以上均不正确

标准答案：D

知识点解析：本题考查地址转换技术的基本原理.地址转换技术采用端U映射的方

式是内部主机可以访问外部的服务。由于内部主机对外部是不可见的，因此具有一

定的保护作用。故答案是D。

39、如果在TCP连接中有一方发送了FIN分组，并且收到了回复，那么它将（）。

A、不可以发送数据，也不可以接收数据

B、可以发送数据，不可以接收数据

C、不可以发送数据，可以接收数据

D、连接马上断开

标准答案：C

知识点解析：TCP采用全双工的通信方式，当一方请求断开连接，发送FIN分组

后，另一方仍然可以发送数据。

40、在电子邮件程序向邮件服务器中发送邮件时，使用的是简单邮件传送协议

SMTP,而电子邮件程序从邮件服务器中读取邮件时，可以使用（）协议。

A、PPP

B、POP3

C、P2P

D、NFWS

标准答案：B

知识点解析：电子邮件的读取协议是POP3。

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

41、已知AOE网中顶点Vi，V2,V3,V4,V5,V6,V7,分别表示7个时间，有

向线段a”a2，a3，a*as，a6，a7，ag,ag，aio分别表示10个活动，线段旁的数

值表示每个活动花费的天数，如下图所示。请填写下面两个表格，并用顶点序列表

示出关键路径，给出关键活动。

事件V,%V,匕V,V、V，

最早发生时间

最晚发生时间

活动

最早-发生时间

最晚发生时间

时间余最

标准答案：AOE网中从源点到终点的最大路径长度(这里的路径长度是指该路径上

的各个活动所需时间之和)的路径称为关键路径。关键路径长度是整个工程所需的

最短工期。关键路径上的活动称为关键活动。要缩短整个工期，必须加快关键活

动的进度。寻找关键活动时所用到的几个参量的定义：假设第i条弧为，dut()为

弧上的权值。(I)事件的最早发生时间ve|k]=从源点到顶点k的最长路径长度。

ve(源点)=0；ve(k)=Max{Ve(j)+dut()}(2)事件的最迟发生时间vl(k)=从顶点j到汇点

的最短路径长度。vl(汇点)：ve(汇点)；vl(j尸min{vl(k)-dut())⑶活动i的最早开始

时间e(i)=ve(j)o(4)活动i的最晚开始时间l(i)=vl(k[-dut()。的活动就是关键

活动，关键活动所在的路径就是关键路径。

事件V.：

VV,v4v,乂VT

「早发生时间03267510

最晚发生时间03367610

活动%4a.%a；3|0

最早发生时间0003322675

最晚发生时间0013453676

时间余量00i1013i001

知识点解析：暂无解析

42、线性表（ai，a2,a3...,an）中元素值递增有序（没有重复元素）且按顺序存储于计

算机内。如果想在当前的线性表中查找数值为x的元素，请设计一个时间复杂度坡

低的算法。找到x后，洛其与后继元素位置相交换。如果线性表中没有x,将其插

入表中并使表中元素仍递增有序。请回答下列问题：（1）给出算法的主要思想；（2）

写出算法的实现函数；（3）总结所用算法的时间和空间复杂度。

标准答案：（1）顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目

要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。（2）

算法实现如下：voidSearchExchangeInesert（ElemTypea[]»ElemTypex）||a是具有n

个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的元素，如查到

则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序low=0：

high=n-l：//low和high指向线性表下界和上界的下标

while（low<=high）{mid=（low+high）/2；//找中间位置if（a[mid]==x）break；//

找到x,退出while循环elseif（a[mid]high）//查找失败，插入数据元素x

V{for（i=n-l：i>high：i-）a[i+l]=a[i]：//后移元素a[i+l]=x：//插入x}ll结束

插入}II结束本算法（3）折半的时间复杂度为0（10gn）,如果不存在x的情况下，在线

性表中插入元素的时候，时间复杂度取决于x插入的位置，最坏情况下为0（n）。算

法实现过程中使用的辅助空间为常量，空间复杂度为0（1）。

知识点解析：暂无解析

43、某机主存容量为1MB,两路组相连方式（每组仅有两块）的Cache容量为64

KB；每个数据块为256字节。CPU要顺序访问的地址为20124H、58100H、

60140H和60138H等4个主存字节单元中的数。已知访问开始前第2组（组号为1）

的地址阵列内容如下图所示，Cache采用LRU替换策略。

000100（二进制）

1________________01011（二进制）_______________

说明Cache的结构

（即分多少组、组内分多少块），给出主存及Cache的地址格式。上述4个数能否直

接从Cache中读取，若能，请给出实际访问的Cache地址。第4个数访问结束时,

上图的内容如何变化。

标准答案：根据题意知，主存容量为1MB,Cache容量为64KB,分成大小相等

的数据块。设每个数据块为256字节，则主存共有4098块，Cache共有256块，

两路组相连方式（即每组仅有两块），所以Cache中共有128组。Cache分为12B

组，组内分成2块，主存和Cache的地址格式，如下图所示。

主存地址标记（5位）组号（7位）块内总址（8位）

cache地址1位组号（7位）块内地址（8位）

组内块号将CPU要顺序访问的4个

数的地址写出二进制，可以发现：（1）20124H=00100000000100100100B

20124的主存地址0010000000010010010()

20124的cache地址0（XX）000100100100

T

组内块号组号为1,是第2组的

块，根据题目中给出的图可知，现在Cache内有这个块，第1次访问命中，实际访

问的Cache地址为0124H。（2）58100H=01011000000100000000B

58】00的主存地址0101I~000000100000000

58100的cache地址|000000100(X)0000

组内块号组号为1,是第2组的

块，根据题目中给出的图可知，现在Cache内有这个块。第2次访问命中，实际访

问的Cache地址为OlOOHo（3）60140H=01100000000101000000B

60140的主存地址|―01100000000101000000

000000010100()000

组内块号组号为I,是第2组的

块，但Cache中没有这个块，第3次访问不命中。根据LRU算法，替换掉第0块

001100

101011

位置上的数据块，变化后的地址阵列，如下图所示:

（4）60138H=0110000000010ol11000B

60138的主存地址01100000000100111000

60138的cache地址0000000100111000

组内块号组号为1，是第2组的

块，与上一个地址处于同一个块，此时这个块已调入Cache中，所以第4次访问命

中，实际访问的Cache地址为0138H。第4个数访问结束时，地址阵列的内容与刚

才相同。

知识点解析：暂无解析

44、某计算机有下图所示的功能部件，其中M为主存，MDR为主存数据寄存器,

MAR为主存地址寄存器，Ro〜R3为通用寄存器，IR为指令寄存器，PC为程序计

数器（具有自动加1功能），C、D为暂存寄存器，ALu为算术逻辑单元，移位器可

左移、右移、直通传送。

移位器|~以1RoMDR

/ALU\|PC|

R.

L_____ZK_____AM

1CIR

DRMAR

s（1）将所有功能部件连接

起来，组成完整的数据通路，并用单向或双向箭头表示信息传送方向。（2）画出

“ADDR|,（RA”指令周期流程图。该指令的含义是将R］中的数与（RA指示的主存

单元中的数相加，相加的结果直通传送至Ri中。（3）画出“ADDRi，R2”指令周期

流程图。该指令的含义是将R］中的数与R2中的数相加，相加的结果直通传送至

R1中。

(1)

标准答案:

知识点解析：暂无解析

45、设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同

时进入就绪状态，进程A先得到CPu运行，进程B后运行。进程A的运行轨迹

为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程

B的运行轨迹为：计算50ms,输入数据80ms,再计算100ms,结束。试画出它

们的时序关系图(可以用甘特图)，并说明：(1)开始运行后，CPu有无空闲等待?若

有，在哪段时间内等待。计算CPU的利用率。(2)进程A运行时有无等待现象?若

有，在什么时候发生等待现象？(3)进程B运行时有无等待现象?若有，在什么时候

发生等待现象？

标准答案：(1)

50100150180200300

时间!II」一」