2018年全国硕士研究生入学统一考试
计算机科学与技术学科联考计算机学科专业基础综合试题
一、单项选择题（第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，
只有一个选项最符合试题要求）
1.若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：
（1）从S1中依次弹出两个操作数a和b；
（2）从S2中弹出一个运算符op；
（3）执行相应的运算b op a；
（4）将运算结果压入S1中。
假定S1中的操作数依次是5,8,3,2（2在栈顶），S2中的运算符依次是*,-,+（+在栈顶）。
调用3次F()后，S1栈顶保存的值是。
A.-15
B.15
C.-20
D.20
2.现有队列Q与栈S，初始时Q中的元素依次是1,2,3,4,5,6（1在队头），S为空。若仅允许下列3种操作：①出队并输出出队元素；②出队并将出队元素入栈；③出栈并输出出栈元素，则不能得到的输出序列是。
A.1,2,5,6,4,3
B.2,3,4,5,6,1
C.3,4,5,6,1,2
D.6,5,4,3,2,1
3.设有一个12×12的对称矩阵M，将其上三角部分的元素m i,j（1≤i≤j≤12）按行优先存入C语言的一维数
组N中，元素m6,6在N中的下标是。
A.50
B.51
C.55
D.66
4.设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是。
A.2k-1
B.2k
C.k2
D.2k-1
5.已知字符集{a,b,c,d,e,f}，若各字符出现的次数分别为6,3,8,2,10,4，则对应字符集中各字符的哈夫曼编码可能是。
A.00,1011,01,1010,11,100
B.00,100,110,000,0010,01
C.10,1011,11,0011,00,010
D.0011,10,11,0010,01,000
6.已知二叉排序树如下图所示，元素之间应满足的大小关系是。
A.x1<x2<x5
B.x1<x4<x5
C.x3<x5<x4
D.x4<x3<x5
7.下列选项中，不是如下有向图的拓扑序列的是。
A.1,5,2,3,6,4
B.5,1,2,6,3,4
C.5,1,2,3,6,4
D.5,2,1,6,3,4
8.高度为5的3阶B树含有的关键字个数至少是。
A.15
B.31
C.62
D.242
9.现有长度为7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字22,43,15依次插入到HT后，查成功的平均查长度是。
A.1.5
B.1.6
C.2
D.3
10.对初始数据序列(8,3,9,11,2,1,4,7,5,10,6)进行希尔排序。若第一趟排序结果为(1,3, 7,5,2,6,4,9,11,10,8)，第二趟排序结果为(1,2,6,4,3,7,5,8,11,10,9)，则两趟排序采用的增量（间隔）依次是。
A.3,1
B.3,2
C.5,2
D.5,3
11.在将数据序列(6,1,5,9,8,4,7)建成大根堆时，正确的序列变化过程是。
A.6,1,7,9,8,4,5→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5
B.6,9,5,1,8,4,7→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5
C.6,9,5,1,8,4,7→9,6,5,1,8,4,7→9,6,7,1,8,4,5→9,8,7,1,6,4,5
D.6,1,7,9,8,4,5→7,1,6,9,8,4,5→7,9,6,1,8,4,5→9,7,6,1,8,4,5→9,8,6,1,7,4,5
12.冯·诺依曼结构计算机中数据采用二进制编码表示，其主要原因是。
I.二进制的运算规则简单
II.制造两个稳态的物理器件较容易
III.便于用逻辑门电路实现算术运算
A.仅I、II
B.仅I、III
C.仅II、III
D.I、II和III
13.假定带符号整数采用补码表示，若int型变量x和y的机器数分别是FFFF FFDFH和00000041H，则x、y的值以及x-y的机器数分别是。
A.x=-65,y=41，x-y的机器数溢出
B.x=-33,y=65，x-y的机器数为FFFF FF9DH
C.x=-33,y=65，x-y的机器数为FFFF FF9EH
D.x=-65,y=41，x-y的机器数为FFFF FF96H
14.IEEE754单精度浮点格式表示的数中，最小的规格化正数是。
A.1.0×2−126
B.1.0×2−127
C.1.0×2−128
D.1.0×2−149
15.某32位计算机按字节编址，采用小端（Little Endian）方式。若语句“int i=0;”对应指令的机器代码为“C745FC00000000”，则语句“int i=−64;”对应指令的机器代码是。
A.C745FC C0FF FF FF
B.C745FC0C FF FF FF
C.C745FC FF FF FF C0
D.C745FC FF FF FF0C
16.整数x的机器数为11011000，分别对x进行逻辑右移1位和算术右移1位操作，得到的机器数分别是。
2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题
A.11101100，11101100
B.01101100，11101100
C.11101100，01101100
D.01101100，01101100
17.假定DRAM芯片中存储阵列的行数为r、列数为c，对于一个2K×1位的DRAM芯片，为保证其地址引脚数最少，并尽量减小刷新开销，则r、c的取值分别是。
A.2048、1
B.64、32
C.32、64
D.1、2048
18.按字节编址的计算机中，某double型数组A的首地址为2000H，使用变址寻址和循环结构访问数组A，保存数组下标的变址寄存器初值为0，每次循环取一个数组元素，其偏移地址为变址值乘以sizeof(double)，取完后变址寄存器内容自动加1。若某次循环所取元素的地址为2100H，则进入该次循环时变址寄存器的内容是。
A.25
B.32
C.64
D.100
19.减法指令“sub R1,R2,R3”的功能为“(R1)-(R2)→R3”，该指令执行后将生成进位/借位标志CF和溢出标志OF。若(R1)=FFFF FFFFH，(R2)=FFFF FFF0H，则该减法指令执行后，CF与OF分别为。
A.CF=0,OF=0
B.CF=1,OF=0
C.CF=0,OF=1
D.CF=1,OF=1
20.若某计算机最复杂指令的执行需要完成5个子功能，分别由功能部件A～E实现，各功能部件所需时间分别为80ps、50ps、50ps、70ps和50ps，采用流水线方式执行指令，流水段寄存器延时为20ps，则CPU时钟周期至少为。
A.60ps
B.70ps
C.80ps
D.100ps
21.下列选项中，可提高同步总线数据传输率的是。
I.增加总线宽度II.提高总线工作频率
III.支持突发传输IV.采用地址/数据线复用
A.仅I、II
B.仅I、II、III
C.仅III、IV
D.I、II、III和IV
22.下列关于外部I/O中断的叙述中，正确的是。
A.中断控制器按所接收中断请求的先后次序进行中断优先级排队
B.CPU响应中断时，通过执行中断隐指令完成通用寄存器的保护
C.CPU只有在处于中断允许状态时，才能响应外部设备的中断请求
D.有中断请求时，CPU立即暂停当前指令执行，转去执行中断服务程序
23.下列关于多任务操作系统的叙述，正确的是。
I.具有并发和并行的特点
II.需要实现对共享资源的保护
III.需要运行在多CPU的硬件平台上
A.仅I
B.仅II
C.仅I、II
D.I、II、III
24.某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为1µs。在T时刻就绪队列中有3个进程P1、P2和P3，其在就绪队列中的等待时间、需要的CPU时间和优先权如下表所示。
进程等待时间需要的CPU时间优先权
P130µs12µs10
P215µs24µs30
P318µs36µs20
若优先权值大的进程优先获得CPU，从T时刻起系统开始进程调度，系统的平均周转时间为。
A.54µs
B.73µs
C.74µs
D.75µs
25.属于同一进程的两个线程thread1和thread2并发执行，共享初值为0的全局变量x。thread1和thread2实现对全局变量x加1的机器级代码描述如下。
thread1thread2
mov inc mov
R1,x
R1
x,R1
//(x)→R1
//(R1)+1→R1
//(R1)→x
mov
inc
mov
R2,x
thread技术R2
x,R2
//(x)→R2
//(R2)+1→R2
//(R2)→x
在所有可能的指令执行序列中，使x的值为2的序列个数是。
A.1
B.2
C.3
D.4
26.假设系统中有4个同类资源，进程P1,P2和P3需要的资源数分别为4,3和1，P1,P2和P3已申请到的资源数分别为2,1和0，则执行安全性检测算法的结果是。
A.不存在安全序列，系统处于不安全状态
B.存在多个安全序列，系统处于安全状态
C.存在唯一安全序列P3,P1,P2，系统处于安全状态
D.存在唯一安全序列P3,P2,P1，系统处于安全状态
27.下列选项中，可能导致当前进程P阻塞的事件是。
I.进程P申请临界资源
II.进程P从磁盘读数据
III.系统将CPU分配给高优先权的进程
A.仅I
B.仅II
C.仅I、II
D.I、II、III
28.若x是管程内的条件变量，则当进程执行x.wait()时所做的工作是。
A.实现对变量x的互斥访问
B.唤醒一个在x上阻塞的进程
C.根据x的值判断该进程是否进入阻塞状态
D.阻塞该进程，并将之插入x的阻塞队列中
29.当定时器产生时钟中断后，由时钟中断服务程序更新的部分内容是。
I.内核中时钟变量的值
II.当前进程占用CPU的时间
III.当前进程在时间片内的剩余执行时间
A.仅I、II
B.仅II、III
C.仅I、III
D.I、II、III
30.系统总是访问磁盘的某个磁道而不响应对其他磁道的访问请求，这种现象称为磁臂黏着。下列磁盘调度算法中，不会导致磁臂黏着的是。
A.先来先服务（FCFS）
B.最短寻道时间优先（SSTF）
C.扫描算法（SCAN）
D.循环扫描算法（CSCAN）
31.下列优化方法中，可以提高文件访问速度的是。
I.提前读III.延迟写II.为文件分配连续的簇IV.采用磁盘高速缓存
A.仅I、II
B.仅II、III
C.仅I、III、IV
D.I、II、III、IV
32.下列同步机制中，可以实现让权等待的是。
A.Peterson方法
B.swap指令
C.信号量方法
D.TestAndSet指令
33.下列TCP/IP应用层协议中，可以使用传输层无连接服务的是。
2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题
A.FTP
B.DNS
C.SMTP
D.HTTP
34.下列选项中，不属于物理层接口规范定义范畴的是。
A.接口形状
B.引脚功能
C.物理地址
D.信号电平
35.IEEE802.11无线局域网的MAC协议CSMA/CA进行信道预约的方法是。
A.发送确认帧
B.采用二进制指数退避
C.使用多个MAC地址
D.交换RTS与CTS帧
36.主机甲采用停-等协议向主机乙发送数据，数据传输速率是3kbps，单向传播延时是200ms，忽略确认帧的传输延时。当信道利用率等于40%时，数据帧的长度为。
A.240比特
B.400比特
C.480比特
D.800比特
37.路由器R通过以太网交换机S1和S2连接两个网络，R的接口、主机H1和H2的IP地址与MAC地址如下图所示。若H1向H2发送1个IP分组P，则H1发出的封装P的以太网帧的目的MAC地址、H2收到的封装P
的以太网帧的源MAC地址分别是。
A.00-a1-b2-c3-d4-62,00-1a-2b-3c-4d-52
B.00-a1-b2-c3-d4-62,00-a1-b2-c3-d4-61
C.00-1a-2b-3c-4d-51,00-1a-2b-3c-4d-52
D.00-1a-2b-3c-4d-51,00-a1-b2-c3-d4-61
38.某路由表中有转发接口相同的4条路由表项，其目的网络地址分别为35.230.32.0/21,
35.230.40.0/21,35.230.48.0/21和35.230.56.0/21，将该4条路由聚合后的目的网络地址为。
A.35.230.0.0/19
B.35.230.0.0/20
C.35.230.32.0/19
D.35.230.32.0/20
39.UDP协议实现分用（demultiplexing）时所依据的头部字段是。
A.源端口号
B.目的端口号
C.长度
D.校验和
40.无须转换即可由SMTP协议直接传输的内容是。
A.JPEG图像
B.MPEG视频
C.EXE文件
D.ASCII文本
二、综合应用题（第41～47小题，共70分）
41.（13分）给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
42.（12分）拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH8个城市，题42图中无向边上的权值表示两个城市间备选光纤的铺设费用。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。