2019年全国硕士研究生入学统一考试计算机学科专业基础综合模拟试题1

1、2019年全国硕士研究生入学统一考试计算机学科专业基础综合模拟试题1（总分：150.00，做题时间：150分钟）一、单项选择题（总题数：40，分数：80.00）1. 在下列各项叙述中，正确的说法是（）。A. 在线性表中，每个元素有且仅有一个直接前趋，有且仅有一个直接后继B. 线性表中至少有一个元素C. 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继VD. 线性表中元素必须从大到小或从小到大排列线性表一般被定义为由若干个元素组成的有序序列，中可以没有元素，称为空表。注意，线性表是位置有序而不是数据有序。线性表2. 设有一个10阶的对称矩阵A，采用

2、压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1,每个元素占一个地址空间，则a85（即该元素下标i=85）的地址为（）。A.13B.33VC.18D.40矩阵A的前7行中，第i行有i个元素被存储，所以前7行共7X（7+1）/2=28个元素。a85是第8行中第5个被存储的元素，所以a85是第28+5=33个元素。3.若用一维数组表示一个深度为5、结点个数为10的二叉树，数组的长度至少为（）。A.10B.16C.317D.64由于二叉树的顺序存储是按完全二叉树来存储的，根据二叉树的性质：深度为k的二叉树最多有2k-1个结点，深度为5的二叉树最多有31个结点。4. 假设一棵二叉树的后

3、序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为（）。A.ABCDEFGHIJB.ABDEGHJCFIVC.ABDEGHJFICD.ABDEGJHCFI再根据中序遍历的特根据中序、后序遍历的特点，可以确定A是根结点（在后序遍历的最后一个），点，可以知道DBGEHJ为左子树，CIF为右子树。再看右子树的后序遍历为IFC,可以确定C为右子树的根结点；再加上中序为CIF,说明C无左子树，只有右子树。而左子树的后序遍历为DGJHEB，因此B为左子树的根结点，再结合中序遍历，可以得知B的左子树只有D，GEHJ都是右子树。GEHJ子树的后序遍历是GJHE说明E是根，

4、HJ为E的右子树，G是E的左子树。最后可以得出，H为HJ子树的根，J为右子树。然后再由前序遍历，可以得到：ABDEGHJCF。I5. 对于一棵二叉排序树，为了得到所有结点的有序序列，应该对二叉排序树进行（）。A.前序遍历B.中序遍历VC. 后序遍历D. 层次遍历在二叉排序树中，左子树的结点值全部小于根结点，右子树的结点值全部大于根结点，如果按照左子树、根结点、右子树的顺序遍历（即中序遍历）二叉排序树，得到的就是一个有序序列。6. 从图中结点V出发，按广度优先遍历算法查找结点U时，最先经过（得到）的是从V到U的边数（）的路径。A. 最多B. 最少VC. 既不是最多，也不是最少D. 既可能最多，也

5、可能最少本题需注意广度优先遍历与深度优先遍历的区别。7. 从一个具有n个结点的单链表中查找其值等于X的结点时，在查找成功的情况下，需平均比较的元素结点个数是（）。A.2*nB.nC. （n+1）/2VD. （n-1）2无论是顺序结构还是链式存储结构，顺序查找的效率都是一样的。8. 一棵m阶非空B+树，每个结点最多的关键字数为（）。A.m2B.m-1C.mVD.m+19. 设有10000个无序记录，希望用最快速度从中选择前10个关键字最小的记录，在以下排序方法中采用（）最好。A.直接插入排序B.简单选择排序VC. 快速排序D. 希尔排序在题中所列出的排序方法中，直接插入排序、快速排序、希尔排序都

6、是排序完成后，才能选出前10个关键字最小的记录。只有简单选择排序能直接选出前10个关键字最小的记录。10. 下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的算法是（）。A. 快速排序B.shell（希尔）排序VC. 堆排序D. 冒泡排序因为shell排序每趟是对多个分组进行排序，不可能保证一个元素放到其最终的位置上。11. 关于计算机字长，下面说法错误的是（）。A.表示该计算机能够存储的最大二进制数位数VB. 表示该计算机的CPU可以同时处理的二进制位数C. 机器字长一般与CPU中寄存器的位数有关D. 机器字长决定了数的表示范围和表示精度计算机字长是指CPU一次能处理的数据

