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

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

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

1、用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈

时，该栈的最小容量应为（）。

A.nB.|.n/2jC.|Jog"」D.[log2nJ4-1

A、

B、

C、

D、

标准答案：D

知识点解析：根据折半杳找的过程，由于需要栈结构实现递归算法，栈的容量应该

保证能存放查找失败时所有未完成运行的算法的活动记录。第一次调用该算法

时，栈中加入了一条查找记录，表示待查有序表中元素的个数为n；第二次调用

时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找

区间中的元素最多为n/2：第三次调用时，栈中又加入了一条查找记录，所确定

的查找区间中的元素最多为n/4；依次类推，当所确定的查找区间中的元素为0

时，递归调用该算法的次数为Llogzn」+1次，查找结束。

2、排序趟数与序列的原始状态无关的排序方法是（）。I.直接插入排序D.简单

选择排序m.冒泡排序W.基数排序

A、仅I、m

B、仅I、n、w

c、仅I、口、m

D、仅I、w

标准答案：B

知识点解析：直接插入排序：每趟排序都是插入一个元素，所以排序趟数固定为n

一l（n为元素数）。简单选择排序：每趟排序都是选出一个最小（或最大）的元素，

所以排序趟数固定为n—l（n为元素数）。交换类的排序：其趟数和原始序列状态有

关，所以冒泡排序与初始序列有关。基数排序：每趟排序都要进行“分配”和“收

集”，排序趟数固定为d（d为组成元素的关键字位数）。综上所述，I、口、W都是

无关的，所以选B。

3、堆栈寻址方式中，设A为某通用寄存器，SP为堆栈指示器，Map为SP指示器

的堆栈顶单元，如果进戌操作的动作是（A）-Map,（SP）-I-SP,那么出栈操作为

（）。

A、（SP）+1->SP,M叩一（A）

B、Map—(A),(SP)+1—SP

C、(SP)-l-SP,Map->(A)

D、Map—(A),(SP)NTSP

标准答案：A

知识点解析：进栈是先存数再SP减一，故出栈是先SP加一再取数。故选A。

4、下面()不是数据报服务的特点。

A、尽最大努力将分组交付给目的主机

B、不保证按源主机发送分组的先后顺序交付给目E勺主机

C、是一种没有质量保证的服务

D、是一种面向连接的服务

标准答案：D

知识点解析：数据报服务提供的是一种尽最大努力的、不保证按源主机发送分组的

先后顺序交付的、不可靠的服务，非面向连接的服务。故D选项错误。

5、已知小写英文字母“a”的ASCH码值为61H,现字母“g”被存放在某个存储单元

中，若采用偶校验(假设最高位作为校验位)，则该存储单元中存放的十六进制数是

()o

A、66H

B、E6H

C、67H

D、E7H

标准答案：D

知识点解析：因为“a”的ASCII码值为61H,而“g”是第7号字母，所以“g”的ASCII

码值应为67H=110011IB。标准的ASCII码为7位，在7位数前面增加1位校验

位。现“g”的ASCII码中1的个数有5个，按照偶校验规则，存储单元中存放的是

整个校验码(包括校验位和信息位)，为11100111B=E7H。［归纳总结］此题涉及两

个知谡点.第一是ASCII编码表顺序排列问题,第二是奇偶检验码的编码规如问

题。由若干位有效信息(如一个字节)，再加上一个二进制位(校验位)组成校验码，

偶校验就是整个校验码中“1”的个数为偶数个。［解题技巧］在ASCII码中，数字和

英文字母都是按顺序排列的，只要知道其中一个数字或英文字母的二进制代码，不

要查表就可以推导出其他数字或字母的二进制代码。此题容易误选C,这是因为

“g”的ASCII码中确实为67H,但整个校验码中1的个数必须是偶数个，所以正确

选项为D。

6、堆排序分为两个阶段，其中第一阶段将给定的序列建成一个堆，第二阶段逐次

输出堆顶元素。设给定序列{48,62,35,77,55,14,篁,98},若在堆排序的第一阶段将该

序列建成一个堆(大根堆)，那么交换元素的次数为()。

A、5

B、6

C、7

D、8

标准答案：B

知识点解析：考查初始谁的构造过程。首先对以第5/2」个结点为根的子树筛

选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，直到筛选到根

结点。序列｛48,62,35,77,55,14,35,98）建立初始堆的过程如卜.所示：

苜先准备第选77

