文档内容
考研 真题
2024 408
一、单项选择题：1～40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一
个选项是符合题目要求的。
1.已知带头结点的非空单链表 L 的头指针为 h，结点结构为 data next ，其中 next 是指向直
接后继结点的指针。现有指针 p和 q， 若 p 指向 L 中非首且非尾的任意一个结点，则执行语
句序列“q=p->next； p->next=q->next；q->next= h->next;；h->next=q；”的结果是（ ）。
A. 在p所指结点后插入q所指结点
B. 在q所指结点后插入p所指结点
C. 将p所指结点移动到L的头结点之后
D. 将q所指结点移动到L的头结点之后
2.与表达式x+y*(z-u) / v等价的后缀表达式是（ ）。
A. xyzu-*v/+ B. xyzu-v/*+
C. +x / * y-zuv D. +x* y /-zuv
3.若 p 、q 和 v 均为二叉树 T 中的结点，v 有两个孩子结点，T 的中序遍历序列形如：“...，
p，v，q，...”，则下列叙述中，正确的是（ ）。
A. p没有右孩子，q没左孩子
B. p没有右孩子，q有左孩子
C. p有右孩子，q没有左孩子
D. p有右孩子，q有左孩子
4.若无向图G = (V，E)的邻接多重表如下图所示，则G中顶点b与d的度分别是（ ）。
A. 0，2 B. 2，4
C. 2，5 D. 3，4
5.下列数据结构中, 不适合直接使用折半查找的是（ ）。I.有序链表 II.无序数组
III.有序静态链表 IV.无序静态链表
A.仅I 、III B.仅II、IV
C.仅II、III、IV D.I、II、III、IV
6.KMP算法使用修正后的next数组进行模式匹配，模式串 S= “aabaab”，当主串中某字符与
S中某字符失配时， S将向右滑动的最长距离是（ ）。
A.5 B.4 C.3 D.2
7.一棵二叉搜索树如题7图所示，k1、k2、k3分别是对应结点保存的关键字，子树T的任一
结点中保存的关键字x满足的是（ ）。
A. x< k1
B. x > k2
C. k1 < x < k3
D. k3 < x < k2
8.使用快速排序算法对含 n(n≥3)个元素的数组 M 进行排序， 若第一趟排序将 M 中除枢轴
外的n-1个元素划分为均不为空的 P和Q两块，则下列叙述中，正确的是（ ）。
A. P与Q 块间有序
B. P与Q 均块内有序
C. P和Q 的元素个数大致相等
D. P中和 Q中均不存在相等的元素
9.已知关键字序列 28，22，20，19，8，12，15，5 是大根堆 (最大堆)，对该堆进行两次删除
操作后， 得到的新堆是（ ）。
A.20，19，15，12，8，5
B.20，19，15，5，8，12
C.20，19，12，15，8，5
D.20，19，8，12，15，5
10.现有由关键字组成的3个有序序列（3，5）、（7，9）和（6），若按从左至右的次序选择
有序序列进行二路归并排序， 则关键字之间的总比较次数是（ ）。
A.3 B.4 C.5 D.6
在外排序中，利用败者树对初始为升序的归并段进行多路归并， 败者树中记录“冠军”的结
点保存的是（ ）。A.最大关键字 B.最小关键字
C.最大关键字所在的归并段号 D.最小关键字所在的归并段号
12. C语言代码如下。
int i=32777；
short si=i；
int j=si；
执行上述代码段后，j 的值是（ ）。
A. -32 777 B. -32 759
C. 32 759 D. 32 777
13.通常情况下，将汇编语言程序中实现特定功能的指令序列定义成一条伪指令
(pseudoinstruction)。下列选项中，CPU能理解并直接执行的是（ ）。
I.伪指令 II.微指令
III.机器指令 IV.汇编指令
A.仅I、 IV B.仅II、III
C.仅III、IV D.仅I、III、IV
14.某科学实验中，需要使用大量的整型参数，为了保证表数精度的基础上提高运算速度， 需
要选择合理的数据表示方法。若整型参数 α 、β的取值范围分别为- 220~220、- 240~240，则下列
选项中，α 、β最适宜采用的数据表示方法分别是（ ）。
A. 32位整数、32位整数
B.单精度浮点数、单精度浮点数
C. 32位整数、双精度浮点数
D.单精度浮点数、双精度浮点数
15.下列关于整数乘法运算的叙述中，错误的是（ ）。
A.用阵列乘法器实现乘运算可以在一个时钟周期内完成
B.用ALU 和移位器实现的乘运算无法在一个时钟周期内完成
C.变量与常数的乘运算可以编译优化为若干条移位及加/减运算指令
D.两个变量的乘运算无法编译转换为移位及加法等指令的循环实现
16.对于页式虚拟存储管理系统，下列关于存储器层次结构的叙述中, 错误的是（ ）。
A. Cache-主存层次的交换单位为主存块，主存-外存层次的交换单位为页
B. Cache-主存层次替换算法由硬件实现，主存-外存层次替换算法由软件实现C. Cache-主存层次可采用回写法写策略，主存-外存层次通常采用回写法写策略
D. Cache-主存层次可采用直接映射方式，主存-外存层次通常采用直接映射方式
17.某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址为32位，主存地址为30位，
页大小为 1KB。若 TLB 共有 32 个表项，采用 4 路组相联映射方式，则 TLB 表项中标记字段
的位数至少是（ ）。
A.17 B.18 C.19 D.20
18.下列事件中，不是在MMU地址转换过程中检测的是（ ）。
A.访问越权 B. Cache 缺失 C.页面缺失 D. TLB缺失
19.对于采用“取指、译码/取数、执行、访存、写回” 5 段流水线的 RISC 数据通路， 下列
关于指令流水线数据冒险处理的叙述中，错误的是（ ）。
A.相邻两条指令中的操作数相关可能引起数据冒险
B.在数据相关的指令间插入 “气泡”能避免数据冒险
C.所有数据冒险都可以通过加入转发（旁路）电路解决
D.所有数据冒险都能通过调整指令顺序和插入 nop 指令解决
20.某存储器总线的时钟频率为 420MHz，总线宽度为 64 位，每个时钟周期传送 2 次数据；
其总线事务支持突发传送方式, 最多传送8次数据，第1个时钟周期传送地址和读/写命令，从
第4个至第7个时钟周期连续传送8次数据。该总线的总线带宽（最大数据传输率)为 （ ）。
A 3.84 GB/s B. 6.72 GB/s
C. 30.72 GB/s D. 53.76 GB/s
21.下列关于中断I/O方式的叙述中，错误的是（ ）。
A.中断屏蔽字用于确定中断响应的优先级
B.保存断点和程序状态字在中断响应阶段完成
C.保存通用寄存器和设置新中断屏蔽字由软件实现
D.单重中断方式下中断处理时CPU处于关中断状态
22.DMA 控制 I/O 方式下，设备的输入/输出由 DMA 控制器控制完成，此时，DMA 控制器控
制的数据传输通路位于（ ）。
A. CPU和主存之间
B. CPU和 DMA控制器之间
C.设备接口和主存之间
D.设备接口和DMA控制器之间23.下列关于中断、异常和系统调用的叙述中，错误的是（ ）。
A.中断或异常发生时，CPU处于内核态
B.每个系统调用都有对应的内核服务例程
C.中断处理程序开始执行时，CPU处于内核态
D.系统添加新类型设备时，需注册相应的中断服务例程
24.下列选项中，操作系统在终止进程时不一定执行的是（ ）。
A.终止子进程 B.回收进程占用的设备
C.释放进程控制块 D.回收为进程分配的内存
25.在支持页式存储管理的系统中，进程切换时操作系统需要执行的操作是（ ）。
I. 更新程序计数器的值 II.更新栈基址寄存器的值
Ⅲ.更新页表基地址寄存器的值
A. 仅Ⅲ B.仅I、Ⅱ
C. 仅I、Ⅲ D. I、Ⅱ、Ⅲ
26.文件系统需占用部分外存空间记录空闲块位置。下列方法中，占用外存空间的大小与当前空
闲块数量无关的是（ ）。
A.位图法 B.空闲表法
C.成组链接法 D.空闲链表法
27.下列算法中，每次回收分区时仅合并大小相等的空闲分区的是（ ）。
A.伙伴算法 B.最佳适应算法
C.最坏适应算法 D.首次适应算法
28.若进程P中的线程T先打开文件，得到文件描述符fd，再创建两个线程 Ta 和 Tb，则下列
资源中，Ta 与Tb可共享的是（ ）。
I.进程 P的地址空间 Ⅱ.线程T的栈 Ⅲ.文件描述符fd
A. 仅I B.仅I、Ⅲ
C. 仅Ⅱ、Ⅲ D. I、Ⅱ、Ⅲ
29.下列系统调用的实现中，包含文件按名查找功能的是（ ）。
A. open( ) B. read( )
C. write( ) D. close( )
30.假设某系统使用时间片轮转调度算法进行CPU调度，时间片大小为5ms，系统共有10个进
程，初始时均处于就绪队列，执行结束前仅处于执行态或就绪态。若队尾的进程 P 所需 CPU时间最短，时间为25ms，在不考虑系统开销的情况下，则进程P的周转时间为（ ）。
A. 200ms B. 205ms
C. 250ms D. 295ms
31.键盘中断服务例程执行结束时，所输入数据的存放位置是（ ）。
A.用户缓冲区
B. CPU中的通用寄存器
C.内核缓冲区
D.键盘控制器的数据寄存器
32.某磁盘的磁道数为400(磁道号为0~399)，采用循环扫描算法（CSCAN）进行磁盘调度，完
成对200号磁道的请求后，磁头向磁道号减小的方向移动。若还有7个磁盘请求，对应的磁道
号分别为300，120，110，0，160，210，399，则完成上述磁盘访问请求后磁头移动的距离是
（ ）。
A.599 B.619 C. 788 D. 799
33.若某分组交换网络及每段链路的带宽如下图所示，则H1到H2的最大吞吐量约为（ ）。
A. 1 Mb/s B. 10 Mb/s C. 100 Mb/s D. 1000 Mb/s
34.在下列二进制数字调制方法中，需要2个不同频率载波的是（ ）。
A. ASK B. PSK C. FSK D. DPSK
35.如题35图所示的支持VLAN 划分的交换机，已按端口划分了3个VLAN，部分端口连接主
机的IP地址和MAC 地址如图中所示，ARP 表结构为。下列选项
中，不会出现在 H4的ARP表中的是（ ）。
A. 192.168.3.81，00-18-A2-3B-36-21， 14: 32:00
B. 192.168.3.91，00-3E-C2-39-12-B5， 14: 37:00
C. 192.168.3.125，00-E5-78-4A-09-B2，14:45:00
D. 192.168.3.129，00-08-6E-05-A7-82，14:52:0036.在采用 CSMA/CA 的 802.11 无线局域网中，DIFS=128μs，SIFS=28μs，RTS、CTS 和 ACK
帧的传输时延分别是3μs、2μs 和2μs，忽略信号传播时延。若主机A欲向AP发送一个总长度
为1998 B 的数据帧，无线链路带宽为54Mb/s，则隐藏站B收到 AP发送的 CTS帧时，设置
的网络分配向量NAV的值是（ ）。
A. 326μs B. 354μs C. 385μs D. 513μs
37.主机甲通过选择重传(SR)滑动窗口协议向主机乙发送帧的部分过程如题37图所示，Fx为数
据帧，ACKx 为确认帧，x 是位数为 3 比特的序号。乙只对正确接收的数据帧进行独立确认，
发送窗口与接收窗口大小相同且均为最大值。甲在t 时刻和t 时刻发送的数据帧分别是（ ）。
1 2
A. F1，F3 B. F1，F4 C. F3，F1 D. F4，F1
38. 假设主机 H 通过 TCP 向服务器发送长度为 3000B 的报文，往返时间 RTT=10ms，最长报
文段寿命MSL=30s，最大报文段长度MSS=1 000 B，忽略TCP 段的传输时延，报文传输结束
后 H 首先请求断开连接，则从 H 请求建立 TCP 连接时刻起，到 H 进入 CLOSED 状态为止，
所需的时间至少是（ ）。
A. 30.03 s B. 30.04 s C. 60.03 s D. 60.04 s
39. 若UDP协议在计算校验和过程中，计算得到中间结果为1011 1001 1011 0110时，还需要加上最后一个16位数0110 0101 1100 0101，则最终计算得到的校验和是（ ）。
A. 0001 1111 0111 1011
B. 0001 1111 0111 1100
C. 1110 0000 1000 0011
D. 1110 0000 1000 0100
40. 若浏览器不支持并行 TCP 连接，使用非持久的 HTTP/1.0 协议请求浏览 1 个 Web 页，该
页中引用同一网站上 7 个小图像文件，则从浏览器为传输 Web 页请求建立 TCP 连接开始，
到接收完所有内容为止，所需要的往返时间RTT数至少是（ ）。
A. 4 B. 9 C. 14 D. 16
二、综合应用题：41～47小题，共 70分。
41.（13分）2023年10月26日，神州十七号载人飞船发射取得圆满成功，再次彰显了中国航
天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开
展，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向
图的拓扑序列问题。已知有向图G采用邻接矩阵存储，类型定义如下。
typedef struct //图的类型定义
{
int numVertices，numEdges; //图的顶点数和有向边数
char VerticesList[MAXV]; //顶点表，MAXV 为已定义常量
int Edge[MAXV][MAXV]; //邻接矩阵
}MGraph;
请设计算法: int uniquely(MGraph G)，判定G 是否存在唯一的拓扑序列，若是，则返回1，否
则返回0。要求如下。
（1）给出算法的基本设计思想。（4分）
（2）根据设计思想，采用C或 C++语言描述算法，关键之处给出注释。（9分）42.（10分）将关键字序列 20，3，11，18，9，14，7 依次存储到初始为空、长度为 11的散
列表 HT 中，散列函数 H（key）=（key×3）%11。H（key）计算出的初始散列地址为H ，
0
发生冲突时探查地址序列是 H ，H ，H ，…，其中，H =（H +k2）%11，k=1，2，3，…。
1 2 3 k 0
请回答下列问题。
（1）画出所构造的 HT，并计算 HT的装填因子。（6分）
（2）给出在 HT 中查找关键字 14 的关键字比较序列。（2分）
（3）在 HT中查找关键字8，确认查找失败时的散列地址是多少？（2分）43.（13分）假定计算机M 字长为32位，按字节编址，采用32位定长指令字，指令add、slli
和1w的格式、编码和功能说明如图43（a）图所示。
指令 31 25 24 20 19 15 14 12 11 7 6 0 指令功能说明
add 0000000 rs2 rs1 000 rd 0110011 R[rd]←R[rs1]+ R[rs2]
slli 0000000 shamt rs1 010 rd 0010011 R[rd]← R[rs1]<