7、长度，它通常与CPU中的寄存器的位数相等，决定了机器所能表示数据的范围和精度。计算机通过多次操作，可以存储长度远大于字长的二进制数据，也有些寄存器的位数会大于字长，如x86中的段基址寄存器。12. X是整数，X扑=（011100011）2,X的十进制真值是（）。A.456B.454C.227VD.228最高位的符号位是0，所以X的真值为正，正数的补码与真值相同，所以X的十进制真值为1x27+1x25+1x21+1x20=227.13. 已知凶价=01100011.则-X扑等于（）。A.00011100B.10011100C.10011101VD.以上都不是X为正整数,则原码、补码、反码相同。X

8、原=01100011,卜X原=11100011原=1001110010011101补14.若由高速缓存、主存、硬盘构成三级存储体系，则CPLB问该存储体系时发送的地址为（A.高速缓存地址B.虚拟地址VC.主存物理地址D.磁盘地址CPU运行时得到的是虚拟地址，由操作系统转变成物理地址。15 .下列寻址方式中，一旦指令从内存读出后，能够较快地获取操作数据的寻址方式是（）A.寄存器寻址VB.直接寻址C.间接寻址D.变址寻址由于操作数不在主存而在CPU寄存器中，寄存器寻址在指令执行阶段无须访存，可较快获取操作数。16 .设机器字长为32位，一个容量为16MB的存储器，CPU按半字寻址，其寻址范围是（A

9、.16MB.8MVC.4MD.2M他普8位二进制表示一个字节，机器字长为32位，按半字寻址则每次寻址为16位，寻址范围是I1x8=8Mo17 .算术/逻辑运算单元74181ALU芯片可完成（）。A.16种逻辑运算功能B.16种算术运算功能C.4位乘法运算和除法运算功能D.16种算术运算功能和16种逻辑运算功能V74181ALU有两种工作方式。对正逻辑操作数来说，算术运算称高电平操作，逻辑运算称正逻辑操作（即高电平为“1”，低电平为“0”）。对于负逻辑操作数来说，正好相反。由于S-S有16种状态组合，因此对正逻辑输入与输出而言，有16种算术运算功能和16种逻辑运算功能。同样，对于负逻辑输入与输出

10、而言，也有16种算术运算功能和16种逻辑运算功能。18.计算机的存储系统采用分级方式是为了（）A.减少主机箱的体积B.操作方便C.保存大量数据方便D.解决容量、价格和速度三者的矛盾V计算机的存储系统采用分级方式是尽量以外存的价格得到容量与外存相当，速度与内存相近的存储系统，解决了容量、价格和速度三者的矛盾，本题选D项。另外，用排除法可以首先排除A、B两项。分级方式并不能方便保存大量数据，C项也不正确。19. 为协调计算机系统各部件工作，需有（）提供统一的时钟标准。A. 总线缓冲器B. 总线控制器C.时钟发生器VD. 操作命令产生器A项总线缓冲器是起缓冲作用的，是时钟信号的受动者。B项总线控制器

11、，主要判决总线的使用情况，也是在时钟信号的控制下工作。D项操作命令产生器，是对指令解码后，产生具体控制信号的部件，它也是时钟信号的受动者。计算机系统的时钟信号的源头是时钟发生器。20. 在机器数中，零的表示形式唯一的是（）。A. 原码B.补码VC. 反码D. 原码和反码计算机中零也有正负之分，原码中零有两种表示形式：10000000或00000000，反码也有两种表示形式：11111111或01111111。补码中正零和负零的表示形式相同都为：00000000。21. 采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是（）。A.224B.216C.28D.2

12、3224位地址，前8位为段号，剩余16位为段内地址。22. 在文件系统中，文件的不同物理结构有不同的优缺点。在下列文件的物理结构中，（）具有直接读写文件任意一个记录的能力，提高了文件存储空间的利用率。A. 顺序结构B. 链接结构C.Hash结构D.索引结构V索引是一个单独的、物理的数据库结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。它可以直接读写任意一个记录。23. 设计操作系统的时候需要关心许多方面的问题，其中不需要关心的是（）。A. 计算机的逻辑特性B. 操作系统今后的应用目标C. 计算机所具有的资源D.高级程序没计语言的编译器V设计操作系统需

