计算机专业（基础综合）模拟试卷2（共473题）

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

9套）

（共473题）

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

套

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

1、图的邻接表存储表示，数据元素之间的关系是（）。

A、线性结构

B、树形结构

C、网状结构

D、无结构

标准答案：A

知识点解析：根据数据元素间关系的不同特性，通常有下列四类基本的结构：（1）

集合结构。该结构的数据元素间的关系是“属于同一个集合（2）线性结构。该结

构的数据元素之间存在着一对一的关系。（3）树型垢•构。该结构的数据元素之间存

在着一对多的美系。（4）图形结构。该结构的数据元素之间存在着多对多的关系，

也称网状结构。邻接表（adjacencylist）是图的一种链式存储结构。这种存储表示法类

似于树的孩子链表表示法。对于图G中每个顶点vi,把所有邻接于vi的顶点vj链

成一个单链表，这个单链表称为顶点vi的邻接表。每个顶点对应一个相应的邻接

表故图的邻接表存储表示，数据元素之间的关系足线性关系。

2、I、2、3、4顺序入栈（起始为空栈），只要栈不空即可出栈，不可能的序列是

（）。

A、4、3、2、1

B、2、1、3、4

C、1、2、3、4

D、4,3,1,2

标准答案：D

知识点解析：D错，首先出栈的是4,故1、2、3必然己入过栈，出栈序列必为

4、3、2、!<,

3、一棵N个结点的非空二叉树，其叶子结点个数的最小值和最大值分别是（），

A、1,N—1

B、N/2,N/2

C、I,（N+l）/2

D、（N—1）/2,（N+l）/2

标准答案：C

知识点解析：当二叉树排列成单链树时，二叉树的高度最大，此时叶子结点数最少

只有1个，当二叉树排列成完全二叉树时，叶子节点数最多有（N+1）/2个。

4、一棵结点个数为63的满二叉树转换为森林。则森林中树的个数是（）。

A、7

B、6

C、5

D、4

标准答案：B

知识点解析：63个结点的满二叉树高度为6,根结点与其右孩子的连线上（包括根

节点）共有6个结点，故转化为森林后有6棵树。所以选B。

O——©

5、给定下图，0------6（）不是它的广度优先遍历。

A、1243

B、4312

C、2134

D、3214

标准答案：D

知识点解析：图的BFS遍历。D选项，首先访问结点3,与3邻接的结点4、2都

未曾访问过，故3后面因该为2、4（或4、2）,故D错。

6、一棵BST树共7个结点，值分别为1、2、3、4、5、6、7,形态为满二叉树，

（）不是插入序列。

A、4261357

B、4231675

C、4213567

D、4657213

标准答案：C

知识点解析：二叉排序树（BST）是具有下列性质的二叉树：（1）若它的左子树不空，

则左子树上所有结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子

树上所有结点的值均大于它的根结点的值；（3）它的左、右子树也分别是二又排序

树。据此分别画出相应序列的二叉树，知C错。

7、将N个关键字映射到一个Hash表中，用链地址法解决冲突。在这个Hash表中

查找一个关键字所需的操作为（）。

A、HashH决射N次，链结点比较最多1次

B、Hash映射1次，链结点比较最多N次

C、Hash映射N/2次，链结点比较最多N/2次

D、Hash映射N—1次，链结点比较最多1次

标准答案：B

知识点解析：查找一个关键字只需一次Hash映射就可找到关键字所在的链表，紧

接着在该链表中从头到尾依次查找每个元素是否是所要查找的关键字，此时最多需

N次链表结点的比较。

8、高度为4的4阶B树最多可容纳（）个关键字（根是第1层）。

A、254

B、255

C、340

D、383

标准答案：B

知识点解析：B一树：一种平衡的多路查找树，在外存文件系统中常用的动态索引

技术。一棵m阶B一树，或为空树，或为满足下列特性的m叉树：（1）树中每个结

点至多有m棵子树；（2）若根结点不是叶子结点，则至少有两棵子树；（3）除根之

外的所有非终端结点至少有［m/2］棵子树；（4）所有的非终端结点中包含下列信息

数据（n,Ao，Ki，Ai，Kn,An）（lm/21—19Sm—1）：（5）所有的叶子结点都

出现在同一层次上，并且不带信息。分析这些性质知道，故选B。

9、己知待排数据基本有序，则以下四种排序方法中比较合适的选择应为（）。

A、快速排序

B、选择排序

C,插入排序

D、堆排序

标准答案：C

知识点解析：数据基本有序时，插入排序是最好的。

10、对已知范围矩形中的坐标排序，数据量较大，要求先排横坐标，再排纵坐标，

则应选（）。

A、归并排序

B、快速排序

C、堆排序

D、基数排序

标准答案：D

知识点解析：基数排序的时间复杂度为O（d（n+rd））,适用于n值很大而关键字较小

的序列。

II、一个8位的二进制整数，若采用补码表示，KLh3个“1”和5个“0”组成，财最

小值为（）。

A、一127

B、一32

C、一125

D、一3

标准答案：C

知识点解析：8位补码最小时必为负数，此时第1位（符号为）必为1,而负数的数值

位绝对值越大负数越小。又负数的补码表示的高位。相当于原码表示的1,故当剩

下的2个“「和5个“0”中的5个“0”全在除符号位的高5位，2个“1”在低2位时此负

数最小。该负数的补码的二进制表示为是10000011,转换为10十进制为一125,

故选C。

12、以下（）寻址方式用来支持浮动程序设计。

A^相对寻址

B、变址寻址

C、寄存器间接寻址

D、基址寻址

标准答案：A

知识点解析：浮动程序技术是指在多道程序设计的系统中，要求每道程序存放在主