如图所示，（a）调整结点77,交换1次；（b）调整结点35,不交换：（c）调整结点

62,交换2次；（d）调整结点48,交换3次。所以上述序列建初始堆，共交换元素

6次。

7、假脱机技术（SPOOLing）中，被利用来做虚拟设备的是（）。

A、打印机

B、磁带

C、内存

D、磁盘

标准答案：D

知识点解析：SPOOLing技术，即同时联机外围操作技术，又称假脱机技术，是指

在多道程序环境下，利用多道程序中的一道或两道程序来模拟脱机输入输出中的外

围控制机的功能，以达到“脱机”输入输出的目的，即在联机的条件下，将数据从输

入设备传送到磁盘，或从磁盘传送到输出设备。通过它可以将一台独占的物理设备

虚拟为多台逻辑设备，从而使该物理设备可被多个进程共享。因此，假脱机技术用

求作为虚拟设备的主要载体是磁盘，对应于输入输出，分别称之为输入井和输山

井。

8、在大量数据的传送过程中，常用且有效的检验法是（）。

A、海明码校验

B、偶校验

C、奇校验

D、CRC

标准答案：D

知识点解析：CRC适合对大量数据进行校验。

9、假设系统为某进程分配了3个物理块，考虑页面走向为：7,0,1,2,0,3,

0,4。试问采用CLOCK页面淘汰算法时缺页中断的次数为（）。

A、8

B>7

C、6

D、5

标准答案：C

知识点解析：CLOCK页面淘汰算法的缺页情况（见表3—7）。

表3-7CLOCK页面海冰算法的跳页情况

访问页物理块0物理块1物理块2说明

-*AAA

初始状蠢P指向块

000

7一八A

访问页7调入页7,块0访问位置1,p指针后移

100

70-A

访问页0现入页0.块1访问位置1,pm针后移

110

-*701

访问页1调入仅1.块2访问位置1,p指针后移

111

2-01p指针循环垢移（移动前修改访问位），找到块0

访问页2

的访问位为"怏进页后移

1000.2,pftiW

2一01

访问页。访问页0存在,修改其访问位.P指针不移动

1i0

-203P指针拙环后移（移动扃修改访问位），找刎块2

访问页3

的访问位为替换进页指针后移

1010.3.P

-203

访faj贡0访问页0存在，修改其访问位，p指针不移动

111

4-03P指针粘环痔（梅动解修改访向位），找到块0

访问更4

的访问位为替换这页指针后移、'

1000.4.P

知识点回顾：CLOCK算法是LRU算法的近似算法。CLOCK算法流程图如图3—

14所示。CLOCK算法给每个页面设置一个访问位，标识该页最近有没有被访问

过，再将内存中的所有页面通过一个指针链接成一个循环队列。

（人口）

图3/4CLOCK算法流程图

注意：若循环链表存在当前访问

页时（访问页在某物理决中），直接将其访问位改为】，指针p不移动（命中后指

针不移动）；否则，若当前p指针指向页面的访问位为0,则淘汰该页，调入新

页，将其访问位改为1.指针p移到下一个物理块：若当前p指针指向页面的访问

位为1,则将其访问位改为0,并移动P指针到下一个物理块。

10、在滑动窗口机制中，已知帧的序号为3bit时，若采用后退N帧协议传送数

据，则发送窗口的最大尺寸为（）；若采用选择重传协议，并且发送窗口与接收窗口

的尺寸相同时，发送窗口的最大尺寸为（）。

A、8：6

B、8：4

C、7；4

D、7：6

标准答案：C

知识点解析：只有在发送窗口的大小Wt<2m-I时（帧序号位数m）即发送窗口最大尺

寸为7时，后退N帧协议才能正确运行；对于选择重传协议，若用m比特进行编

号，则接收窗口的大小WRqmJ,即接收窗口最大尺寸为4。其理由是防止上一轮

的帧号与下一轮的相同项号同时出现而造成接收方误判。

11、在TCP报文段的报头中，窗口字段的作用是

A、报头中32bit字节的数量

B、说明对方端口的数量

C、控制对方的发送流量

D、说明网络的负荷能力

标准答案：C

知识点解析：本题考查TCP报文段的作用窗口大小：用于流量控制。表示在确认

了的字节之后还可以发送多少字节。窗口大小也允许为0,表示它已经收到了包括

确认号减1在内的所有数据段，但接收方急需暂停接受数据。对于窗口字段，占2