13、要得到计算机硬件设施，即裸机特性，然后编写相应的功能。同时，还需要根据客户需求，设计实现的功能。计算机拥有什么资源，才能用软件编写相应操作的程序。操作系统可以用多种语言实现，因此不需要考虑编写的语言是什么。24. 实时操作系统必须在（）内处理完来自外部的事件。A. 响应时间B. 周转时间C.规定时间VD. 调度时间实时操作系统能使计算机系统接收到外部信号后及时进行处理，并在严格的规定时间内完成处理，且给出反馈信号。它是较少有人为干预的监督和控制系统。实时系统对可靠性和安全性要求极高，不强求系统资源的利用率。实时系统为每个作业都规定了运行时间和截止时间。25. 若有一个进程拥有100个线程，这些

14、线程属于用户级线程，则在系统调度执行时间上占用（）个时间片。A.1VB.100C.1/100D.0以进程为单位分配资源，每个进程分得一个时间片，进程内的多个线程共享时间片。每个线程得到的时间片为1100，所以一个进程只有一个时间片。26. 在操作系统中，要对并发进程进行同步的原因是（）。A. 进程必须在有限的时间内完成B. 进程具有动态性C.并发进程是异步的VD.进程具有结构性若系统中存在一组可同时执行的进程,进程”。同时执行并不是真的同时,所以要对并发进程进行同步。则说明该组进程具有并发性，并把可同时执行的进程称为“并发因为任一时刻CPU中只能有一个进程运行，即并发进程是异步的,27 .以下

15、不可能引起进程调度的是（）A. 一个进程完成工作后被撤消B. 一个进程从就绪状态变成了运行状态VC. 一个进程从等待状态变成了就绪状态D. 一个进程从运行状态变成了等待状态或就绪状态可能引起进程调度的情况有：一个进程从运行状态变成了等待状态，一个进程从运行状态变成了就绪状态，一个进程从等待状态变成了就绪状态或者一个进程完成工作后被撤销。而“一个进程从就绪状态变成了运行状态”是一次进程调度完成时的情况，因此，选项B不可能引起进程调度。28 .主存的管理方案不同时，对主存储器的访问（）。A.对于段式或页式管理，以块（即页）或段为单位B.以字节或字为单位VC.随存储器的管理方案不同而异D.以用户定义

16、的逻辑记录为单位对主存的访问不管采用什么管理方案，最终都要转换成访问主存的字或字节地址。29 .某页式存储管理系统中，地址寄存器长度为24位，其中页号占14位，则主存的分块大小是（）字节。A.210B.10C.214D.24在分页存储管理系统中，其地址结构如下:页号P位移量W其中，页号P占了14位，地址总长度为24位，那么位移量W的长度就应如下计算:位移量W的长度=地址总长度-页号P长度=24-14=10位所以，每个主存分块的大小是210个字节。30 .使Cache命中率最高的替换算法是（）。A. 先进先出算法FIFOB. 随机算法RANDC. 先进后出算法FILOD.替换最近最少使用的块算法

17、LRUV先进先出算法、先进后出算法和随机算法的命中率可以说都具有很大的随机性，不符合程序运行的特点，命中率比较低。最近最少使用替换算法，用最近的使用情况预测未来的使用情况在一定程度上考虑了程序的局部性原理，命中率相对较高。31 .有3个作业A（到达时间8:50,执行时间1.5小时）、B（到达时间9:00,执行时间0.4小时）、C（到达时间9:30,执行时间1小时）。当作业全部到达后，单道批处理系统按照响应比高者优先算法进行调度，则作业被选中执行的次序是（）。A. （A，B，C）B. （B,A,C）7C. （C，A，B）D. （A，C，B）响应比=作业周转时间/作业运行时间=1+作业等待时间/作

18、业运行时间。9:30作业全部到达，计算作业的响应比：以A为例，它的作业计算时间是1.5小时，即90分钟；A从8:50到达输入，在9:30时刻，A的等待时间为40分钟，因此作业A的响应比为：1+40分钟/90分钟=1.44。同理，B:1+30分钟/24分钟=2.25;C:1+0分钟/60分钟=1。因此按照响应比高者优先算法，优先调度B。在9:54，B完成，这时计算A，C的响应比:A:1+（40+24）分钟/90分钟=1.71；C：1+24分钟/60分钟=1.4。按照响应比高者优先算法，优先调度A。在11:24，A完成，系统调度C，C的响应比为1+（24+90）分钟/60分钟=2.9。因此，作业被