存的任何区域都能正确执行，甚至在执行过程中，当程序的存放区域被改变，也要

求其执行不受影响。也就是说，程序可以随机地从主存的一个区域移动到另一个区

域，程序被移动后仍丝毫不影响它的执行。相对寻址是用程序计数器PC的内容作

为基准地址，指令中给出的形式地址作为偏移量，偏移量可正可负，二者相加后形

成操作数的有效地址。这种方式实际上是以当前指令位置为基准，相对它进行位移

定位，即不必用指令的绝对地址编程，因此可以将所编程序放在内存中的任何地

方，符合浮动程序技术的特点。而其他几种寻址方式则没有这种特点。故选A。

13、Cache用组相联映射，一块大小为128字节，Cache共64块，4块分一组。主

存有4096块，主存地址供需（）位。

A、19

B、18

C、17

D、16

标准答案：A

知识点解析：组相联映像是直接映像和全相联映像的一种折中方案，它把cache分

组，组内分块，将主存笈照（2ache容量分组，组内按照Cache中块的大小分块，映

射时，主存中每组的第i块必须映射到Cache中第i组中的任意一字块中。这样组

问为直接映像，组内为全相联映像。本题中，主存容量为4096x128=2四字节，故

主存地址供需19位，其中包括块内地址7位，组内块号2位，组号4位，及主存

高位地址16位。故选A。

14、下列说法中不正确的是（）。

A、变址寻址时，有效数据存放在主存中。

B、堆栈是先进后出的随机存储器。

C、堆栈指针SP的内容表示当前堆栈内所存储的数据的个数。

D、内存中指令的寻址和数据的寻址是交替进行的,

标准答案：C

知识点解析：SP是栈顶指针，指向当前栈顶元素的下一位置，不表示当前栈内数

据的个数，故C错。

15、下列各部件中不属于控制器的部件是（）。

A、指令寄存器

B、操作控制器

C、程序计数器

D、状态条件寄存器

标准答案：D

知识点解析：控制器是由程序计数器、指令寄存器、指令译码器、时序发生器和操

作控制器组成，它是发布命令的“决策机构”，完成协调和指挥整个计算机系统的操

作。

16、下列各种情况中，应采用异步通信方式的是（），

A、I/O接口与打印机交换信息

B、CPU与存储器交换信息

C、CPU与I/O接口交换信息

D、CPU与PCI总线交换信息

标准答案：A

知识点解析：暂无解析

17、在浮点数机制中，判断补码规格化形式的原则是（）。

A、尾数的第一位为1,数符位任意

B、尾数的符号为与第一数位相同

C、尾数的符号位与第一数位不同

D、阶符与数符不同

标准答案：C

知识点解析：尾数采用补码表示，对于正数，规格化后符号位为0,数值位最高位

为1;对于负数恰好相反，因此，尾数规格化后，符号位与第一数位不同。

18、下列各术语中，用于表征计算机系统性能指标的是（）。

A、RISC

B、PSW

C、PC

D、MFLOPS

标准答案：D

知识点解析：MF、LOPS：每秒百万个浮点数操作，是衡量计算机系统的性能的指

标之一。MIPS：每秒处理的百万级的机器语言指令数，是衡量CPU速度的指标。

RISC：精简指令系统；PSW：程序状态字；PC：程序计数器都不是衡量计算机性

能的指标。故选Do

19、IEEE：754标准规定的32位浮点数格式中，符号位为1位，阶码为8位，尾

数为23位。则它所能表示的最大规格化正数为（）。

A、+（2—223）x2+127

B、+（1-223）x2+127

C>4-（2-223）X2+2+255

D、2十⑵一223

标准答案：A

知识点解析：暂无解析

20、在集中式总线仲裁中，（）方式响应时间最快。

A、链式查询

B、独立请求

C、无条件传送

D、计数器定时查询

标准答案：B

知识点解析：独立请求方式每个设备都有一对总线请求线和总线允许线，各设备独

立请求总线。故响应速度最快。

21、CPU在每个（）周期后响应DMA清求。

A、时钟

B、总线

C、存储

D、指令

标准答案：B

知识点解析：暂无解析

22、“守护进程”在系统中一般不需要使用（）。

A、辅助存储设备

B、中断机制提供的功能

C>终端

D、物理内存

标准答案：C

知识点解析：在linux或者unix操作系统中在系统的引导的时候会开启很多服务，

这些服务就叫做守护进程。为了增加灵活性，root可以选择系统开启的模式，这些

模式叫做运行级别，每一种运行级别以一定的方式配置系统。守护进程是脱离于终

端并且在后台运行的进程。守护进程脱离于终端是为了避免进程在执行过程中的信

息在任何终端上显示并且进程也不会被任何终端所产生的终端信息所打断。

23、既允许在操作系统内核态执行又可以在用户态执行的指令是（）。

A^禁止所有中断

B、读系统时钟

C、写系统时钟

D、改变存储映射

标准答案：B

知识点解析：内核态与用户态是操作系统的两种运行级别，inlelcpu提供Ring。一

Ring3三种级别的运行模式。Ring。级别最高，Ring3最低。当一个任务（进程）执行

系统调用而陷入内核代码中执行时，我们就称进程处于内核运行态（或简称为内核

态）。此时处理器处于特权级最高的（O级）内核代码中执行。当进程处于内核态时，

执行的内核代码会使用当前进程的内核栈。每个进程都有自己的内核栈。当进程在

执行用户自己的代码时，则称其处于用户运行态（用户态）。即此时处理器在特权级

最低的（3级）用户代码中运行。

24、“程序与进程”的类比最接近（）。

A、演员与演出

《雷雨》剧本与该剧本的一次演出

