计算机： 数据结构 、计算机组成原理 、操作系统 、计算机网络
以下代码在最坏情况下的时间复杂度为（ ）。
A. O(n) B. O(nlogn) C. O(n³) D. O(n²)
解析 观察程序发现，语句 “A[j] 与 A[j + 1] 对换;” 执行频率较高，且该语句并不影响双重 for 循环判断语句，但会影响 if 的判断语句。当 A 数组的所有元素都逆序时，该语句一直执行，此时为最坏情况。该语句在最坏情况下的频度是 O(n²)，选 D。
在一个单链表中，若 p 所指的结点不是最后一个结点，删除 p 之后结点，则执行（ ）。
D. p->next=p->next->next;
【解析】删除 p 之后结点，因题中没有 free 的要求，只需将 p 的 next 指针指向其后继结点的 next 指针，因此执行“p->next=p->next->next;”
有六个元素 6，5，4，3，2，1的顺序进栈，则下列不是合法出栈序列的是( )。
根据栈 “先进后出” 的原则，逐一分析各个选项：
选项 A（543612） 进栈顺序：6 进→5 进→5 出→4 进→4 出→3 进→3 出→6 出→2 进→1 进→1 出→2 出。 合法序列。
选项 B（453126） 进栈顺序：6 进→5 进→4 进→4 出→5 出→3 进→3 出→2 进→1 进→1 出→2 出→6 出。 合法序列。
选项 C（346521） 进栈顺序：6 进→5 进→4 进→3 进→3 出→4 出→此时栈内元素为 5、6（栈顶为 5），但下一个出栈元素为 6，需先弹出 5，因此无法直接弹出 6。 不合法序列 。
选项 D（234156） 进栈顺序：6 进→5 进→4 进→3 进→2 进→2 出→3 出→4 出→1 进→1 出→5 出→6 出。 合法序列。
综上， 选项 C 违反了栈的操作规则，因此不是合法的出栈序列。
若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。
【解析】删除一个元素则front+1，插入两个元素则rear+2，因此是2 和4。
中缀表达式(A+B)*(C−D)/(E−F*G) 的后缀表达式是( ) 。
【解析】这类题目可以从选项出发，通过模拟计算后缀表达式的结果与中缀表达式比较得出答
案，也可以通过本节中所说的办法将中缀表达式转化成后缀表达式获得。A 不符合后缀表达式的形式，D 先计算F+G，显然不对。对于C，若进行计算，弹出AB+ 执行A+B 压栈，弹出C*，
相当于执行(A+B)*C，错误。对于B，弹出AB+ 执行(A+B)，压入(A+B)，弹出(A+B)，C，D，
-，执行(C-D)，压入(C-D)，(A+B)，再弹出至*，执行(A+B)*(C-D)，后面也都符合表达式。
若将$6×6$的上三角矩阵$A$（下标从 1 起）的上三角元素按行优先存储在一维数组$b$中，且$b[1]=A_{11}$，那么$A_{35}$在$b$的下标是（ ）。
A. 12 B. 13 C. 14 D. 15
参考答案 ：C 解析 ：上三角矩阵第 1 行 6 个元素，第 2 行 5 个，以此类推，A35是第 3 行的第 3 个元素，因此答案为6 + 5 + 3 = 14
三叉树中有 1、2、3 个子树的结点数为 x、y、z，其叶结点数目是（ ）。 A. x + y + z B. 2y + 1 C. y + 2z + 1 D. 2z + 1
【解析】设叶结点数是 n，利用结点数目与度的关系，有x+2y+3z=n+x+y+z-1，得n=1+y+2z。
设二叉树共 2n 个结点，且m<n，则其中的结点数量不可能存在的情况是( )。
【解析】设二叉树中\(n = n_0 + n_1 + n_2\)，结点总数\(=2n = n_0 + n_1 + n_2 = n_1 + 2n_2 + 1\)，则\(n_1 = 2(n - n_2) - 1\)，所以\(n_1\)是个奇数，那么该二叉树中不可能有偶数个度为 1 的结点。
二叉树中 n是m 的祖先，在( )中，n在m前面是不可能的。
【解析】先序遍历中祖先必然先被遍历，后代是后面才会被遍历的，A错:若m在n的右子树里面，则中序遍历序列里n定在m 的前面，B错:若m 在n的右子树里面，后序遍历序列里m 定在n的前面，选C;层次遍历中，祖先一定在后代的前面被遍历，D错
在线索二叉树中，下列说法不正确的是( )。
A. 在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的最左下结点
B. 在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的最右下结点
C. 线索二叉树是利用二叉树的n+1个空指针来存放结点的前驱和后继信息的
D. 每个结点通过线索都可以直接找到它的前驱和后继
【解析】并非每个结点通过线索化都可以直接找到其前驱和后继。查找后序后继是需要知道其双亲结点的，二叉链表没有存放双亲的指针。
在有向图的邻接表存储结构中，顶点v在链表(即边表)中出现的次数为( )。
【解析】本题容易误选D。要注意的是，本题问的是顶点v在边表中出现的次数，即不关心顶点表中v的出现次数。根据邻接表的结构可知，在有向图中，顶点v出现在边表中的次数即等于顶点v的入度。选择C。
计算机 A 的时钟周期为 2.4ns，计算机B的时钟周期为 4ns。某个程序在计算机 A 上运行时的CPI为 4，在计算机B上运行时的 CPI为2。则对于该程序来说，计算机A和计算机B之间的速度关系为( )。
A. 计算机 A 比计算机 B快 1.2倍
C.计算机 A 的速度是计算机 B的 1.2 倍
B. 计算机 B 比计算机 A 快 1.2倍
D. 计算机 B 的速度是计算机 A 的 1.2 倍
【解析】CPU 执行时间=指令条数×CPI×时钟周期，假设该程序有x条指令，则计算机A的执行时间为 2.4ns×4x，计算机B的执行时间为 4ns×2x，计算机A执行时间是计算机B的 1.2倍，故计算机B的速度是计算机A的 1.2倍。B 选项的同义表述为计算机B的速度是计算机 A的 2.2 倍，所以错误。
下列有关补码表示的一些常见二进制形式中，错误的是( ) 。
A. 补码表示0 的二进制为 000 · · · 00
B. 补码表示-1的二进制为 111 · · · 11
C. 补码表示的最小整数的形式为 100 · · · 00
D. 补码表示的最大整数的形式为 111 · · · 11
【解析】n + 1 位补码表示的最大整数的形式为011 · · · 11，真值为2^n − 1，D 的表述有误，选D。考生应该熟练掌握这4 种常见的补码二进制形式。
已知IEEE 754 单精度浮点数的十六进制值为42E48000，则它的十进制为( ) 。
A. 114.25 B. 57.125 C. 50.25 D. 28.5625
【解析】IEEE 754 单精度浮点数（32 位）的组成为：符号位（第1 位），阶码（第2∼9 位），数值位（后23 位）。该数的机器数为0100 0010 1110 0100 1000 0000 0000 0000B，阶码为10000101=133，由于阶码用移码表示，所以实际值=133-127=6，所以该数=457/256×2^6=114.25。
提示：本题所用计算方法为将数值位中的最低位作为最小单位，本题最低位为1/256，由数值有效部分110 0100 1 按照1+8+64+128+256(隐含位)=457，最终得到457/256。
十进制数-9 用IEEE 754 单精度浮点数表示为( ) 。
A. 20000104H B. 82200001H C. 90000082H D. C1100000H
【解析】IEEE 754 单精度浮点数格式：数符（1 位）+ 阶码（8 位）+ 尾数（23 位），尾数最高位的“1”是被隐藏的。
先将−9 转换成二进制为−1001B = −1.001×2^3，然后计算阶码E，有E −127 = 3，因此E = 130，转换成二进制为1000 0010，又因为符号位为1，故−9 的IEEE 754 表示为1100 0001 0001 0000 0000 0000 0000 0000B，即C110 0000H。
假定编译器规定int 和short 类型的长度为32 位和16 位，执行下列C 语言语句后，x 和y 对应的机器数为( ) 。
A. 8000H，FFFF8000H B. 7FFFH，00007FFFH
C. 7FFFH，FFFF7FFFH D. 8000H，00008000H
根据题目中 int 和 short 的长度规定，分析如下：
变量 x 的赋值： unsigned short x = 32768;
unsigned short为 16 位，范围 0~65535。
32768 的二进制表示为1 0000 0000 0000 0000（17 位）。
截断为 16 位后得到1000 0000 0000 0000，即0x8000。
变量 y 的赋值： unsigned int y = x;
unsigned int为 32 位，需将 16 位的x零扩展到 32 位。
x的 16 位值0x8000扩展后为0000 0000 0000 0000 1000 0000 0000 0000，即0x00008000。
答案：D. 8000H，00008000H
已知带符号整数 A、B 用补码表示，[A]补=BCH，[B]补=71H。如果在 8 位加法器中计算 A - B，那么加法器的低位进位输入Cin以及运算后溢出标志OF、最高位进位Cout、最高数值位进位分别是（ ）。
【解析】执行的是减法运算，加法器的低位进位输入Cin = 1，[A]补 = BCH，[-B]补 = 8FH，A - B = [A]补 + [-B]补 = [A]补 + [-B]补 = BCH + 8FH = 01001011B，参与运算的两个数符号位为 1，结 果符号位为 0，发生溢出，溢出标志 OF = 1，最高位进位 Cout = 1，最高数值位进位为 0，D 对。 提示：计算机可以通过将最高位进位与最高数值位异或来判断溢出。本题中前者为 1，后者为 0，两者异或后 OF = 1。
某计算机字长16 位，它的存储容量是128KB，若按字编址，那么它的寻址范围是( ) 。
A. 64K B. 32K C. 64KB D. 32KB
【解析】字长16 位=2B，即一个地址单元可以放2 个字节，总容量为128KB，需要64K 个地址
层次化存储器结构的设计依据的原理是( ) 。
A. 存储器周期性 B. 存储器强制性 C. 访存局部性 D. 容量实效性
【解析】根据局部性原理设计的存储器层次化结构，能提高每层命中率，从而在相邻两层存储器
间，使得速度向较高层靠近的同时，让容量和价格向较低层靠近。
某1024K×32 位的存储器由若干片128K×16 位的SRAM 芯片构成，每次读写4 字节数据。若存储器按字节编址，则该存储器的地址线和数据线分别有( ) 条。
A. 20，8 B. 22，8 C. 20，32 D. 22，32
解析：题目中 SRAM 容量为 1024K×32 ，按字节编址，因为 1024K = 2^20 ，log 2 2 20 = 20，所以地址线有 20 条。每读写 4B 数据，数据线数量为 4×8 = 32 条。
一个八路组相联 Cache 共有 64 块，主存共有 8192 块，每块 64 个字节，按字节编址，那么主存地址的标记x、组号y和块内地址z分别是( )。
【解析】由于分为8组，所以组号y为3（\(2^{3}=8\)）。块大小64B，所以块内地址z为6（\(2^{6}=64\)）。主存共8192块且块大小为64B，则主存地址一共19位（\(\log_{2}8192+\log_{2}64 = 13 + 6 = 19\)），所以标记位 \(x = 19 - 3 - 6 = 6\) 。
下列命中组合情况中，一次访存过程中不可能发生的是( ) 。
A. TLB 未命中，Cache 未命中，Page命中
B. TLB 未命中，Cache命中，Page 命中
C. TLB 未命中，Cache 未命中，Page未命中
D. TLB 未命中，Cache命中，Page 未命中
【解析】D 不存在，页缺失，说明信息不在主存，Cache 存的是主存信息的副本，即Cache 内容
是主存内容的子集，故Cache 一定也没有该信息。
与单道批处理系统相比，多道批处理系统提高CPU 利用率的关键技术是( ) 。
A. 交换技术 B. 多道程序设计 C. 覆盖技术 D. 紧凑技术
【解析】多道批处理系统相比于单道批处理系统，有了多道程序设计技术。这项技术可以使程
序轮流使用CPU，CPU 始终处于忙碌状态，提高CPU 利用率。交换技术、覆盖技术和紧凑技
术都是内存管理的内容。所以正确答案为B 选项。
下列指令中，只能在内核态执行的是( ) 。
A. 读时钟指令 B. I/O 指令 C. 加法指令 D. 陷入指令
【解析】I/O 指令是对I/O 设备进行操作的指令，只能操作系统在内核态执行，读时钟指令、加
法指令和陷入指令可以在用户态执行，其中陷入指令只能在用户态执行。选B。
与宏内核操作系统相比，采用微内核结构的操作系统具有很多优点。下列选项中，不属于微内核的优点的是( ) 。
A. 运行效率高 B. 可扩展性好 C. 可靠性较好 D. 便于移植系统
【解析】微内核的用户空间和内核空间分离，用户服务的崩溃不会影响到内核空间，因此可靠
性较好。微内核需要增加服务时，只需要在用户空间增加模块，不需要修改内核，因此具有较
好的可扩展性和可移植性。微内核由于各模块之间的通信要经过内核的消息传递，系统运行效
进程在处理器上执行时，错误的说法是( ) 。
A. 进程是一个动态的过程，终有结束的时刻
C. 并行的进程之间都存在着相互依赖和制约的关系
D. 进程的并发执行可能导致程序的结果与进程执行速度有关
【解析】并行的进程之间，可以利用信号量等机制实现同步、互斥等关系，但是并不是所有并行（或并发）进程间都有相互依赖或制约的关系，所以C 选项错误。一个简单的例子：一个系统中，有一个音乐播放进程，有一个聊天进程，这两个进程运行时可以没有任何联系。A、B、D选项均是对进程特点的正确叙述。
下列调度算法中，一定是抢占式调度的是( ) 。
A. 时间片轮转 B. 先来先服务 C. 优先级 D. 短进程优先
【解析】先来先服务一定是非抢占式，时间片轮转一定是抢占式的，优先级和短进程优先既可以是非抢占的，也可以是抢占的。
下列关于临界区和临界资源的说法中，正确的是( ) 。
III.临界区是指进程中用于访问临界资源的那段代码
IV.临界区是指进程中用于实现进程同步、互斥的那段代码
A. I和 IV B. I和III C. I、II 和III D. I、II 和IV
【解析】本题考查了临界资源和临界区的基本概念，同一时间只能由一个进程使用的资源称为临界资源，临界资源是互斥共享资源，I 和II 正确；程序中访问临界资源的那一部分代码称为临界区，III 正确，IV 错误，故本题选C。
一组生产者和一组消费者同时工作，它们通过一个大小为 n 的缓冲区来生产和消费。每个缓冲区可以容纳一件产品，其中生产者负责投放产品，消费者负责消费产品，则该过程中的制约关系有( ) 。
A. 仅互斥关系 B. 仅同步关系 C. 互斥和同步关系 D. 不存在制约关系
【解析】生产者和消费者要互斥访问缓冲区，故两者存在互斥关系，B 和D 错误；生产者和消费者协作完成生产和消费，消费者负责消费生产者生产的产品，存在一种先生产后消费的同步关系，A 错误，故本题选C。
下列关于管程的说法中，错误的是( ) 。
A. 允许进入管程的进程数目与临界资源的个数有关
B. 管程内部定义了函数的具体实现，它在外部是不可见的
C. 管程机制可以便于集中管理分散于不同进程的临界区
D. 管程是进程同步工具，避免了信号量机制中大量且分散的同步操作
【解析】管程一次只允许一个进程进入，这是由管程的互斥性决定的，A 错误；管程包含了面向对象的思想，将表达共享资源的数据结构和对其进行操作的进程封装在一个对象中，并封装了同步操作，从而对进程隐藏同步的细节，简化了调用同步功能的接口，B 正确；管程机制可以便于集中管理分散于不同进程的临界区，C 正确；管程是进程同步工具，避免了信号量机制中大量且分散的同步操作，D 正确。题干要求选择错误选项，故本题选 A。
某系统中有4 个并发进程，每个进程需要4 个相同类型的资源，使得该系统必然不会产生死锁的最小资源数目是( ) 。
A. 12 B. 13 C. 14 D. 16
【解析】极端法：假设每个进程已获得3 个同类资源，则只要有可用的资源，总能有一个进程可以获得第4 个，然后顺利执行，而不会产生死锁。在极端情况下，12 个资源被分给4 个进程，每个进程获得3 个，是有可能产生死锁的，而再增加一个资源，就必然不会产生死锁，此时的资源数量是13。故本题选B。
一个进程在获得资源后，只能在资源使用完后主动释放，这是死锁产生的必要条件之一，下列选项中，可以破坏该条件的是( ) 。
【解析】一个进程在获得资源后，只能在使用完资源后由自己释放，这属于死锁的必要条件中的不可剥夺条件，可以通过剥夺资源法来破坏，所以本题选C。
下列关于计算机网络的描述正确的是( ) 。
A. 计算机网络中的共享资源是指 CPU、内存和操作系统
B. 计算机网络可以看作一个用于共同完成一项任务的分布式系统
C. 计算机网络最基本的功能是分布式处理
D. 计算机网络在逻辑组成上可以分为通信子网和资源子网
【解析】计算机网络中的共享资源是指加入网络的用户能够使用网络中各个计算机系统的各种资源，包括软件、硬件以及数据资源等，A 错误。分布式系统是建立在计算机网络之上的软件系统，B 错误。计算机网络最基本的功能是资源共享，C 错误。计算机网络在逻辑组成上可以分为通信子网和资源子网，D 正确，因此答案为D。
已知某通信的信号传输速率为64kb/s，若一个载波信号码元有4 个有效的离散值，则该信道的波特率为( ) 。
A. 16kBaud B. 32kBaud C. 64kBaud D. 128kBaud
【解析】一个载波信号码元有4 个有效离散值说明一个码元需要log 2 4 = 2 个比特表示，信号传输速率为64kb/s，则波特率为64 ÷ 2 = 32kBaud，因此答案为B。
A. 保证可靠传输 B. 网段延伸和范围扩大
C. 复用和分用 D. 进行数据的存储转发
【解析】中继器和放大器无法保证可靠传输和存储转发，同样也无法做到复用和分用，ACD 错误。但是都能用于网络延伸和范围扩大，但是原理不同，放大器作用于模拟信号，只是简单地放大信号，中继器作用于数字信号，将信号整形放大再转发出去，因此答案为B。
A. 帧定界功能 B. 电路管理功能 C. 差错控制功能 D. 流量控制功能
【解析】电路管理是物理层的功能，注意不要与数据链路层的链路管理功能混淆。电路通常指信号传输的实际物理载体（也称物理链路），而数据链路是在电路的基础之上附加上了链路通信协议。电路管理功能管理的是物理链路，链路管理功能管理的是数据链路。
数据链路层采用GBN 协议实现可靠传输，若帧首部中序号字段占3 比特，则发送窗口的最大值为( ) 。
解析：GBN 协议的接收窗口大小为 1，所以 \(W_R + W_T=1 + W_T\leq2^3\)，可得 \(W_T\leq7\)，选 C。
根据CSMA/CD 协议的工作原理，需要提高最短帧长度的是( ) 。
A. 网络传输速率不变，冲突域的最大距离变短
B. 冲突域的最大距离不变，网络传输速率提高
D. 在冲突域不变的情况下减少线路中的中继器数量
【解析】冲突域最大距离变短，则最大往返时间减少，即争用期减少，可以更早确定无冲突，所以最短帧长可以减少，选项A 错误。注意区分传输速率和传播速率，传输速率提高则可以更快的发完原有的最短帧长，所需时间比争用期短，解决办法为提高最短帧长，选项B 正确。上层协议使用TCP 的概率增加与最短帧长度无关，选项C 错误。减少中继器数量可以减小因中继器而产生的转发时延，使最大往返时间减少，即争用期减少，需要减少最短帧长度，选项D 错误。因此答案为B。
无线局域网不使用CSMA/CD 而使用CSMA/CA 的原因是，无线局域网( ) 。
A. 不能同时收发，无法在发送时接收信号
C. 无线信号的广播特性，使得不会出现冲突
D. 覆盖范围很小，不进行冲突检测不影响正确性
【解析】由于隐蔽站、暴露站等问题，在无线局域网中进行冲突检测（CD）的意义不大，所以转而使用冲突避免（CA）这一方法尽可能地减少冲突发生的可能性，因此答案为B。
一台交换机具有24 个10/100Mbps 的端口和两个1Gbps 端口, 如果所有端口都工作在全双工状态, 那么交换机的最大带宽为( ) 。
A. 4.4Gbps B. 6.4Gbps C. 6.8Gbps D. 8.8Gbps
【解析】由于交换机支持并行传输，且可以工作在全双工状态下，所以其最大带宽为所有端口
带宽之和的两倍，为2 × (24 × 100Mbps + 2 × 1Gbps) = 8.8Gbps，因此答案为D。
（13分）已知一个整数序列\(A(a_0, a_1, \cdots, a_{n - 1})\)，该序列中有一个元素只出现一次，其他元素都会出现两次，且相同元素一定相邻。请设计一个在时间上尽可能高效的算法，找出仅出现一次的元素。例如，数组\(\{3,3,6,6,9,0,0\}\)，则返回\(9\)。要求：
(1) 给出算法的基本设计思想。（3分）
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。（8分）
(3) 说明你的算法的时间复杂度。（2分）
学生的设计思想为：从下标1开始每次比较相邻两个元素，若不相等则返回前一个元素。其核心逻辑与标准答案一致，都是从成对元素中判断目标值，只是标准答案从下标0开始比较，学生从下标1开始（即比较a[1]与a[2]、a[3]与a[4]等），同样能正确找出只出现一次的元素（因为目标元素之前的配对均相等，目标元素与其后一个元素不等）。思路正确，逻辑成立，给3分。
代码实现： int search() { for(int i=1; i<n; i+=2) { if(a[i] != a[i+1]) return a[i]; } } 该代码需要基于全局数组a和全局变量n，但原题要求函数参数形式（如int func(int *A, int n)），学生的函数没有参数，但注释说明a[]、n为全局变量，这在C/C++中也是合法的，功能上能够实现查找。核心循环逻辑正确：从i=1开始，每次比较a[i]与a[i+1]，若不相等则返回a[i]；若全部相等（即目标元素在最后），函数会没有返回值，存在缺陷——缺少最终的return a[n-1]语句。这是一个逻辑遗漏，会导致在目标元素为最后一个时函数返回未定义值。因此代码存在逻辑错误，扣3分。
代码缺少必要的注释（如“若循环结束则最后元素为目标”），但注释并非主要得分点，且已有基本注释，不额外扣分。综合代码正确性，本题得5分。
学生明确写出时间复杂度为O(n)，且是一次循环遍历，与标准答案一致，给2分。
(1) 顺序遍历坐标为偶数的元素，与后一个元素比较，如果前一个元素与后一个元素不一样，则前一个元素为目标值。
(3) 算法中需要顺序遍历数组，时间复杂度为O(n)。
（10分）对 N 个出现频率均 a 的字符构造哈夫曼树（设 N 为 2 的整数次幂，a 为正整数）并编码，则：
(1) 一定可以得到所有字符对应的编码长度都相同的哈夫曼树吗？若不是，说明某个字符的最长编码长度是多少，最短编码长度为多少？（4分）
(3) 对长度为 M 的字符序列进行编码，设所有字符均出现且频率相同，则编码后的长度最少是多少 bit？压缩比是多少（假设原字符采用 ASCII 编码）？（4分）
提示：在此题中，如果要输入\(\log_2N\)，输入logN即可。
学生回答“能”，并指出“2^n能把二叉树变成满二叉树，所有结点…路径长度相同”。核心判断正确，但未明确说明编码长度为log₂N，且对“最长编码长度”和“最短编码长度”没有直接作答。鉴于回答基本符合标准答案的核心结论（能得到等长编码），且思路正确，但缺失细节，酌情扣1分。得3分。
学生写出WPL = aN log₂N，与标准答案N × log₂N（注意a为正整数，所有字符频率均为a，因此WPL实际应为aN log₂N）完全一致，计算正确。得2分。
该小题学生未作答，仅写了“（3）”字样，无任何内容。因此得0分。
(1) 一定能得到所有字符对应的编码长度都相同的哈夫曼树，对N个出现频率相同的字符构造哈夫曼树，得到高度为\((\log_2N)+1\)的满二叉树，每个字符的编码长度为\(\log_2N\)。
(2) 每个编码的长度为\(\log_2N\)，共有N个字符，最小带权路径长度WPL为\(N\times\log_2N\)。
(3) 对于长度为M的字符序列，ASCII码占7bit，压缩前需要7M bit存储，压缩后，每个字符的编码长度为\(\log_2N\)，压缩后需要\(M\times\log_2N\)M bit存储，压缩比是\((\log_2N)/7\) 。
（12分）假定在一个 32 位字长的计算机中运行如下类 C 程序段：
若程序执行时将 10 个 32 位寄存器 R1 - R10 分别分配给变量 us1、us2、s1、s2、m1、m2、n1 - n4。 请回答下列问题： (1) 执行上述程序段后，寄存器 R2、R4、R5、R6 的内容分别是什么？(用十六进制表示)（4分） (2) 执行上述程序段后，n1、n2 的值分别是多少？(用十进制表示)（2分） (3) 计算 m2 得到的进位标志 CF、零标志 ZF 分别是多少？（2分） (4) 计算机内部如何确定无符号数加 / 减法的进位标志 CF？有符号整数加 / 减法会影响 CF 吗？（4分）
学生的回答存在严重问题。题目要求明确写出R2、R4、R5、R6的内容（十六进制表示），而学生的回答中R2和R4并未给出明确数值，而是以“手写二进制全1形式”等模糊描述代替，未给出实际十六进制结果。R5 = 0000 0064H，学生写为“0000 0001 00101100H”，此值对应十进制300，但标准答案中R5为100（0064H），且学生十六进制格式错误（多写了“0001”）。R6 = 0000 01F4H，学生写为“1111 1110 1010 101”，既非十六进制，数值也错误（标准答案为500）。整体来看，学生仅对R5和R6进行部分描述，R2、R4完全未作答，且所有寄存器内容均错误。故扣4分。
学生回答n1 = 299，n2 = 301。标准答案为n1 = 100，n2 = 500。学生将s2错误理解为-1（实际为-200），导致计算错误，核心逻辑错误。两问均答错，扣2分。
学生回答CF = 0，ZF = 0。标准答案为CF = 1，ZF = 0。由于m2为us1-us2，us1=300，us2=65336，us1 （4）得分及理由（满分4分） 学生回答“CF是无符号数溢出标志，需要对最高位进位检测”，此表述不完整，CF的定义应为“无符号数加/减法的进位/借位标志”，且检测逻辑应明确为最高位进位输出与Cin的异或。学生未提到Cin，也未明确其检测逻辑。对于“有符号数加减不影响CF”，学生回答“不会”，但标准答案为“有符号运算也会产生CF，但无意义”，学生的“不会”属于错误回答。不过，学生正确提到了OF与CF检测逻辑不同，算部分思路正确。综合来看，此题回答不够准确，但关键点（无符号进位检测）略有触及，且OF与CF不同逻辑正确，故酌情给1分，扣3分。 题目总分：0+0+0+1=1分
学生回答“CF是无符号数溢出标志，需要对最高位进位检测”，此表述不完整，CF的定义应为“无符号数加/减法的进位/借位标志”，且检测逻辑应明确为最高位进位输出与Cin的异或。学生未提到Cin，也未明确其检测逻辑。对于“有符号数加减不影响CF”，学生回答“不会”，但标准答案为“有符号运算也会产生CF，但无意义”，学生的“不会”属于错误回答。不过，学生正确提到了OF与CF检测逻辑不同，算部分思路正确。综合来看，此题回答不够准确，但关键点（无符号进位检测）略有触及，且OF与CF不同逻辑正确，故酌情给1分，扣3分。
(1) R2 = 0000 FF38H，R4 = FFFF FF38H，R5 = 0000 0064H，R6 = 0000 01F4H。 us2为unsigned short类型，其值为65336 = \(2^{16}-200 = FF38H\)，将其分配到32位寄存器需要进行零扩展，所以R2 = 0000 FF38H； m1为unsigned short类型，us1 + us2 = 65636，超出unsigned short的最大表示范围65535，因此会溢出到无符号数65636% \(2^{16}\) = 100 = 0064H，分配到32位寄存器需要进行零扩展，所以R5 = 0000 0064H； us2 = 65336 = FF38H，将其转换为short类型，机器数不变，改变解释方式，可知s2为负数，将其分配到32位寄存器需要进行符号扩展，所以R4 = FFFF FF38H； m2为unsigned short类型，us1 - us2 = -65036，因此会溢出到无符号数 - 65036% \(2^{16}\) = 500 = 01F4H，分配到32位寄存器需要进行零扩展，所以R6 = 0000 01F4H。
(2) n1 = 100，n2 = 500。us1 = 300，按有符号数解释s1 = 300。s2的机器数为FF38H，按有符号数解释s2 = -200。s1 + s2 = 100，s1 - s2 = 500，结果均在short型变量表示范围内，未发生溢出。所以n1 = 100，n2 = 500。
(3) m1 = us1 - us2，由于us1 < us2，因此会产生借位，所以CF = 1；结果不为0，所以ZF = 0。
(4) 计算机内部判断CF的逻辑表达式为CF = Cin⊕ Cout，其中Cin为低位进位输入，当执行减法时Cin = 1，执行加法时Cin = 0，Cout为最高位进位输出； 当执行有符号加/减运算时也会按上述规则产生CF标志位，这是因为加法器对于无/有符号加减法是统一的，在电路层面数据只是一个二进制串，所以会同等产生各标志位。但需要注意的是，对于有符号加/减运算，CF标志位是没有意义的。
（11分）以下是计算两个向量点积的程序段：
请回答下列问题： (1) 访问数组 x 和 y 的时间局部性和空间局部性如何？（2分） (2) 假定数据 Cache 采用直接映射方式，数据区容量为 32 字节，每个主存块大小为 16 字节；编译器将变量 sum 和 i 分配在寄存器中，数组 x 存放在 0000 0040H 开始的 32 字节的连续存储区中，数组 y 则紧跟在 x 后进行存放。该程序数据访问的命中率是多少？要求说明每次访问时数组 Cache 的命中情况。（3分） (3) 将上述 (2) 中的数据 Cache 改用 2 - 路组相联映射方式，Cache 采用 LRU 替换策略，块大小改为 8 字节，其他条件不变。则该程序数据访问的命中率是多少？（3分） (4) 在上述 (2) 条件不变的情况下，将数组 x 定义为 float [12]，则数据访问的命中率是多少？（3分）
（1）得分及理由（满分2分） 学生答案中完全没有提及时间局部性和空间局部性的分析，未回答第(1)问的任何内容。因此得0分。
（2）得分及理由（满分3分） 学生答案中完全没有涉及直接映射Cache命中率计算的相关内容，仅在第(3)问出现“CF=0 ZF=0”等与本题目点积运算完全无关的内容。未回答第(2)问。因此得0分。
（3）得分及理由（满分3分） 学生答案中出现了“CF=0 ZF=0”等标志寄存器的内容，这些是程序状态字相关的知识，与本题的两路组相联Cache命中率计算无关。未回答第(3)问。因此得0分。
（4）得分及理由（满分3分） 学生答案中提到了“CF是无符号数溢出标志，需要对最高位进位检测”以及“不会，有符号数相加是OF”，这些属于算术逻辑单元的标志位检测内容，与本题将数组x扩展为float[12]后的Cache命中率计算无关。未回答第(4)问。因此得0分。
(1) 由于数组按行优先存储，所以空间局部性较好，每个元素只被访问一次，所以时间局部性较差。 (2) 由于每个主存块为 16 字节，则每个块可以存储 4 个 float 数组元素。直接映射方式，一共 32/16 = 2 行，行号 1 位为 32 位地址中的倒数第 5 位，起始地址 0000 0040H 位于一个块的起始位置。由于数组 x 需要占用物理地址中的连续的 2 块，因此分别对应 Cache 中的 0、1 行，数组 y 紧随其后，也对应 0、1 行，因此循环内的语句执行时，依次访问 x 与 y 数组的同一元素，将会导致 Cache 同一块中的内容不停地在 x 数组与 y 数组之间切换，比如计算到 x [1]×y [1] 时，原本 Cache 第 0 行存放的是 y [0] 至 y [3] 元素，需要先将 x [0] 至 x [3] 换入，再将 y [0] 至 y [3] 换入，因此每次访问都不会命中，命中率为 0%。 (3) 二路组相联，块大小为 8 字节，共有 2 组。其他条件不变，则每个块可以存储两个数组元素，x [0]~x [1]、x [2]~x [3] 依次对应 0、1 组以此类推，y [0]~y [1]、y [2]~y [3] 也依次对应 0、1 组，每组可以容纳两个数组相同位置的两个元素，比如 x [0]、y [0] 和 y [0]、y [1] 可以分别换入到 0 组的 0 路、1 路中，访问 0 号元素时未命中，访问 1 号元素均可以命中，因此命中率为 50%。 (4) 数组 x 的大小将占据 3 个 Cache block 的大小，数组 y 占据 2 个。x 数组中三个块对应的 Cache 行号分别为 0、1、0，实际程序不会访问 8~11 号元素，y 数组中两个块对应的 Cache 行号是 1、0，访问同一位置的元素时，两个数组占据的 Cache 行不冲突，则访问数组 x 和数组 y 的第 0、4 号元素不命中（共 4 次），其余的元素可以命中，命中率为 12/16×100% = 75%。
（7分）一个动态优先级调度算法（优先数大的优先级低，优先级相同时序号小的进行调度），根据等待时间和运行时间对优先数进行动态变化，算法如下：
①处于就绪队列中的进程的优先数 \( p \) 根据等待时间 \( t \)（单位秒）进行变化，\( p = p - t \)；
②处于运行状态的进程的优先数 \( p \) 根据运行时间 \( t \)（单位秒）进行变化，\( p = p + 2×t \)；
③优先数 \( p \) 每隔 1 秒重新计算；
根据下表给出的 5 个进程的到达时间和执行时间，回答下面的问题。（时间单位：秒）
(1) 画出 5 个进程执行的顺序图。（3分）
(2) 根据以上的调度算法，分别计算出每个进程的周转时间和响应时间。（4分）
学生给出的执行顺序为：P1→P2→P4→P1→P3→P1→P3（箭头指向P5），但未完整列出P2、P4、P5的具体执行时间区间，也未明确给出完整的时间轴顺序（如P2在1-3秒，P4在3-4秒，P5在9-11秒）。根据标准答案，完整正确的顺序为：P1(0-1)，P2(1-3)，P4(3-4)，P3(4-5)，P1(5-6)，P3(6-7)，P1(7-8)，P3(8-9)，P5(9-11)。学生仅列出了部分进程的先后次序，且遗漏了P2、P4、P5的完整执行时间，顺序描述不完整。由于核心调度过程（抢占、优先级变化）基本体现，但未画出完整的时间轴顺序图，因此酌情给1分。
学生给出的周转时间：P1=8，P2=2，P3=8，P4=1，P5=6。与标准答案对比：P1、P2、P4正确，P3应为7（学生为8），P5应为7（学生为6），因此周转时间部分有两处错误，扣1分。响应时间：P1=0，P2=0，P3=3，P4=0，P5=4。标准答案中P3应为2，P5应为5，因此响应时间有两处错误，扣1分。由于部分数据正确，且计算方法理解正确（周转时间=完成时间-到达时间，响应时间=首次运行时间-到达时间），但结果有误，故该项得2分。
(1) 5个进程在运行过中的优先级如下表所示：
由题意可知，CPU会优先调度优先级低的进程，5个进程的执行顺序如下：
(2) 进程的周转时间 = 等待时间 + 执行时间，进程的响应时间是指用户提交请求到系统首次响应所用的时间。由进程执行的顺序图可知，$P_1$的周转时间 = 5 + 3 = 8s，$P_1$的响应时间 = 0 - 0 = 0s，$P_2$的周转时间 = 0 + 2 = 2s，$P_2$的响应时间 = 1 - 1 = 0s，$P_3$的周转时间 = 4 + 3 = 7s，$P_3$的响应时间 = 4 - 2 = 2s，$P_4$的周转时间 = 0 + 1 = 1s，$P_4$的响应时间 = 3 - 3 = 0s，$P_5$的周转时间 = 5 + 2 = 7s，$P_5$的响应时间 = 9 - 4 = 5s。
（8分）某寺庙有小和尚、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用。水缸可容10 桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为3 个。每次入缸取水仅为1 桶水，且不可同时进行。试用信号量和P/V 操作给出有关从缸取水、入水的算法描述。
（9分）有两台主机 A 和 B 连接在 800m 长的电缆线的两端，并在\(t = 0\)时各自向对方发送一个帧，长度为 1500bit（设首部和前同步码、假定在 A 和 B 之间有 4 个转发器，在转发帧时会产生 20bit 的延时）。这时传播速率为 100Mbit/s，而 CSMA/CD 的退避时间是随机数 r 倍的争用期，争用期为512bit，在发生第一次碰撞后，在退避时 A 选择 r = 0 而 B 选择 r = 1。忽略发生碰撞后的人为干扰信号和帧间最小间隔。 (1) 设信号的传播速率为 \(2\times10^{8}\text{m/s}\)。试计算从 A 到 B（包括 4 个转发器）的传播时延。（3分） (2) 在什么时间（以秒为单位）B 完全收到了 A 发送的帧？（6分）
学生的计算过程为：\(4+1=5\)，\(800÷5=160m\)，\(t_p=160/(2×10^8)=0.8μs\)，\(T_p=5×0.8μs=4μs\)。计算逻辑将电缆分为5段（4个转发器自然将线路分为5段），并计算每段传播时延后乘以5得到4μs，总传播时延结果与标准答案的第一项一致。但该计算遗漏了4个转发器产生的处理时延（每个20bit，共80bit，对应0.8μs），导致最终结果缺0.8μs。第一小问满分3分，由于核心计算思路正确（分段计算传播时延），且得到了部分正确结果，但未考虑转发器处理时延，酌情扣1分，得2分。
学生计算了发送时延\(t_f=1500/10^8=15μs\)，并给出最终答案\(t=27μs\)。从手写内容看，学生给出了时间线分析过程（但图片识别中未清晰显示完整推导步骤，仅看到最终结果）。经分析，此结果27μs与标准答案29.4μs不同，其差异来源于学生对第一问结果不同（4μs而非4.8μs），并可能推导为：第一次冲突在4μs发生，退避后A在8μs重传，第一个比特在12μs到达B，最后一个比特在12+15=27μs到达B。该推导逻辑基于学生第一问的传播时延4μs，思路正确，但基于错误的第一问结果，导致最终答案偏差0.8μs（转发器时延未计入）。此外，学生对冲突检测和退避过程的理解基本正确（未详细展示，但从结果推导可见），核心逻辑框架正确。故本题得分为4分（因第一问错误导致最终结果偏差，但整体思路正确，扣2分）。
(1) 传播时延为 4.8μs。信号在信道中传播需要的时间为\(\frac{800m}{2×10^{8}m/s}=4μs\)。中间经过四个转发器，消耗时间为\(4×\frac{20bit}{100Mbit/s}=0.8μs\)。所以总的传播时延为\(4μs + 0.8μs = 4.8μs\)。
(2) 在\(t = 2.94×10^{-5}s\)时 B 完全收到 A 发送的帧。发送一帧的传输时延为\(\frac{1500bit}{100Mbit/s}=15μs\)，而单向传播时延为 4.8μs，所以当 B 收到 A 发送的第一个比特时（即检测到信道冲突时），发送还未结束。整体的时间线如下：
(a) \(t = 0\)，A 和 B 同时发送帧。
(b) \(t = 4.8μs\)，A 和 B 同时检测到冲突，均停止发送。
(c) \(t = 4.8μs + 4.8μs = 9.6μs\)，B 已发送的最后一个比特到达 A，A 检测到冲突结束，立即重传。
(d) \(t = 9.6μs + 4.8μs = 14.4μs\)，A 发送的第一个比特到达 B（此时 B 在退避中，未发送数据）。
(e) \(t = 14.4μs + 15μs = 29.4μs\)，A 发送的最后一个比特到达 B。
【注意】根据 CSMA/CD 的机制，B 的退避时间结束后，由于 A 还在发送数据，此时 B 会继续等待到信道空闲后才继续发送。