19、选中执行的次序是B,A,Co32. 设磁盘的转速为3000rmin，盘面划分成10个扇区，则读取一个扇区的时间为（）。A.20msB.5msC.2ms7D.1ms因为磁盘1min的转数为3000,故1s的转数为3000/60=50;每一转需要的时间为1000ms/50=20m4每一转通过10个扇区，故通过一个扇区需花费时间为20ms/10=2ms33. 在共享介质的以太网中，采用的介质访问控制方法是（）。A.并发连接B.CSM/A/CDVC.时间片D.令牌CSMA/CD共享介质的以太网中最经典、最常使用的方法。34. 如果互联的局域网高层分别采用TCPIP协议与SPXIPX协议，那么我们可以选

20、择的多个网络互联设备应该是（）。A. 中继器B. 网桥C. 网卡D.路由器V一般说来，异种网络互联与多个子网互联都应采用路由器来完成。两个分别采用TCPIP协议与SPX35.使用中继器连接器个数最多是（IPX协议的局域网，属于异种网络，所以必须用路由器。另三种设备都不能连接异构网络。LAN的电缆段是有限制的，任何两个数据终端设备间允许的传输通路中可使用的中继）。A.1B.3C.4D.5个个个V个中继器连接必须遵守网段可以连接站点。5-4-3规则（4中继器限制），即用4个中继器连接5个网段，其中只有3个36. 采用有序接收的滑动窗口协议，设序号位数为n，则发送窗口最大尺寸为（）。A.-1B.+1

21、C.D.2n用有序接收的滑动窗口协议时，为了保证接收端能正确有效地区别接收到的报文的序号，窗口大小和接收窗口大小之和不大于整个序列号空间2n-1。2n，而接收窗口最小为1，必须保证发送所以发送窗口最大为37. 以太网中，在第5次碰撞之后，一个结点选择的K值为4的概率是（）。A.18B.116C.1/32VD.164在第5次碰撞后，从整数集合0,1,，（25-1）中随机选取K值，因此，选择的K值为4的概率是132。38. 对于由交换机连接起来的10Mbits的共享式以太网，若共有10个用户，则每个用户能够占有的带宽为（）。A.1MbitsB.2MbitsC.10Mbit/sVD.100Mbits

22、对于普通10Mbits的共享式以太网，若共有N（10Mbits）的N分之一。但使用以太网交换机时，由于一个用户在通信时是独占而不是和其他网络用户共享传输媒体的带宽，因此，每个用户仍然可以得到10Mbits的带宽，这正是交换机的最大优点。39. 假设某模拟信道的带宽是3KHz，其理想信道的波特率是，如果该信道的信噪比是30dB，则该信道的带宽为。（）A.3KBaud，20KbsB.6KBaud,30Kb/sVC.12KBaud，30KbsD.24KBaud，20Kbs根据奈奎斯特定律，理想信道的波特率是带宽的2倍，即6KBaud。而对于有噪声的信道而言，要计算其数据速率应使用香农理论：速率=带宽

23、xlog2（S/N+1）=3KXlog2（1000+1）3000X9.9730Kb/So40. 为了提供更多的子网，为一个B类地址指定了子网掩码255.255.240.0，则每个子网可以有的主机数是（）。A.16B.256C.4094VD.4096将255.255.240.0用二进制表示是11111111.11111111.11110000.00000000，因此有12位可用于主机地址，又因为全0和全1地址不能使用，所以每个子网可以有的主机数是212-2=4094。二、综合应用题（总题数：7，分数：70.00）41. 如图2所示，顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一

24、个村庄能使各村庄总体交通代价最小？图2村庄的有向带权图正确答案：（该图的邻接矩阵如下:利用Floyd算法可求得两顶点之间最短路径长度。最后求得:从A4中可求得每对村庄之间的最少交通代价。价如下所示：假设医院建在i村庄时，其他各村庄往返总的交通代医院建在村庄0时,各村庄往返总的交通代价为12+16+4+7+13+16+4+18=90;医院建在村庄1时,各村庄往返总的交通代价为13+29+17+20+12+11+8+5=115;医院建在村庄2时,各村庄往返总的交通代价为16+11+12+6+16+29+12+34=136;医院建在村庄3时,各村庄往返总的交通代价为4+8+12+3+4+17+12+

