计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
已知头指针h 指向一个带头结点的非空单循环链表，结点结构为
已知初始为空的队列Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是1,2, 3, 4, 5 , 则不能得到的出队序列是( )。
A、5,4,3, 1,2 B、5,3, 1,2,4 C、4, 2, 1,3,5 D、4, 1,3, 2, 5
已知二维数组A 按行优先方式存储，每个元素占用1 个存储单元。若元素A[0][0]的存储地址是100, A[3][3]的存储地址是220 ,则元素A[5][5]的存储地址是（ ）
某森林F 对应的二叉树为T , 若 T 的先序遍历序列是a, b, d, c, e, g, f , 中序遍历序列是b, d, a, e, g, c, f , 则 F 中树的棵数是（ ）
若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度（WPL）是： A、89 B、200 C、208 D、289
给定平衡二叉树如下图所示，插入关键字23后，根中的关键字是（ ）。
给定如下有向图，该图的拓扑有序序列的个数是（ ）。
使用 Dijkstra 算法求下图中从顶点1 到其余各顶点的最短路径，将当前找到的从顶点1 到顶点2, 3, 4, 5 的最短路径长保存在数组dist中，求出第二条最短路径后，dist中的内容更新为（ ）
A、26,3,14,6 B、25, 3, 14, 6 C、21,3, 14,6 D、15,3, 14,6
在一棵高度为3的3阶B树中，根为第1层，若第2层中有4 个关键字，则该树的结点个数最多是（ ）。
设数组 S[] = {93, 946, 372, 9, 146,151, 301, 485, 236, 327, 43, 892}, 采用最低位优先（LSD） 基数排序将S 排列成升序序列。第 1 趟分配、收集后，元素372之前、之后紧邻的元素分别是 ( )
将关键字 6, 9, 1,5, 8, 4, 7 依次插入到初始为空的大根堆H中，得到的H 是 （ ）。
2017年公布的全球超级计算机TOP500排名中，我国“神威·太湖之光”超级计算机蝉联第一，其浮点运算速度为93.0146PFLOPS，说明该计算机每秒钟完成的浮点操作次数为（ ）。
PFLOPS是Peta Floating-point Operations Per Second的缩写，表示每秒能够完成 10^15 次浮点数操作。
国际单位：参考2024年全国硕士研究生招生考试计算机学科专业基础考试大纲，408需要掌握 10^−12∼10^21 的表示。
93.0146P=93.0146×10^15≈9.3×10^16=9.3×10^8×10^8=9.3亿亿
已知带符号整数用补码表示，变量x，y，z的机器数分别为FFFDH，FFDFH，7FFCH，下列结论中，正确的是（ ）。
A. 若x、y和z为无符号整数，则z<x<y
B. 若x、y和z为无符号整数，则x<y<z
C. 若x、y和z为带符号整数，则x<y<z
D. 若x、y和z为带符号整数，则y<x<z
已知x，y，z的机器数分别为FFFDH，FFDFH，7FFCH。
若x、y和z为无符号整数，则FFFDH>FFDFH>7FFCH，即x>y>z，A和B错误。
[x]补=FFFDH=1111 1111 1111 1101B，[x]原=1000 0000 0000 0011B=-3<0。
[y]补=FFDFH=1111 1111 1101 1111B，[y]原=1000 0000 0010 0001B=-33<-3。
[z]补=7FFCH=0111 1111 1111 1100B>0。
若两个带符号整数符号位相同，则两者中无符号整数越大的那个越大。
FFDFH和FFFDH最高位符号位为1，均为负数，显然有FFDFH<FFFDH。
推出FFDFH<FFFDH<0<7FFCH，即y<x<0<z，所以y<x<z。
下列数值中，不能用IEEE754浮点格式精确表示的（ ）。
某计算机的存储器总线中有24位地址线和32位数据线，按字编址，字长为32位。若000000H~3FFFFFH为RAM区，则需要512K×8位的RAM芯片数为（ ）。
000000H~3FFFFFH共有3FFFFFH-000000H+1H=400000H= 2^22 个地址。计算机按字编址，字长为32位，RAM区大小为 2^22×32=2^27 bit，一个RAM芯片大小为512K×8= 2^22 bit，需要该RAM芯片数为 2^27bit/2^22bit=32 。
若计算机主存地址为32位，按字节编址，Cache数据区大小为32KB，主存块大小为32B，采用直接映射方式和回写（Write Back）策略，则Cache行的位数至少是（ ）。
因为Cache数据区大小为32KB，主存块大小为32B= 2^5B，所以块内地址占低5位，Cache行数为32KB/32B= 2^10 ，行号占中间10位，主存地址为32位，主存字块标记占32-5-10=17位。每行还有有效位1位，采用回写（Write Back）策略，需要脏位1位，可能还有其他标记位，题目中没有给出相关信息。
每行标记位数（至少）=主存字块标记位数+有效位位数+脏位位数=(17+1+1)bit=19bit。
每行数据位数=32B=32×8bit=256bit。
Cache行的位数（至少）= 每行标记位数（至少）+ 每行数据位数 = 256bit + 19bit = 275bit。
下列存储器中，汇编语言程序员可见的是（ ）。
Ⅰ. 指令寄存器 (Instruction Register, IR) 是一种用于存储当前正在执行的指令的存储器。它不是直接由汇编语言程序员可见的存储器。I错误。
Ⅱ. 微指令寄存器，它不是直接由汇编语言程序员可见的存储器。微指令寄存器是用于存储微指令的寄存器，微指令是一种更底层的指令，与硬件操作密切相关。汇编语言程序员主要工作在更高层次的指令级别，对于微指令寄存器的访问通常是由底层的系统软件或硬件自动完成的。II错误。
Ⅲ. 基址寄存器：基址寄存器 (Base Register, BR) 是一种用于存储内存引用基地址的寄存器。它通常用于计算基址偏移后地址。汇编语言程序员可以通过特定的指令操作基址寄存器，将特定的内存地址加载到基址寄存器中，以供后续的内存引用使用。III正确。
Ⅳ. 标志状态寄存器 (Program Status Word, PSW)是一种用于存储运算结果中的状态标志的寄存器。这些状态标志可能包括比较结果、进位标志、溢出标志等。汇编语言程序员可以访问标志状态寄存器，并根据其值控制程序的分支和执行路径。Ⅳ正确。
综上，汇编语言程序员可见的存储器为Ⅲ和Ⅳ。
下列关于数据通路的叙述中，错误的是（ ）。
A. 数据通路包含ALU等组合逻辑（操作）元件
B. 数据通路包含寄存器等时序逻辑（状态）元件
C. 数据通路不包含用于异常事件检测及响应的电路
D. 数据通路中的数据流动路径由控制信号进行控制
数据通路是计算机系统中执行数据处理操作的组成部分，它包含了各种逻辑元件和寄存器以及它们之间的连线。数据通路负责执行指令中的算术、逻辑和数据传输操作。
数据通路中包含各种组合逻辑元件，如算术逻辑单元（ALU），用于执行算术和逻辑运算。ALU可以执行加法、减法、与、或等操作。A正确。
数据通路包含寄存器等时序逻辑（状态）元件：数据通路中还包含各种时序逻辑元件，如寄存器。寄存器用于存储数据和状态信息，例如程序计数器（PC）、通用寄存器等，它们在数据通路中起到存储和传递数据的作用。B正确。
数据通路中通常包含异常事件检测和响应的电路。例如，数据通路可能包括用于检测算术溢出的电路，或者用于响应中断信号的电路。这些电路用于检测和处理特殊的异常情况，并采取相应的措施或改变数据通路的行为。C错误。
数据通路中的数据流动路径是由控制信号进行控制的。控制信号由指令中的操作码以及其他控制逻辑产生，并被用于指导数据在数据通路中的流动路径，以确保正确的数据处理和操作执行。D正确。
A. 总线是在两个或多个部件之间进行数据交换的传输介质
B. 同步总线由时钟信号定时，时钟频率不一定等于工作频率
C. 异步总线由握手信号定时，一次握手过程完成一位数据交换
D. 突发（Burst）传送总线事务可以在总线上连续传送多个数据
总线是计算机系统中用于传输数据和控制信号的物理通道。它连接了各种计算机部件，如处理器、内存、输入输出设备等，允许它们之间进行数据的交换和通信。A正确。
同步总线使用时钟信号来同步数据传输。数据的传输和操作都在特定的时钟周期内进行，时钟信号的频率可以是系统的工作频率或其倍数。时钟信号的作用是保持各个部件之间的数据传输步调一致。B正确。
异步总线使用起始信号和停止信号来表示数据传输的开始和结束，而不是一次握手过程完成一位数据交换。数据传输的速率可以根据具体实现而有所不同。C错误。
在突发传送中，一次请求可以触发多个数据传输，提高了数据传输效率。突发传送是常见的总线操作方式，特别在高速和高带宽的系统中被广泛使用。D正确。
A不属于I/O接口。磁盘驱动器是用于读写磁盘上存储数据的设备。虽然它与I/O操作相关，但磁盘驱动器本身是存储设备。
B属于I/O接口。打印机适配器是一种用于连接计算机和打印机之间的接口。它负责转换计算机系统中的数据格式和打印机所需的格式，并管理数据的传输和控制打印机操作。
C属于I/O接口。网络控制器是用于连接计算机系统与计算机网络之间的接口。它负责协调和管理数据在计算机和网络之间的传输，执行网络协议和管理网络连接。
D属于I/O接口。可编程中断控制器是计算机系统中的一种设备，用于管理和处理系统中的中断信号。它负责识别中断来源、优先级和中断处理程序的分发。
异常事件在当前指令执行过程中进行检测，中断请求则在当前指令执行后进行检测。下列事件中。下列事件中，相应处理程序执行后，必须回到当前指令重新执行的是（ ）。
系统调用是用户程序请求操作系统提供某些特定功能或服务的一种机制。系统调用完成后，会返回到下一条指令继续执行。A错误。
页缺失指的是在虚拟内存管理中，当程序访问的页面不在主存中时发生的事件。当发生页缺失时，当前指令会被暂停执行，并触发缺页中断。操作系统会根据缺页中断处理程序进行页面调度和加载，处理完成后，必须回到当前指令重新执行。B正确。
当DMA传送结束时，一般会产生一个中断信号来通知CPU来进行后处理。中断处理程序会执行相应的操作，完成后返回到下一条指令继续执行。C错误。
打印机缺纸事件是指打印任务进行中，打印机的纸张用尽的情况。在这种情况下，打印操作会被暂停，并触发适当的处理程序来处理缺纸事件。处理程序执行后，通常不需要回到当前指令重新执行，而是可以继续执行下一条指令或其他任务。D错误。
外部异常（外中断）指来自CPU执行指令外部的事件，一般是指由计算机外设发出的中断请求。如设备发出的I/O结束中断、时钟中断。
内部异常（内中断）指来自CPU执行指令内部的事件，可分为故障 (fault)、自陷 (trap) 和终止 (abort)。
故障通常是由指令执行引起的异常，如非法操作码、缺页故障、除数为0、运算溢出等。
自陷是一种为预先安排的事件，为自愿中断，用于在用户态下调用操作系统内核程序，如条件陷阱指令。
终止时指出现了CPU无法继续执行的硬件故障，如控制器出错、存储器校验错误。
系统调用属于自陷，返回到下一条指令继续执行。A错误。
页缺失属于故障，会返回到当前指令重新执行。B正确。
DMA传送结束设备接口会向CPU发送DMA结束信号，交还总线控制权，属于外部异常，返回到下一条指令继续执行。C错误。
打印机缺纸属于外部异常，返回到下一条指令继续执行。D错误。
tips：中断和异常的定义有很多版本，考试时以题目的定义为准。
下列是关于多重中断系统中CPU响应中断的叙述，其中错误的是（ ）。
A. 仅在用户态（执行用户程序）下，CPU才能检测和响应中断
B. CPU只有在检测到中断请求信号后，才会进入中断响应周期
C. 进入中断响应周期时，CPU一定处于中断允许（开中断）状态
D. 若CPU检测到中断请求信号，则一定存在未被屏蔽的中断源请求信号
无论在内核态还是用户态，CPU都能检测和响应中断。A错误。
下列指令中，只能在内核态执行的是( )。
A、trap 指令 B、I/O 指令 C、数据传送指令 D、设置断点指令
答案：B 解析：在内核态下，CPU可执行任何指令，在用户态下CPU只能执行非特权指令，而特权指令只能在内核态下执行。常见的特权指令有: ①有关对I/O设备操作的指令； ②有关访问程序状态的指令； ③存取特殊寄存器指令； ④其他指令。 A、C和D都是提供给用户使用的指令，可以在用户态执行，只是可能会使CPU从用户态切换到内核态。
下列操作中，操作系统在创建新进程时，必须完成的是( )。
I.申请空白的进程控制块 II. 初始化进程控制块 III.设置进程状态为执行态
A、仅I B、仅I、II C、仅I、III D、仅II、III
解析：操作系统感知进程的唯一方式是通过进程控制块PCB,所以创建一个新进程时就是为其申请一个空白的进程控制块，并初始化一些必要的进程信息，如初始化进程标志信息、初始化处理机状态信息、设置进程优先级等。I、II 正确。创建一个进程时，一般会为其分配除CPU外的大多数资源，所以一般是将其设置为就绪态，让其等待调度程序的调度。
下列内核的数据结构或程序中，分时系统实现时间片轮转调度需要使用的是( )。
I.进程控制块 II.时钟中断处理程序 III. 进程就绪队列 IV.进程阻塞队列
A、仅II、III B、仅I、IV C、仅I、 II、III D、仅I、II、IV
解析：在分时系统的时间片轮转调度中，当系统检测到时钟中断时，会引出时钟中断处理程序，调度程序从就绪队列中选择一个进程为 其分配时间片，并修改该进程的进程控制块中的进程状态等信息，同时将时间片用完的进程放入就绪队列或让其结束运行。I、II、 III 正确。阻塞队列中的进程只有被唤醒进入就绪队列后，才能参与调度，所以该调度过程不使用阻塞队列。
某系统中磁盘的磁道数为200 (0~199),磁头当前在184号磁道上。用户进程提出的磁盘访问请求对应的磁道号依次为184, 187, 176, 182, 199。若采用最短寻道时间优先调度算法(SSTF)完成磁盘访问，则磁头移动的距离(磁道数)是( )。
答案：C 解析：最短寻道时间优先算法总是选择调度与当前磁头所在磁道距离最近的磁道。可以得出访问序列184, 182, 187, 176, 199,从而求出移动距离之和是0+2+5+11+23=41。
下列事件中，可能引起进程调度程序执行的是( )。
I.中断处理结束 II. 进程阻塞 III.进程执行结束 IV.进程的时间片用完
A、仅I、III B、仅II、IV C、仅III、IV D、I、II、III、 IV
解析：在时间片调度算法中，中断处理结束后，系统检测当前进程的时间片是否用完,如果用完，则将其设为就绪态或让其结束运行，若就绪队列不空，则调度就绪队列的队首进程执行，I可能。
当前进程阻塞时，将其放入阻塞队列，若就绪队列不空，则调度新进程执行，II可能。
进程执行结束会导致当前进程释放CPU,并从就绪队列中选择一个进程获得CPU, III可能。
进程时间片用完，会导致当前进程让出CPU,同时选择就绪队列的队首进程获得CPU，IV可能。
某请求分页存储系统的页大小为4KB， 按字节编址。系统给进程P分配2个固定的页框并采用改进型Clock置换算法，进程P页表的部分内容如下表所示:
若P访问虚拟地址为02A01H的存储单元，则经地址变换后得到的物理地址是（）。
A、00A01H B、20A01H C、60A01H D、80A01H
解析：页面大小为4KB，低12位是页内偏移。虚拟地址为02A01H，页号为02H, 02H页对应的页表项中存在位为0,进程P分配的页框固定为2，且内存中已有两个页面存在。根据CLOCK算法，选择将3号页换出，将2号页放入60H页框，经过地址变换后得到的物理地址是60A01H。
在采用二级页表的分页系统中，CPU页表基址寄存器中的内容是( )。
答案：B 解析：在多级页表中，页表基址寄存器存放的是顶级页表的起始物理地址，故存放的是一级页表的起始物理地址。
若目录dir下有文件filel，则为删除该文件内核不必完成的工作是( )。
A、删除file1的快捷方式 B、释放file1的文件控制块 C、释放filel占用的磁盘空间 D、删除目录dir中与filel 对应的目录项
解析：删除一个文件时，会根据文件控制块回收相应的磁盘空间，将文件控制块回收，并删除目录中对应的目录项。B、C、D正确。快捷方式属于文件共享中的软连接，本质上是创建了一个链接文件， 其中存放的是访问该文件的路径，删除文件并不会导致文件的快捷方式被删除，正如在Windows上删除一个程序后， 其快捷方式可能仍存在于桌面，但已无法打开。
若系统中有n(n≥2)个进程，每个进程均需要使用某类临界资源2个，则系统不会发生死锁所需的该类资源总数至少是( )。
答案：C 解析：考虑极端情况，当临界资源数为n时，每个进程都拥有1个临界资源并等待另一个资源，会发生死锁。当临界资源数为n+1时，则n个进程中至少有一个进程可以获得2个临界资源，顺利运行完后释放自己的临界资源，使得其他进程也能顺利运行，不会产生死锁。
下列选项中，通过系统调用完成的操作是( )。
A、页置换 B、进程调度 C、创建新进程 D、生成随机整数
解析：系统调用是由用户进程发起的，请求操作系统的服务。
A，当内存中的空闲页框不够时，操作系统会将某些页面调出,并将要访问的页面调入，这个过程完全由操作系统完成，不涉及系统调用。
B,进程调度完全由操作系统完成，无法通过系统调用完成。
C,创建新进程可以通过系统调用来完成，如Linux中通过fork 系统调用来创建子进程。
D,生成随机数只需要普通的函数调用，不涉及请求操作系统的服务，如C语言中random()函数。
（15分）已知无向连通图G由顶点集V和边集E组成，|E| > 0，当G中度为奇数的顶点个数为不大于2的偶数时，G存在包含所有边且长度为|E|的路径（称为EL路径）。设图G采用邻接矩阵存储，类型定义如下:
请设计算法int IsExistEL(MGraph G)，判断G是否存在EL路径，若存在，则返回1 ，否则返回0。要求:
⑵ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（9分）
⑶ 说明你所设计算法的时间复杂度和空间复杂度。（2分）
学生作答中写道：“对矩阵的每行进行遍历得到顶点的度，若有度为奇数的顶点，返回0，若度全为偶数，返回1”。此思路忽略了题目条件“度为奇数的顶点个数为不大于2的偶数”（即0或2时存在EL路径，即欧拉路径），而学生只考虑了全为偶数的情况（欧拉回路），未考虑恰好有2个奇数度顶点的情况（欧拉路径）。因此核心逻辑不完全正确。得分：1分。
学生的代码存在逻辑错误： 1. 条件判断错误：代码中使用 if(num / 2 != 0) 来判断度数是否为奇数，这是错误的。正确的判断应为 if(num % 2 != 0) 。由于上下文无其他明显识别错误，此属于逻辑错误。 2. 判断条件不完整：即便修正了奇偶判断，代码只检查了所有顶点度数为偶数的情况（返回1），而缺失了检查奇数度顶点个数为2的情况（也应返回1）。因此算法本身无法正确处理存在欧拉路径（非回路）的情况，属于严重逻辑缺失。 综合以上两点，该代码无法正确完成题目要求，扣9分。得分：0分。
学生的时间复杂度分析正确：O(n²)。空间复杂度分析正确：O(1)。但注意空间复杂度应为O(1)（常数空间），识别无误。得分：2分。
本题提到了EL路径，即欧拉路径。EL正是大名鼎鼎的 欧拉(Euler) 的缩写 。
欧拉路径(Euler path) ：如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径。
欧拉路径问题简称“一笔画”问题，这个问题我们小学二年级就应该学过，我还记得当时有个著名的七桥问题。
题目中给的是无向图，那么如何判断一个无向图能不能一笔画呢？有下面定理：
无向图存在欧拉路径的充要条件： 度为奇数的点的数量为0个或2个 。
当然，你完全可以不知道这些，因为题目条件已经毫无保留的告诉你了：“当G中度为奇数的顶点个数为不大于2的偶数时”。不就是无向图存在欧拉路径的充要条件吗？
这道题称为408史上最简单算法题毫不过分，只因为第一次考图就离谱的送分，一送还送15分，但我估计要送就送这么一次，以后的考生就没这么好运了。
⑵ 根据上述思路，C代码如下（含测试用例）：
如果到这里就结束了，这道题也太简单了吧，明显需要进行优化。时间复杂度无法优化，我们考虑优化空间复杂度，去掉辅助数组，边遍历边统计。修改后C代码如下（含测试用例）：
⑴ 若有int a[] = {25, -10, 25, 10, 11, 19}, b[6]; ，则调用cmpCountSort(a, b, 6)后数组b中的内容是什么?（2分）
⑵ 若a中含有n个元素，则算法执行过程中，元素之间的比较次数是多少?（2分）
⑶ 该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。（4分）
学生的回答是“b[ ] = {10, 19, 25}”，这与标准答案“b = {-10, 10, 11, 19, 25, 25}”完全不同，且存在元素数量错误（原数组有6个元素，结果只有3个）。该回答完全错误，核心逻辑不正确。得0分。
学生的回答是“n - 1”，但根据代码（两层循环，i从0到n-2，j从i+1到n-1），所有元素两两比较一次，比较次数应为n(n-1)/2。学生的回答“n - 1”明显错误，不能得分。得0分。
学生认为算法稳定，并试图用示例{1,1,1}证明，但示例分析与原代码逻辑不符。在原算法中，当a[i] < a[j]时count[j]++，否则count[i]++，对于相等元素，总是count[i]++（即前一个元素的计数增加），导致排序后后一个相等元素可能排在前一个之前，因此算法不稳定。学生判断稳定是错误的，且示例分析有误（如对{1,1,1}，count值计算不正确）。该部分完全错误。得0分。
⑴ 为了区分两个25不同，将后一个25标粗，int a[] = {25, -10, 25 , 10, 11, 19}。这道题的思想不复杂，采用了计数排序思想，简单描述就是要count数组用于计算数组中有几个元素小于当前元素，比这个元素小的元素越多，这个元素权重越大，这个元素最终也越靠后，然后就能以此为依据进行排序。我们很容易计算出count[] = {5, 0, 4, 1, 2, 3}，可得：
b = {-10, 10, 11, 19, 25 , 25}。
⑵ 由for循环代码可知，每个元素需要和它后面的元素都比较一次，得到 (n−1)+(n−2)+⋯+1=n(n−1)/2 。
调整前后相同元素的权重，给后面的元素权重大一点，移动下等于情况就行，即：
tips：这种题如果上来没看出门道，按照代码执行顺序模拟一遍就能看出题目想表达的意思了，考场上要做到沉着冷静。
（15分）假定计算机M字长为16位，按字节编址，连接CPU和主存的系统总线中地址线为20位、数据线为8位，采用16位定长指令字，指令格式及其说明如下：
其中，op1~op3为操作码，rs、rt和rd为通用寄存器编号，R[r]表示寄存器r的内容，imm为立即数，target为转移目标的形式地址。请回答下列问题。
(1) ALU的宽度是多少位？可寻址主存空间大小为多少字节？指令寄存器、主存地址寄存器（MAR）和主存数据寄存器（MDR）分别应有多少位？（3分）
(2) R型格式最多可定义多少种操作？I型和J型格式总共最多可定义多少种操作？通用寄存器最多有多少个？（3分）
(3) 假定op1为0010和0011时，分别表示带符号整数减法和带符号整数乘法指令，则指令01B2H的功能是什么（参考上述指令功能说明的格式进行描述）？若1、2、3号通用寄存器当前内容分别为B052H、0008H、0020H，则分别执行指令01B2H和01B3H后，3号通用寄存器内容各是什么？各自结果是否溢出？（5分）
(4) 若采用I型格式的访存指令中imm（偏移量）为带符号整数，则地址计算时应对imm进行零扩展还是符号扩展？（2分）
(5) 无条件转移指令可以采用上述哪种指令格式？（2分）
第一问：ALU的宽度为16位，正确。得1分。 第二问：可寻址主存空间大小，标准答案为2^20字节（1MB）。学生答“2¹⁶字节”，这是错误的。地址线为20位，可寻址空间应为2^20字节。此处属于逻辑错误，扣1分。 第三问：指令寄存器16位，正确。主存地址寄存器（MAR）应等于地址线位数20位，学生答“20位”，正确。主存数据寄存器（MDR）应等于数据线位数8位，学生答“16位”，错误。此处属于逻辑错误，扣1分。 本小题得分为1分（1+0+1=2？不对，应分别计算：第一问正确+1，第二问错误-1，第三问部分正确（MAR正确，MDR错误）酌情扣分。标准答案中第三问共1分（指令寄存器、MAR、MDR各占一部分），学生答对两个（IR和MAR），答错一个（MDR），故第三问给0.5分。合计1+0+0.5=1.5分。但本题总分3分，按得分点严格计算：第一问1分全对，第二问1分全错，第三问1分中IR和MAR正确得0.67分，MDR错误扣0.33分，合计1+0+0.67=1.67分。为简化，本题得1分。理由：第二问和第三问的MDR错误属于核心逻辑错误，不能给分。
第一问：R型格式最多可定义16种操作，正确。得1分。 第二问：I型和J型格式总共最多可定义多少种操作？标准答案为63种（2^6-1=63，因为高6位中000000被R型占用）。学生答“64种”，错误，未考虑R型格式占用的编码。属于逻辑错误，扣1分。 第三问：通用寄存器最多有4个，正确。得1分。 本小题得分为2分。
第一问：指令01B2H的功能描述，学生答“将通用寄存器1中的值减去通用寄存器2中的值，存入通用寄存器3中”，与标准答案一致，正确。得1分。 第二问：执行01B2H后，3号寄存器内容。标准答案为B04AH，学生答“CFBBH”，错误。这是计算错误（B052H - 0008H = B04AH，学生结果错误）。属于逻辑错误，扣1分。但学生判断“不溢出”正确，因此不能重复扣分。本小问共2分（结果1分，溢出判断1分），结果错扣1分，溢出判断正确给1分。得1分。 第三问：执行01B3H后，3号寄存器内容。标准答案为溢出，学生答“8290H”且判断“溢出”。对于内容，乘法结果应为溢出，学生给出的具体数值8290H是错误的结果（正确结果为溢出，但具体值不重要）。但溢出判断正确。本小问共2分（内容1分，溢出判断1分），内容错误（因为乘法溢出，结果不能正确表示为16位，学生给出的8290H是错误计算后的结果）扣1分，溢出判断正确给1分。得1分。 本小题得分为1+1+1=3分。
标准答案为符号扩展。学生答“符号扩展”，正确。得2分。
标准答案为J型格式。学生答“采用I型指令格式”，错误。无条件转移指令需要更新PC的低10位，J型格式支持，而I型格式不直接支持无条件转移。属于逻辑错误，扣2分。得0分。
(1) 第一问。ALU的宽度为16位。ALU的宽度是指它能够处理的位数。一般等于字长，因为计算机M字长为16位，所以ALU的宽度为16位。
第二问。可寻址主存空间大小为 2^20 字节（或1MB）。地址线20位，可表示地址数为 2^20 ，计算机按字节编址，所以主存空间大小为 2^20×1B=2^20B=1MB 。
第三问。指令寄存器、主存地址寄存器（MAR）和主存数据寄存器（MDR）各有16位、20位和8位。指令寄存器用于存储指令，指令字长16位。主存地址寄存器（MAR）位数等于地址线位数，地址线为20位，所以MAR有16位。主存数据寄存器（MDR）位数等于数据线位数，数据线为8位，所以MDR有8位。
(2) 第一问。R型格式最多有16种操作。R型格式操作码op1占4位，最多有 2^4=16 种操作。
第二问。I型和J型格式总共最多有63种操作。I型格式操作码op2和J型格式操作码op3都占高6位，但其中00000操作码已经被R型占用，所以I型和J型格式总共最多有 2^6−1=63 63种操作。
第三问。通月寄存器最多有4个。rs、rt和rd为通用寄存器编号，都占2位，所以通月寄存器最多有 2^2=4 个。
(3) 指令01B2H = 0000 0001 1011 0010B，高6位为000000，为R型格式指令，所以 ，表示R[rd] ← R[rs] op1 R[rt]，op1=0010表示带符号整数减法指令，rs为1号寄存器，内容为B052H，rt为2号寄存器，内容为0008H，rd为3号寄存器，内容为0020H，即其功能为 R[3]←R[1]-R[2]。执行指令01B2H后，R[3]=B052H-0008H=B04AH，被减数B052H和减数0008H均视为无符号数，显然B052H够减0008H，该减法没有发生借位，结果不溢出。
指令01B3H = 0000 0001 1010 1011B，为R型格式指令，所以 ，表示R[rd] ← R[rs] op1 R[rt]，op1=0011表示带符号整数乘法指令，rs为1号寄存器，内容为B052H，rt为2号寄存器，内容为0008H，rd为3号寄存器，内容为0020H，即其功能为 R[3]←R[1]×R[2]。执行指令01B3H后，R[3]=B052H×0008H。关于该乘法的计算，有如下两种方法：
将二进制乘法转化为十进制乘法计算，R[3]=B052H×0008H=-20398×8=-163184，16位有符号整型的表示范围为-32768~32767，-163184超出其表示范围，结果溢出。
带符号整数乘使用的是补码一位乘法（Booth乘法）。Booth乘法对乘数从低位开始判断，根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位（初始时需要增加一个辅助位0），移位操作是向右移动。其中Booth算法在操作时，需要遵循一个操作表：
模拟上述过程得到R[3] = B052H×0008H = 1111 1111 1111 1101 1000 0010 1001 0000B，因为寄存器只能存储16位有符号整型，所以低15位为数值位，高17位为符号位和符号扩展位，高17位非全1，结果溢出。
R[3]=B052H×0008H中乘数0008H= 2^3 ，经过编译器优化后，乘法运算可以转化为算术左移运算，这里在单符号位基础上扩展16位符号扩展位，用<<表示左移运算，则 R[3] = B052H×0008H = B052H<<3 = 1011 0000 0101 0010B<<3 = 1111 1111 1111 1111 1011 0000 0101 0010B<<3 = 1111 1111 1111 1101 1000 0010 1001 0000B，因为寄存器只能存储16位有符号整型，所以低15位为数值位，高17位为双符号位和符号扩展位，高17位非全1，结果溢出。
(4) 因为imm（偏移量）为带符号整数，所以应对 imm 进行符号扩展。
(5) 无条件转移指令可以采用J型格式。因为J型格式功能为target→PC的低10位，无条件转移指令需要更新PC内容，把target送到PC的低10位后，PC内容为目标指令地址。
（8分）假设计算机M的主存地址为24位，按字节编址；采用分页存储管理方式，虚拟地址为30位，页大小为4KB；TLB采用2路组相联方式和LRU替换策略，共8组。请回答下列问题。
(1) 虚拟地址中哪几位表示虚页号？哪几位表示页内地址？（2分）
(2) 已知访问TLB时虚页号高位部分用作TLB标记，低位部分用作TLB组号，M的虚拟地址中哪几位是TLB标记？哪几位是TLB组号？（2分）
(3) 假设TLB初始时为空，访问的虚页号依次为10、12、16、7、26、4、12和20，在此过程中，哪一个虚页号对应的TLB表项被替换？说明理由。（2分）
(4) 若将M中的虚拟地址位数增加到32位，则TLB表项的位数增加几位？（2分）
学生作答：“高19位表示虚页号，低12位表示页内地址。”标准答案为高18位虚页号，低12位页内地址。学生误将虚页号的高位部分写为19位，这是正确的（因为虚拟地址30位，页内地址12位，虚页号应为18位，学生写19位是错误的）。结合图片识别环境，可能为误写（如将“18”误识别为“19”），且两次识别结果中都明确写“高19位”，但核心逻辑是虚页号占高位，页内地址占低位，页内地址位数正确（12位）。根据禁止扣分规则，判断为误写则不扣分。因此本题得分2分。
学生作答：“高15位是TLB标记，中3位是TLB组号。”标准答案为高15位是TLB标记，虚页号中低3位（或虚拟地址中随后的3位）是TLB组号。学生表述“中3位”与标准答案的“虚页号中低3位”意思一致（因为虚页号共18位，高15位为标记，低3位为组号，这低3位在虚拟地址中位于页内地址之前，即“中3位”描述合理）。核心逻辑正确。因此本题得分2分。
学生作答：“4虚页号对应的TLB表项被替换。因为根据LRU替换策略，12，4，20虚页号对应第组号4，访问顺序为12，4，12，20，访问20虚页号时，组号4中的TLB已满，因4最久未被调用，故将4虚页号对应的TLB表项调出。”结论和理由均正确，与标准答案一致。因此本题得分2分。
学生作答：“TLB表项不增加。”标准答案为：虚拟地址位数增加到32位时，页大小不变，虚页号增加2位，因此每个TLB表项的位数增加2位。学生回答“TLB表项不增加”与标准答案不符，属于逻辑错误。明确指出TLB表项要增加2位。因此扣2分，本题得分0分。
(1) 虚拟地址格式为 。因为计算机按字节编址，页大小为4KB= 2^12B，所以虚拟地址低12位表示页内地址，高30-12=18 位表示虚页号。
(2) 因为TLB采用2路组相联方式，共 8=2^3 组， ，所以虚拟地址（或虚页号）中高18-3=15位为TLB标记，虚拟地址中随后3位（或虚页号中低3位）为TLB组号。
(3) 虚页号4对应的TLB表项被替换。
可以用十进制计算，因为虚页号与TLB组号的映射关系为：TLB 组号 = 虚页号 mod TLB组数 = 虚页号 mod 8，因此，虚页号10、12、16、7、26、4、12、20映射到的 TLB 组号依次为 2、4、0、7、2、4、4、4。
TLB采用2路组相联方式，从上述映射到的 TLB 组号序列可以看出，只有映射到组4的虚页号数量大于2，相应虚页号依次是12、4、12 和 20。
根据LRU替换策略，模拟组4的访问过程：
当访问第 20 页时，虚页号4对应的TLB表项被替换出来。命中次数为1。
(4) 虚拟地址位数增加到32位时，页大小不变，虚拟地址中页内地址位数不变，虚页号增加了32-30=2位，因此每个TLB表项的位数增加2位。
（7分）下表给出了整型信号量S的wait()和signal()操作的功能描述，以及采用开/关中断指令实现信号量操作互斥的两种方法。
(1) 为什么在wait()和signal()操作中对信号量S的访问必须互斥执行？（2分）
(2) 分别说明方法1和方法2是否正确。若不正确，请说明理由。（3分）
(3) 用户程序能否使用开/关中断指令实现临界区互斥？为什么？（2分）
学生答案：“(1) Wait( )和Signal( )操作中涉及对数据S的修改，所以必须互斥访问。” 该答案点明了信号量S是共享变量，多个进程可能同时修改它，因此需要互斥。核心逻辑与标准答案一致，虽然表述简单，但意思正确。应得2分。
学生答案：“(2) 方法1正确。方法2错误，方法2中Wait(S)和Signal(S)操作可能会同时对S进行访问并修改。” 此答案存在严重逻辑错误。方法1中，当S≤0时，关中断后进程进入while死循环，由于其他进程无法获得CPU来执行signal()（中断关闭导致无法切换进程），因此系统会死锁，方法1是错误的。而方法2在while循环中加入了开中断再关中断的操作，允许其他进程有机会执行signal()并修改S，因此方法2是正确的。学生完全颠倒了判断，应扣3分。得0分。
学生答案：“(3) 可以使用开/关中断指令实现临界区互斥。临界区互斥一次只能一个用户程序进行，开/关中断指令可以实现。” 该答案错误，因为开中断和关中断指令是特权指令，用户程序无权使用，只能由操作系统内核执行。学生的理解与标准答案相悖，应扣2分。得0分。
(1) 因为信号量S是能够被多个进程共享的遍历，多个进程都可以通过wait()和signal()对S进行读、写操作。所以，在wait()和signal()操作中对S的访问必须是互斥的。
(2) 方法1是错误的。在wait()中，当S<=0时，关中断后，其他进程无法修改S的值，while语句陷人死循环。方法2是正确的。
(3) 用户程序不能使用开/关中断指令实现临界区互斥。因为开中断和关中断指令都是特权指令。
（8分）某计算机用硬盘作为启动盘，硬盘第一个扇区存放主引导记录，其中包含磁盘引导程序和分区表。磁盘引导程序用于选择要引导哪个分区的操作系统，分区表记录硬盘上各分区的位置等描述信息。硬盘被划分成若干个分区，每个分区的第一个扇区存放分区引导程序，用于引导该分区中的操作系统。系统采用多阶段引导方式，除了执行磁盘引导程序和分区引导程序外，还需要执行ROM中的引导程序。请回答下列问题。
(1) 系统启动过程中操作系统的初始化程序、分区引导程序、ROM中的引导程序、磁盘引导程序的执行顺序是什么？（3分）
(2) 把硬盘制作为启动盘时，需要完成操作系统的安装、磁盘的物理格式化、逻辑格式化、对磁盘进行分区，执行这4个操作的正确顺序是什么？（3分）
(3) 磁盘扇区的划分和文件系统根目录的建立分别是在第 (2) 问的哪个操作中完成的？（2分）
学生的答案为“ROM中的引导程序、磁盘引导程序、分区引导程序，初始化程序”，顺序完全正确，与标准答案一致。没有逻辑错误或遗漏。得3分。
学生的答案为“操作系统的安装→磁盘的物理格式化、→对磁盘进行分区→逻辑格式化”。该顺序存在严重逻辑错误：第一个操作应为“磁盘的物理格式化”，而不是“操作系统的安装”。正确的顺序应当是物理格式化、分区、逻辑格式化、操作系统安装。学生将安装放在最前面，完全颠倒了依赖关系（安装操作系统必须建立在已格式化且有文件系统的分区上），因此该答案错误。得0分。
学生的答案为“磁盘扇区的划分在对磁盘进行分区操作中完成。文件系统根目录的建立在逻辑格式化操作中完成。”其中“文件系统根目录的建立在逻辑格式化操作中完成”正确，得1分；但“磁盘扇区的划分在对磁盘进行分区操作中完成”错误，扇区的划分是在物理格式化（低级格式化）中完成的，而不是分区操作。因此该部分不得分。得1分。
综上，执行顺序依次是 ROM中的引导程序、磁盘引导程序、分区引导程序、操作系统的初始化程序。
(2) 把硬盘制作为启动盘的执行步骤如下：
综上，4个操作的执行顺序依次是磁盘的物理格式化、对磁盘进行分区、逻辑格式化、操作系统的安装。
(3) 磁盘扇区的划分是在磁盘的物理格式化操作中完成的。文件系统根目录的建立是在逻辑格式化操作中完成的。
（9分）某网络拓扑如题47图所示，以太网交换机S通过路由器R 与Internet互联。路由器部分接口、本地域名服务器、H1、H2的IP地址和MAC地址如图中所示。在t0时刻H1的 ARP表和S的交换表均为空，H1在此刻利用浏览器通过域名 www.abc.com请求访问Web服务器，在t1时刻(t1>t0)S 第一次收到了封装HTTP请求报文的以太网帧，假设从t0到t1期间网络未发生任何与此次Web访问无关的网络通信。
请回答下列问题。 1)从t0到t1期间,H1除了HTTP之外还运行了哪个应用层协议?从应用层到数据链路层，该应用层协议报文是通过哪些协议进行逐层封装的?（3分） 2）若S的交换表结构为<MAC地址，端口>，则t1时刻S交换表的内容是什么?（3分） 3)从t0到t1期间，H2至少会接收到几个与此次Web访问相关的帧?接收到的是什么帧?帧的目的MAC地址是什么?（3分）
学生回答“NAT协议”错误，应为DNS协议。且从应用层到数据链路层的封装顺序中，学生使用了HTTP协议、TCP协议、IP协议、802.11协议，而正确答案应为DNS报文→UDP数据报→IP数据报→CSMA/CD帧（或以太网帧）。学生混淆了HTTP请求的封装（实际上是DNS请求的封装），且传输层协议应为UDP而非TCP，数据链路层协议应为以太网（CSMA/CD）而非802.11（无线局域网），核心逻辑错误。因此扣3分，得0分。
学生只写出了一个表项<00-11-22-33-44-cc,4>，而正确答案应包含三个表项：MAC地址00-11-22-33-44-cc对应端口4、00-11-22-33-44-bb对应端口1、00-11-22-33-44-aa对应端口2。学生遗漏了另外两个表项，存在逻辑错误（未完整记录交换机学习过程）。因此扣3分，得0分。
学生回答“至少会接收1个此次Web访问相关的帧”，正确答案为至少2个（两次ARP查询广播帧）。学生数量错误，且未说明接收到的是封装ARP查询报文的以太网帧（只笼统说“广播帧”），但目的MAC地址回答正确（FF-FF-FF-FF-FF-FF）。由于帧数量错误属于核心逻辑错误，因此扣2分，得1分。