个字节，用来控制对方发送的数据量，并不能说明网络的负荷能力，因此答案是

Co

12、顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索

引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在

等概率的情况下，分块查找成功的平均查找长度为()。

A、21

B、23

C、41

D、62

标准答案：B

知识点解析：分块查找成功的平均查找长度为ASL=(s2+s+n)/2s。在本题中，

n=123,s=123/3=41,故平均查找长度为23。

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

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

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

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

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

标准答案：A

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

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

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

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

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

O(n),因此D不对。

14、一个快速SCSI-n总线上的磁盘转速为7200RPM,每磁道160个扇区，每扇

区512字节，那么在理想状态下，其数据传输率为

A、7200*160KB/s

B、7200KB/s

C、9600KB/s

D、19200KB/s

标准答案：C

知识点解析：7200/60*160*0.5=9600,所以选C。

15、在含有12个结点的平衡二义树上，查找关键字为35(存在该结点)的结点，则

依次比较的关键字有可能是()。

A、46,36,18,20,28,35

B、47,37,18,27,36

C、27,48,39,43,37

D、15,45,55,35

标准答案：D

知识点解析：设Nn表示深度为h的平衡二叉树中含有的最少结点数，有：

No=ONi=lNh=Nh-i+Nh-2+l当结点数为12时，Nh=12,h=5,即12个结点的平衡二

叉树而最小叶子结点的层数为3,最大叶子结点的层数为5,由于存在关键字为35

的结点，即最多比较5次一定能找到该结点。故排除A、B、C,选D。

16、对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划

分。在第1趟划分过程中，元素移动次数最多的是。。

A、70,75,82,90,23,16,10,68

B、70,75,68,23,10,16,90,82

C、82,75,70,16,10,90,68,23

D、23,10,16,70,82,75,68,90

标准答案：A

知识点解析：快速排序第一趟划分的方法是：将第1个元素放在最终排好序列的最

终位置上，则在这个位置右边小于该元素值的元素都移到其左边，则在这个位置左

边小于该元素值的元素都移到其右边。故先A。

17二若一个栈的输入序列为1,2,3…n,输出序列的第一个元素是i,则第j个输

出元素是（）。

A、i—j一1

B、i-j

C、j—i+1

D、不确定

标准答案：D

知识点解析：一串数据依次通过一个栈，并不能保证出栈数据的次序总是倒置.，可

以产生多种出栈序列v一串数据通过一个栈后的次序由每个数据之间的进栈、出栈

操作序列决定，只有当所有数据“全部进栈后再全部出栈''才能使数据倒置。事实

上，存在一种操作序列——“进栈、出栈、进栈、出栈……”——可以使数据通过栈

后仍然保持次序不变。题目中输出序列的第一个元素是i,则第j个输出元素是不

确定的。

18、对n个关键字进行快速排序，最大递归深度为［）,最小递归深度为（）。

A、1,n

B、n,log2n

C、logon,n

D、nlog2n,n

标准答案：B

知识点解析：快速排序过程构成一个递归树，递归深度即为递归树的高度。当枢轴

值每次都将子表等分时，此时递归树的高为k）g2n。当枢轴值每次都是子表的最大

值或最小值时，此时递归树退化为单链表，树高为n。

19、.如果x为负数，则己知［x］补与［一x］补的方法是（）。

A、［X］补各值保持不变

B、［x］补符号位变反，其他各位不变

C、［X］补除符号位外，各位变反，末位加1

D、［x］补连同符号位一起各位变反，末位加1

标准答案：D

知识点解析：［-X］补被称为［X］补的机器负数，由［X］补求［-X］补的过程称为对［X］补变补

（求补），这是做减法运算时必须要完成的操作。不管x的真值为正或为负，己知

［X］补求［-X］补的方法是：将［X］补连同符号位一起求反，末尾加“1"。［X］补表示的真值

如果是正数，则变补后卜X］补所表示的真值变为负数；反过来，［X］补表示的真值如

果是负数，则变补后［-X］补所表示的真值变为正数。此题容易错选选项C。如果除

符号位外，各位变反，末位加1,得到的是［X］原而不是［-X］*卜，且只有X为负数时

成立。

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

高度是（）。

A、3

B、4

C、5

D、6

标准答案：C

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

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

上取整，结果为5。

21、在操作系统中引入并发可以提高系统效率。若有三个进程Pl、P2和P3,按照