25、22=82;医院建在村庄4时，各村庄往返总的交通代价为18+5+34+22+7+20+6+3=115显然，把医院建在村庄3时总体交通代价最少。)42. 试利用循环队列编写求k阶斐波那契序列中前n+1项(fo,fi,fn)的算法，要求满足fnWmax且fn+1>max,其中max为某个约定的常数。循环队列的容量为k，因此，在算法执行结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项fn-k+i，fn。正确答案：(voidGetFib(intk,intn)InitQueue(Q);for(i=0;i<k-1;i+)Q.basei=0;Q.basek-1=1;for(i=0

26、;i<k;i+)printf(“%d”,Q.basei);for(i=k;i<=n;i+)m=i%k;sum=0;for(j=0;j<k;j+)sum+=Q.base(m+j)%k;Q.basem=sum;printf(“%d”,sum);有一台磁盘机，其平均寻道时间为30ms，平均等待时间为10ms，数据传输率为500Bytems，磁盘机中随机存放着1000块，每块为3000Byte的数据。现欲把一块块数据取走，更新后再放回原地。假设一次取出或写入所需时间为：平均寻道时间+平均等待时间+数据传输时间。另外，使用CPU更新信息所需时间为4ms，并且更新时间同输入输出操作不相重

27、叠。试问：(分数：10)(1) .更新磁盘上的全部数据需多少时间?(分数：5)正确答案：(由于数据块是随机存放的，所以每取出或写入一块均要定位。Byte/500Byte/ms=6ms更新全部数据所需时间=2X1000X(平均寻道时间+平均等彳f时间+数据传输时间)+1000XCPl2X1000X(30+10+6)+1000X4=96000ms=96s。)(2) .若磁盘机旋转速度和数据传输率都提高一倍，更新全部数据需要多少时间?(分数：5)正确答案：(磁盘机旋转速度提高一倍后，平均等待时间为5ms。数据传输率提高一倍为1000Byte/ms,数据传输时间变为3000/1000Byte/ms=3

28、ms更新全部数据所需时间=2X1000X(30+5+3)+1000X4=80000ms=80s。)图3所示为用8片2114构成的4KX8的存储器，与8位的一个微处理器相连，2114为1024X4位的静态RAM芯片。问：图34KX8的存储器与CPU的连接（分数：10）（1） .每一组芯片组的地址范围和地址线数目是多少？（分数：2）（芯片组的容量为1024B,地址范围为000H3FFH,地址线数目为10根（AAo）。）（2） .4KB的RAM寻址范围是多少？（分数：5）正确答案：（根据图3所示的连线，各芯片组的片选端由地址线A15、A14进行译码。芯片组内地址线为A9A,A3A。空闲，即为任意态。

29、假设Ai3A。为全0,4KBRAM的寻址范围分别是：第0组为0000H03FFH,第1组为4000H43FFH,第2组为8000H83FFH,第3组为C000HC3FFH可见这4KB存储器的地址空间是不连续的。）（3） .存储器有没有地址重叠？（分数：3）正确答案：（由于A13A10没有参与译码（部分译码），所以存储器存在地址重叠现象。关于死锁问题的银行家算法中，若出现如表1所列的资源分配情况:表1资源分配表请回答：（分数：10）（1） .该状态是否安全？请说明理由。（分数：5）正确答案：（,根据已知条件列出表2:银行家算法有：Maxi,j=Allocationi,j+Needi,j表2含最大需求矩阵的资源分配表检测过程如下面所述。资源可用量（1,6资源可用量（1,6资源可用量（1,9资源可用量（2,92,2),能满足P05,4),可满足P38,6),可满足P18,6),可满足P2资源可用量14,14）。3,12,13,10）,可满足P4。待其完成后使系统的资源可用量达到初始值（3,12,由此可得，系统此刻存在安全序列P0,P3,P1,P2,P4,因此状态是安全的5)（2） .若进程Pi提出请求Request(1,2,2,2)后，系统能否将资源分配给它？(分数:正确答案：(若进程Pi提出请求(1,2,2