模拟卷 5
选择题
第 1~40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个选项最符合试题要求。
1
假设栈的容量为 3,入栈的序列为 1,2,3,4,5,则出栈的序列可能为( )。
【解析】
栈的容量为 3,入栈序列固定为 1,2,3,4,5。出栈序列必须符合栈的后进先出规则,且受容量限制。
对于选项 A(3,2,1,5,4):
- 先入栈 1,2,3(栈满),出栈 3,2,1,栈空。
- 再入栈 4,入栈 5,出栈 5,4。
操作过程中栈内元素数始终不超过 3,且符合出栈序列,因此可能。
对于选项 B(1,5,4,3,2):
- 出栈 1 后,需出栈 5,但 5 尚未入栈。入栈 2,3,4 后栈满,无法直接入栈 5;若先出栈元素则破坏序列顺序。
- 要使 5 先出栈,需在 5 入栈时栈中包含 4,3,2,但容量仅为 3,无法同时容纳 4 个元素,因此不可能。
对于选项 C(5,4,3,2,1):
- 需先出栈 5,但 5 最后入栈。入栈 1,2,3 后栈满,入栈 4 需先出栈元素,而出栈会破坏序列以 5 开始,因此不可能。
对于选项 D(4,3,2,1,5):
- 需先出栈 4,但入栈 1,2,3 后栈满,入栈 4 需先出栈元素,而出栈会导致序列首元素不为 4,因此不可能。
综上,只有选项 A 可能。
2
若以 1234 作为双端队列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是( )。
【解析】
输入序列为 1234,需找出既不能由输入受限双端队列(插入仅在一端,删除可在两端)也不能由输出受限双端队列(删除仅在一端,插入可在两端)得到的输出序列。
- 选项 A(1234):两种受限队列均可通过顺序插入和删除得到。
- 选项 B(4132):输入受限队列可通过插入 1,2,3,4 后依次删除后端 4、前端 1、后端 3、前端 2 得到;输出受限队列无法得到,因为需要插入 4 前队列前端为 1 且后续顺序为 3,2,但无法通过插入 1,2,3 得到所需队列[1,3,2]。
- 选项 C(4231):输入受限队列中,插入 1,2,3,4 后删除后端 4,队列变为[1,2,3],2 不在端部,无法直接输出 2 而不先输出 1 或 3;输出受限队列中,需要插入 4 前队列为[2,3,1],但无法通过插入 1,2,3 得到该队列。因此两种队列均无法得到 4231。
- 选项 D(4213):输入受限队列无法得到(类似 4231 的原因),但输出受限队列可通过插入 1,2,3 得到队列[2,1,3],再插入 4 前端后依次删除得到 4213。
综上,4231 既不能由输入受限也不能由输出受限双端队列得到。
3
在下列遍历算法中,在遍历序列中叶结点之间的次序可能与其他算法不同的算法是( )。
【解析】
先序、中序和后序遍历算法均属于深度优先遍历,其递归或迭代过程都遵循先处理左子树、后处理右子树的原则。因此,对于任意二叉树,这三种遍历算法访问叶结点的次序始终相同:左子树中的所有叶结点都先于右子树中的所有叶结点被访问,且左、右子树内部叶结点的相对顺序也一致。而层次遍历算法采用广度优先策略,按层次从上到下、从左到右访问节点。由于叶结点可能分布在不同层次,其访问次序取决于层次和同一层次中的左右位置,可能与深度优先遍历的叶结点次序不同。例如,对于根节点有左子节点(含两个叶结点)和右子节点(为叶结点)的二叉树,先序、中序和后序遍历的叶结点次序均为左子树中的两个叶结点先于右子叶结点,而层次遍历则先访问右子叶结点(位于第二层),再访问左子树中的叶结点(位于第三层)。因此,层次遍历算法的叶结点次序可能与其他算法不同。
4
一般说来,若深度为 的 个结点的二叉树具有最小路径长度时,第 层(根为第 1 层)上的结点数为( )。
【解析】
对于深度为 k 且具有最小路径长度的二叉树,为了使所有结点到根的路径长度之和最小,树应尽可能平衡,即前 k-1 层完全填满。前 k-1 层的结点总数为 ,剩余结点全部位于第 k 层。因此,第 k 层的结点数为 ,对应选项 A 和 B(两者表达式相同)。选项 C 和 D 与推导结果不符,故正确答案为 A。
5
利用逐个插入建立序列 (50,72,43,85,75,20,35,45,65,30) 对应的二叉排序树后,要查找元素 30 要进行的元素间比较次数是( )。
【解析】 考查二叉排序树的构造和查找。按题中数据的输入次序,建立的二叉排序树如右图所示。查找元素 30 需要依次比较的元素为 50,43,20,35,30,比较次数为 5 次。
50
/ \
43 72
/ \ / \
20 45 65 85
\ /
35 75
/
30
6
由 4 棵树组成的森林中,第一、第二、第三和第四棵树中的结点数分别为 30、10、20、5,当把森林转换成二叉树后,对应二叉树中根结点的右子树的左子树的结点数为( )。
【解析】
将森林转换成二叉树时,采用“左孩子右兄弟”的表示法。对于由多棵树组成的森林,转换规则为:取第一棵树的根作为二叉树的根,根的左子树由第一棵树中根的子树森林转换而成,根的右子树由剩余树组成的森林转换而成。
给定森林中四棵树的结点数分别为 30、10、20、5。转换后二叉树的结构如下:
- 二叉树的根对应第一棵树的根。
- 根的左子树由第一棵树中除根外的 29 个结点转换而成,结点数为 29。
- 根的右子树由第二、三、四棵树(结点数共 10+20+5=35)转换而成。
根的右子树本身也是一棵二叉树,其根对应第二棵树的根。该右子树的左子树由第二棵树中除根外的子树森林转换而成,第二棵树有 10 个结点,除根外有 9 个结点,因此该左子树的结点数为 9。
故根结点的右子树的左子树的结点数为 9。
7
如果具有 个顶点的图是一个环,则它有( )棵生成树。
【解析】 由于图是一个环,它包含 n 个顶点和 n 条边。生成树是连接所有顶点且无环的子图,对于环图,只需移除任意一条边即可打破环并得到一棵生成树。环中共有 n 条边,每条边的移除对应一棵不同的生成树,因此生成树的数量为 n。
8
假设有 个顶点 条边的有向图用邻接表表示,则删除与某个顶点 相关的所有边的时间复杂度为( )。
【解析】
在有向图的邻接表表示中,每个顶点维护一个链表存储其出边。删除与顶点 相关的所有边包括两部分:一是删除顶点 的所有出边,二是删除所有指向顶点 的入边。删除出边只需清空顶点 的邻接链表,时间复杂度为 ,其中 。删除入边则需要遍历所有顶点的邻接链表,检查每条边是否指向 ,并在找到时删除。遍历所有链表需访问 个顶点和 条边,时间复杂度为 。因此,总时间复杂度为 。
9
折半查找有序表 (2,10,25,35,40,65,70,75,81,82,88,100),若查找元素 75,需依次与表中元素( )进行比较。
【解析】 考查折半查找的查找过程。有序表长度为 12,依据折半查找的思想:
- 第一次查找第 个元素,即 65;
- 第二次查找第 个元素,即 81;
- 第三次查找第 个元素,即 70;
- 第四次查找第 个元素,即 75。
比较的元素依次为 65、81、70、75。对应的折半查找判定树如下图所示。
65
/ \
25 81
/ \ / \
2 35 70 88
/ \ \ / \
10 40 75 82 100
10
堆排序分为两个阶段,其中第一阶段将给定的序列建成一个堆,第二阶段逐次输出堆顶元素。设给定序列{48,62,35,77,55,14,35,98},若在堆排序的第一阶段将该序列建成一个堆(大根堆),那么交换元素的次数为( )。
【解析】 考查初始堆的构造过程。首先对以第 个结点为根的子树筛选,使该子树成为堆,之后向前依次对各结点为根的子树进行筛选,直到筛选到根结点。序列 建立初始堆的过程如下所示:

11
对 {05,46,13,55,94,17,42} 进行基数排序,一趟排序的结果是( )。
【解析】
基数排序通常从最低有效位(LSD)开始,对数字的每一位进行稳定排序。给定序列 {05,46,13,55,94,17,42} 均为两位数,第一趟排序根据个位数字进行。
首先,提取每个数字的个位:05(个位 5)、46(个位 6)、13(个位 3)、55(个位 5)、94(个位 4)、17(个位 7)、42(个位 2)。
按照个位数字分配桶(0-9),保持稳定性:
- 个位 2:42
- 个位 3:13
- 个位 4:94
- 个位 5:05、55(保持原序,05 在 55 前)
- 个位 6:46
- 个位 7:17
按桶顺序收集数字,得到序列:42,13,94,05,55,46,17。这与选项 C 一致。
选项 A 是原始序列;选项 B 是完全排序后的结果;选项 D 不符合个位排序顺序。因此,一趟排序结果为 C。
12
计算机中,与 CPU 的 CPI 无关的因素是( )。
【解析】 CPI(Cycles Per Instruction)表示每条指令的平均时钟周期数,它衡量 CPU 执行指令的效率。时钟频率决定 CPU 的时钟速度,即每秒钟的时钟周期数,它影响时钟周期时间(时钟周期时间的倒数),但并不直接改变每条指令所需的周期数,因此与 CPI 无关。系统结构(B)定义了计算机的整体设计,包括指令执行方式,直接影响 CPI;指令集(C)决定了指令的复杂性和执行所需的周期数,与 CPI 密切相关;计算机组织(D)涉及硬件实现如流水线、缓存等,通过优化指令执行来降低 CPI。因此,只有时钟频率与 CPI 无关。
13
若数据在存储器中以小端方式存放,则十六进制数 12345678H 按字节地址从小到大依次为( )。
【解析】 小端方式(Little-endian)存储规则为:多字节数据中,最低有效字节存放在最低地址,最高有效字节存放在最高地址。对于十六进制数 12345678H,这是一个 32 位数据,占 4 个字节,从高到低字节依次为 12H、34H、56H、78H。按小端方式存放时,地址从小到大依次存储最低有效字节到最高有效字节,即 78H、56H、34H、12H,组合起来即为 78563412H。因此选项 A 正确。
14
按 IEEE754 标准规定的 32 位浮点数(单精度浮点数)41A4C000H 对应的十进制数是( )。
【解析】 首先,将十六进制数 41A4C000H 转换为二进制:0100 0001 1010 0100 1100 0000 0000 0000。
按照 IEEE754 单精度浮点数格式:
- 第 1 位为符号位 ;
- 第 2–9 位为指数位 (8 位);
- 第 10–32 位为尾数位 (23 位)。
具体分析如下:
- 符号位 ,表示正数。
- 指数位
,转换为十进制为
。IEEE754 中指数采用偏置表示,偏置量为
,因此实际指数
- 尾数位
,表示小数部分。计算
的十进制值:对应二进制小数位中,
,
,
,
为 1,其余为 0,求和得
IEEE754 中尾数包含隐含的 1,因此实际尾数
浮点数的值为
因此,对应的十进制数为 ,选项 D 正确。
15
设有一主存-Cache 层次的存储器,其主存容量 1MB,Cache 容量 16KB,每字块有 8 个字,每字 32 位,采用直接地址映像方式,若主存地址为 35301H,且 CPU 访问 Cache 命中,则该主存块在 Cache 的第( )字块中(Cache 起始字块为第 0 字块)。
【解析】
主存容量为 1MB,即
字节,因此主存地址为 20 位。
Cache 容量为 16KB,即
字节。
每个字为 32 位(即 4 字节),每个字块包含 8 个字,因此块大小为
字节,块内偏移需要
位。
Cache 共有
块,索引需要
位。
在直接映射方式下,主存地址划分为:标签(高 6 位)、索引(中间 9 位)、偏移(低 5 位)。
给定主存地址 35301H,转换为二进制为 0011 0101 0011 0000 0001(共 20 位)。
偏移量为低 5 位(00001),索引为位 5 至位 13(010011000),转换为十进制为
。
也可通过计算主存块号得到:地址 35301H 对应十进制 217857 字节,块号为
(余数为 1),Cache 块号为
。
因此,该主存块位于 Cache 的第 152 字块中。
16
在页面尺寸为 4KB 的页式存储管理中,页表中的内容如下图所示,则物理地址 32773 对应的逻辑地址为( )。
【解析】 首先,页面尺寸为 4KB,即 4096 字节。物理地址 32773 可以分解为页框号和页内偏移:页框号 = 32773 ÷ 4096 = 8(因为 4096 × 8 = 32768),页内偏移 = 32773 - 32768 = 5。然后,根据页表内容,页框号 8 对应虚页号 3。因此,逻辑地址由虚页号和页内偏移组成:逻辑地址 = 虚页号 × 页面尺寸 + 页内偏移 = 3 × 4096 + 5 = 12288 + 5 = 12293。故正确答案为 C. 12293。
17
在通用计算机指令系统的二地址指令中,操作数的物理位置可安排在( )。
I. 一个主存单元和缓冲存储器
II. 两个数据寄存器
III. 一个主存单元和一个数据寄存器
IV. 一个数据寄存器和一个控制存储器
V. 一个主存单元和一个外存单元
【解析】
在通用计算机指令系统的二地址指令中,操作数的物理位置是指指令能够直接寻址或指定的存储位置。分析各选项:缓冲存储器(如缓存)通常对程序员透明,指令不能直接寻址缓存地址,因此 I 不正确;两个数据寄存器(II)是常见的安排,如寄存器 - 寄存器指令;一个主存单元和一个数据寄存器(III)也常见,如寄存器 - 内存指令;控制存储器用于存储微程序,不是数据操作数的存储位置,因此 IV 不正确;外存单元(如磁盘)需要通过 I/O 机制访问,指令不能直接寻址,因此 V 不正确。综上,只有 II 和 III 是合理的安排,对应选项 B。
18
某微机的指令格式如下所示:

其中 D 为位移量,X 为寻址特征位。
X=00:直接寻址;用变址寄存器 X1 进行变址;
X=10:用变址寄存器 X2 进行变址;X=11:相对寻址
设 (PC) = 234H,(X1) = 0037H,(X2) = 1122H,则指令 2222H 的有效地址是( )。
【解析】 指令格式中,操作码占据位 15 至 10,寻址特征位 X 占据位 9 至 8,位移量 D 占据位 7 至 0。指令 2222H 的二进制表示为 0010 0010 0010 0010。分解后,位 9 至 8 为 10,对应 X=10;位 7 至 0 为 00100010,即 D=22H。根据寻址特征,X=10 表示使用变址寄存器 X2 进行变址寻址,有效地址计算公式为 (X2) + D。已知 (X2)=1122H,D=22H 为 8 位正数,扩展为 16 位后仍为 0022H,因此有效地址为 1122H + 0022H = 1144H。选项 B 符合计算结果。
19
某机采用微程序控制方式,微指令字长 24 位,采用水平型编码控制的微指令格式,断定方式。共有微命令 30 个,构成 4 个互斥类,各包含 5 个、8 个、14 个和 3 个微命令,外部条件共 3 个。则控制存储器的容量应该为( )。
【解析】 微指令字长为 24 位,控制字段采用水平型编码。微命令分为 4 个互斥类,每类所需的位数需包含“无操作”状态,计算如下:
- 第一类有 5 个微命令,需 位;
- 第二类有 8 个微命令,需 位;
- 第三类有 14 个微命令,需 位;
- 第四类有 3 个微命令,需 位。
控制字段共需 位。
顺序字段占 位,用于断定方式下的地址生成。外部条件共有 3 个,条件选择字段需 3 位(可编码 8 种转移条件,满足 3 个外部条件及其他功能),下地址字段占 位。下地址字段 8 位可寻址 个微指令单元,因此控制存储器容量为 位。
20
数据总线的宽度由总线的( )定义。
【解析】
数据总线的宽度指的是总线一次能传输的数据位数,这由数据线的数量决定。在总线的各类特性中,功能特性定义了各信号线的具体功能,如地址线、数据线、控制线等。数据总线的宽度直接与数据线的功能相关,因此它由功能特性定义。
物理特性涉及总线的机械连接方式(如插头、插座),电气特性涉及电压、电流等参数,时间特性则关注信号时序关系。这些特性均不直接决定数据总线的宽度,故其他选项不正确。因此,本题选择 B。
21
DMA 方式的接口电路中有程序中断部件,其作用包括( )。
I. 实现数据传送
II. 向 CPU 提出总线使用权
III. 向 CPU 提出传输结束
IV. 检查数据是否出错
【解析】 考查 DMA 方式中的中断与中断传输方式的区别。前者是向 CPU 报告数据传输结束,后者是传送数据,另外 DMA 方式中的中断不包括检查是否出错,而是报告错误。
注意:DMA 方式与程序中断方式的比较如下。
① DMA 传送数据的方式是靠硬件传送,而程序传送方式是由程序来传送。
② 程序中断方式需要中断 CPU 的现行程序,需要保护现场,而 DMA 方式不需要中断现行程序。
③ 程序中断方式需要在一条指令执行结束才能得到响应,而 DMA 方式则可以在指令周期内的任意存储周期结束时响应。
④ DMA 方式的优先级高于程序中断方式的优先级。
22
某机有四级中断,优先级从高到低为 1→2→3→4。若将优先级顺序修改,改后 1 级中断的屏蔽字为 1101,2 级中断的屏蔽字为 0100,3 级中断的屏蔽字为 1111,4 级中断的屏蔽字为 0101,则修改后的优先顺序从高到低为( )。
【解析】 首先,理解屏蔽字的含义:每个中断的屏蔽字表示当处理该中断时,哪些中断被屏蔽。屏蔽字为 4 位二进制数,假设位顺序对应中断 1、2、3、4。若某位为 1,则屏蔽对应中断;若为 0,则不屏蔽。根据中断优先级规则,高优先级中断可以屏蔽低优先级中断,而低优先级中断不能屏蔽高优先级中断。因此,从屏蔽字可以推导优先级关系:若中断 i 的屏蔽字中对应中断 j 的位为 1,则中断 j 的优先级低于中断 i;若为 0,则中断 j 的优先级高于中断 i。
给定屏蔽字:中断 1 为 1101,中断 2 为 0100,中断 3 为 1111,中断 4 为 0101。分析每个屏蔽字:
- 中断 1 的屏蔽字 1101:位 3 为 0,说明中断 3 优先级高于中断 1;位 2 和位 4 为 1,说明中断 2 和中断 4 优先级低于中断 1。
- 中断 2 的屏蔽字 0100:位 1、位 3、位 4 均为 0,说明中断 1、3、4 优先级均高于中断 2。
- 中断 3 的屏蔽字 1111:所有位为 1,说明中断 3 屏蔽所有中断,因此中断 3 优先级最高。
- 中断 4 的屏蔽字 0101:位 1 和位 3 为 0,说明中断 1 和中断 3 优先级高于中断 4;位 2 为 1,说明中断 2 优先级低于中断 4。
综合上述关系:中断 3 优先级最高;中断 1 优先级高于中断 4 和中断 2;中断 4 优先级高于中断 2。因此,修改后的优先级从高到低为 3→1→4→2,对应选项 B。验证屏蔽字与优先级顺序一致,确认正确。
23
相对采用单一内核结构,采用微内核结构设计和实现操作系统有诸多好处,但是( )不是微内核的优势。
【解析】 微内核结构通过最小化内核功能,仅保留进程调度、内存管理等核心服务,而将文件系统、设备驱动等其他服务置于用户空间。这种设计提升了系统的安全性和可靠性:用户空间服务的故障不易蔓延至内核,从而增强了隔离性(对应选项 C 和 D)。同时,微内核支持模块化扩展,添加新任务时只需在用户空间实现,无需修改内核,提高了灵活性(对应选项 B)。
然而,微内核的劣势在于效率:由于服务分布在用户空间,需要频繁的进程间通信和上下文切换,这引入了额外开销,导致性能通常不如单一内核结构高效。因此,选项 A“使系统更高效”并非微内核的优势,反而是其常见缺点。
24
有一个计数信号量 S,若干个进程对 S 进行了 28 次 P 操作和 18 次 V 操作后,信号量 S 的值为 0。然后又对信号量 S 进行了 3 次 V 操作。此时有( )个进程等待在信号量 S 的队列中。
【解析】 首先,设信号量 S 的初始值为 X。根据信号量的操作规则,P 操作会使 S 减 1,V 操作会使 S 加 1。经过 28 次 P 操作和 18 次 V 操作后,S 的值为 X - 28 + 18 = X - 10。已知此时 S 的值为 0,因此 X - 10 = 0,解得初始值 X = 10。
然后,在 S 值为 0 的情况下,又进行了 3 次 V 操作。每次 V 操作使 S 加 1,所以 S 变为 0 + 3 = 3。
在计数信号量中,当 S 的值大于或等于 0 时,表示没有进程等待在信号量的队列中。具体地,若 S > 0,表示有可用资源;若 S = 0,表示资源刚好用完且无进程等待;若 S < 0,其绝对值表示等待进程数。在 28 次 P 和 18 次 V 操作后 S = 0,说明等待队列已空。后续 3 次 V 操作使 S 变为 3,S 仍为正数,因此等待队列中依然没有进程。
故此时有 0 个进程等待在信号量 S 的队列中。
25
进程从运行状态到等待状态可能是( )。
【解析】 进程从运行状态进入等待状态通常是由于进程请求某个资源或等待某个事件,但该资源暂时不可用或事件尚未发生。P 操作(即 wait 操作)是同步机制中的一种,用于申请资源。当运行进程执行 P 操作时,如果信号量值小于等于 0,表示资源不足,该进程会被阻塞并进入等待状态,因此选项 A 正确。
其他选项中,B 和 C 通常导致进程从运行状态转为就绪状态:进程调度程序的调度可能将运行进程切换为就绪状态以让其他进程运行;时间片用完也会触发调度,使进程从运行转为就绪。D 选项的 V 操作(即 signal 操作)用于释放资源,可能唤醒等待中的进程,但执行 V 操作的进程本身不会进入等待状态。
因此,只有 A 选项描述了进程从运行状态到等待状态的可能情况。
26
关于临界区问题(critical section problem)的一个算法(假设只有进程 P0 和 P1 可能会进入该临界区)如下(i 为 0 或 1),该算法( )。
Repeat
retry: if(turn!=i) turn=i;
if(turn!=i) goto retry;
turn=1-i;
临界区
turn=0;
剩余区
until false;
【解析】
该算法不能保证进程互斥进入临界区。分析两个进程 P0 和 P1 的执行流程:假设初始时共享变量 turn=0,P0 首先执行,检查 turn!=0 为假,跳过 turn=0 的设置,再检查 turn!=0 为假,不跳转,然后设置 turn=1 并进入临界区。此时 P1 也开始执行,检查 turn!=1 为假,跳过 turn=1 的设置,再检查 turn!=1 为假,不跳转,设置 turn=0 并进入临界区。这样,P0 和 P1 同时处于临界区,违反了互斥条件。
虽然互斥无法保证,但算法不会导致“饥饿”(即某个进程永远无法进入临界区)。因为每个进程在尝试进入时,都会通过循环检查 turn 是否等于自己的标识 i。无论 turn 初始值如何,进程在执行中总会将 turn 设置为对方或 0,使得另一个进程在后续尝试中能够通过检查并进入临界区。例如,P0 退出临界区时设置 turn=0,之后 P1 尝试时可能先设置 turn=1 再检查通过,从而进入临界区。两个进程在竞争中有机会交替进入,没有进程会被永久阻塞。
因此,该算法不能保证互斥,但不会出现饥饿。
27
设 为同类资源数, 为系统中并发进程数。当 个进程共享 个互斥资源时,每个进程的最大需求是 ,则下列情况会出现系统死锁的是( )。
【解析】 系统死锁的一个常见条件是当所有进程都持有部分资源并等待更多资源时,资源总数不足以满足任何进程的剩余需求。具体来说,如果每个进程的最大需求为 w,那么在最坏情况下,每个进程都已获得 w-1 个资源并等待最后一个资源。此时,已分配资源总数为 n(w-1),如果资源总数 m 不超过 n(w-1),即 m ≤ n(w-1),则系统可能陷入死锁。
分析各个选项:
A. m=2, n=1, w=2:计算 n(w-1)=1×(2-1)=1,m=2>1,不会死锁。
B. m=2, n=2, w=1:计算 n(w-1)=2×(1-1)=0,m=2>0,不会死锁。
C. m=4, n=3, w=2:计算 n(w-1)=3×(2-1)=3,m=4>3,不会死锁。
D. m=4, n=2, w=3:计算 n(w-1)=2×(3-1)=4,m=4 恰好等于 n(w-1),此时两个进程各获得 2 个资源后,所有资源被占用,每个进程还需 1 个资源才能完成,但无可用资源,因此系统会出现死锁。
28
总体上说,“按需调页”(Demand-paging)是一个很好的虚拟内存管理策略。但是,有些程序设计技术并不适合于这种环境。例如,( )。
【解析】 按需调页(Demand-paging)是一种虚拟内存管理策略,它在页面被实际访问时才将其加载到内存中,依赖于程序的局部性原理来减少页面错误和提高性能。适合该环境的程序通常具有良好时间或空间局部性,即访问模式集中或连续。
堆栈操作集中在栈顶,具有高度局部性;线性搜索顺序访问元素,连续内存访问利于页面重用;矢量运算通常涉及顺序或规律数据访问,也能有效利用页面。这些技术都能较好适应按需调页。
然而,二分搜索需要在有序数组中反复跳跃访问中间元素,访问模式非连续且不可预测,导致频繁跨页面访问。这种低局部性会引发大量页面错误,显著降低系统效率,因此不适合按需调页环境。
29
在某请求分页系统中,内存的存取时间为 1μs。若有一个可用的空页被置换的页表被修改,则它处理一个缺页中断需要 8μs;若被置换的页已被修改,则处理一个缺页中断因增加写回外存时间而需要 20μs。假设所有访问页表都在 TLB 中,且 TLB 中存储有页面是否在主存中的信息。假定 70% 被置换的页被修改过,为保证有效存取时间不超过 2μs,可接受的最大缺页中断率约为( )。
【解析】
有效存取时间由无缺页和有缺页两种情况组成:
- 无缺页时,存取时间为内存存取时间 ;
- 有缺页时,存取时间为缺页中断处理时间,该时间已包含后续内存访问。
根据题意,缺页中断处理时间取决于被置换页是否被修改:
- 的概率为 (已修改);
- 的概率为 (未修改)。
平均处理时间为
设缺页中断率为
,则有效存取时间为
要求
,即
解得
即约 。
因此,可接受的最大缺页中断率约为 。
30
在某个计算机系统中,内存的分配采用按需调页方式,测得当前 CPU 的利用率为 8%,硬盘交换空间的利用率为 55%,硬盘的繁忙率为 97%,其他设备的利用率可以忽略不计,由此断定系统发生异常,则解决方法是( )。
I. 加大交换空间容量
II. 增加内存容量
III. 增加 CPU 数量
IV. 安装一个更快的硬盘
V. 减少多道程序的道数
【解析】 在按需调页系统中,CPU 利用率仅为 8%,表明 CPU 经常空闲;硬盘交换空间利用率为 55%,说明交换空间尚有剩余;但硬盘繁忙率高达 97%,表明硬盘持续进行大量 I/O 操作,这通常是因为物理内存不足导致频繁的页面交换(抖动)。
CPU 利用率低是因为进程频繁等待硬盘 I/O,而非 CPU 本身不足,因此增加 CPU 数量(III)无效。交换空间利用率未满,加大其容量(I)不能解决频繁交换问题。安装更快硬盘(IV)可能缩短单次交换时间,但无法从根本上减少交换频率,不是最佳方案。
增加内存容量(II)可以直接减少缺页和交换操作,从而降低硬盘繁忙率并提高 CPU 利用率;减少多道程序的道数(V)能减轻内存压力,减少进程竞争内存导致的抖动。因此,II 和 V 是直接有效的解决方法。
31
信息在外存空间的排列也会影响存取等待时间。考虑几个逻辑记录 A、B、C、…、J,它们被存放在磁盘上,每个磁道存放 10 个记录,安排如表 1 所示。
表 1 每个磁道存放 10 个记录
| 物理块 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 逻辑记录 | A | B | C | D | E | F | G | H | I | J |
假定要经常顺序处理这些记录,磁盘旋转速度为 20ms/r,处理程序读出每个记录后花 4ms 进行处理。考虑对信息的分布进行优化,如表 2 所示,相比之前的信息分布,优化后的时间缩短了( )。
表 2 优化后磁道存放的 10 个记录
| 物理块 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 逻辑记录 | A | H | E | B | I | F | C | J | G | D |
【解析】 题中磁盘旋转速度为 20 ms/r,每个磁道存放 10 个记录,因此读出一个记录的时间为 。
1)对于第一种记录分布的情况,读出并处理记录 A 需要 6 ms,则此时读写磁头已转到记录 D 的开始处,因此为了读出记录 B,必须再转一圈少两个记录(从记录 D 到记录 B)。后续 8 个记录的读取及处理与此相同,但最后一个记录的读取与处理只需 6 ms。于是,处理 10 个记录的总时间为
2)对于第二种记录分布的情况,读出并处理记录 A 后,读写磁头刚好转到记录 B 的开始处,因此立即就可读出并处理,后续记录的读取与处理情况相同。共选择 2.7 圈。最后一个记录的读取与处理只需 6 ms。于是处理 10 个记录的总时间为
综上,信息分布优化后,处理的时间缩短了 。
32
下列有关虚拟设备的论述中,正确的是( )。
【解析】 本题考查虚拟设备的概念。虚拟设备是指采用虚拟技术将一台独占设备转换为若干台逻辑设备的情况。这种设备并不是物理地变成共享设备,一般的独享设备也不能转变为共享设备,否则会导致很多不可预知的错误,而是用户在使用它们时“感觉”是共享设备,是逻辑的概念。引入虚拟设备的目的是为了克服独占设备速度慢、利用率低的特点。
33
电路交换的优点有( )。
I. 传输时延小
II. 分组按序到达
III. 无需建立连接
IV. 线路利用率高
【解析】 电路交换、分组交换、报文交换的特点是重要的考查点。主要有两种考查方式:一、直接考查某一种(或多种)交换方式的特点,辨别选项的正误;二、给定应用背景,问适用哪一种交换方式,比较灵活,间接考查它们的特点。其中,电路交换是面向连接的,一旦连接建立,数据便可直接通过连接好的物理通路到达接收端,因此传输时延小;由于电路交换是面向连接的,可知传送的分组必定是按序到达的;但在电路交换中,带宽始终被通信的双方独占,利用率就低了。
34
以下滑动窗口协议中,一定按序接收到达的分组的有( )。
I. 停止—等待协议
II. 后退 N 帧协议
III. 选择重传协议
【解析】 停止—等待协议的发送窗口和接收窗口大小均为 1,发送方每发送一个分组后必须等待确认,才能发送下一个分组。接收方一次只处理一个分组,因此分组到达的顺序与发送顺序完全一致,一定按序接收。
后退 N 帧协议中,接收方只按序接收分组。如果某个分组丢失或出错,发送方会重传该分组及之后的所有分组,接收方对乱序到达的分组直接丢弃,确保只有顺序正确的分组被接受,因此也保证按序接收。
选择重传协议允许接收方缓存乱序到达的分组,即分组到达时可能不是按序的,但接收方会将这些分组暂时存储,等待缺失分组到达后再按序交付给上层。因此,分组到达时不一定按序,不满足“一定按序接收到达的分组”的条件。
综上,只有停止—等待协议和后退 N 帧协议一定按序接收分组,对应选项 A。
35
以下几种 CSMA 协议中,什么协议在监听到介质是空闲时一定发送( )。
I. 1-坚持 CSMA
II. p-坚持 CSMA
III. 非坚持 CSMA
【解析】 本题考查 CSMA 协议的各种监听。1-坚持 CSMA 和非坚持 CSMA 检测到信道空闲时,都立即发送数据帧,它们之间的区别是:如果检测到媒体忙时,是否持续监听媒体(1-坚持)还是等待一个随机的延迟时间后再监听(非坚持)。p-坚持 CSMA:当检测到媒体空闲时,该站点以概率 p 的可能性发送数据,而有 1-p 的概率会把发送数据帧的任务延迟到下一个时槽,Ⅱ错误。
36
一台主机的 IP 地址为 11.1.1.100,子网掩码为 255.0.0.0。现在用户需要配置该主机的默认路由。经过观察发现,与该主机直接相连的路由器具有如下 4 个 IP 地址和子网掩码:
I. IP 地址:11.1.1.1,子网掩码:255.0.0.0
II. IP 地址:11.1.2.1,子网掩码:255.0.0.0
III. IP 地址:12.1.1.1,子网掩码:255.0.0.0
IV. IP 地址:13.1.2.1,子网掩码:255.0.0.0
问 IP 地址和子网掩码可能是该主机默认路由的是( )。
【解析】 主机的 IP 地址为 11.1.1.100,子网掩码为 255.0.0.0,其网络地址通过按位与运算得到 11.0.0.0/8。默认路由的网关必须与主机在同一子网内,即网关的网络地址也应为 11.0.0.0/8,这样主机才能直接通信。
逐一分析路由器选项:
- I:IP 地址 11.1.1.1,子网掩码 255.0.0.0,网络地址为 11.0.0.0,与主机相同。
- II:IP 地址 11.1.2.1,子网掩码 255.0.0.0,网络地址为 11.0.0.0,与主机相同。
- III:IP 地址 12.1.1.1,子网掩码 255.0.0.0,网络地址为 12.0.0.0,与主机不同。
- IV:IP 地址 13.1.2.1,子网掩码 255.0.0.0,网络地址为 13.0.0.0,与主机不同。
只有 I 和 II 与主机在同一子网,可能作为默认路由的网关。III 和 IV 不在同一子网,主机无法直接可达,因此不能作为默认路由。故正确选项为 A。
37
路由器中发现 TTL 值为 0 的分组,将进行( )处理,并向源主机返回( )的 ICMP 报文。
【解析】 在 IP 网络中,TTL(生存时间)字段用于限制数据包在网络中的存活跳数。路由器每转发一次分组,TTL 值减 1;当 TTL 值减为 0 时,路由器必须丢弃该分组,以防止其无限循环消耗网络资源。
丢弃后,路由器会向源主机发送一个 ICMP 时间超过报文(ICMP Type 11),通知源主机该分组因 TTL 超时而被丢弃。这有助于源主机诊断网络路径问题,例如在 traceroute 工具中就是利用这一机制。
其他选项中:A 的“源点抑制”是 ICMP 用于流量控制的报文;B 的“改变路由”是 ICMP 重定向报文,用于提示更优路由;D 的“终点不可达”是 ICMP 用于指示目的地无法到达的报文。这些均与 TTL 值为 0 的处理场景无关。
38
位于不同子网中的主机之间互相通信,下面说法中正确的是( )。
【解析】 当主机位于不同子网时,通信必须经过路由器转发。路由器在转发 IP 数据报时,保持网络层的源 IP 地址和目的 IP 地址不变(除非进行 NAT),但数据链路层的封装需要更新。具体来说,路由器会解封装接收到的帧,根据路由表确定下一跳,然后重新封装成新的帧,其中源硬件地址(如 MAC 地址)改为路由器出口的地址,目的硬件地址改为下一跳设备(如另一个路由器或目的主机)的地址。因此,选项 C 正确。
选项 A 和 B 错误,因为标准 IP 路由中不重新封装 IP 地址;选项 D 错误,因为 ARP 广播只能用于同一子网内获取硬件地址,跨子网时源主机通过 ARP 获取默认网关的地址,而非直接获取目的主机的硬件地址。
39
下列关于路由器的说法中,正确的是( )。
【解析】
关于路由器与交换机的比较,路由器工作在网络层(第三层),负责在不同网络之间基于 IP 地址进行路由选择和分组转发,处理过程涉及路由表查找和决策,因此处理的信息更复杂,转发速度通常比工作在数据链路层(第二层)、基于 MAC 地址快速转发的交换机慢,故选项 A 错误。
对于路由选择,路由器使用路由协议(如 RIP、OSPF)计算路径,最佳路由的度量标准可能包括延迟、带宽、跳数等多种因素,并非只追求延迟最小,且在实际中可能根据配置提供多条路径或负载均衡,因此选项 B 过于绝对,不正确。
路由器通常设计为支持多种网络层协议(如 IP、IPX 等),并能处理不同协议的分组,实现跨协议网络的互联,这体现了其多协议处理能力,尽管现代路由器主要专注于 IP 协议,但传统概念上这一说法成立,因此选项 C 正确。
路由器转发决策依赖于网络层地址(如 IP 地址),而物理地址(MAC 地址)是数据链路层用于局域网内寻址的,由交换机或网卡处理,路由器仅在发送数据到直接相连的网络时需要获取 MAC 地址,但不基于 MAC 地址进行路由转发,故选项 D 错误。
综上所述,正确选项为 C。
40
第一次传输时,设 TCP 的拥塞窗口的慢启动门限初始值为 8(单位为报文段),当拥塞窗口上升到 12 时,网络发生超时,TCP 开始慢启动和拥塞避免,那么第 12 次传输时拥塞窗口大小为( )。
【解析】 首先,根据 TCP 拥塞控制机制,初始慢启动门限 ssthresh=8,拥塞窗口 cwnd 从 1 开始。在慢启动阶段,cwnd 每轮次翻倍:第 1 次传输 cwnd=1,第 2 次传输 cwnd=2,第 3 次传输 cwnd=4,第 4 次传输 cwnd=8(达到 ssthresh,进入拥塞避免)。拥塞避免阶段每轮次 cwnd 加 1:第 5 次传输 cwnd=9,第 6 次传输 cwnd=10,第 7 次传输 cwnd=11,第 8 次传输 cwnd=12。此时网络发生超时,超时后将 ssthresh 设置为当前 cwnd 的一半,即 12/2=6,cwnd 重置为 1。
超点后重新开始慢启动:第 9 次传输 cwnd=1,第 10 次传输 cwnd=2,第 11 次传输 cwnd=4。由于此时 cwnd=4 小于 ssthresh=6,仍处于慢启动,但慢启动的目标是使 cwnd 达到 ssthresh,因此从第 11 次传输到第 12 次传输,cwnd 应从 4 增长至 ssthresh 值 6,而不是翻倍到 8。故第 12 次传输时 cwnd=6。
解答题
第 41~47 题,共 70 分。
41
(10 分)下图所示是一带权有向图的邻接表。其中出边表中的每个结点均含有三个字段,依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求:

(1)该带权有向图的图形。
(2)从顶点 V1 为起点的广度优先搜索的顶点序列及对应的生成树。
(3)以顶点 V1 为起点的深度优先搜索生成树。
(4)由顶点 V1 到顶点 V3 的最短路径。
(5)若将该图看成无向图,用 Prim 算法给出图 G 的一棵最小生成树的生成过程。
42
(12 分)假设二叉树采用二叉链表存储结构,设计一个算法求其指定的某一层
(
)的叶子结点个数,要求:
(1)给出算法的基本设计思想。
(2)写出二叉树采用的存储结构代码。
(3)根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。
43
(11 分)已知两个实数
,
,它们在 C 语言中定义为 float 型变量,分别存放在寄存器 A 和 B 中。另外,还有两个寄存器 C 和 D。A、B、C、D 都是 32 位的寄存器。请问下列问题(要求用十六进制表示二进制序列):
(1)寄存器 A 和 B 中的内容分别是什么?
(2)
与
相加后的结果存放在 C 寄存器中,寄存器 C 中的内容是什么?
(3)
与
相减后的结果存放在 D 寄存器中,寄存器 D 中的内容是什么?
44
(12 分)现有 4 级流水线,分别完成取指、指令译码并取数、运算、回写四步操作。假设完成各部操作的时间依次为 100ns、100ns、80ns、50ns。请问:
(1)流水线的操作周期应设计为多少?
(2)若相邻两条指令如下,发生数据相关,而且在硬件上不采取措施,那么第 2 条指令要推迟多少时间进行?
ADD R1, R2, R3 # R2 + R3 -> R1
SUB R4, R1, R5 # R1 - R5 -> R4
(3)如果在硬件设计上加以改进,至少需要推迟多少时间?
45
(7 分)一个主修动物行为学、辅修计算机科学的学生参加了一个课题。调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷,横跨峡谷拉了一根绳索(假设为南北方向),这样猴子就可以攀着绳索越过峡谷。只要它们朝着相同的方向,同
一时刻可以有多只猴子通过。但是如果是相反的方向上同时有猴子通过则会发生死锁(这些猴子将被卡在绳索中间,假设这些猴子无法在绳索上从另一只猴子身上翻过去)。如果一只猴子想越过峡谷,它必须看当前是否有别的猴子在逆向通过。请用 P、V 操作来解决该问题。
46
(8 分)在某段式存储管理系统中,逻辑地址为 32 位,其中高 16 位为段号,低 16 位为段内偏移量,以下是段表(其中的地址均为 16 进制):
以下是代码段的内容(代码前的数字表示存放代码的十六进制逻辑地址):
main
240 push x[10108H]
244 call sin
248 ...
sin
360 mov r2,4+(sp)
364 ...
368 ret
试问:
(1)x 的逻辑地址为 10108H,它的物理地址是多少?要求给出具体的计算过程。
(2)若栈指针 SP 的当前值为 70FF0H,push x 指令的执行过程:先将 SP 减 4,然后存储 x 的值。试问存储 x 的物理地址是多少?
(3)call sin 指令的执行过程:先将当前 PC 值入栈,然后在 PC 内装入目标 PC 值。请问:哪个值被压入栈了?新的 SP 指针的值是多少?新的 PC 值是多少?
(4)“mov r2,4+(SP)”的功能是什么?(假设指令集与 x86 系列 CPU 相同)
47
(9 分)在本地主机使用 Ping 命令测试与远端主机 192.168.0.101 的连通性,Ping 测试仅进行了一次,由于测试数据较大,在 IP 层进行了数据分片。Ping 命令执行时,使用 Sniffer 工具捕获本机以太网发送方向的所有通信流量,得到 6 个 IP 数据报,表 1 以 16 进制格式逐字节给出了六个 IP 数据报的前 40 个字节。
IP 分组头的结构如图 1 所示。