Pl、P2到P3的优先次序运行，采用可抢先式调度，其运行过程如下：P1：计算

6ms；I/O8ms；计算2ms；P2：计算12ms；I/06ms；计算2ms；P3：计算

4ms；I/08ms；计算4ms；不计系统开销，相比单通道顺序运行，多道并发可以

节省的时间和CPU利用率分别是（）。

A、14ms；79%

B、16ms；83%

C、12ms；75%

D、22ms；100%

标准答案：A

知识点解析：本题考查多道程序运行的工作方式，解决此类问题的关键一般根据进

程的优先级和时序关系，画出时序图，注意1/0设备不能抢夺，CPU可以根据优

先级来抢夺。［解题技巧］根据题意，进程运行时序图是这样的:

6皿8m»2ww4m2au4n*AIF

ITUKP3nP3英

P2p32i

1/(>Pl单道运行是需要耗时:6+8

+2+12+6+2+4+8+4=52(ms)从表中分析，并发运行时需要耗时6+8+2+4

+4+2+2+6+4=38(IllS)节省时间为52—38=14(ms),CPU效率为(6+8+2+4

+4+2+4):38=79%

22、设有下面4条路由：172.18.129.0/24、172.18.130.0/24、

172.18.132.0/24和172.18.133.0/24,如果进行路由聚合,能覆盖这4

条路由的地址是（）。

A、172.18.128.0/21

B、172.18.128.0/22

C、172.18.130.0/22

D、172.18.132.0/23

标准答案：A

知识点解析：前两个字节和最后一个字节不做比较了，只比较第三个字节即可。

129-*10000001130—10000010132—10000100133110000101显然,这4个数字只

有前5位是完全相同的，因此汇聚后的网络的第3个字节应该是10000000—128。

汇聚后的网络的掩码中1的数量应该有8+8+5=21,因此答案是

172.18.128.0/21。

23、在下列叙述中，正确的是（）。

A、在磁带上的顺序文件中插入新纪录时，必须复制整个文件

B、由于磁带的价格比磁盘便宜，用磁带实现索引文件更经济

C,在磁带上的顺序文件末尾插入新纪录时，不必复制整个文件

D、由于磁带不利于随机存储，故用磁带来作为备份的介质是不合适的

标准答案：A

知识点解析：磁带是顺序访问的存储设备，所以复制文件时必须复制整个文件。由

于磁带上文件是顺序文件，所以无法实现索引文件，不管其有多便宜。备份文件时

不需要作随机访问，所以用磁带来备份文件是合理的，也是经济的。

24、与本指令的地址有关的寻址方式是（）。

A、寄存器寻址

B、直接寻址

C、相对寻址

D、间接寻址

标准答案：C

知识点解析：相对寻址本身就是相对于本指令的地址进行上下浮动，所以相对寻址

的区间范围和本指令的地址密切相关，其他3个选项都与本指令的地址无关。

25、某容量为256MB的存储器由若干16Mx8bitDRAM芯片构成，该DRAM芯片

的地址引脚和数据引脚总数是（）。

A、20

B、24

C、32

D、36

标准答案：A

知识点解析：很多不了解DRAM引脚结构的同学很可能会得出24+8=32的结果，

其实这是不正确的，在《高分笔记》当中讲过半导体存储芯片的译码驱动方式，其

中介绍了重合法，将存储单元分成行和列，然后分别通过行地址线和列地址线来确

定行列地址从而确定一个单元，这里DRAM采用引脚复用，将行地址线和列地址

线合用作一组，只不过在译码时，需要发送两次地址信号（相当于一次行地址，

次列地址），从而减少了DRAM的引脚总数，便于设计DRAM；因此这里地址空

间是16M,需要24个地址位来标识，分为两次发送，则地址引脚数为12,故地址

引脚和数据引脚总数为12+8=20。【总结】DRAM芯片采用引脚复用，且行列地

址位数一致。

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

是（）。

A、4

B、5

C、6

D、7

标准答案：C

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

27、一组数据（30,20,10,15,35』,10,5）,用堆排序（小顶堆）的筛选方法建立的初始堆

为（）。

A、1,5,15,20,35,10,30,10

B、1,10,30,10,5,15,35,20

C、1,5,10,15,35,30,10,20

D、A、B和C均不正确

标准答案：c

知识点解析：考查初始谁的建立。首先对以第Fn/2J个结点为根的子树（也即最

后一个结点的父结点为艰的子树）筛选，使该子树成为堆，之后向前依次对各结点

为根的子树进行筛选，直到筛选到根结点。从Pn/2J〜1依次筛选堆的过程如下

图所示:

箫选结点20

28、下列方式中，不是死锁预防策略的是（）。

A、一次分配所有资源

B、银行家算法

C、建立SPOOLing系统

D、按序分配资源

标准答案：B

知识点解析：死锁发生的四个必要条件是互斥、部分分配、非剥夺和循环等待。死

锁预防就是打破死锁的这四个条件，建立SPOOLing系统可以部分解决互斥条件，

•次分配所有资源是打破部分分配条件，按序分配资源是打破循环等待条件，而银

行家算法是死锁避免的算法，不是死锁预防的算法。

29、一个使用CSMA/CA的网络上，计算机A的帧际间隔是2时槽，计算机B的

帧际间隔是6时槽，如果计算机C使用（）帧际间隔可以获得最高优先级。

A、8时槽

B、5时槽

C、3时槽

D、1时槽

标准答案：D

知识点解析：在CSMA/CA中，帧际间隔值可以用来分配发送方的优先级，如果

一个设备被分配一个较小的帧际优先级，那么它就会有更多的机会得到对传输介质

访问的机会。

30、IEEE802.11采用了CSMA/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（MultipleAccesswithCollisionAvoidanceforWireless,带冲突避免的

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

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

31、既考虑作业等待时间又考虑作业执行时间的调度算法是（）。

A、响应比高者优先

B、短作业优先

C、优先级调度

D、先来先服务

标准答案：A

知识点解析：响应比=（等待时间+执行时间）/执行时间。

32、已知关键序列5,8,12,19,28,20,15,22是小根堆（最小堆），插入关键

字3,调整后得到的小根堆是（）。

A、3,5,12,8,28,20,15,22,19

B、3,5,12,19,20,15,22,8,28

C、3,8,12,5,20,15,22,28,19

D、3,12,5,8,28,20,15,22,19

标准答案：A

知识点解析：暂无解析

33、在PC—DOS中，某磁盘文件A与B,它们所占用的磁盘空间如下所示。试问

FDT（文件目录表）FAT（文件配置表）

帐号FAT值

000FFD

001FFF

002004

003008

004009

005007

006FFF

007FFF

008006

009005

♦♦♦•••

A、3,3

B、4,5

C、5,3

D、5,4

标准答案：c

知识之解析：当查找文件在磁盘上的存放地址时，首先从目录中找到文件的起始簇

号，然后再到FAT表的相应表目中找到文件存放的下一个簇号，依此类推，直至

遇到值为FFF的表项为止。文件A在磁盘上占用5簇，簇号依次为002、004、

009、005、007o文件B在磁盘上占用3簇，簇号依此为003、008、006。知识点

回顾：链接分配中每个文件对应一个盘块的链表，盘块分布在磁盘的任何地方。

链接方式可分为隐式链谖和显示链接两种。隐式链接：在文件目录的每个目录项

中，都必须含有指向链透文件第一个盘块和最后一个盘块的指针。例如，目录表中

有一个目录项为（jeep,9,25）,表示jeep文件的第一个盘块号是9,最后一个盘块

号是25,而在每个盘块中都含有一个指向下一个盘块的指针，如

9—16—一10—25。如果指针占用4B,对于盘块大小为512B的磁盘，则每个盘

块中只有508B可供用户使用。显示链接：把用于链接文件各物理块的指针，显示

地存放在内存的一张链装表中。该表在整个磁盘仅设置一张。表的序号是物理盘块

号，从0开始，直到N—1,其中N为盘块总数。在每个表项中存放链接指针，即

下一个盘块号。

34、CPU中决定指令执行顺序的是（）。

A、指令寄存器IR

B、程序计数器PC

C、程序状态字寄存器PSWR

D、主存地址寄存器MAR

案：B

标准答

即通

地址，

指令的

执行的

条将要

踪下一

C来跟

数器P

程序计

中用

CPU

解析：

知识点

顺序。

令执行

决定指

PC来

数器

序计

过程

表项

的页

页表

许不同

，允

微改造

表做细

略的页

管理策

式存储

的分页

对经典

如果

35、

需要

口.只

共享

码的

入代

可重

现对

.实

)。I

果有(

的结

可能

页帧，

一物理

指向同

通

程间

现进