C、四个运动员和4x100米接力比赛

D、WindowslE与MSWindows操作系统

标准答案：B

知识点解析：程序是静态的，进程是程序的一次动态执行过程，故与B所描述现

象相似。

25、Spooling技术一般不为（）提供虚拟化支持。

A、键盘

B、打印机

C、磁盘

D、鼠标

标准答案：C

知识点解析：磁盘属于高速设备一般不需虚拟化的支持。

26、把某设备motlnt到一个非空目录dir则（）。

A、dir中仅可见原来的文件

B、dir中不仅可见原来的文件，还同时可见设备中的文件

C、dir中的文件被删除，仅可见设备中的文件

D、dir中的文件未被删除，仅可见设备中的文件

标准答案：D

知识点解析：考察UNIXShcll基本命令。toount［一参数］［设备名称］［挂载点］;挂载

点必须是一个已经存在的目录，这个目录可以不为空，但挂载后这个目录下以前的

内容将不可用，Limoun【以后会恢复正常。

27、不需要抢占的进程调度算法是（）。

A、最早截至时问优先

B、时间片轮转

C、最短时间优先

D、最短剩余时间优先

标准答案：c

知识点解析：最短时间优先算法以进程本次所需CPU时间的长短作为调度的依据

来选择进程投入运行，一旦进程获得处理机后就不可被抢占直到本进程执行完毕。

而其他3种进程调度算法都是基于抢占的调度算法，当前获得处理机的进程可能被

刚进来的进程抢占处理机。故选C。

28、三哲学家进餐问题的伪代码如下，fl,f2,俘是三根筷子，贝1」（）。

PhP2.P3,

wfulr(!)(while(1){while(1)(

P(fl)»Peru,P(f3)i

Kf2)iP(£2)«

Ott(J|EatOtEatOi

V(f3)：V<f2)«V(f2)»

v<n>i

1I

A、可能死锁，pl或p2或p3都有可能饥饿

B、不可能死锁.但pl或p2或p3都有可能饥饿

C、不可能死锁，但只有pl或p2有可能饥饿

D、不可能死锁。但只有p2或p3有可能饥饿

标准答案：B

知识点解析：pl、p2和p3不满足死锁的四个必要条件中的循环等待条件，故不可

能发生死锁。排除A。设p3先申请到廿，若此时p2先于pl申请到fl,则此时p2

好和p3任意一个申请到f2都可执行完毕，假设是p2中请到了f2执行完毕，释放

f2,fl,则p3可获得f2执行完毕，倘若p2紧接着又申请到了fl,p3执行完后紧

接着又申请到了如此循环则pl始终没有机会获得处理机执行而发生饥饿现

象。以此类推p2和p3都有可能发生饥饿现象。故选B。

29、某操作系统采用变长存储分区机制，分区有两类，一类是占用块，一类是空闲

块。占用块又可进一步分为（I）左右均为占用块。（II）仅左边为占用块，（ID）仅右边

为占用块，（W）左右均为空闲块，用a记⑴类块的个数，b记（II）类块的个数，c记

（DI）类块的个数，d记（W）类块的个数，则系统中的空闲块数为（）。

A、a+b+c+d

B、b+c+2d

C、2b+2d

D、b+d

标准答案：D

知识点解析：暂无解析

30、某文件系统专用于影视多媒体应用，数据存放在光盘，则合理的文件物理存储

格式应为（）。

A、顺序存储

B、链式存储

C、索引式存储

D、BS"rM

标准答案：A

知识点解析：顺序存储是用一组地址连续的存储单元依次存储各元素，其特点是无

需为表示结点间的逻辑关系而增加额外的存储空间，可以方便地随机访问表中的任

一结点；非常适合于影视多媒体等应用。

31、某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生

产者提的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区

的速度快，则缓冲区个数的最优值应为（）。

A、n-1

B、n

C、n+l

D、2n

标准答案：C

知识点解析•：由于生产者写缓冲区的速度比消费者读缓冲区的速度快，所以为使生

产者写入的数据不至丢失最少需n个缓冲区供生产者写入外加1个单独的缓冲区供

消费者读出。故缓冲区个数最优值为n+l。选C。

32、UNIX设备驱动程序分为上半区和下半区，上、下半区的工作方式为（）。

A、同步、同步

B、异步、同步

C^同步、异步

D、异步、异步

标准答案：C

知识点解析：暂无解析

33、TCP/IP网络协议主要在OSI模型中进行操作的层次是（）。

A、数据链路层、传输层、物理层

B、物理层、传输层、会话层

C、网络层、传输层、应用层

D、网络层、传输层、会话层

标准答案：C

知识点解析：暂无解析

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

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

为Bbps,虚电路建立连接的时间都为S秒，在分组交换方式下每个中间节点产生

d位的延迟时间，则传送所有数据，虚电路分组交换所需时间是（［X］表示对X向上

取整）（）。

A、S+(hd/B+P/B)x|L/(P—H)]^

B、S+(hD+P/B)x[L/(P—H)]秒

C>S+[(h—l)D+P/B]x[L/(P—H)]秒

D、S+|(h—l)d/B+hEH-P/B]x|L/(P—H)]^

标准答案：D

知识点解析：暂无解析

35、在IP数据报报头中有两个有关长度的字段，一个为报头长度(IHL)字段，一个

为总长度(totallength)字段，下面说法正确的是()。

A、报头长度字段和总长度字段都以X比特为计数单位

B、报头长度字段以8比特为计数单位，总长度字段以32比特为计数单位

C、报头长度字段以32比特为计数单位，总长度字段以8比特为计数单位

D、报头长度字段和总长度字段都以32比特为计数单位

标准答案：C

