2024年5月30日发(作者：蹇语柳)
2018年全国硕士研究生入学统一考试
计算机科学与技术学科联考计算机学科专业基础综合试题
一、单项选择题（第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，
只有一个选项最符合试题要求）
1.
若栈
S
1
中保存整数，栈
S
2
中保存运算符，函数
F()
依次执行下述各步操作：
（1）
从
S
1
中依次弹出两个操作数
a
和
b
；
（2）
从S
2
中弹出一个运算符op；
（3）
执行相应的运算
bopa
；
（4）
将运算结果压入S
1
中。
假定
S
1
中的操作数依次是
5,8,3,2
（
2
在栈顶），
S
2
中的运算符依次是
*,
-
,+
（
+
在栈顶）。
调用3次F()后，S
1
栈顶保存的值是。
A.-15B.15C.-20D.20
2.
现有队列Q与栈S，初始时Q中的元素依次是1,2,3,4,5,6（1在队头），S为空。若仅允
许下列3种操作：①出队并输出出队元素；②出队并将出队元素入栈；③出栈并输出出栈元素，
则不能得到的输出序列是。
A.1,2,5,6,4,3B.2,3,4,5,6,1C.3,4,5,6,1,2D.6,5,4,3,2,1
3.
设有一个
12×12
的对称矩阵
M
，将其上三角部分的元素
m
i,j
（
1
≤
i
≤
j
≤
12
）按行优先存
入C语言的一维数组N中，元素m
6,6
在N中的下标是。
A.50B.51C.55D.66
4.
设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。
若T有k个叶结点，则T的结点总数是。
A.2k-1B.2kC.k
2
D.2
k
-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,010D.0011,10,11,0010,01,000
6.
已知二叉排序树如下图所示，元素之间应满足的大小关系是。
1
A.x
1
2 5 B.x 1 4 5 C.x 3 5 4 7. 下列选项中，不是如下有向图的拓扑序列的是 D.x 4 3 5 。 A.1,5,2,3,6,4B.5,1,2,6,3,4C.5,1,2,3,6,4 8. 高度为5的3阶B树含有的关键字个数至少是。 D.5,2,1,6,3,4 A.15B.31C.62D.242 9. 现有长度为7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解 决冲突。将关键字22,43,15依次插入到HT后，查找成功的平均查找长度是。 A.1.5B.1.6C.2D.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,1B.3,2C.5,2D.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、IIB.仅I、IIIC.仅II、III 。 D.I、II和III 13. 假定带符号整数采用补码表示，若 int 型变量 x 和 y 的机器数分别是 FFFFFFDFH 和 00000041H ，则 x 、 y 的值以及 x - y 的机器数分别是 A.x= - 65,y=41 ， x - y 的机器数溢出 B.x=-33,y=65，x-y的机器数为FFFFFF9DH C.x=-33,y=65，x-y的机器数为FFFFFF9EH D.x= - 65,y=41 ， x - y 的机器数为 FFFFFF96H 754单精度浮点格式表示的数中，最小的规格化正数是。 A.1.0×2 −126 B.1.0×2 −127 C.1.0×2 −128 D.1.0×2 −149 15. 某 32 位计算机按字节编址，采用小端（ LittleEndian ）方式。若语句“ inti=0; ”对应 指令的机器代码为“C745FC00000000”，则语句“inti=−64;”对应指令的机器代码是 A.C745FCC0FFFFFFB.C745FC0CFFFFFF 。 。 C.C745FCFFFFFFC0D.C745FCFFFFFF0C 16.整数x的机器数为11011000，分别对x进行逻辑右移1位和算术右移1位操作，得到的 机器数分别是。 2 2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试 题 A.11101100，11101100 C.11101100 ， 01101100 B. D. 01101100，11101100 01101100 ， 01101100 。 D.1、2048 17.假定DRAM芯片中存储阵列的行数为r、列数为c，对于一个2K×1位的DRAM芯片，为 保证其地址引脚数最少，并尽量减小刷新开销，则 r 、 c 的取值分别是 A.2048、1B.64、32C.32、64 18. 按字节编址的计算机中，某 double 型数组 A 的首地址为 2000H ，使用变址寻址和循环 结构访问数组A，保存数组下标的变址寄存器初值为0，每次循环取一个数组元素，其偏移地 址为变址值乘以sizeof(double)，取完后变址寄存器内容自动加1。若某次循环所取元素的地址 为 2100H ，则进入该次循环时变址寄存器的内容是。 A.25B.32C.64D.100 19.减法指令“subR1,R2,R3”的功能为“(R1)-(R2)→R3”，该指令执行后将生成进位/ 借位标志CF和溢出标志OF。若(R1)=FFFFFFFFH，(R2)=FFFFFFF0H，则该减法指令执行 后，CF与OF分别为。 =0,OF==1,OF==0,OF==1,OF=1 20.若某计算机最复杂指令的执行需要完成5个子功能，分别由功能部件A～E实现，各 功能部件所需时间分别为 80ps 、 50ps 、 50ps 、 70ps 和 50ps ，采用流水线方式执行指令，流水段 寄存器延时为 20ps ，则 CPU 时钟周期至少为。 D.100psA.60psB.70psC.80ps 21.下列选项中，可提高同步总线数据传输率的是。 I. 增加总线宽度 III.支持突发传输 A.仅I、II II. 提高总线工作频率 IV.采用地址/数据线复用 B.仅I、II、IIIC.仅III、IV 。 D.I、II、III和IV 22.下列关于外部I/O中断的叙述中，正确的是 A.中断控制器按所接收中断请求的先后次序进行中断优先级排队 响应中断时，通过执行中断隐指令完成通用寄存器的保护 只有在处于中断允许状态时，才能响应外部设备的中断请求 D. 有中断请求时， CPU 立即暂停当前指令执行，转去执行中断服务程序 23.下列关于多任务操作系统的叙述，正确的是 I.具有并发和并行的特点 II. 需要实现对共享资源的保护 III. 需要运行在多 CPU 的硬件平台上 A. 仅 IB. 仅 IIC. 仅 I 、 IID.I 、 II 、 III 24.某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系 统时间开销为 1µs 。在 T 时刻就绪队列中有 3 个进程 P 1 、 P 2 和 P 3 ，其在就绪队列中的等待时间、 需 要的CPU时间和优先权如下表所示。 进程 P 1 P 2 P 3 等待时间 30µs 15µs 18µs 需要的CPU时间 12µs 24µs 36µs 优先权 10 30 20 。 若优先权值大的进程优先获得CPU，从T时刻起系统开始进程调度，系统的平均周转时间 为。 3 A.54µsB.73µsC.74µsD.75µs 25.属于同一进程的两个线程thread1和thread2并发执行，共享初值为0的全局变量x。 thread1 和 thread2 实现对全局变量 x 加 1 的机器级代码描述如下。 thread1 movR1,x incR1 movx,R1 //(x)→R1 //(R1)+1→R1 //(R1)→x movR2,x incR2 movx,R2 thread2 //(x)→R2 //(R2)+1→R2 //(R2)→x 在所有可能的指令执行序列中，使x的值为2的序列个数是。 A.1B.2C.3D.4 26. 假设系统中有4个同类资源，进程P 1 ,P 2 和P 3 需要的资源数分别为4,3和1，P 1 ,P 2 和 。 P 3 已申请到的资源数分别为 2,1 和 0 ，则执行安全性检测算法的结果是 A. 不存在安全序列，系统处于不安全状态 B.存在多个安全序列，系统处于安全状态 C. 存在唯一安全序列 P 3 ,P 1 ,P 2 ，系统处于安全状态 D. 存在唯一安全序列 P 3 ,P 2 ,P 1 ，系统处于安全状态 27. 下列选项中，可能导致当前进程 P 阻塞的事件是 I.进程P申请临界资源 II. 进程 P 从磁盘读数据 III.系统将CPU分配给高优先权的进程 A.仅IB.仅IIC.仅I、IID.I、II、III 。 28. 若 x 是管程内的条件变量，则当进程执行 () 时所做的工作是 A.实现对变量x的互斥访问 B. 唤醒一个在 x 上阻塞的进程 C.根据x的值判断该进程是否进入阻塞状态 D.阻塞该进程，并将之插入x的阻塞队列中 29.当定时器产生时钟中断后，由时钟中断服务程序更新的部分内容是 I. 内核中时钟变量的值 II. 当前进程占用 CPU 的时间 III.当前进程在时间片内的剩余执行时间 A.仅I、IIB.仅II、IIIC.仅I、III 。 D.I、II、III 30.系统总是访问磁盘的某个磁道而不响应对其他磁道的访问请求，这种现象称为磁臂黏 着。下列磁盘调度算法中，不会导致磁臂黏着的是 A.先来先服务（FCFS） C. 扫描算法（ SCAN ） I.提前读 III.延迟写 A.仅I、II on 方法 B.最短寻道时间优先（SSTF） D. 循环扫描算法（ CSCAN ） 。 II.为文件分配连续的簇 IV.采用磁盘高速缓存 B.仅II、IIIC.仅I、III、IV 。 C. 信号量方法 dSet 指令 。 指令 。 。 31.下列优化方法中，可以提高文件访问速度的是 D.I、II、III、IV 32.下列同步机制中，可以实现让权等待的是 33.下列TCP/IP应用层协议中，可以使用传输层无连接服务的是 4 2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试 题 34.下列选项中，不属于物理层接口规范定义范畴的是 A.接口形状 A. 发送确认帧 C.使用多个MAC地址 B.引脚功能C.物理地址 。 D.信号电平 。802.11无线局域网的MAC协议CSMA/CA进行信道预约的方法是 B. 采用二进制指数退避 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, 将该 4 条路由聚合后的目的网络地址为 35.230.40.0/21,35.230.48.0/21 和 35.230.56.0/21 ， A.35.230.0.0/19B.35.230.0.0/20 。 D. 校验和 。 文本 C.35.230.32.0/19D.35.230.32.0/20 协议实现分用（ demultiplexing ）时所依据的头部字段是 A. 源端口号 图像 B. 目的端口号 视频 C. 长度 文件 40.无须转换即可由SMTP协议直接传输的内容是 二、综合应用题 （第 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图中无向边上的权值表示两个城市间备选光纤的铺设费用。 5 题 42 图 请回答下列问题。 ， （1） 仅从铺设费用角度出发，给出所有可能的最经济的光纤铺设方案（用带权图表示） 并计算相应方案的总费用。 （2） 题 42 图可采用图的哪种存储结构？给出求解问题（ 1 ）所使用的算法名称。 （3） 假设每个城市采用一个路由器按（ 1 ）中得到的最经济方案组网，主机 H1 直接连接在 TL 的路由器上，主机 H2 直接连接在 BJ 的路由器上。若 H1 向 H2 发送一个 TTL=5 的 IP 分组，则 H2 是否可以收到该 IP 分组？ 43.（8分）假定计算机的主频为500MHz，CPI为4。现有设备A和B，其数据传输速率分 别为2MB/s和40MB/s，对应I/O接口中各有一个32位数据缓冲寄存器。请回答下列问题，要 求给出计算过程。 （1） 若设备 A 采用定时查询 I/O 方式，每次输入 / 输出都至少执行 10 条指令。设备 A 最多 间隔多长时间查询一次才能不丢失数据？CPU用于设备A输入/输出的时间占CPU总时间的百 分比至少是多少？ （2） 在中断I/O方式下，若每次中断响应和中断处理的总时钟周期数至少为400，则设备B 能否采用中断I/O方式？为什么？ （3） 若设备 B 采用 DMA 方式，每次 DMA 传送的数据块大小为 1000B ， CPU 用于 DMA 预 处理和后处理的总时钟周期数为500，则CPU用于设备B输入/输出的时间占CPU总时间的百分 比最大是多少？ 44. （ 15 分）某计算机采用页式虚拟存储管理方式，按字节编址。 CPU 进行存储访问的过 程如题44图所示。 根据题 44 图回答下列问题。 （1） 主存物理地址占多少位? （2） TLB 采用什么映射方式？ TLB 是用 SRAM 还是用 DRAM 实现？ （3） Cache采用什么映射方式？若Cache采用LRU替换算法和回写（WriteBack）策略， 则Cache每行中除数据（Data）、Tag和有效位，还应有哪些附加位？Cache的总容量是多少？ Cache 中有效位的作用是什么？ （4） 若 CPU 给出的虚拟地址为 0008C040H ，则对应的物理地址是多少？是否在 Cache 中 命中？说明理由。若CPU给出的虚拟地址为0007C260H，则该地址所在主存块映射到的Cache 组号是多少？ 6 2024年5月30日发(作者：蹇语柳) 2018年全国硕士研究生入学统一考试 计算机科学与技术学科联考计算机学科专业基础综合试题 一、单项选择题（第1～40小题，每小题2分，共80分。下列每题给出的四个选项中， 只有一个选项最符合试题要求） 1. 若栈 S 1 中保存整数，栈 S 2 中保存运算符，函数 F() 依次执行下述各步操作： （1） 从 S 1 中依次弹出两个操作数 a 和 b ； （2） 从S 2 中弹出一个运算符op； （3） 执行相应的运算 bopa ； （4） 将运算结果压入S 1 中。 假定 S 1 中的操作数依次是 5,8,3,2 （ 2 在栈顶）， S 2 中的运算符依次是 *, - ,+ （ + 在栈顶）。 调用3次F()后，S 1 栈顶保存的值是。 A.-15B.15C.-20D.20 2. 现有队列Q与栈S，初始时Q中的元素依次是1,2,3,4,5,6（1在队头），S为空。若仅允 许下列3种操作：①出队并输出出队元素；②出队并将出队元素入栈；③出栈并输出出栈元素， 则不能得到的输出序列是。 A.1,2,5,6,4,3B.2,3,4,5,6,1C.3,4,5,6,1,2D.6,5,4,3,2,1 3. 设有一个 12×12 的对称矩阵 M ，将其上三角部分的元素 m i,j （ 1 ≤ i ≤ j ≤ 12 ）按行优先存 入C语言的一维数组N中，元素m 6,6 在N中的下标是。 A.50B.51C.55D.66 4. 设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。 若T有k个叶结点，则T的结点总数是。 A.2k-1B.2kC.k 2 D.2 k -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,010D.0011,10,11,0010,01,000 6. 已知二叉排序树如下图所示，元素之间应满足的大小关系是。 1 A.x 1 2 5 B.x 1 4 5 C.x 3 5 4 7. 下列选项中，不是如下有向图的拓扑序列的是 D.x 4 3 5 。 A.1,5,2,3,6,4B.5,1,2,6,3,4C.5,1,2,3,6,4 8. 高度为5的3阶B树含有的关键字个数至少是。 D.5,2,1,6,3,4 A.15B.31C.62D.242 9. 现有长度为7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解 决冲突。将关键字22,43,15依次插入到HT后，查找成功的平均查找长度是。 A.1.5B.1.6C.2D.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,1B.3,2C.5,2D.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、IIB.仅I、IIIC.仅II、III 。 D.I、II和III 13. 假定带符号整数采用补码表示，若 int 型变量 x 和 y 的机器数分别是 FFFFFFDFH 和 00000041H ，则 x 、 y 的值以及 x - y 的机器数分别是 A.x= - 65,y=41 ， x - y 的机器数溢出 B.x=-33,y=65，x-y的机器数为FFFFFF9DH C.x=-33,y=65，x-y的机器数为FFFFFF9EH D.x= - 65,y=41 ， x - y 的机器数为 FFFFFF96H 754单精度浮点格式表示的数中，最小的规格化正数是。 A.1.0×2 −126 B.1.0×2 −127 C.1.0×2 −128 D.1.0×2 −149 15. 某 32 位计算机按字节编址，采用小端（ LittleEndian ）方式。若语句“ inti=0; ”对应 指令的机器代码为“C745FC00000000”，则语句“inti=−64;”对应指令的机器代码是 A.C745FCC0FFFFFFB.C745FC0CFFFFFF 。 。 C.C745FCFFFFFFC0D.C745FCFFFFFF0C 16.整数x的机器数为11011000，分别对x进行逻辑右移1位和算术右移1位操作，得到的 机器数分别是。 2 2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试 题 A.11101100，11101100 C.11101100 ， 01101100 B. D. 01101100，11101100 01101100 ， 01101100 。 D.1、2048 17.假定DRAM芯片中存储阵列的行数为r、列数为c，对于一个2K×1位的DRAM芯片，为 保证其地址引脚数最少，并尽量减小刷新开销，则 r 、 c 的取值分别是 A.2048、1B.64、32C.32、64 18. 按字节编址的计算机中，某 double 型数组 A 的首地址为 2000H ，使用变址寻址和循环 结构访问数组A，保存数组下标的变址寄存器初值为0，每次循环取一个数组元素，其偏移地 址为变址值乘以sizeof(double)，取完后变址寄存器内容自动加1。若某次循环所取元素的地址 为 2100H ，则进入该次循环时变址寄存器的内容是。 A.25B.32C.64D.100 19.减法指令“subR1,R2,R3”的功能为“(R1)-(R2)→R3”，该指令执行后将生成进位/ 借位标志CF和溢出标志OF。若(R1)=FFFFFFFFH，(R2)=FFFFFFF0H，则该减法指令执行 后，CF与OF分别为。 =0,OF==1,OF==0,OF==1,OF=1 20.若某计算机最复杂指令的执行需要完成5个子功能，分别由功能部件A～E实现，各 功能部件所需时间分别为 80ps 、 50ps 、 50ps 、 70ps 和 50ps ，采用流水线方式执行指令，流水段 寄存器延时为 20ps ，则 CPU 时钟周期至少为。 D.100psA.60psB.70psC.80ps 21.下列选项中，可提高同步总线数据传输率的是。 I. 增加总线宽度 III.支持突发传输 A.仅I、II II. 提高总线工作频率 IV.采用地址/数据线复用 B.仅I、II、IIIC.仅III、IV 。 D.I、II、III和IV 22.下列关于外部I/O中断的叙述中，正确的是 A.中断控制器按所接收中断请求的先后次序进行中断优先级排队 响应中断时，通过执行中断隐指令完成通用寄存器的保护 只有在处于中断允许状态时，才能响应外部设备的中断请求 D. 有中断请求时， CPU 立即暂停当前指令执行，转去执行中断服务程序 23.下列关于多任务操作系统的叙述，正确的是 I.具有并发和并行的特点 II. 需要实现对共享资源的保护 III. 需要运行在多 CPU 的硬件平台上 A. 仅 IB. 仅 IIC. 仅 I 、 IID.I 、 II 、 III 24.某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系 统时间开销为 1µs 。在 T 时刻就绪队列中有 3 个进程 P 1 、 P 2 和 P 3 ，其在就绪队列中的等待时间、 需 要的CPU时间和优先权如下表所示。 进程 P 1 P 2 P 3 等待时间 30µs 15µs 18µs 需要的CPU时间 12µs 24µs 36µs 优先权 10 30 20 。 若优先权值大的进程优先获得CPU，从T时刻起系统开始进程调度，系统的平均周转时间 为。 3 A.54µsB.73µsC.74µsD.75µs 25.属于同一进程的两个线程thread1和thread2并发执行，共享初值为0的全局变量x。 thread1 和 thread2 实现对全局变量 x 加 1 的机器级代码描述如下。 thread1 movR1,x incR1 movx,R1 //(x)→R1 //(R1)+1→R1 //(R1)→x movR2,x incR2 movx,R2 thread2 //(x)→R2 //(R2)+1→R2 //(R2)→x 在所有可能的指令执行序列中，使x的值为2的序列个数是。 A.1B.2C.3D.4 26. 假设系统中有4个同类资源，进程P 1 ,P 2 和P 3 需要的资源数分别为4,3和1，P 1 ,P 2 和 。 P 3 已申请到的资源数分别为 2,1 和 0 ，则执行安全性检测算法的结果是 A. 不存在安全序列，系统处于不安全状态 B.存在多个安全序列，系统处于安全状态 C. 存在唯一安全序列 P 3 ,P 1 ,P 2 ，系统处于安全状态 D. 存在唯一安全序列 P 3 ,P 2 ,P 1 ，系统处于安全状态 27. 下列选项中，可能导致当前进程 P 阻塞的事件是 I.进程P申请临界资源 II. 进程 P 从磁盘读数据 III.系统将CPU分配给高优先权的进程 A.仅IB.仅IIC.仅I、IID.I、II、III 。 28. 若 x 是管程内的条件变量，则当进程执行 () 时所做的工作是 A.实现对变量x的互斥访问 B. 唤醒一个在 x 上阻塞的进程 C.根据x的值判断该进程是否进入阻塞状态 D.阻塞该进程，并将之插入x的阻塞队列中 29.当定时器产生时钟中断后，由时钟中断服务程序更新的部分内容是 I. 内核中时钟变量的值 II. 当前进程占用 CPU 的时间 III.当前进程在时间片内的剩余执行时间 A.仅I、IIB.仅II、IIIC.仅I、III 。 D.I、II、III 30.系统总是访问磁盘的某个磁道而不响应对其他磁道的访问请求，这种现象称为磁臂黏 着。下列磁盘调度算法中，不会导致磁臂黏着的是 A.先来先服务（FCFS） C. 扫描算法（ SCAN ） I.提前读 III.延迟写 A.仅I、II on 方法 B.最短寻道时间优先（SSTF） D. 循环扫描算法（ CSCAN ） 。 II.为文件分配连续的簇 IV.采用磁盘高速缓存 B.仅II、IIIC.仅I、III、IV 。 C. 信号量方法 dSet 指令 。 指令 。 。 31.下列优化方法中，可以提高文件访问速度的是 D.I、II、III、IV 32.下列同步机制中，可以实现让权等待的是 33.下列TCP/IP应用层协议中，可以使用传输层无连接服务的是 4 2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试 题 34.下列选项中，不属于物理层接口规范定义范畴的是 A.接口形状 A. 发送确认帧 C.使用多个MAC地址 B.引脚功能C.物理地址 。 D.信号电平 。802.11无线局域网的MAC协议CSMA/CA进行信道预约的方法是 B. 采用二进制指数退避 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, 将该 4 条路由聚合后的目的网络地址为 35.230.40.0/21,35.230.48.0/21 和 35.230.56.0/21 ， A.35.230.0.0/19B.35.230.0.0/20 。 D. 校验和 。 文本 C.35.230.32.0/19D.35.230.32.0/20 协议实现分用（ demultiplexing ）时所依据的头部字段是 A. 源端口号 图像 B. 目的端口号 视频 C. 长度 文件 40.无须转换即可由SMTP协议直接传输的内容是 二、综合应用题 （第 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图中无向边上的权值表示两个城市间备选光纤的铺设费用。 5 题 42 图 请回答下列问题。 ， （1） 仅从铺设费用角度出发，给出所有可能的最经济的光纤铺设方案（用带权图表示） 并计算相应方案的总费用。 （2） 题 42 图可采用图的哪种存储结构？给出求解问题（ 1 ）所使用的算法名称。 （3） 假设每个城市采用一个路由器按（ 1 ）中得到的最经济方案组网，主机 H1 直接连接在 TL 的路由器上，主机 H2 直接连接在 BJ 的路由器上。若 H1 向 H2 发送一个 TTL=5 的 IP 分组，则 H2 是否可以收到该 IP 分组？ 43.（8分）假定计算机的主频为500MHz，CPI为4。现有设备A和B，其数据传输速率分 别为2MB/s和40MB/s，对应I/O接口中各有一个32位数据缓冲寄存器。请回答下列问题，要 求给出计算过程。 （1） 若设备 A 采用定时查询 I/O 方式，每次输入 / 输出都至少执行 10 条指令。设备 A 最多 间隔多长时间查询一次才能不丢失数据？CPU用于设备A输入/输出的时间占CPU总时间的百 分比至少是多少？ （2） 在中断I/O方式下，若每次中断响应和中断处理的总时钟周期数至少为400，则设备B 能否采用中断I/O方式？为什么？ （3） 若设备 B 采用 DMA 方式，每次 DMA 传送的数据块大小为 1000B ， CPU 用于 DMA 预 处理和后处理的总时钟周期数为500，则CPU用于设备B输入/输出的时间占CPU总时间的百分 比最大是多少？ 44. （ 15 分）某计算机采用页式虚拟存储管理方式，按字节编址。 CPU 进行存储访问的过 程如题44图所示。 根据题 44 图回答下列问题。 （1） 主存物理地址占多少位? （2） TLB 采用什么映射方式？ TLB 是用 SRAM 还是用 DRAM 实现？ （3） Cache采用什么映射方式？若Cache采用LRU替换算法和回写（WriteBack）策略， 则Cache每行中除数据（Data）、Tag和有效位，还应有哪些附加位？Cache的总容量是多少？ Cache 中有效位的作用是什么？ （4） 若 CPU 给出的虚拟地址为 0008C040H ，则对应的物理地址是多少？是否在 Cache 中 命中？说明理由。若CPU给出的虚拟地址为0007C260H，则该地址所在主存块映射到的Cache 组号是多少？ 6