计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
求整数 n(n≥0) 阶乘的算法如下，其时间复杂度是（ ）。
这里分析代码需要用到递归式，递归式原则上为超纲内容，详见本题注解。
用递推的方式可以求解递归式： T(n)=T(n−1)+1=T(n−2)+1+1=⋯=n=O(n) 。
我们很容易理解代码的含义即求 n!=1×2×⋯×n 。
由于递归相比迭代多了一个压栈过程，所以一般情况下，迭代比递归更加高效。
已知操作符包括‘ + ’、‘ − ’、‘ ∗ ’、‘ / ’、‘ ( ’ 和 ‘ ) ’。将中缀表达式 a+b−a∗((c+d)/e−f)+g 转换为等价的后缀表达式 ab+acd+e/f−∗−g+ 时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。
本题考察中缀表达式转后缀表达式，需要利用栈作为辅助。
转换过程中同时保存在栈中的操作符的最大个数是 5 。
其实我们没有必要老老实实模拟整个流程，只需要观察表达式即可，保存在栈中的操作符数量最大，则未计算的操作数嵌套最深，即最内层括号中最后一个操作数，很容易找到这个操作数 d ，观察前面与 d 相关的操作，也是没有能够输出的操作，这些操作都暂存在栈中，我们依次分析：
为了区别外层括号和内层括号，外层括号加粗。
受 d 直接或间接影响未能输出的操作符在中缀表达式中依次为 −∗((+ ，越靠近栈顶的优先级越高，总计 5 个操作符。
若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点（）
答案解析：考查树的遍历、及由遍历序列确定二叉树的树形。
前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点 的前序序列为 XY 与后序序列为 YX 时，则 X 为 Y 的祖先。考虑前序序列 a,e,b,d,c、后序序列 b,c,d,e,a， 可知 a 为根结点，e 为 a 的孩子结点；此外，a 的孩子结点的前序序列 e,b,d,c、后序序列 b,c,d,e，可知 e 是 bcd 的祖先，故根结点的孩子结点只有 e。本题答案为 A。
已知某二叉树的前序遍历序列和后序遍历序列，能构造的二叉树不一定唯一。
前序遍历是“根左右”遍历，后序遍历是“左右根”遍历。
第一轮递归：从前序遍历序列中取出第一个元素作为二叉树的根结点，从后序遍历序列中取出最后一个元素作为二叉树的根结点，这两个元素一定相同，否则无法构造二叉树，本题均为a。
第二轮递归：从前序遍历序列未处理的子串中取出第一个元素作为二叉树的左子树的根结点，从后序遍历序列未处理的子串中取出最后一个元素作为二叉树的右子树的根结点，这两个元素不一定相同。如果相同，说明有一个子树为空，本题均为e，也就是根结点只有一个孩子结点e，e可以随机分配在左子树或者右子树。
到这里没必要继续递归执行了，本题只要求出根结点的孩子结点即可。
若平衡二叉树的高度为 6 ，且所有非叶结点的平衡因子均为 1 ，则该平衡二叉树的结点总数为（ ）。
本题默认叶结点高度为 1 ，采用归纳法思路，从高度为 1 的平衡二叉树进行递推，假设左子树比右子树高。
构造高度为3的平衡二叉树时，左子树为高度为2的平衡二叉树，右子树为高度为1的平衡二叉树。
设高度为 n 的平衡二叉树结点数为 Cn ，可得递推式： Cn=Cn−1+Cn−2+1 。
对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。
答案解析：考查不同存储结构的图遍历算法的时间复杂度。
广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为 O(e)，算法总的时间复杂度为 O(n+e)。
若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。
用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，若对顶点按照矩阵下标进行编号，也就是只有从编号小的顶点往编号大的顶点的有向边，没有从编号大的顶点往编号小的顶点的有向边，也就是该有向图不可能存在环，既然没有环，也就是一定存在 拓扑序列 。由于没有具体的有向图，无法判断其拓扑序列是否唯一。
该有向图有两个拓扑序列，拓扑序列不唯一。
对如下有向图带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余最短路径的目标顶点依次是（ ）。
模拟完整的Dijkstra算法过程，初始点集 S 为空。
暴力找最短路径，算出最终的距离数组，如表格中最后一行所示。
下列关于最小生成树的叙述中，正确的是（）。
Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ．使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同
Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同
答案解析：考查最小生成树、及最小生成树算法的性质。
对于 I，最小生成树的树形可能不唯一（这是因为可能存在权值相同的边），但是代价一定是唯一的，I 正确。对于 II，如果权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，II 错误。对于 III，设 N 个结点构成环，N-1 条边权值相等，则从不同的顶点开始普里姆算法会得到 N-1 中不同的最小生成树，III 错误。对于 IV，当最小生成树唯一时（各边的权值不同），普里姆算法和克鲁斯卡尔算法得到的最小生成树相同，IV 错误。
已知一棵 3 阶 B-树，如下图所示。删除关键字 78 得到一棵新 B-树，其最右叶结点中的关键字是（）。
对于上图所示的 3 阶 B- 树，被删关键字 78 所在结点在删除前的关键字个数 =1= é 3/2 ù -1 ，且其左兄弟结点的关键字个数 =2 ≥ é 3/2 ù ，属于 “兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。
在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是（）
对于Ⅰ，简单选择排序每次选择未排序列中的最小元素放入其最终位置。对于Ⅱ，希尔排序每次是对划分的子表进行排序，得到局部有序的结果，所以不能保证每一趟排序结束都能确定一个元素的最终位置。对于Ⅲ，快速排序每一趟排序结束后都将枢轴元素放到最终位置。对于Ⅳ，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。对于Ⅴ，二路归并排序每趟对子表进行两两归并从而得到若干个局部有序的结果，但无法确定最终位置。
对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是______。
题目里出现了一个新概念，折半插入排序，本质还是插入排序，遵守插入排序的规则。
折半插入排序插入元素时采用的是折半查找的方式，直接插入排序插入元素时采用的是顺序查找的方式。
折半查找的时间复杂度为 O(logn) ，顺序查找的时间复杂度是 O(n) ，都是基于比较的查找算法。
折半插入排序和直接插入排序元素之间的比较次数可能不同。
插入排序的排序的总趟数、元素的移动次数取决于待排序序列。
插入排序使用辅助空间的数量恒为 O(1) 。
假定基准程序A在某计算机上的运行时间为100秒，其中90秒为CPU时间，其余为I/O时间。若CPU速度提高50%，I/O速度不变，则运行基准程序A所耗费的时间是（ ）。
本题为一道小学应用题， 工作量速度时间工作量=速度×时间 ，可以类比 路程速度时间路程=速度×时间 。
设初始时，CPU运行时间为 t1 ，速度为 v1 ，I/O运行时间为 t2 ，速度为 v2 。
提速后，CPU运行时间为 t1′ ，速度为 v1′ ，I/O运行时间为 t2′ ，速度为 v2′ 。
根据题意，初始时，CPU运行时间 t1=90 ，I/O运行时间 t2=100−90=10 。CPU工作量不变，有 v1t1=v1′t1′ ，CPU速度提升50%，有 v1′=1.5v1 。I/O工作量不变，有 v2t2=v2′t2′ ，I/O速度不变，有 v2′=v2 。求 t1′+t2′ 。
假定编译器规定int和short型长度分别为32位和16位，执行下列C语言语句：
unsigned short x=65530;
解析：将一个 16 位 unsigned short 转换成一个 32 位的 unsigned int，新表示形式的所有附加位都用 0 进行填充。X 的 16 进制表示为 FFFA，所以 y 的十六进制表示为 0000FFFA。
x=65530=65536−6=216−1−5=FFFFH−5H=FFFAH 。
unsigned short转unsigned int，高位补0，y=x=0000FFFAH。
float类型(即IEEE754单精度浮点数格式)能表示的最大正整数是（ ）。
本题考察float的取值范围，float最大值为 (2−2^−23)×2^127=2^128−2^104 。
如果忘记了float的最大值，首先排除float的特殊表示。
然后构造出float的最大值，符号位 S=0 ，阶码 E=254 ，尾数 M 所有位全1，float的值为 (−1)^S×1.M×2^(E−127)=(1+1−2^−23)×2^(254−127)=(2−2^−23)×2^127=2^128−2^104 。
某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int型和short型长度分别为32位和16位，并且数据按边界对齐存储。某C语言程序段如下：
若record变量的首地址为0xC008，则地址0xC008中内容及record.c的地址分别为（ ）。
分为按字编址和按字节编址，在32位和64位计算机中，基本数据类型大小如下
若按字节编址，则一个数据类型占的地址单元数等于其字节数。
以字节为单位的边界对齐，也称字节对齐，数据在存储时需要被放置在内存地址的倍数上，比如数据类型的大小为4个字节，那么它需要被存放在地址是4的倍数的位置上。数据按边界对齐存储是一种优化技术，通过调整数据在内存中的存储位置，可以提高计算机系统的性能和效率。
边界对齐后，结构体大小为其大小最大成员变量大小的整数倍。
根据边界对齐的定义，record变量的首地址为0xC008，从首地址开始，按顺序从低地址到高地址依次放入a、b和c这3个成员变量，模拟过程如下：
大端方式(Big Endian)：数据低位保存在高地址中，数据高位保存在低地址中。大端序和人的书写顺序一致。
小端方式(Little Endian)：数据低位保存在低地址中，数据高位保存在高地址中。
以一个16位（2字节）整数0x1234为例，它在大端方式和小端方式下的存储方式如下：
大端方式存储：高字节0x12存储在低地址，低字节0x34存储在高地址。
小端方式存储：低字节0x34存储在低地址，高字节0x12存储在高地址。
在实际应用中，不同的计算机体系结构和操作系统可能采用不同的字节序。例如，x86架构的计算机一般使用小端方式，而网络传输通常使用大端方式。
record.a=273=0x 00 00 01 11，采用小端方式存放数据，可以画出如下布局：
0xC008中内容为0x11，record.c的地址为0xC00E。
下列关于闪存（Flash Memory）的叙述中，错误的是（ ）。
A. 信息可读可写，并且读、写速度一样快
B. 存储元由MOS管组成，是一种半导体存储器
C. 掉电后信息不丢失，是一种非易失性存储器
D. 采用随机访问方式，可替代计算机外部存储器
闪存的信息可读可写，但写入操作相对读取操作来说较慢。写入操作需要先擦除整个闪存块的数据，然后再进行写入操作。这个擦除和写入的过程需要一定的时间，所以写入速度较读取速度慢。选项A错误。
闪存是一种基于半导体技术的存储器，其存储单元由MOS（Metal-Oxide-Semiconductor）管组成，也被称为闪存晶体管。选项B正确。
闪存是一种非易失性存储器，意味着即使在失去电源的情况下，存储在闪存中的信息仍然不会丢失。选项C正确。
闪存可以通过随机访问方式进行读取和写入操作，因此可以用作计算机的外部存储器，例如固态硬盘（SSD）和闪存驱动器（USB闪存驱动器）等。选项D正确。
假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为1个字。若Cache的内容初始为空，采用2路组相联映射方式和LRU替换策略。访问的主存地址依次为 0,4,8,2,0,6,8,6,4,8 时，命中Cache的次数是（ ）。
本题考察了Cache映射方式和替换策略。
Cache有4个行，采用2路组相联映射方式，有 4/2=2^1 组，组号占1位，因为计算机按字编址且块大小为1个字，所以主存地址低1位为组号，剩余高位为主存字块标记，这里主存地址最大为
所有元素都被映射到组0，因为采用2路组相联映射，每组只有2行，组内采用全相联映射，置换算法为LRU，模拟过程如下：
某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有（ ）。
答案解析：C，字段直接编码就是把微命令多个段，段的数目等于互斥类的数目。因此这里分为5个段，每段里要 留一个离散状态表示自己没命令 。所以7个微命令对应3位，3个微命令对应2位，12个微命令对应4位，5个微命令对应3位，6个微命令对应3位，共15位。
操作控制字段釆用字段直接编码法，将微命令字段分成若干个小字段，互斥类微命令可组合在同一字段。根据微命令字段分段的原则：1. 互斥性微命令分在同一段内，相容性字段分在不同段内。2. 每个字段留出一个状态，表示本字段不发出任何微命令。
操作控制字段至少有 位，其中 m 表示互斥类数量， ni 表示第 i 个互斥类的微命令数量，本题有5个互斥类，分别包含7、3、12、5和6个微命令，计算结果为 ⌈log(7+1)⌉+⌈log(3+1)⌉+⌈log(12+1)⌉+⌈log(5+1)⌉+⌈log(6+1)⌉=15 。
某同步总线的时钟频率为100MHz，宽度为32位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输128位数据所需要的时间至少是（ ）。
本题考察突发（猝发）传输，指在同一行中相邻的存储单元连续进行数据传输的方式，只要指定起始地址和突发长度，控制器就会依次自动对后面相同数量的存储单元进行读/写操作，而不需要控制器连续提供列地址。
总线的时钟频率为100MHz，得时钟周期为10ns，总线宽度为32位。因为每传输一个地址或数据占用一个时钟周期，所以传输起始地址需要10ns，每个时钟周期可传输32位数据，传输128位数据需要128/32×10ns=40ns，总共需要10ns+40ns=50ns。
下列关于USB总线特性的描述中，错误的是（ ）。
USB总线支持即插即用和热插拔功能。这意味着外设可以在系统运行时插入或拔出，并且系统会自动检测和配置新插入的设备。A正确。
USB总线可以使用级联方式连接多个外设，通过USB集线器（hub）实现。一个USB集线器可以提供额外的USB端口，使多个外设可以同时连接到计算机或其他主机设备上。B正确。
USB总线是一种通信总线，它使用标准化的连接器和协议，可以连接各种不同类型的外设，例如鼠标、键盘、打印机、摄像头、存储设备等。C正确。
USB总线是一种串行总线，数据位按照顺序一个接一个地传输，不能同时传输2位数据。通过使用串行传输，USB总线可以在相对较低的成本和资源占用情况下提供高速的数据传输。USB总线的数据传输速率可以根据USB设备的版本和类型而有所不同。USB 1.1或更早版本的标准传输速率为1.5 Mbps（低速模式）和12 Mbps（全速模式）。然而，USB 2.0引入了高速模式，其传输速率可达480 Mbps。此外，USB 3.0、USB 3.1和USB 3.2等更高版本的标准可以提供更快的数据传输速率，达到5 Gbps、10 Gbps甚至20 Gbps。因此，USB总线的数据传输率可以是相当高的。D前半句错误，后半句正确，D错误。
下列选项中，在I/O总线的数据线上传输的信息包括（ ）。
I/O接口与CPU之间的I/O总线有数据线、控制线和地址线。控制线和地址线是单向传输的，从CPU传送给I/O接口，数据线用于在计算机系统的CPU和I/O接口之间传输数据和命令。以下是给出的选项的解释：
Ⅰ正确。命令字是一组位模式，用于控制I/O接口和外部设备的操作。它包含指示特定操作（例如读、写、复位）以及相关参数的信息。这些命令字将通过数据线从CPU传输到I/O接口。
Ⅱ正确。状态字是一组位模式，用于指示I/O接口的当前状态和条件。它可以包括设备空闲、数据传输完成、错误状态等信息。这些状态字也通过数据线从I/O接口传输回CPU。
Ⅲ正确。中断类型号是一个用于标识特定中断类型的数值。当外部设备需要处理器的处理或发生了特定的事件时，会触发相应的中断。每个中断类型都对应一个唯一的中断类型号。中断控制器或操作系统会将该中断类型号发送给CPU，以便CPU能够识别并执行相应的中断处理程序。中断类型号也通过数据线传送给CPU。
响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（ ）。
在响应外部中断的过程中，中断隐指令完成的操作包括：①关中断，②保护断电，③引出中断服务程序（形成中断服务程序入口地址并送PC），所以只有Ⅰ、Ⅲ正确。Ⅱ中的保存通用寄存器的内容是进入中断服务程序后首先进行的操作。
下列选项中，不可能在用户态发生的事件是（ ）。
A.系统调用 B.外部中断 C.进程切换 D.缺页
【解析】本题的关键是对“在用户态发生"（与上题的“执行”区分）的理解。对于A，系统调用是操作系统提供给用户程序的接口，系统调用发生在用户态，被调用程序在核心态下执行。对于B，外部中断是用户态到核心态的“门”，也发生在用户态，在核心态完成中断过程。对于C ，进程切换属于系统调用执行过程中的事件，只能发生在核心态；对于D ，缺页产生后，在用户态发生缺页中断，然后进入核心态执行缺页中断服务程序。
本题考察“在用户态发生”，而非“在用户态执行”。
A错误。系统调用是由用户态程序主动发起的请求，用于请求操作系统提供特权操作或资源访问权限。用户态程序可以通过系统调用接口向操作系统发起请求并执行相应的内核函数。
B错误。外部中断是由外部设备或事件触发的中断请求，可能发生在用户态。外部中断通常在内核态进行处理。
C正确。进程切换是操作系统调度器根据调度策略从一个运行的进程切换到另一个进程的操作。用户态程序是无法直接调用进程切换的，程序只能通过系统调用接口向操作系统发送某些请求，如fork、exec、yield等，然后由操作系统内核在内核态中处理这些请求，处理请求的过程中可能需要进行进程切换。进程切换涉及到修改和管理进程的上下文信息，包括保存和恢复寄存器状态、切换页表、更新进程控制块等操作。
D错误。缺页指的是程序访问的内存页不在物理内存中，需要通过页表映射和磁盘交换等机制从磁盘加载到内存中才能继续执行。当用户态程序访问一个缺页时，处理器会触发缺页异常，并由操作系统在内核态进行缺页处理。
中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（ ）。
【解析】子程序调用只需保存程序断点，即该指令的下一条指令的地址；中断调用子程序不仅要保存断点（PC的内容），还要保存程序状态字寄存器（PSW）的内容。在中断处理中,最重要的两个寄存器是PC和 PSWR。
中断处理需要保存的内容通常包括程序计数器（保存当前指令的地址）、程序状态字寄存器（保存标志位和其他与程序状态相关的信息）和所需保留的通用寄存器（包括一些通用数据寄存器和通用地址寄存器），以保护现场并确保在中断处理完成后能够正确地恢复原来的执行状态。
子程序调用需要保存的内容通常包括程序计数器（保存当前指令的地址）、栈指针（保存当前栈的位置）以及所需保留的通用寄存器（包括一些通用数据寄存器和通用地址寄存器），以确保在子程序执行完毕后能够正确返回到调用者，并保护调用者的数据。
综上，中断处理一定会保存而子程序调用不需要保存其内容的是程序状态字寄存器。
下列关于虚拟存储器的叙述中，正确的是（ ）。
A错误，B正确。非连续分配技术则可以将虚拟地址空间中的不同部分映射到内存或外存的任意位置。根据所用的存储器映像算法，虚拟存储器管理方式主要有段式、页式、和段页式三种。
C和D错误。虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。
用户程序发出磁盘I/O请求后，系统的正确处理流程是操作系统的I/O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（ ）。
A. 用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序
B. 用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序
C. 用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序
D. 用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序
用户程序发出磁盘 I/O 请求后，系统的处理流程是用户程序→系统调用处理程序→设备驱动程序→中断处理程序。四个步骤分别对应用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序。
假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3，这些资源总数分别为18、6、22。T0时刻的资源分配情况如下表所示，此时存在的一个安全序列是（ ）。
A. P0, P2, P4, P1, P3
B. P1, P0, P3, P4, P2
C. P2, P1, P0, P3, P4
D. P3, P4, P2, P1, P0
先将表格转化为已分配资源、尚需资源、可用资源三栏的形式。进程Pi尚需资源=进程Pi资源最大需求-进程Pi已分配资源，可用资源=资源总数-所有进程已分配资源之和。
使用银行家算法，保证可用资源大于或等于某进行尚需资源，该进程可以输出到序列，并回收该进程已分配资源。若所有进程均可被输出到序列，则存在安全序列，该输出序列为安全序列，否则不存在安全序列。
根据第一步能够输出到序列的进程分情况讨论。
总共有3×3!+4!+4!=66种安全序列。
将选项逐一和安全序列进行比对，只有D正确。
若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（ ）。
Ⅰ. 若该文件的数据不在内存中，则该进程进入睡眠等待状态
Ⅱ. 请求read系统调用会导致CPU从用户态切换到核心态
Ⅲ. read系统调用的参数应包含文件的名称
Ⅰ正确。若该文件的数据不在内存中，产生中断，该进程暂时进入睡眠等待状态（阻塞态）。这是因为操作系统需要将磁盘中的数据加载到内存中，这个过程可能需要一定的时间。当数据准备好后，操作系统会通知进程，使其从睡眠状态转变为可执行状态（就绪态），并继续执行读取操作。
Ⅱ正确。请求read系统调用会导致CPU从用户态切换到核心态。
Ⅲ错误。read系统调用的参数应包含文件的描述符 (file descriptor)，而不是文件的名称。read系统调用是用于从文件描述符 (file descriptor) 读取数据的操作。其参数包括：
读取操作的返回值是一个整数，表示实际读取的字节数。如果读取成功，返回值将是大于等于0的值；如果达到文件末尾，返回值将是0；而如果发生错误，返回值将是-1，并且错误码会被设置以指示特定的错误类型。
一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达，它们的计算和I/O操作顺序如下：
P1：计算60ms，I/O80ms，计算20ms
P2：计算120ms，I/O40ms，计算40ms
若不考虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。
由于P2比P1晚5ms到达，P1先占用CPU，作业运行的甘特图如下：
若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（ ）。
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度
选项A、B、D属于可以进行处理机调度的情况。
对于选项C，当进程处于临界区时，说明进程正在占用处理机，只要不破坏临界资源的使用规则，就不会影响处理机的调度。比如，通常访问的临界资源可能是慢速的外设（如打印机），若在进程访问打印机时，不能进行处理机调度，则系统的性能将非常差。
由于单处理器同一时刻只能处理一个进程。所以没有进程占用处理机的情况下进行处理机调度是没有任何问题的，A、B、D正确。
在很多情况下，进程访问临界区并非原子操作，如果要在进程处于临界区时进行处理机调度，执行中断处理即可，C错误。
下列关于进程和线程的叙述中，正确的是（ ）。
A.不管系统是否支持线程，进程都是资源分配的基本单位
B.线程是资源分配的基本单位，进程是调度的基本单位
C.系统级线程和用户级线程的切换都需要内核的支持
D.同一进程中的各个线程拥有各自不同的地址空间
【解析】在引入线程后，进程依然是资源分配的基本单位，线程是调度的基本单位，同一进程中的各个线程共享进程的地址空间。在用户级线程中，有关线程管理的所有工作都由应用程序完成，无须内核的干预，内核意识不到线程的存在。
A正确。不管系统是否支持线程，进程都是资源分配的基本单位。
B错误。线程是操作系统中调度的基本单位，它是进程内的执行流。线程共享进程的资源，包括内存空间、文件句柄和其他系统资源。正确表述应该是“进程是资源分配的基本单位，线程是调度的基本单位”。
C错误。不同类型的线程切换方式不同。系统级线程是由操作系统内核创建和管理的线程，其切换需要内核的支持。而用户级线程（也称为轻量级线程）是在用户空间实现的线程，其切换由用户级线程库负责，不需要内核的干预。
D错误。同一进程中的各个线程共享相同的地址空间，即它们在同一进程的上下文中执行，并访问相同的内存和其他资源。
下列选项中，不能改善磁盘设备I/O性能的是（ ）。
A错误。通过对 I/O 请求进行重新排序，可以减少磁盘寻道时间和旋转延迟，以提高磁盘设备的 I/O 性能。
B正确。将磁盘分成多个分区可以在逻辑上组织和管理文件，但并不能直接改善磁盘设备的 I/O 性能。
C错误。预读是指在读取一个块时，预先读取相邻的块到缓存中，以供之后的读取请求使用，从而减少磁盘访问延迟。滞后写是指将写操作先缓存起来，并在合适的时机一次性批量执行，以减少频繁的磁盘写入操作。这些技术可以优化磁盘设备的 I/O 性能。
D错误。通过合理地安排文件的物理块分布，例如将频繁访问的文件块放置在磁盘上相邻的区域，可以减少寻道时间，提高磁盘设备的 I/O 性能。
在 TCP/IP 体系结构中，直接为 ICMP 提供服务的协议是（ ）。
ICMP (Internet Control Message Protocol) 互联网控制消息协议，是在 IP 层上运行的协议，用于在 IP 网络上发送控制消息。这些消息通常用于诊断和报告有关数据包传输的问题。
A 错误。PPP (Point-to-Point Protocol) 点对点协议，是一种数据链路层协议，用于通过串行连接（例如电话线、光纤等）在两个节点之间进行数据通信。
B 正确。IP (Internet Protocol) 互联网协议，在 TCP/IP 体系结构中为网际层协议。直接为 ICMP 提供服务的协议。ICMP 是建立在 IP 协议之上的，用于发送控制消息。
C 错误。UDP (User Datagram Protocol) 用户数据报协议，在 TCP/IP 体系结构中为传输层协议。提供面向无连接的数据报服务。UDP 通常用于传输不需要可靠数据传输的应用，如 DNS 查询和音视频流媒体。
D 错误。TCP (Transmission Control Protocol) 传输控制协议，在 TCP/IP 体系结构中为传输层协议。提供面向连接的字节流服务。TCP 通常用于传输需要可靠数据传输的应用，如 HTTP 请求。
在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。
A 错误。机械特性：指明接口所用接线器的形状和尺寸、引线数目和排列、固定和锁定装置等。
B 错误。功能特性：规定了接口信号的来源、作用以及其他信号之间的关系。即物理接口上各条信号线的功能分配和确切定义。物理接口信号般分为数据线、控制线、定时线和地线。
C 正确。过程特性：定义了再信号线上进行二进制比特流传输的一组操作过程，包括各信号线的工作顺序和时序，使得比特流传输得以完成。
D 错误。电气特性：指明在接口电缆的各条线上出现的电压的范围。
在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是过程特性。
有连接需要双方建立连接后才能进行数据交互。有连接的数据传输方式类似于打电话，
无连接不需要双方建立连接后才能进行数据交互。无连接的数据传输方式则类似于发送微信信息，不需要等待对方在线或回复，按下发送键后即可发送数据。
可靠服务是指网络具有纠错、检错、应答机制，能保证数据正确、可靠地传送到目的地。
不可靠服务是指网络只是尽量正确、可靠地传送，而不能保证数据正确、可靠地传送到目的地，是一种尽力而为的服务。
MAC 协议是一种无连接的、不可靠的数据传输服务，它负责处理数据帧在物理介质上传输的细节，但不保证数据的可靠交付。
两台主机之间的数据链路层采用后退 N 帧协议 (GBN) 传输数据，数据传输速率为 16 kbps，单向传播时延为 270 ms，数据帧长度范围是 128~512 字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（ ）。
在后退 N 帧协议 (GBN) 中，发送方可以发送 N 个帧而无需等待确认。从发送方发送一个数据帧到发送方接收到接收方传来的确认帧为一个周期。
发送方发送一个数据帧的时延为 t1 ，传播时延为 τ=270 ms ，接收方发送一个确认帧的时延为 t2 ，因为接收方总是以与数据帧等长的帧进行确认，所以 t1=t2 ，传播时延为 τ=270 ms 。一个周期 T=t1+τ+t2+τ=2t1+2τ 。因为数据链路层采用后退 N 帧协议 (GBN) 传输数据，为使信道利用率达到最高，在一个周期内，发送方可以连续发送多个数据帧，将位于发送窗口中的帧全部发送出去。
根据题目条件，数据传输速率为 16 kbps，该数据数据传输速率过低，不属于正常的以太网传播速率范围，属于卫星链路数据传输速率范围，卫星链路的数据传输速率通常在几 kbps到 十几 kbps 之间，卫星链路支持全双工通信，即通信双方可以同时发送和接收数据。在 408 真题中，后退 N 帧协议 (GBN) 中默认采用全双工通信，即通信双方可以同时发送和接收数据。
一个周期内能发送的帧数为 T/t1=(2t1+2τ)/t1=2(1+τ/t1) ，题目要求帧序号的比特数至少为多少需要满足所有情况，即满足最坏情况。 在 τ 固定的情况下， t1 越小，可发送的帧数越大。因为 t1=l/C ，其中 l 为数据帧长度，范围是 128~512 字节， C 是数据传输速率，为 16 kbps， l 越小， t1 越小，取 l=128 B ，此时 t1=l/C=128 B/16 kbps=(128×8 bit)/(16×1000 bit/s)=64 ms 。因此一个周期内能发送的最大帧数为 T/t1=(2t1+2τ)/t1=2(1+τ/t1)=2(1+270 ms/64 ms)≈10.4 。
GBN 协议发送窗口大小 WT 满足 1<WT≤2^n−1 ，其中 n 是构成帧序号的比特数量，将 WT=⌈T/t1⌉=11 代入，解得 n=4 ，即帧序号的比特数至少为 4。
下列关于 IP 路由器功能的描述中，正确的是（ ）。
II. 监测到拥塞时，合理丢弃 IP 分组
III. 对收到的 IP 分组头进行差错校验，确保传输的 IP 分组不丢失
IV. 根据收到的 IP 分组的目的 IP 地址，将其转发到合适的输出线路上
I 正确。路由器负责运行路由协议并设置路由表来指示数据包该如何转发。
II 正确。路由器会根据网络的情况进行流量控制，包括拥塞时的数据包的合理丢弃。
III 错误。IP 路由器会对收到的 IP 分组头进行差错校验，即重新计算该 IP 分组头的 校验和 ，与该 IP 分组头的头部校验和字段进行比对，检查是否一致。如果发现错误则丢弃该分组。III 的前半句正确。IP 路由器工作在 TCP/IP 体系结构中的网际层，该层不负责可靠传输，无法确保传输的 IP 分组不丢失。III 的后半句错误。确保传输的 IP 分组不丢失是端到端的任务，在 TCP/IP 体系结构中通常由传输层的 TCP 协议来完成。
IV 正确。路由器根据目的 IP 地址来决定将数据包转发到哪个输出线路上。
A. 根据 IP 地址查询 MAC 地址
B. 根据 MAC 地址查询 IP 地址
ARP (Address Resolution Protocol) 地址解析协议，是根据 IP 地址获取 MAC 地址的一个 TCP/IP 协议。
A 正确。根据 IP 地址查询 MAC 地址是 ARP 协议的功能。
B 错误。根据 MAC 地址查询 IP 地址是 RARP 协议的功能。RARP (Reverse Address Resolution Protocol) 反向地址解析协议，将局域网中某个主机的 MAC 地址转换为 IP 地址。
C 错误。根据域名查询 IP 地址是 DNS 协议的功能。DNS (Domain Name System) 域名系统，是互联网的一项服务。它作为将域名和 IP 地址相互映射的一个分布式数据库，能够使人更方便地访问互联网。根据域名查询 IP 地址需要进行正向 DNS 查询。
D 错误。根据 IP 地址查询域名是 DNS 协议的功能。反向 DNS 查询 (Reverse DNS lookup) 可以在命令行中使用 nslookup 命令实现。
某主机的 IP 地址为 180.80.77.55，子网掩码为 255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是（ ）。
要确定向特定子网发送广播分组的目的地址，需要使用该子网的广播地址。子网广播地址为该子网的网络地址加上该子网主机位全部为 1 的情况。
该 IP 地址的子网掩码为 255.255.252.0，写成二进制形式为 1111 1111 1111 1111 1111 1100 0000 0000，前 22 位全 1 为网络号，后 10 位全 0 为主机号。
将 IP 地址 180.80.77.55 和子网掩码 255.255.252.0 按位与运算，得到子网 180.80.76.0/22。
子网 180.80.76.0/22 前 22 位为网络前缀，将 180.80.76.0/22 后 10 位写成二进制形式，其中主机号部分用的位用 x 表示，每个 x 可以取 0 或 1。二进制位用红色表示。得到 180.80. 010011xx.xxxxxxx 。将将主机位全取1，得到该子网的广播地址 180.80. 01001111.11111111 ，即 180.80.79.255。
若用户1与用户2之间发送和接收电子邮件的过程如下图所示，则图中 ①、②、③ 阶段分别使用的应用层协议可以是
SMTP (Simple Mail Transfer Protocol) 简单邮件传输协议，是用于在网络上发送电子邮件的标准协议。SMTP 可以实现将邮件从你的一台主机发送到一个邮件服务器。该邮件服务器会查找接收者的邮件服务器，并使用 SMTP 将邮件转发到接收者的邮件服务器。
POP3 (Post Office Protocol version 3) 邮局协议第3版，它是用于接收电子邮件的标准协议。当你用邮件客户端以从邮件服务器上下载邮件时，它通常会使用 POP3 协议。
阶段①用户1发送邮件到邮件服务器，可通过 SMTP 协议传输。
阶段②邮件服务器发送邮件到用户2的邮件服务器，可通过 SMTP 协议传输。
阶段③用户2从自己的邮件服务器接收邮件，通常会使用 POP3 或 IMAP 协议。
综上所述，可以选择 SMTP、SMTP、POP3 作为阶段①、②、③分别使用的应用层协议。
（10分）设有 6 个有序表A、B、C、D、E，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列.要求通过 5 次两两合并，将 5 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。
⑴ 给出完整的合并过程，并求出最坏情况下比较的总次数。（7分）
⑵ 根据你的合并过程，描述 N(N≥2) 个不等长升序表的合并策略，并说明理由。（3分）
该学生的答案中，合并过程的描述与标准答案完全一致：第一次合并A和B，第二次合并AB和C，第三次合并D和E，第四次合并ABC和DE，第五次合并ABCDE和F。同时，各次合并的最坏情况比较次数计算正确（44、84、109、194、394），总和825计算正确。学生完整给出了合并过程和比较总次数，符合评分标准中“①用类似哈夫曼树思想进行合并，过程描述正确，给5分；②正确算出与合并过程一致的总比较次数，给2分”。因此本题给满分7分。
该学生描述了“对于若干不等长升序表的合并，最坏情况依赖于表的合并次序，可借用哈夫曼树的构造思想，依次选两个最短的表进行合并”，这与标准答案中的策略完全一致，明确说明了借用哈夫曼树思想，并且给出了正确的策略。根据评分说明，考生只要说明采用的是类似哈夫曼树的构造方法作为合并策略，即可给3分。因此本题给满分3分。
本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中的 Merge()函数；对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。 1）对于长度分别为 m，n 的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为 m+n-1 次。故，最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据哈夫曼树（最佳归并树）思想的启发，可采用如图所示的合并顺序。
根据上图中的哈夫曼树，6个序列的合并过程为： 第1次合并：表A与表B合并，生成含有45个元素的表AB； 第2次合并：表AB与表C合并，生成含有85个元素的表ABC； 第3次合并：表D与表E合并，生成含有110个元素的表DE； 第4次合并：表ABC与表DE合并，生成含有195个元素的表ABCDE； 第5次合并：表ABCDE与表F合并，生成含有395个元素的最终表。
由上述分析可知，最坏情况下的比较次数为：第1次合并，最多比较次数=10+35-1=44；第2次合并，最多比较次数=45+40-1=84；第3次合并，最多比较次数=50+60-1=109；第4次合并，最多比较次数=85+110-1=194；第5次合并，最多比较次数=195+200-1=394。 故，比较的总次数最多为：44+84+109+194+394=825
2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。
【1）2）评分说明】 ①对于用类似哈夫曼树（或最佳归并树）思想进行合并，过程描述正确，给5分。按其他策略进行合并，过程描述正确，给3分。 ②正确算出与合并过程一致的总比较次数，给2分。若计算过程正确，但结果错误，可给1分。 ③考生只要说明采用的是类似哈夫曼树（或最佳归并树）的构造方法作为合并策略，即可给3分。如果采用其他策略，只要能够完成合并，给2分。
（13分）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，’loading’和’being’的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为 datanext ，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在的结点位置p）。要求：
⑵ 根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。（8分）
⑶ 说明你所设计算法的时间复杂度。（1分）
1）顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点，我们先在长链表上遍历k个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第一个公共结点。算法的基本设计思想： ①分别求出str1和str2所指的两个链表的长度m和n； ②将两个链表以表尾对齐：令指针p、q分别指向str1和str2的头结点，若m>=n，则使p指向链表中的第m-n+1个结点；若m<n，则使q指向链表中的第n-m+1个结点，即使指针p和q所指的结点到表尾的长度相等。 ③反复将指针p和q同步向后移动，并判断它们是否指向同一结点。若p和q指向同一结点，则该点即为所求的共同后缀的起始位置。 2）算法的C语言代码描述：
【1）2）的评分说明】 ①若考生所给算法实现正确，且时间复杂度为O(m + n)，可给12分；若算法正确，但时间复杂度超过O(m + n)，则最高可给9分。 ②若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。 ③若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。 ④参考答案中只给出了使用C语言的版本，使用C++/JAVA语言的答案视同时用C语言。 3）时间复杂度为：O(len1 + len2)或O(max(len1,len2))，其中len1、len2分别为两个链表的长度。 【3）的评分说明】 若考生所估计的时间复杂度与考生所实现的算法一致，可给1分。
（10分）假定某计算机的CPU主频为80MHz，CPI为4，平均每条指令访存1.5次，主存与Cache之间交换的块大小为16B，Cache的命中率为99%，存储器总线宽度为32位。请回答下列问题。
(1) 该计算机的MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMA传送的情况下，主存带宽至少达到多少才能满足CPU的访存要求？（4分）
(2) 假定在Cache缺失的情况下访问主存时，存在0.0005%的缺页率，则CPU平均每秒产生多少次缺页异常？若页面大小为4KB，每次缺页都需要访问磁盘，访问磁盘时DMA传送采用周期挪用方式，磁盘I/O接口的数据缓冲寄存器为32位，则磁盘I/O接口平均每秒发出的DMA请求次数至少是多少？（2分）
(3) CPU和DMA控制器同时要求使用存储器总线时，哪个优先级更高？为什么？（2分）
(4) 为了提高性能，主存采用四体低位交叉存储模式，工作时每1/4个存储周期启动一个体。若每个体的存储周期为50ns，则该主存能提供的最大带宽是多少？（2分）
学生回答中：MIPS数为20（正确，得1分）；平均每秒Cache缺失次数为3×10⁵次（即300k，正确，得1分）；但主存带宽计算错误，标准答案为4.8MB/s，学生给出120MB/s，逻辑错误（误将缺失次数与块大小相乘时计算错误或单位换算错误，非识别误写），故扣2分。本小题共得2分。
学生回答缺页异常次数为1.5次（正确，得1分），但未计算DMA请求次数（标准答案为1536次），缺失该部分内容，扣1分。本小题共得1分。
学生回答DMA优先级更高（正确，得1分），理由为“防止数据丢失”（正确，得1分）。本小题共得2分。
学生回答最大带宽为320MB/s（正确，得2分）。本小题共得2分。
(1) 第一问，因为CPU主频为80MHz，CPI为4，所以平均每秒CPU执行的指令数为80M/4=20M，即MIPS数是20。
第二问，因为平均每条指令访存1.5次，平均每秒CPU执行的指令数为20M，Cache的命中率为99%，所以平均每秒Cache缺失次数为20M×1.5×(1-99%)=0.3M。
第三问，在Cache缺失的情况下，Cache需要和主存进行块交换，因为主存与Cache之间交换的块大小为16B，平均每秒交换0.3M次，所以为满足CPU的访存要求，主存带宽至少达到16B×0.3M/s=4.8MB/s。
(2) 第一问，因为在Cache缺失的情况下访问主存时，存在0.0005%的缺页率，根据(1)结果，平均每秒Cache缺失次数为0.3M，所以平均每秒产生的缺页中断次数为0.3M×0.0005%=1.5。
第二问，考察周期挪用方式，周期挪用是指利用CPU不访问存储器的那些周期来实现DMA操作，此时DMA可以使用总线而不用通知CPU也不会妨碍CPU的工作。在这种方法中，每当I/O设备发出DMA请求时，I/O设备便挪用或窃取总线占用权一个或几个主存周期，而DMA不请求时，CPU仍继续访问主存。
因为存储器总线宽度为32位，所以每传送32位数据，磁盘控制器发出一次DMA请求，平均每秒产生的缺页中断次数为1.5，页面大小为4KB，所以每秒发出的DMA请求次数至少是1.5×4KB/4B=1.5× 2^10=1536。注意，当K、M、G、T修饰字节或比特时分别表示 2^10 、 2^20 、 2^30 、 2^40 ，当K、M、G、T修饰字节或比特相关的速率时分别表示 10^3 、 10^6 、 10^9 、 10^12 。
(3) 第一问，CPU和DMA控制器同时要求使用存储器总线时，DMA优先级更高。
第二问，因为如果DMA请求得不到及时响应，I/O传输数据可能会丢失。
(4) 因为主存采用四体低位交叉存储模式，四体低位交叉存储为流水线四体并行。又因为存储器总线宽度为32位，工作时每1/4个存储周期启动一个体，则每个存储周期最多（四体并行时）可以传输32bit/(1/4)=16B，又因为每个体的存储周期为50ns，所以最大带宽是16B/50ns=320MB/s。
（13分）某16位计算机中，带符号整数用补码表示，数据Cache和指令Cache分离。下表给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，mem表示存储单元地址，(x)表示寄存器x或存储单元x的内容。
该计算机采用5段流水方式执行指令，各流水段分别是取指（IF）、译码/读寄存器（ID）、执行/计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB），流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题：
(1) 若int型变量x的值为-513，存放在寄存器R1中，则执行指令“SHR R1” 后，R1的内容是多少（用十六进制表示）？（2分）
(2) 若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少？（2分）
(3) 若高级语言程序中某赋值语句为x=a+b，x、a和b均为int型变量，它们的存储单元地址分别表示为[x]、[a]和[b]。该语句对应的指令序列及其在指令流水线中的执行过程如下图所示。
则这4条指令执行过程中，I3的ID段和I4的IF段被阻塞的原因各是什么？（2分）
(4) 若高级语言程序中某赋值语句为x=x*2+a，x和a均为unsigned int类型变量，它们的存储单元地址分别表示为[x]、[a]，则执行这条语句至少需要多少个时钟周期？要求模仿题44图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。（7分）
学生回答R1的内容为7EFFH，标准答案为FEFFH。学生的答案错误，因为-513的补码应为FDFFH（1111 1101 1111 1111），右移一位（算术右移）后应为FEFFH（1111 1110 1111 1111）。学生给出的7EFFH与正确结果不符。经判断，学生写“7EFFH”可能是将“F”误识别为“7”，但核心逻辑错误导致结果不正确，无法视为笔误。因此不得分。 得分：0分
学生回答需要8个时钟周期，与标准答案一致，正确。 得分：2分
学生回答I₃的ID段被阻塞的原因是“要等R₂寄存器存了b的值”。根据标准答案，正确原因应为I₃与I₁和I₂存在数据相关，需等待I₁和I₂写回结果。学生提到了等待R₂（b），但未完整指出需等待I₁和I₂两个写回，且表述不够准确，但核心思路（因数据相关等待）正确，可视为部分正确。对于I₄的IF段被阻塞的原因，学生回答“因为I₃的指令还没完成译码”，标准答案为“因为I₃在ID段被阻塞，所以I₄的IF段被阻塞”。学生回答基本正确，但表述不够精确（应强调是因前一条指令的ID段停滞导致IF段阻塞，而非泛指“没完成译码”）。综合来看，两个原因的核心意思正确，可各给1分。 得分：2分
I1 LOAD R1, [X] I2 LOAD R2, [X] I3 ADD R1, R1 I4 ADD R1, R2 I5 STORE R2, [X]
此处存在逻辑错误：I2应加载a的地址[ a]，但学生写成了[X]（与I1相同），导致后续计算结果错误。虽然x=x*2+a中的2*x可通过左移或加法实现，学生选择了ADD R1,R1（加法），但I2加载错误导致整体逻辑错误。此外，STORE指令将结果存入[x]时，应使用R1（存有最终值），而学生写的是R2（存储的是错误的[x]值），进一步加深错误。因此指令序列部分仅能因思路（使用加法实现乘2）给部分分，但因逻辑错误（地址用错）需扣分。建议给1分（基础结构正确）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 I₁ IF ID EX M WB I₂ IF ID EX M WB I₃ IF ID EX M WB I₄ IF ID EX M WB I₅ IF ID EX M WB
标准答案的流水线图中，因I₃与I₁存在数据相关（未采用转发），I₃的ID需等待至I₁的WB结束后才能执行，故I₃的IF在时钟3结束后，ID需暂停至时钟6才开始；I₄的IF需等待I₃的ID结束后才能开始，因此I₄的IF在时钟6，ID在时钟10；I₅的IF在时钟10，依次类推。学生的示意图中：I₃的IF在时钟3，但ID却放在时钟6？之间缺少明确暂停，且未画出I₄和I₅的合理延时（I₄的IF从时钟10开始？不正确）。学生的表格存在严重时序错误（例如I₃的ID在时钟6，但EX在时钟7，中间缺少暂停标示；I₄和I₅的起始周期也混乱）。流水线图完全错误，但学生未考虑因无转发导致的多个阻塞点，整体逻辑严重错误。因此示意图部分不得分。
综上，本题得分：指令序列部分1分（仅因结构正确，逻辑错误扣分），示意图0分，总周期数未单独计算（但示意图错误导致周期数不正确）。 得分：1分
1）x的机器码为[x]补=1111 1101 1111B，即指令执行前(R1)=FDFFH，右移1位后为1111 1110 1111 1111B，即指令执行后(R1)=FEFFH。（2分） 【评分说明】仅正确写出指令执行前的(R1)可给1分。 2）至少需要4+(5 - 1)=8个时钟周期数。（2分） 3）I₃的ID段被阻塞的原因：因为I₃与I₁和I₂都存在数据相关，需等到I₁和I₂将结果写回寄存器后，I₃才能读寄存器内容，所以I₃的ID段被阻塞。（1分） I₄的IF段被阻塞的原因：因为I₄的前一条指令I₃在ID段被阻塞，所以I₄的IF段被阻塞。（1分） 4）因2*x操作有左移和加法两种实现方法，故x=x*2+a对应的指令序列为 I1 LOAD R1，[x] I2 LOAD R2，[a] I3 SHL R1 //或者 ADD R1，R1 I4 ADD R1，R2 I5 STORE R2，[x] 【评分说明】指令正确给2分；其他正确答案同样给分；部分正确，酌情给分。 这5条指令在流水线中执行过程如下图所示。（3分）
故执行 x=x*2+a 语句最少需要 17 个时钟周期。（2分）
（7分）某请求分页系统的局部页面置换策略如下：
系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。
假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的<虚拟页号，访问时刻>是：
<1, 1>、<3, 2>、<0, 4>、<0, 6>、<1, 11>、<0, 13>、<2, 14>。请回答下列问题。
(1) 访问<0, 4>时，对应的页框号是什么？（1分）
(2) 访问<1, 11>时，对应的页框号是什么？说明理由。（2分）
(3) 访问<2, 14>时，对应的页框号是什么？说明理由。（2分）
(4) 该策略是否适合于时间局部性好的程序？说明理由。（2分）
学生答案正确，页框号为21，与标准答案一致。得1分。
学生答案错误，给出的页框号为41，而标准答案为32。学生的理由存在逻辑错误：学生认为6~10秒只访问了虚拟页0，据此推断11秒时驻留集中只剩页框41的页面，但实际系统规则是每5个时间单位扫描并回收本轮未被访问的页框，且<1,11>访问时页1曾使用过且其页框32仍可能在空闲链表中应被重新放回。学生忽略了“重新放回”的机制。此小题得0分。
学生答案错误，给出的页框号为32，而标准答案为41。学生的理由错误地认为此时驻留集已满，从空闲链表表头取出页框32，但实际在访问<2,14>时，空闲链表头部已是41（因为之前的回收和重新放回操作已改变了链表顺序），且虚拟页2从未被访问过，应取链表头部页框41。此小题得0分。
学生答案正确，认为适合且理由“被频繁访问的页面将持续留在驻留集中”与标准答案的“时间局部性越好，从空闲链表中重新取回机会越大”意思一致。得2分。
为了方便讨论，驻留集的页表中每个记录增加标记位，表示本轮该页面是否被访问，若该页面被访问，则标记位为1，否则标记位为0。这样每次访问某页只需要将该页的页表项中的访问位设为1，每次扫描将访问位为1的页表项的访问位修改为0，将访问位为0的页表项的页框回收。
初始时系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的<虚拟页号，访问时刻>是：<1, 1>、<3, 2>、<0, 4>、<0, 6>、<1, 11>、<0, 13>、<2, 14>。模拟完整过程如下：
仿照LRU算法，通过移动链表结点调整结点访问优先级。用蓝色标记页框链表中本轮被访问过的页框，黄色标记页框链表中本轮未被访问过的页框，所有黄色结点构成空闲页框链表，所有蓝色结点构成驻留集。这样每次访问某页只需要将该页被分配的页框号移动到链表尾，并标记为蓝色，每次扫描将页框链表中所有结点恢复成黄色。
注：题45图(a)和题45图(b)中空闲页框链表中结点的括号内数字表示最近一次页框号被分配的页号。
(1) 访问<0, 4>时，对应的页框号是21。
初始时进程驻留集为空，系统空闲页框链表中页框号依次为32、15、21、41，时刻4是第一轮的第三次访问，且访问的页号与前两次均不同。而0页对应的页框为空闲链表中的第三个空闲页框号是21。
(2) 访问<1, 11>时，对应的页框号是32。
第三轮初始时系统空闲页框链表中页框号依次为41、32(1)、15(3)，括号内数字表示最近一次页框号被分配的页号，时刻11是第三轮的第一次访问，而且访问页面1之前被分配的页框号为32，将页框32重新放入驻留集中。
(3) 访问<2, 14>时，对应的页框号是41。
第三轮初始时系统空闲页框链表中页框号依次为41、32(1)、15(3)，括号内表示最近一次页框号分配的页号，时刻14是第三轮的第三次访问，页面2从来没有被访问过，因此从空闲页框链表中取出链表头的页框41，页框号为41。
(4) 该策略适合于时间局部性好的程序。
如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。
（8分）某文件系统空间的最大容量为4TB（1TB= 2^40 B），以磁盘块为基本分配单位。磁盘块大小为1KB。文件控制块 (FCB) 包含一个512B的索引表区。请回答下列问题。
(1) 假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？（4分）
(2) 假设索引表区采用如下结构：第0～7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B，块数占2B；剩余504字节采用直接索引结构，一个索引项占6B，那么可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。（4分）
学生回答中，第一问的答案：“块号最少占4个字节，可支持的文件最大长度为128KB”与标准答案完全一致，逻辑正确，计算过程（虽未展示但结果正确）符合题意。因此，本小题得满分4分。
学生回答中，第二问的计算结果“单个文件最大长度为65624个字节”是错误的。标准答案应为65620KB（即2^26 + 84KB = 65620KB），而学生给出的“65624个字节”数值错误，且单位错误（应为KB而非字节），属于计算逻辑错误。因此，对于该部分，依据评分说明，过程描述不完整且计算结果错误，扣2分（共2分）。
对于后续回答：“起始块号与块数应分别占4个字节与4个字节，因为4个字节已经足够表示块号，同时块数所占字节应尽可能地大，这样才能使单个文件长度达最大。”，该思路正确，与标准答案中“4,4”的合理值及理由一致。因此，此部分得满分2分。
综上，第二问共得2分（从4分中扣除计算错误部分2分）。
(1) 第一问。因为该文件系统空间的最大容量为4TB，磁盘块大小为1KB，所以该文件系统中所能容纳的磁盘块总数为4TB/1KB= 2^32 。要完全表示所有磁盘块，索引项中的块号最少要占32bit=4B。
第二问。因为文件控制块 (FCB) 包含一个512B的索引表区，根据第一问结果，索引表项中块号最少占4字节，索引表区仅采用直接索引结构，所以索引表区最多能容纳512B/4B=128个索引项。又因为每个索引项对应一个磁盘块，磁盘块大小为1KB，所以该系统可支持的单个文件最大长度是128×1KB=128KB。
(2) 第一问。因为块数占2B=16bit，共可以表示 2^16 个磁盘块，磁盘块大小为1KB，所以预分配的连续存储空间大小为 2^16 ×1KB= 2^16 KB。又因为块号占6B，剩余504字节采用直接索引结构，直接索引区共504B/6B=84个索引项，磁盘块大小为1KB，所以直接索引区存储空间大小为84×1KB=84KB。综上，该系统可支持的单个文件最大长度=预分配的连续存储空间大小+直接索引区存储空间大小= 2^16 KB+84KB=65620KB。
第二问。根据(1)中第一问的结果，块数最少要占4B，才可表示4TB大小的文件长度，此时达到文件系统的空间上限，第0～7字节采用<起始块号，块数>格式表示文件创建时预分配的连续存储空间，总共8B，所以合理的起始块号和块数所占字节数分别为4、4，或3、5，或2、6，或1、7。
（9分）主机 H 通过快速以太网连接 Internet，IP 地址为 192.168.0.8，服务器 S 的 IP 地址为 211.68.71.80。H 与 S 使用 TCP 通信时，在 H 上捕获的其中 5 个 IP 分组如题 47-a 表所示。
(1) 题 47-a 表中的 IP 分组中，哪几个是由 H 发送的？哪几个完成了 TCP 连接建立过程？哪几个在通过快速以太网传输时进行了填充？（5分）
(2) 根据题 47-a 表中的 IP 分组，分析 S 已经收到的应用层数据字节数是多少？（2分）
(3) 若题 47-a 表中的某个 IP 分组在 S 发出时的前 40 字节如题 47-b 表所示，则该 IP 分组到达 H 时经过了多少个路由器？（2分）
注：IP 分组头和 TCP 段头结构分别如题 47-a 图，题 47-b 图所示。
第一问“哪些是由H发送的”：学生回答“第1, 3, 4为H发送的”，与标准答案完全一致，正确。 第二问“哪些完成了TCP连接建立过程”：学生回答“第1, 2, 3个”，与标准答案一致，正确。 第三问“哪些在传输时进行了填充”：学生回答“第3, 6个”，但标准答案为“第3, 5个”。根据题表，5号分组总长度为40字节（小于46字节），属于需要填充的分组；而6号分组在表中并未出现（表中只有1~5号分组），显然学生将“5”误写为“6”。结合识别结果上下文，这是典型的字符识别错误（5和6在图像中可能混淆），且该错误不改变核心判断依据（均为符合填充条件的分组）。按禁止扣分规则，误写不扣分，因此该部分正确。故本小问得5分。
学生回答“已经收到17个字节”，标准答案为16字节。计算过程：3号分组初始序号为846b 41c6H，5号分组确认序号ack=846b 41d6H，差值为10H=16字节。学生得出17，可能是计算错误（如误将差值算为11H），属于逻辑错误而非识别问题（字符识别错误不会导致17与16的差异）。按扣分规则，逻辑错误需扣分。但标准答案评分说明指出：“若解答结果不正确，但分析过程正确给1分”，本题未看到学生分析过程，仅给出结果，无法给过程分。因此该小问不得分。
学生回答“已经过64个路由器”，标准答案为15个路由器。标准解析：S发出时TTL=40H=64，到达时TTL=31H=49，差值为15。学生直接回答64，显然是误将TTL值当作经过路由器数，属于逻辑错误，且与正确答案偏差极大。不满足“误写”条件（64和15在图像中无明显相似性）。因此该小问不得分。
1）由于题47 - a表中1、3、4号分组的源IP地址（第13~16字节）均为192.168.0.8（c0a8 0008H），因此可以判定1、3、4号分组是由H发送的。（3分） 题47 - a表中1号分组封装的TCP段的FLAG为02H（即SYN=1，ACK=0），seq=846b 41c5H，2号分组封装的TCP段的FLAG为12H（即SYN=1，ACK=1），seq=e059 9fefH，ack=846b 41c6H，3号分组封装的TCP段的FLAG为10H（即ACK=1），seq=846b 41c6H，ack= e059 9ff0H，所以1、2、3号分组完成了TCP连接建立过程。（1分） 由于快速以太网数据帧有效载荷的最小长度为46字节，表中3、5号分组的总长度为40（28H）字节，小于46字节，其余分组总长度均大于46字节。所以3、5号分组通过快速以太网传输时进行了填充。（1分） 2）由3号分组封装的TCP段可知，发送应用层数据初始序号为seq=846b 41c6H，由5号分组封装的TCP段可知，ack为seq=846b 41d6H，所以5号分组已经收到的应用层数据的字节数为846b 41d6H - 846b 41c6H=10H=16。（2分） 【评分说明】其他正确解答，亦给2分；若解答结果不正确，但分析过程正确给1分；其他情况酌情给分。 3）由于S发出的IP分组的标识=6811H，所以该分组所对应的是题47 - a表中的5号分组。S发出的IP分组的TTL=40H=64，5号分组的TTL=31H=49，64 - 49=15，所以，可以推断该IP分组到达H时经过了15个路由器。（2分） 【评分说明】若解答结果不正确，但分析过程正确给1分；其他情况酌情给分。