知识点解析：IHL实段以4字节为单位，totallength字段以字节为单位。

36、如果一台主机的机地址为192.168.0.10,子网掩码为

255.255.255.224,那么主机所在网络的网络号占IP地址的位数是()。

A,24

B、25

C、27

D、28

标准答案：C

知识点解析：先将子网掩码转换为二进制得到

11111111,11111111,11141111,IHOOOOOo前27位为1所以网络号占IP地址的位数

是27,故选C。

37、关于DHCP的工作过程，下面说法错误的是()。

A、新入网的计算机一般可以从DHCP服务器取得IP地址，获得租约

B、若新入网的计算机找不到DHCP服务器，则该计算机无法取得IP地址

C、在租期内计算机重新启动，而且没有改变与网络的连接，允许该计算机维夺原

租约

D、当租约执行到50%时，允许该计算机申请续约

标准答案：B

知识点解析•：DHCP动态主机配置协议，它允许一台计算机加入新的网络和获得

1P地址而不用手工参与。也可以不用DHCP协议来获取IP地址，而是手工给主机

设定一个可用的IP地址。

38、路由器中发现TTL值为。的分组将进行的处理是()。

A、返回发送方

B、丢弃

C、继续转发

D、本地提交

标准答案：B

知识点解析：TTL：（TimcToLive）生存时间；指定数据包被路由器丢弃之前允许通

过的网段数量。TTL是由发送主机设置的，以防止数据包不断在IP互联网络上永

不终止地循环。转发1P数据包时，要求路由器至少将TTL减小1。当路dj器发现

TTL值为0的分组时则丢弃该分组。

39、关于TCP和UDP端口，下列说法正确的是（）。

A、TCP和UDP分别拥有自己的端口号，它们互不干扰，可以共存于同一台主机

B、TCP和UDP分别拥有自己的端口号，但它们不能共享于同一台主机

C、TCP和UDP的端口没有本质区别，它们可以共存于同一台主机

D、TCP和UDP的端口没有本质区别，它们互不干扰，不能共存于同一台主机

标准答案：A

知识点解析：传输层协议TCP和UDP都使用端口号标识应用程序，也就是使用端

口号实现不同进程的复用。但二者的端口号具有不同含义。TCP端口号标识一个

使用TCP协议的应用进程。UDP端口号标识一个使用UDP协议的应用进程。具体

通过IP协议实现复用和分用：源主机将TCP报文段和UDP用户数据报都交给IP

协议，IP协议通过IP数据报中的“协议”字段进行标识；当IP数据报到达目的主机

时，目的主机将根据IP数据报中的“协议''字段将数据交给JL层的TCO或UDP,然

后TCP和UDP根据端口号将数据交给相应的应用进程。故选Ao

40＞下列Internet应用中，基于C/S计算模式的是（）。

A、FTP

B、BT

C、MSN

D、Skype

标准答案：A

知识点解析：C/s模式是客户服务器模式，选项中只有FTP是基于此模式的.

二、综合应用题（本题共“题，每题1.0分，共〃

分。）

41、设有m个连续单元供一个栈与队列使用，且栈与队列的实际占用单元数事先

不知道，但是要求在任何时刻它们占用的单元数量不超过m,试写出上述栈与队

列的插入算法。

标准答案：算法如下：//定义结点的结构为structNode{ElemTypcdatastruct

Node*next；}//定义栈的结构structStack{Node*base；Node*top；}//定义

队列的结构structQueue{Node*front；Node*tail;）：//设m个连续单元的数组

为b[m],定义全局数组static

知识点解析：暂无解析

42、序列的“中值记录”指的是：如果将此序列排序后，它是第n/2个记录。试写

出一个求中值记录的算法。

标准答案：算法如下：typcdefstruct{intgt；//大于该记录的个数intIt；//小

于该记录的个数(place;intGel—Mid(inta[],intn)(placeb|MAXSIZE]；/*对第i

个元素统计比它大和比它小的元数的个数，分别为gt和It*/for(inti=0；

ia[i])b[i].gt++；if(a[j]

知识点解析：暂无解析

43、某浮点机字长16位，其浮点数格式为：阶码5位(含1位阶符)，采用补他表

示，尾数11位(含1位数符)，采用补码表示，且尾数为规格化形式。已知

X=0.101100001lx200101,Y=0.0001100000x20-1000,试求X+Y,要求写出详细

的计算过程。假设浮点加减过程中阶码和尾数采用双符号位，并使用“0舍1入法”

进行舍入。

标准答案：写出X、Y的机器数形式，根据题意，尾数为规格化形式，故

Y=0.0001100000x2OJOO0,1000=0.11OOOOOOOOX2OO,°,,运算过程中阶码、尾数

采用双符号位，X、Y的机器数形式为X=00,0101；00.1011000011,Y=00,

0101；00.1100000000,X+Y的计算过程如下：①对阶，X、Y阶码相同，阶差

00.1011000011

+00・1100000000

为0,故不需对阶。②尾数求和，OIMIKXXX)】】即得X+Y=OO,0101；

01.011100001lo③规格化,尾

知识点解析：暂无解析

某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周

期)。假定某外设的数据传输率为0.5MB/S,采用中断方式与主机进行数据传

送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开

销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。

44、在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多

少？

标准答案：该外设数据，专输率为0.5MB/s,以32位为传输单位，故1s内因外设

传输数据而引起的中断次数为0.5MB/4B=1.25xl()5(次)对应的中断服务程序及

其他开销共需18+2=20条指令，CPI为5,故is内用于该外设I/O的时钟周期数

为1.25X105X20X5=1.25X1(f(个)CPU主频为500MHZ,即Is内共有500M个时

钟周期，故用于该外设I/O的时间占整个CPU时间的百分比是(1.25xl()7)/(5

知识点解析：暂无解析

45、当该外设的数据传输率达到5MB/S时，改用DMA方式传送数据。假设每次

DMA传送大小为5000B,且DMA预处理和后处理的总开销为500个时钟周期，

则CPU用于该外设I/O的时间占整个CPU时间的百分比是多少?(假设DMA与

CPU之间没有访存冲突)

标准答案：该外设的数据传输率为5MB/s,每次DMA传送大小为5000B,故1s

内的DMA传输次数为5MB/5OOOB=(5xlO5B)/(5X1O3B)=1OOO(}^)DMA预处理及

后处理的总开销为500个时钟周期，故1s内用于该外设传输数据的时钟周期数为

1000x500=5x1()5(个)CPU主频为500MHz,故用于该外设I/O的时间占整个CPU

时间的百分比是(5x105)/(500x105)x100

知识点解析：暂无解析

46、分时系统里，在条件相同的情况下，通常KLT(内核级线程)比ULT(用户级线

程)得到更多的CPU时间，请简要解释之。

标准答案：KLT(内核级线程)直接参与CPU的调度，得到CPU的时间和进程相

当，ULT(用户级线程)由运行threadLJbmry的进程控制和管理，是该进程得到的

CPU时间总数里再次分配，往往比参加内核调度的其他进程少。

知识点解析：暂无解析

47、举例说明P、V操作为什么要求设计成原语(即对同一信号量上的操作必须互

斥)。P(S)操作：S.value--：If(S.valuc<0){AddthisprocesstoS.L：

Block()；}V(S)操作S.value++；If(S.value<=0){RemoveaprocessPfrom

S.L：Wakeup(P)：)

标准答案：例如，用P，V操作来实现进程对临界资源互斥使用。此时，只需定义

一个信号量s,其初值{1,NULL),并在临界区前执行P(S)操作，而在临界区后执

行V(S)操作。此时P,V操作不设计成原语，那么在执行P,V操作时进程可以被

中断。由于在初始状态下，临界资源空闲，故应允许第一个申请临界资源的进程进

入临界区使用临界资源，但如果该进程在执行到P操作的语句S.value-后(此时

S.value的值为0)便被另一个进程中断，而那个进程也企图通过执行P(S)操作进

入临界区，则第二个进程也必须执行语句S.value一一，从

知识点解析：暂无解析

如下图所示为一个TCP主机中的拥塞窗口的变化过程，这里最大数据段长度为

1024字节，请回答如下问题：

48、该TCP协议的初始阀值是多少?为什么？

标准答案：该TCP协议的初始阀值为16KB。最大数据段长度为1KB,可以看出

来在拥塞窗口到达16：KB之后就呈线性增长了，说明初始阀值是16KB。

知识点解析：暂无解析

49、本次传输是否有发生超时?如果有是在哪一次传输超时？

标准答案：该TCP传输在第13次传输时发生了超时，可以看到拥塞窗口在13次

传输后变为IKBo

知识点解析：暂无解析

50、在14次传输的时候阀值为多少？

标准答案：在14次传输的时候拥塞窗口变为了12KB,可以看到在之后的传输

中，拥塞窗口到达12KB之后呈线性增长。

知识点解析：暂无解析

51、在本例中，采用了什么拥塞控制算法？

标准答案：采用了慢启动的算法，因为可以看到在发送失败后拥塞窗口马上变为

了1KB,而且阀值也变为了之前的一半。

知识点解析：暂无解析

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

套

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

1、在n个结点的线性表的数组表示中，以下算法的时间复杂度是0(1)的操作是

()oI.访问第i个结点(七区n)和求第i个结点的直接前驱(2Si0n)U.在最后一个

结点后插入一个新的结点HI.删除第一个结点W.在第i个结点后插入一个结点

(l<i<n)

A、仅I

B、仅口、m

c、仅I、n

D、仅I、口、m

标准答案：c

知识点斤：I：由于线性表是用数组表示的(即顺序存储)，可以直接通过结点编

号访问，所以I的时间复杂度一定是0(1)。n：由于是在最后一个结点处插入一

个结点，所以不需要移动元素，故时间复杂度为on)。n：删除第一个结点之

后，需要将后续所有结点往前移动，所以时间复杂度为o(n)。IV：由于i是不固

定的，后续结点i+l,i+2,…，n—1都需要向后移动，所以时间复杂度为O(n)。

2、中缀表达式a*(b+c)-d的后缀表达式是()。

A、abcd*+-

B、abc+*d—

C、abu*+d-

D、-+*abcd

标准答案：B

*'(b*c»

।出

|<bc«•]

Inbc^dj

知识点解析：本题转化过程如图4-4所示。图J铸化过科示怠图由图44可以写出以

下转化过程。第一步：b+c-bc+(假设x="bc+”)第二步：a*x-ax*(假设v="ax*”)

第三步：y-d—vd-将xy还原后得到：abc+*d—。补充知识点(1)：中缀表达式;转

换成后缀表达式的另一种方式。提示：可以通过手工加除括号来将中缀表达式转

换成后缀表达式，其过程如下：先根据中缀表达式的求值次序加上括号，将右括号

用相应的运算符替换，再除掉所有的左括号。例如，中缀表达式“5+2*(1+6)-8/2”

转换成后缀表达式的过程如下：手工判断该表达式的计算过程。首先肯定是先计算

2*(1+6),加上括号变为“5+(2*(1+6))-8/2”，再计算除法8/2,加上括号变为

“5+(2*(1+6))—(8/2)”,接着进行加法运算,加上括号变为“(5+(2*(1+6)))—(8/

2户，最后再进行减法运算，加上括号变为“((5+(2*(1+6)))—(8/2)广。运算符和右

括号的对应关系如图4-5所示，将右括号用对应的运算符替换，变为

“((5(2(16+*+(82/一”，最后除掉所有左括号得到的后缀表达式为“5216+*+82/

I4112*(Mb>I>-<H'2>>

山M

_，，。图2运算符和右括号的对桎关系注：本方法需要人工判断表达式的执行顺序(即力口

括号)，所以无法用程序实现。按照以上方式可以很轻松地解题，不妨试着将中缀

表达式a*(b+c)—d转换成后缀表达式。第一步：进行乘法运算，加括号变为

(a*(b+c))—d°第二步：进行减法运算，加括号变为((a*(b+c))—d)。第三步：找

出运算符和右括号的对应关系，将右括号用对应的运算符替换，变为((a(bc+*d-。

第四步：最后除掉所有左括号得到的后缀表达式为abc+*d-。补充知识点(2)：怎么

将后缀表达式转换成中缀表达式？提示：当遇到数值的时候入栈，当遇到运算符的

时候，连续两次出栈，将两个出栈元素结合运算符进行运算，将结果当成新遇到的

数值入栈。如此往复，直到扫描到终止符“\0”，此时栈底元素值即为表达式的

值。例：将后缀表达式xy+z+转换为中缀表达式。先将x、y入栈，遇到了“+”，

然后弹出栈顶的两个元素，即x、y,然后对x、y做加法，现在将(x+y)的值入栈，

然后z入栈，遇到了操作符/二所以最后的中缀表达式为：(x+y)+Z。注意：中缀

表达式转化成后缀或者是前缀，结果并不一定唯一。比如ab+cd*+e/同样是

(a+b+c*d)/e的后缀式。后缀式和前缀式都只有唯一的一种运算次序，而中缀式却

不一定，后缀式和前缀式是由中缀式按某一种运算次序而生成的，因此对于一个中

缀式可能有多种后缀式或者前缀式。例如，a+b+c可以先算a+b,也口J以先算

b+c,这样就有两种后缀式与其对应，分别是ab+c+和abc++。

3、设线性表有n个元素，以下操作中，()在顺序表上实现比链表上实现效率更

高。

A、输出第i(lSign)个元素值

B、交换第1个元素与第2个元素的值

C、顺序输出这n个元素的值

D、输出与给定值x相等的元素在线性表中的序号

标准答案：A

知识点解析：顺序表支持随机存储，链表不支持，因此顺序表输出第i个元素的值

的时间复杂度为0(1),链表则为0(n),因此A正确。交换第1个与第2个元素的

值，对于顺序表和链表，时间复杂度均为0(1),因此B不对。输出n个元素的

值，两者时间复杂度均为O(n),因此C不对。输出与给定值x相等的元素在线性

表中的序号，对于顺序表和链表，couni需要搜索整个表，因此时问复杂度为

O(n),因此D不对。【注】有的同学认为B也是正确的，其实严格来说B确实是

对的，因为线性表交换要执行3次操作：tcmp=a[l]；a[l]=a[2]；a[2]=tcmp；而

链表要执行5次：p=head->next；q=head->next->next；temp=p->data；

p->data=q->data：q->data=temp,但本题是单选题的时候，考生需要选择更准确的

一项，显然与B项相比，A项更准确。

4、设k是中序线索二叉树中一个有左子女的结点，且k不是根结点，则k在中序

序列下的直接前驱结点是()。

A、k的左线索(指示中序前驱)所指示的结点

B、从k父结点的左子女开始沿右子女链走到底的结点

C、从k的左子女开始沿右子女链走到底的结点

D、从k的左子女开始沿左子女链走到底的结点

标准答案：C

知识点解析：如果k没有左子女，则k的左指针即为指向k的中序前驱的线索；当

k有左子女时，k的中序直接前驱结点是k的左子树中中序的最后一个结点，即从

k的左子女开始沿右链走到右指针不再是右子女的结点为止，该结点即为k的中序

前驱结点。说明：上述二叉树的线索化算法其实考试中涉及的不多，本节在考试

中涉及最多的是，在选择题中给你一棵二叉树，让你指出其中一个结点的线索按照

某种线索化方法所应该由向的结点。例如：请画出图4—6中按照中序线索化方法

线索化后E结点的右线索的接连情况。解决这类题的方法为，先写出题1=1所要求

的遍历方式卜•的结点访问序列，根据此序列找出题目要求中结点的前驱和后继，然

后连接线索。图4—6中二叉树的中序遍历序列为D,B,E,A,Co结点E的前

驱为B,后继为A,因比其右线索应该指向A,结果如图4-7所示。

图4.6二叉树图a右线索指向A结点总结：⑴引入二叉线索树的目的:

加快查找结点的前驱或后继的速度。(2)二叉树在线索化后，仍不能解决的问题：

后序线索二叉树中求后序后继。(3)n个结点的线索二叉树上含有的线索树为n-K

5、假定一组元素序列为{38,42,55,15,23,44,34,74,45,26},按次序插

入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为2的结点个数

为（）。

A、1

B、3

C、4

D、5

标准答案：C

知识点解析：根据题目所给的元素序列，可以得到以下的平衡二叉树，如图4-8所

示。图3平衡一又树可以看出度为2的结点有4个。

6、某二叉树的先序序列和后序序列正好相反，则该二叉树可能是（）。I.空或只

有一个结点n.任意一个结点无右孩子in.任意一个结点无左孩子

A、只可能为I

B、只可能为n

c、只可能为m

D、口、in都有可能

标准答案：D

知识点解析：考生一定需要知道做这种题目的正确思路，而不是在草稿纸上随意画

一棵二叉树去套答案，因为有些题目是不可能通过举反例来验证的。解题思路：

首先前序序列和后序序列的遍历顺序分别为TLR（根左右）和LRT（左右根），然后分

以下几种情况：（】）假设该二叉树只有一个根结点，此时前序序列和后序序列乜算

是相反，所以满足题意。但是空树比较特殊，不存在遍历的概念，无法给出解释，

记住就行，所以I错误。（2）假设任意一个结点无左孩子，则前序的遍历变成TR,

后序的遍历变成RT,恰好相反，所以该假设的二叉树成立。（3）假设任意一个结点

无右孩子，则前序的遍历变成TL,后序的遍历变成LT,恰好相反，所以该假设的

二义树成立。综上所述，II和HI都有可能。提醒：如果此题为单项选择题，假设

出现选项二叉树的高度等于结点的个数也是正确答案，因为这个答案把口和ni的情

况都包括了。

7、对图4-1进行拓扑排序，可以得到不同的拓扑序列的个数是（）。

图4」第7题图

A、4

B、3

C、2

D、1

标准答案：B

知识点解析：寻找拓扑排序的步骤：（1）在有向图中选一个没有前驱的顶点并且输

出。（2）从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均

己输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中

所给图有3个不同的拓扑排序序列，分别为：l）a,b,c,e,do2）a,b,e,

c,do3）a,e,b,c,do

8、如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，

则该图一定是（）。

A、完全图

B、连通图

C、有回路

D、一棵树

标准答案：B

知识点解析：图的一次深度优先搜索遍历，可以遍历完图中一个连通分量中所有的

顶点。如果图是连通的，则图只含有一个连通分量，即图本身，这样一次深度优先

搜索遍历即可遍历完图中所有顶点。因此本题选B,完全图相当于在连通图上加上

了更严格的条件，即任意两个顶点间都存在边，对于满足本题的要求不需要完全

图，条件达到连通图的强度就足够了。可能疑问点，：有些考生可能认为D也正

确，树难道不是连通图吗？提示：树的类型有很多，相信选D的同学必定是思维定

式，总是想着普通的无向树，这些树当然是连通图。但是，是否想过有向树?想必

提到这个概念误选D的考生就会恍然大悟了，不再多做解释。补充：用深度优先

算法遍历•个无环有向图，并在深度优先退栈返回时打印相应的顶点，则输出的顶

点序列是逆拓扑有序。

9、以下有关m阶B-树的说法中正确的有（）。I.每个结点至少有两棵非空子树

H.树中每个结点至多有m-1个关键字ID.所有叶子在同一层上W.当插入一个

数据项引起B—树结点分裂后，树长高一层

A、仅I、口

B、仅u、m

c、仅m、iv

D、仅I、口、W

标准答案：B

知识点解析：I中：m阶B—树根结点至少有两棵子树，并且这两颗子树可以是

空树，其余结点至少有［m/2］个分支，即［m/2］个子树，所以I错误。补充：B

一树中每个结点至多有m棵子树，由一1个关键字值。D中：每个结点中关键字

的个数比分支数少1,m阶B一树的一个结点中至多有m个分支，因此至多有

m—1个关键字，所以II正确。DI+：B一树是平衡的多路查找树，叶子结点均在

同一层上，所以in正确。w中：发生结点分裂的时候不一定会使树长高。比如向

图4-9中的B—树插入一个关键字10变成图4—10中的B—树，使得第二层右端

的一个结点分裂成两个，但是树并没有长高，所以w错误。综上所述，n、ni正

确。

10、在下列排序方法中，平均时间复杂度为O（nlogn）的排序算法是（）。I.快速

排序口.冒泡排序m.希尔排序W.选择排序

A仅

、I、n

B仅

、I、迎

c仅

、I、m、w

D仅

、H、IV

标准答案：B

知识点解析：这种题目其实就是考查考生的记忆能力，因为在考研紧张的氛围下，

很少有考生在做这种选择题的时候能够分析其算法来选择答案。下面与大家分享一

个记忆总结，该总结可以将内部排序所有的记忆性题目轻轻松松地拿下。由以下总

结可以很轻松地得到答案B。稳定性、时间复杂度、空间复杂度总结：（1）稳定性

总结：一句话解决：本人考研无聊中，那么就快（快速排序）些（些和希尔谐音，希尔

排序）选（选择排序）堆（堆排序）来聊!这里面都是不稳定的，其他的就自然都是稳定的

了。（2）时间复杂度总结：1）在军训的时候，教官说了一句话：快（快速排序）些（希

尔排序）以nlogn的速度归（归并排序）队（堆排序）!在这句话里面包含的排序，时间复

杂度都是O（nlogn）12）冒泡冒得好就是0（n）,冒泡冒得不好就是0（j）。3）直接插

插得好就是0（n）,插得不好就是0（n"其中插得好、冒得好分别对应最好的时间

复杂度，插得不好、冒得不好分别对应最坏时间复杂度，而平均时间复杂度对应最

坏的时间复杂度。（3）辅助空间总结：只需记住几个特殊的就好，归并0（n）、快速

O（log2n）,基数排序O（r+d）,其他的就自然全部是0（1）了。

11、某个文件经内部排序得到80个初始归并段。如果操作系统要求一个程序同时

可用的输入/输出文件的总数不超过15个，则按多路归并至少需要（）趟可以完成

排序。

A、2

B、3

C、4

D、5

标准答案：A

知识点。析：不妨设采用m路归并，则至少需耍m个输入缓冲区和1个输出缓冲

区。因为一个缓冲区对应一个文件，所以m+l=15,解得m=14,所以可做14路归

并。假设需要s趟可以完成排序,则s=I设gi480I=2。

12、考虑以卜C语言代码：shortsi=-8l96；unsignedshortusi=si；执行上述程序

段后，usi的值为()。

A、8196

B、34572

C>57339

D、57340

标准答案：D

知识点解析：此种题型已经在2012年真题中考查过。首先，求得-8196的补码表

示为1101111111111100,赋值给usi后，由于usi为无符号数，所以将二进制

1101111111111100转换为十进制为57340。技巧：FFFFH65535,

应该记住。然后减去3个0对应的权值，分别为8192、2、1,即最后的结果为65

535—8192—2-1=57340。

13、32位字长的浮点数，其中阶码8位(含1位阶符)，尾数24位(含1位数符)，机

器数采用补码表示，且尾数为规格化形式，则对应的最小正数为()。

A、2*7(1-2-23)

B、2-129

C、2“28x2-23

D、2/27x2-23

标准答案：B

知识点解析：最大数、最小数及规格化浮点数的二进制表示如表4—5所示。

«4-5最大费r・小电及JR格化浮点敷的二进制袤示

》大♦的.!8；»&尿011111110I1H11IIIIIIIIIUIIIIII22*x<l-2n>

♦小”的一遗制*系0IIIIIII]oooooooooooooooooooomo

规格化♦Kd&0IHIIIIoniiiiiiiiiiiiiuiiuii

斌格化■小M*,000000001000000000000000000000(12rxl'

螳情化域人先徵10000000lOlllltlllllllllllllltll-2r

同格化♦小贝0Olllllll100000000000000000000000/Xf

____________________________ZkW

XV1/1•

(1)最大数的二进制表示：首先要使得数最大，很明显前面2的XX次方必须是最大

的，自然就想到01111111,后面的尾数也尽量离1最近，自然想到

Olllllllllllllllllllllllo(2)最小数的二进制表示：首先要使得数最小，很明

显前面2的xx次方必须是最大的，自然就想到01111111,后面的尾数也尽量离-1

最近，因为越近和前面的指数乘起来就会越远离0c而补码又恰好可以取到-1,那

就肯定是选择-1了，自然就想到I000(X)000000000000000000。(3)规格化形式范围

其实和(1)(2)的情况类似，这里只讲一个比较难理解的，即规格化最大负数。首先

不考虑规格化的事情，要使得一个数是最大的负数，也就是离0越近越好，所以自

然想到2的指数越小越好，既然是补码，自然就想到最小的数-128,所以阶码应该

是10000000,尾数也应该离1最近，现在的离1最近就不能随便选了，因为是要

选择满足规格化的前提下离1最近的数字。而规格化要求1/2WIsIVI,所以s

应当取得-1/2才是最理想的，但是-1/2不是规格化数，所以退一步，加一个最

小的数，也就是2.23,得到所要的结论。考生看完此总结以后，应当能马上写出

任何位数以补码形式表示的规格化浮点数的范围，不是补码也没有关系，只要知道

此X码能够表示数的范围就好了，思路都是一致的。

14、硬盘平均寻道时间为12ms,传输速率为lOME/s,磁盘控制器延时为2ms,

则一个转速为7200r/min的硬盘写1KB数据的时间为（）。

A、13.11ms

B、14.13ms

C>15.15ms

D、18.27ms

标准答案：D

知识点解析：首先，需要判断1KB数据是否需要存储到多个磁道上。

7200r/min=120r/s；因为传输速率为10MB/s,故每转容量为：而W及,所以

1KB的数据只要在一个磁道上就能存储下了，无须换道。其次，写数据时间二磁盘

启动时间+磁盘寻道时间+旋转等待时间+数据传输时间。旋转等待时间为旋转半圈

的时间，即（60/7200）x1/2=4.17ms；数据传输时间等于1KB/10MB/

s=0.1ms,所以写1KB数据的时间为：2ms+12ms+4.17ms+0.1ms=18.27ms。

可能疑问点：《计算机网络高分笔记》不是说在通信领域K取1000,在计算机领

域K取1024吗?此道题目中1KB应该是属于计算机领域，为什么取值1000?提

示：《计算机网络高分笔记》给出的是最一般的理解的方式，不是绝对的。至于K

到底取多少，至今没有统一标准。笔者根据经验总结出两点：（I）如果在考试口遇

到，K取多少，就看约分，考研的答案一定是最简化的，肯定可以约分，哪个好约

分取哪个。如果分子和分母都有K那就最好了。（2）如果实在不放心，可以参考教

育部针对真题的解释，看看他们取值多少，照着取即可。

15、下面关于各种存储器的说法中，正确的有（）。I.静态RAM不是易失性存储

器，而动态RAM是易失性存储器口.PROM只能写录-•次IK.EPROM是可改写

的，并且也是随机存储器的一种W.EEPROM存储器是可与存储器

A、仅I、n

B、仅口、IV

C、仅I、口、皿

D、仅口、m、IV

标准答案：B

知识点解析：I：静态RAM和动态RAM都是易失性存储器，断电后信息都会遗

失,所以I错误。n：PROM的内部有行列式的熔丝，视需要利用电流将其烧

断，写入所需的资料，但仅能写录一次。PROM在出厂时，存储的内容全为1,用

户可以根据需要将其中的某些单元写入数据0（部分的PROM在出厂时数据全为

0,则用户可以将其中的部分单元写入1）,以实现对其“编程”的目的，所以口正

确。n：EPROM是可改写的，但它不属于随机存储器，所以HI错误。W：（电可

擦可编程只读存储器，ElectricallyErasableProgrammableRead-OnlyoMemory,

EEPROM）属于一种掉电后数据不丢失的存储芯片。EEPROM可以在计算机上或专

用设备上擦除已有信息，重新编程，所以W