下列C语言函数的时间复杂度是( )。

int getK(int k) {
    int cnt = 0, left = 0;
    for (int right = 0; right < n; right++) {
        if (nums[right] == 1) cnt++;
        while (left <= right && cnt >= k) {
            if (nums[left] == 1) cnt--;
            left++;
        }
    }
}

A. \( O(\log_2 n) \)    B. \( O(n) \)    C. \( O(n\log_2 n) \)    D. \( O(n^2) \)

某带头结点的静态链表初始状态如下表所示。next = -1 时，表示当前结点是尾结点。静态链表头指针 head 下标为 0、空闲链表（所有空闲数组单元组成的单链表）头指针 avail 初始为 9。删除当前静态链表中的第三个存储数据的元素、并将空闲位置采用头插法插入空闲链表后，各结点的 next 值更新的结果为（）。

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{数组下标} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \text{data} & & \text{A} & \text{B} & \text{C} & \text{D} & \text{E} & \text{F} & \text{G} & \text{H} & \text{I} \\ \hline \text{next} & 1 & 3 & 5 & 7 & -1 & 6 & -1 & 8 & 2 & 4 \\ \hline \end{array}

A. 1,3,5,7,-1,6,-1,9,2,4    B. 1,3,5,8,-1,6,-1,4,2,7

C. 1,7,5,9,-1,6,-1,8,2,4    D. 1,3,5,7,-1,6,-1,2,9,4

已知大小为10×10×10的三维数组A的前两维构成对称矩阵（即A[i][j][k] = A[j][i][k]），按列优先顺序存储且仅存储下三角部分，每个元素占用4个存储单元。若元素A[2][3][4]的存储地址是3000，则元素A[5][5][5]的存储地址是（）。

A. 3292     B. 3296     C. 3300     D. 3304

对于关键字集合 {1, 4, 5, 10, 16, 17, 21}，能够构成不同的平衡二叉树的数量是(    )。

A. 7          B.  10          C.  13         D.  17

已知字符集$\{a,b,c,d,e\}$，各字符出现的次数分别为$5,3,13,12,9$。进行哈夫曼编码时，生成的哈夫曼树采用顺序存储方式保存在数组$R$中，用$-1$表示结点不存在。哈夫曼树中左子树分支表示编码$0$，右子树分支表示编码$1$。数组$R = [42, 17, 25, 9, 8, 12, 13, −1, −1, 3, 5]$，则编码序列$011011111000011010$的译码结果为（）。

A. $aacdcae$        B.  $aacdeab$       C.  $bacebca$        D. $bacedcb$

并查集的秩指树的高度。并查集按“秩”优化指将将秩较小的树合并到秩较大的树中， 从而尽量 保持树的平衡性。并查集按秩优化的 Union 函数 C 语言实现如下。在以下代码中， rank[x] 指结 点 x 的秩。若某个并查集有元素0 ∼ 5，初始时各个元素的秩均为 1，依次执行下列操作 Union(0, 1) ，Union(2, 3) ，Union(1, 3) ，Union(3, 4) 后，元素 4 的根结点是(    )。

void Union(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}

A. $0$    B. $1$    C. $3$    D. $4$

对下图 (a) 使用 Prim 算法求最小生成树， 对下图 (b) 使用 Kruskal 算法求最小生成树。若分别以 结点 a 和结点f 作为所得最小生成树的根结点，则这两个最小生成树（忽略权值）构成的森林 对应的二叉树不可能是(    )。

已知模式串为"ababac"，主串为"cbabababac"。在 KMP 算法匹配过程中， 第一次出现“失配”时， i = j = 0。则下列描述正确的是(    )。

A.  当主串第 1 个字符 'c' 与模式串第 1 个字符 'a' 发生失配时，模式串指针应移动到 next[0] 的位 置，主串指针不变

B.  模式串"ababac" 的 nextval 数组为 [-1, 0, 0, 1, 2, 3]

C.  当主串第 8 个字符 'b' 与模式串第 6 个字符 'c' 失配后，下次开始匹配时， 主串指针 i = 7 ，模 式串指针j = -1

D. 整个匹配过程中，字符比较的总次数为 11 次

散列表HT长度为7，初始为空，散列函数\( H(k)=k\%7 \)。在HT中依次插入关键字11,21,39,46,55，然后再删除键值21。若分别采用拉链法（尾插法）和线性探测再散列法处理冲突，则下列描述错误的是（）。

A. 采用拉链法时，查找成功的平均查找长度为\( \frac{7}{4} \)，查找失败的平均查找长度为\( \frac{4}{7} \)

B. 采用线性探测再散列法时，查找成功的平均查找长度为\( \frac{9}{4} \)，查找失败的平均查找长度为\( \frac{22}{7} \)

C. 采用拉链法时，HT的装填因子为\( \frac{2}{7} \)，采用线性探测再散列法时，HT的装填因子为\( \frac{4}{7} \)

D. 采用线性探测再散列法时，在HT中查找关键字14，确认查找失败时的散列地址为2

对有序序列{1,2,3,4,5,6,7,8,9,10}，使用折半查找（判定树采用向下取整）。假设各元素的查找概率相等，则下列描述错误的是( )。

A. 该折半查找判定树是AVL树

B. 查找成功的平均查找长度为$\frac{29}{10}$

C. 查找失败的平均查找长度为$\frac{50}{11}$

D. 该折半查找判定树的后序遍历序列为{1,4,3,2,7,6,10,9,8,5}

对初始关键字序列 {49, 38, 65, 97, 76, 13, 27} 进行排序，若堆排序采用大根堆且已完成初始建堆，快速排序每次以序列中第一个元素为枢纽，下列关于两趟排序后的结果描述正确的是(    )。

A. 堆排序后： {13, 49, 65, 38, 27, 76, 97}。快速排序后： {27, 38, 13, 49, 76, 97, 65}

B.  堆排序后： {13, 49, 65, 38, 27, 76, 97}。快速排序后： {13, 27, 38, 49, 65, 76, 97}

C.  堆排序后： {65, 49, 13, 38, 27, 76, 97}。快速排序后： {27, 38, 13, 49, 76, 97, 65}

D. 堆排序后： {65, 49, 13, 38, 27, 76, 97}。快速排序后： {13, 27, 38, 49, 65, 76, 97}

某机器M的主频为100MHz。程序P中最初没有左移2位指令，对P进行优化，将程序中所有的乘4指令都换成左移2位指令，得到优化后的程序P1。已知在M上执行程序P时访问乘4指令的Cache命中率为90%，命中后的CPI为94，程序执行时间为12s。执行程序P1时访问左移2位指令的Cache命中率为99%，命中后的CPI为3，程序执行时间为10s。当Cache未命中时都需要额外的100个时钟周期进行访存取指，则P中乘4指令被换成左移2位指令的数量是( )。

A. 1×10^6      B. 2×10^6      C. 3×10^6      D. 4×10^6

某C语言编译器规定short类型为16位，int类型为32位，long long类型为64位，float采用IEEE754单精度浮点数表示。则执行下列C语言代码段后，t的值是( )。

short s = -1;
unsigned int u = s;
float f = u;
long long t = f;

A. \(2^{31}\)    B. \(2^{31} - 1\)    C. \(2^{32}\)    D. \(2^{32} - 1\)

计算机字长为32位，在进行32位补码整数除法运算时，除数寄存器Y的初始值为FFFF FFFFH，余数寄存器R的初始值为FFFF FFFFH，余数/商寄存器Q的初始值为8000 0000H，则除法结果是（）。

A. \(2^{31}\)     B. \(-2^{31}\)
C. 发生溢出     D. 除0异常

IEEE754双精度浮点格式表示的数中，最大的非规格化数与最大的负规格化数作和的结果是( )。

A. $-2^{-1075} - 2^{-1023}$    B. $-2^{-1074} - 2^{-1022}$

C. $2^{-1074}$    D. $-2^{-1074}$

某计算机采用4体低位交叉编址存储器。存取周期\( T = 80\text{ns} \)，总线启动访问时间\( \Delta t = 20\text{ns} \)，CPU访问的主存地址序列为0,3,9,17,2,4,8,67,51,10。该序列访问过程中，若发生体冲突则后续访问都要随之延后，则发生体冲突的次数是（）。

A. 1    B. 2    C. 3    D. 4

某系统依次进行 4 次访存读数操作，这 4 次访存操作情况如下：第 1 次：TLB 命中，未发生缺 页，Cache 命中；第 2 次：TLB 未命中，未发生缺页， Cache 未命中；第 3 次：TLB 未命中，发 生缺页，Cache 未命中；第 4 次：TLB 命中，未发生缺页， Cache 未命中。已知缺页处理过程中 会同时更新 TLB 和页表，并将整个缺页处理过程只视作一次访存，则这 4 次访存操作的总访存 次数是(    )。

A. 5          B.  6          C.  7         D.  8

某32位计算机采用小端方式存储，指令格式为定长32位。add指令的格式及部分编码为：

\[ \begin{array}{|c|c|c|c|c|} \hline 011001 & \text{rs（4位）} & 00 & \text{rd（4位）} & \text{imm（16位）} \\ \hline \end{array} \]

add指令的功能是：$R[rd] \leftarrow R[rs] + imm$。其中，R[x]表示通用寄存器x的内容，imm为补码表示的立即数，通用寄存器r1～r15的编号为1H～FH。则指令“add r1, r2, -259”（$(r1) \leftarrow (r2) + (-259)$）在内存中存储的机器码是（用十六进制表示）（）。

A. 6481 FEFDH    B. FDFE 8164H

C. 6442 FEFDH    D. FDFE 4264H

在典型的多周期处理器中（包含取指、译码/取数、执行、访存、写回五个阶段），不同类别的异常和中断会在指令执行的特定阶段进行检测。下列描述正确的是(    )。

A.  “缺页”异常一定在访存阶段检测

B.   “溢出”异常一定在访存阶段检测

C.   “外部中断”一定在取指阶段检测

D.   “无效指令操作码”异常一定在译码 / 取数阶段检测

下列部件中，需要控制器提供显式控制信号的是(    )。

I. 算术逻辑部件（ ALU ）        II. 多路选择器（ MUX ）        III. 三态门

IV. 程序计数器（ PC ）的自增加法器          V. 指令译码器

A. I 、II 、III                    B.  I 、II 、V                      C.  II 、III 、IV                  D.  III 、IV 、V

在采用“取指、译码/取数、执行、访存、写回”5段流水线的RISC处理器中，执行如下指令序列，其中s0、s1、s2、t1和t2表示寄存器编号，每个流水段周期为1个时钟周期。

I1: add s2, s1, s0  //R[s2] ← R[s1] + R[s0]
I2: sub t2, s0, s3  //R[t2] ← R[s0] - R[s3]
I3: lw t1, 0(t2)    //R[t1] ← M[R[t2]+0]
I4: addi t1, t1, t2  //R[t1] ← R[t1] + R[t2]

若采用转发（旁路）技术和硬件阻塞处理数据冒险，则执行上述4条指令的CPI是（）。

A. 2    B. 2.25    C. 2.5    D. 3.5

某计算机的主频为 1GHz ，CPI 为 4。若该计算机中配置的磁盘每个磁道有 16 个 512B 的扇区。 磁盘旋转一圈的时间是 8.192ms ，忽略寻道和旋转延迟。采用 DMA 方式传送数据，每次 DMA   传送块大小为 500B，且 DMA 预处理和后处理的总开销为 500 个时钟周期，则 CPU 用于该磁盘  输入/输出的时间、占 CPU 总时间的百分比最大是(    )。

A. 0.05%        B.  0.1%       C.  0.15%       D. 0.2%

下列关于操作系统内核设计与内存管理的描述中，正确的是(    )。

A. 微内核将文件系统置于用户态，通过进程间通信，性能优于宏内核

B.  外核允许用户态直接管理物理内存，但需内核提供虚拟地址映射

C.  虚拟内存通过分页机制实现进程地址隔离，同时支持内存超量分配

D. 宏内核的模块间通过消息传递通信，耦合度低但扩展性更强

当用户进程通过系统调用陷入内核态时，下列描述正确的是(    )。

A. CPU 需保存用户态寄存器到当前进程的 PCB 中，并切换至共享内核栈执行

B.  若此时发生磁盘中断，处理程序一定会直接复用当前进程的内核栈保存上下文

C.  系统调用返回前若进程被阻塞，需将用户栈内容复制到 PCB 以便后续恢复

D.  中断处理程序执行期间，进程调度器可能将 CPU 分配给其他就绪进程

下列关于进程、线程与同步机制的描述中， 错误的是(     )。

A. 多线程进程中，某个线程执行信号量的 P 操作可能导致其他线程阻塞

B.  管程的 wait 操作必须与 signal 成对出现，否则可能破坏条件变量的状态

C.  同一进程的线程共享文件描述符表，但各自拥有独立的用户栈和寄存器

D. 死锁的四个必要条件中，抢占式调度可破坏“不可剥夺条件”

下列关于进程同步机制的描述中，正确的是(    )。

I. 关中断同步方式通过屏蔽中断实现互斥，仅适用于单 CPU 系统

II. 忙等待的同步方式会导致 CPU 资源浪费

III. 信号量机制是操作系统提供的高级同步工具，可跨进程、跨 CPU 核心实现安全互斥与同步

IV. 管程作为编程语言级同步机制，仅适用于单线程环境

V. 硬件实现的 Test-and-Set 指令可在多 CPU 系统中实现原子性互斥

A. I 、II 、III        B.  I 、II 、III 、IV       C.  II 、III 、V        D.  I 、II 、III 、V

在进程的虚拟地址空间中，以下可能位于同一存储段的变量是(    )。

A. 全局变量、函数内的局部指针变量、指针指向的动态分配的变量

B.  全局常量、函数代码

C.  函数内的局部非静态变量、全局指针变量

D.  函数参数、指针指向的静态变量

下列关于内存管理方法的描述中，正确的是(    )。

A. 动态分区分配中的最佳适应算法通过按地址排序空闲块来提高分配速度

B.  伙伴算法在释放内存时立即合并相邻块以减少外部碎片

C.  分页管理消除了外部碎片，但可能存在内部碎片

D. 虚拟内存的页面置换算法中， FIFO 算法不会出现 Belady 现象

某文件系统采用索引结点存放文件的属性和地址信息， 其中包含 10 个直接地址项、 1 个一级间 接项和 1 个二级间接项。磁盘块大小为 2KB，每个地址项占 4 B。若采用混合索引分配方式， 索 引表内仅存储地址项，并采用顺序查找方式。对于某达到理论最大长度的文件，访问索引结点 中直接地址项对应数据的概率为 40% ，访问一级间接项对应数据的概率为 20% ，访问二级间接 项对应数据的概率为 40% ，对于不同层次内部对应的数据等概率进行访问，则该文件的长度以 及访问该文件的平均访问索引表项数分别为(    )。

A. 20KB + 512KB + 512MB ，256.5 个索引表项

B.  20KB + 513MB ，256.5 个索引表项

C.  20KB + 512KB + 512MB ，256 个索引表项

D. 20KB + 513MB ，256 个索引表项

某文件系统采用树形目录结构， 目录项包含文件名、文件大小和指向文件数据块的指针。若系 统使用哈希表加速由文件名到目录项的查找， 即在每个目录中维护独立的哈希表，用于加速该 目录下所有目录项的查找。并采用 LRU 算法管理内存中的文件缓存，下列描述错误的是(    )。

A.  哈希表冲突处理方式会影响目录项查找的平均时间复杂度， 最坏情况下对于规模为 n 的单层 目录下的目录项查找时间复杂度为 O (n)

B.  若文件数据块采用链式存储，则存取效率低于顺序存储

C.  LRU 算法通过维护一个双向链表和哈希表实现

D. 在树形目录结构中，若某个目录的子目录过多，一定导致目录项的查找时间复杂度从 O (1) 退化到 O (n)

UNIX 文件系统中，某文件的绝对路径为/home/user/docs/report.txt。若当前目录为/home/user/pro- ject ，report.txt 的软链接文件 link.txt 位于该目录下。下列描述错误的是(    )。

A. 通过路径./link.txt 可正确读取目标文件内容

B.  删除原文件 report.txt 会导致 link.txt 访问失败

C.  若挂载远程 NFS 文件系统到 /home/user/docs，原 report.txt 文件仍可继续访问

D. link.txt 的 inode 中记录的是目标文件的绝对路径

某磁盘系统共有 4096 个磁盘块，块大小 1KB，使用位示图管理空闲块。若采用 CSCAN 算法调  度磁头请求， 当前磁头位于 100 号柱面（共 200 个柱面），请求序列为 50 、150 、10 、180 、30， 磁头初始移动方向为增大。同时，系统使用成组链接法管理空闲块组，每组记录 100 个块。下列描述正确的是(    )。

A. 位示图大小为 512 字节，CSCAN 磁头移动距离为 290

B.  位示图大小为 512 字节，CSCAN 移动距离为 390

C.  成组链接法需额外存储每组的链表指针，但减少了目录查询时间

D. 成组链接法结合了空闲块组的批量分配与链式检索，优于单一链表

下列关于集线器的描述中，正确的是(    )。

A. 集线器可连接不同速率的以太网段进行正常工作

B.  集线器连接的多个网段必须工作在半双工模式

C.  集线器通过隔离冲突域减少广播风暴

D. 集线器能够识别 MAC 地址并过滤无效帧

某无噪声信道的带宽为1MHz，采用8种相位的PSK调制。若实际数据传输速率为该信道理论最大数据传输速率的50%，传输一个24KB的数据块，单向传播时延为20ms。忽略处理时延和确认时间，则总时延是（注：K=10³，M=10⁶）（）。

A. 28 ms     B. 84 ms     C. 86 ms     D. 148 ms

下列关于海明码的叙述中，正确的是(    )。

A. 海明码的校验位必须位于二进制位的奇数位置

B.  对于 4 位数据位，至少需要 3 位校验位才能实现纠错

C.  海明码的编码过程中，每个校验位仅负责校验一个数据位

D. 接收端检测到码距为 3 的海明码错误时，最多能纠正 2 位同时发生的错误

下列关于 IEEE 802.11 无线局域网的协议机制的描述中，正确的是(    )。

A. 无线 MAC 帧的帧首部必须包含 SSID 以标识接入的无线网络，而 BSSID 仅用于管理帧

B.  站点与 AP 建立关联可通过主动扫描（发送探测请求帧）或被动扫描（监听信标帧）实现

C.  802.11 标准规定点协调功能 PCF 必须实现，分布协调功能 DCF 可以选择实现

D.  802.11 的 MAC 层中的 DCF 层通过 RTS/CTS 可以完全避免隐蔽站问题

下列与 OpenFlow 1.0交换机中流表的匹配字段设计相关的网络层次是(    )。

I. 应用层     II. 运输层     III. 网络层    IV. 链路层

A. I 、II 、III      B.  II 、III 、IV    C.  II 、III     D.  III 、IV

假设主机 H 与服务器已建立一个 TCP 连接，最大段长 MSS 为 1000B ，往返时间 RTT 为 10ms， 最长报文段寿命 MSL = 30s ，拥塞控制的初始阈值是 8MSS ，忽略 TCP 的传输时延。主机 H 以  MSS 段向主机乙发送一个大小为 24000B 的文件 F ，发送完成后 H 主动请求断开连接。该过程  中服务器发送的确认报文段首部的窗口字段值为 6000B。若从 H 开始发送文件 F 的时刻起，到  服务器进入 CLOSED 状态为止，所需的时间至少是(    )。

A. 65ms       B.  75ms      C.  60.06s     D. 60.07s

下列关于 TCP 可靠传输机制的描述中，正确的是(    )。

A. 接收方必须采用累计确认和捎带确认

B.  对不按序到达的数据段， TCP 规定必须立即丢弃

C.  快重传机制通过冗余 ACK 触发，接收方收到失序报文段时需立即发送确认

D. 捎带确认必须与数据段同时发送，否则无法实现累计确认

下列关于校验和机制的描述中，正确的是(    )。

A. IP 首部校验和覆盖整个数据报，而 TCP/UDP 校验和仅覆盖首部

B.  TCP 校验和的计算与 IP 首部无关，而 UDP 校验和必须包含 IP 首部

C.  UDP 校验和的计算需要依赖 IP 首部中的源 IP 地址、目的 IP 地址和协议字段

D. IP 校验和采用伪首部机制

（14分）结点值都为正数的二叉搜索树称为正值二叉搜索树。请设计一个算法$countNodes$，统计给定的正值二叉搜索树中，满足以下条件的结点数：①结点同时存在左子树和右子树；②左子树中结点与右子树中结点分别与当前结点的最小距离相等。（结点间的差的绝对值为距离）

例如，在右图所示二叉搜索树中，结点4存在左子树和右子树，左子树中结点与本结点的最小距离为$|3 - 4| = 1$，右子树中结点与本结点的最小距离为$|6 - 4| = 2$，$1 ≠ 2$，故结点4不满足要求。结点2存在左子树和右子树，左子树中结点与本结点的最小距离为$|1 - 2| = 1$，右子树中结点与本结点的最小距离为$|3 - 2| = 1$，$1 = 1$，故结点2满足要求。叶结点1、3、6都不满足要求。综上，在右图所示二叉搜索树中，满足条件的结点只有1个，故返回1。

二叉树结点定义如下：

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

函数原型为：`int countNodes(TreeNode* root)`。要求：

（1）给出算法的基本设计思想。（3分）

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（9分）

（3）说明你所设计算法的时间复杂度。（2分）

（9 分）某带权有向图采用十字链表存储，类型定义如下：

typedef struct {
    VertexNode vertices[7]; // 顶点数组（编号0~6）
    int vex_num; // 顶点数
} DirectedGraph;

顶点集合为{A,B,C,D,E,F,G}，顶点编号依次为0~6。弧结点（EdgeNode）结构为：包含$
\begin{array}{|c|c|c|c|c|}  % 列格式中添加 | 表示垂直线
\hline  % 顶部水平线
\text{tailves} & \text{headves} & \text{weight} & \text{hlink} & \text{tlink} \\
\hline  % 底部水平线
\end{array}
$。该带权有向图的十字链表存储如下图所示。

请回答下列问题：

(1) 请根据题目给出的条件，并画出该带权有向图。（3分）

(2) 该图中强连通分量的数量是多少？若要求将该有向图中的强连通分量数量变为1，至少需要添加多少条边，请给出一种添加方式。若要求将该有向图中的顶点数量大于1的强连通分量数量变为0，至少需要删除多少条边，请给出一种删除方式。（3分）

(3) 简述利用拓扑排序判断带权有向图是否存在关键路径的思路（无需说明拓扑排序的过程），并说明求关键路径过程中使用十字链表法存储有向图，相比于使用邻接表法最直接的优势所在。（3分）

（16分）已知计算机M字长为32位，带符号整数用补码表示。某C语言完整程序段和该程序段在计算机M上的部分机器级代码如下，每个机器代码行中依次包含指令序号、虚拟地址、机器指令和汇编指令。

   int sum = 0;
1  00401000 C7 45 FC 00 00 00 00 movl $0, -4(%ebp)
   for (int i = 0; i < 2048; i++) {
       ......
3  00401008 EB 21                jmp 00401031h
       sum += A[i];
       ......
5  00401013 C1 E0 02             shll $2, %eax
6  00401016 05 A0 04 00 08       addl $0804A010h, %eax
7  0040101B 8B 08                movl (%eax), %ecx
8  0040101D 01 4D FC             addl %ecx, -4(%ebp)
       if (sum > 100)
       ......
10 00401024 7E 07                jle 0040102Dh
       sum = 0;
   ......
14 00401038 7D DC                jl 00401010h
   }

请回答下列问题：

（1）上述代码中，哪些指令可能会使程序发生跳转？采用了什么寻址方式？请给出第3条指令jmp的跳转目标地址计算过程。（4分）

（2）已知je指令表示“有符号数小于等于时转移”，会根据状态寄存器中的标志位进行判断。若执行到第10条指令jle时，sum=150，则符号标志SF、溢出标志OF和零标志ZF分别是什么？判断跳转的逻辑表达式是什么？（3分）

（3）程序执行过程中，每次在指令5执行前，都会将变量i存储在eax寄存器中。已知shll指令为逻辑左移指令，整型元素int占4字节，A为整型数组。分析第5条指令shll、第6条指令addl和第7条指令movl所实现的功能，cx寄存器存储的内容是什么？第7条指令中操作数“(%eax)”采用了什么寻址方式？计算机M是按字节编址还是按字编址？若数组元素A[10]存在，输出该元素的起始地址。（7分）

（4）计算机M是RISC还是CISC？为什么？（2分）

（7 分）题 43 中的计算机 M 采用微程序控制器。请回答下列问题：

(1)   若微指令中的操作控制字段采用字段直接编码法， 互斥类的划分依据是什么？ 控制 MARin， MDRout ，Rout ，ALUop 取值的微命令中、最少可划分出多少个互斥类？（2 分）

(2)   若计算机 M 的微指令字长为 32 位，采用计数器法确定下条微指令地址，控制存储器按字  编址。已知第 5 条指令“shll  2h,%eax”的微程序入口地址为 0A2H ，该指令由 5 条不 同的微指令构成， 且微指令执行过程中未发生跳转， 则当执行到该指令的第三条微指令时， 微程序计数器的内容是什么？（用十六进制表示）（ 1 分）

(3)   列出题 43  中所示的机器级指令、在执行过程中可能触发的、两种异常类型和对应的指令 号。（ 2分）

(4)   当 CPU 执行第 8 条指令“add   %ecx,-4(%ebp)”时收到外部中断请求，简述 CPU 能够 进行中断响应的条件。（ 2 分）

（7 分）题 43 中的计算机 M 采用页式虚拟存储管理，虚拟地址为 32 位，物理地址为 24 位，页 大小 4 KB 。TLB 采用 4 路组相联方式，共 16 组。请回答下列问题：

(1)   给出第 14 条指令 jl 所在的虚拟页号（十六进制）。已知访问 TLB 时虚页号高位部分用作 TLB 标记，低位部分用作 TLB 组号，请给出 jl 所在虚拟页面页号的划分方式，哪几位是 TLB 标记？哪几位是 TLB 组号？（2 分）

(2)   若题 43 中数组 A 大小为 2048 ，则该 C 语言程序段执行过程中、在访问上述给出的指令代 码和数组 A 时，至少需要访问多少个虚拟页面？请给出计算过程。（ 3 分）

(3)   若系统为执行题 43 中给出指令，初始时给该进程分配两个空的物理页面。当进程发生缺页  时，只允许该进程从已分配的页面中、随机选择一页换出，优先选择空页。若连续两次访  存发生缺页中断， 则系统会在第二次缺页处理完成后、为该进程再分配一个新的物理空页。 此处采用了哪种内存分配策略和置换策略的组合？该进程执行完成后，系统为该进程分配  的物理页面数量最多是多少？（不考虑 Cache ）（2 分）

（ 8 分）某文件系统使用显式链接分配方式组织文件， 磁盘容量为 10GB ，以簇为单位进行分配， 簇的大小为 4KB，簇和簇内字节均从 0 开始编号。已知 FAT 中每个表项仅存放簇号， 占 4 个字  节。该文件系统的部分初始状态如下：文件 A 的簇号链为：30000 → 32000 → 42500 ；文件 B   的簇号链为： 5000 → 4000 → 4500 。请回答下列问题：

(1)   若采用位图法管理该分区的空闲空间，位图在磁盘中连续存储，所在起始簇号为 30 ，则文 件 A 所在簇在位图中的状态位所在的簇号是多少？（3 分）

(2)   FAT 的最大长度为多少字节？ 文件 B 的第 5000 个字节和第 9000 个字节、其簇号所在的 FAT 表项的索引号分别是多少？（3 分）

(3)   若该文件系统中， 针对每个文件， 用户类别分为： 管理员、文件主、其他用户； 访问权限分 为：完全控制、执行、修改、只读。使用二进制位串表示不同类别用户对文件的权限， 则该 二进制位串应保存在文件的什么组织中？表示文件 B 的访问权限至少需要多少位？（2 分）

（9 分）假设 Internet 的两个自治系统构成的网络如下图所示， 自治系统 AS1 由 NAT 路由器 R1 连接两个子网构成； 自治系统 AS2 由路由器 R2 、R3 和 R4 互联并连接两个子网构成。各子网 地址、路由器的部分接口 IP 地址和主机、 FTP 服务器的地址信息如下图所示。

请回答下列问题：

(1)   若 AS2 内部各路由器使用 RIP 协议进行路由选择且已收敛。主机 A 给网络 192.1.3.64/26 中 的主机 B 发送一个 IP 数据报，其首部中 TTL 字段的初始值被设置为 2 ，则主机 A 收到的 回复是什么？（ 1 分）

(2)   当主机 A 向 FTP 服务器主动发起 TCP 控制连接时（主机 A 在短时间内曾与 FTP 服务器完 成过通信）， R1 收到来自主机 A 的 SYN 报文的目的 IP 地址是什么？ 目的端口号是什么？ FTP 服务器收到来自主机 A 的 SYN 报文的目的 IP 地址是什么？（3 分）

(3)   AS1 和 AS2 间使用什么路由协议？该协议端口号为多少？基于传输层的什么协议？（3 分）

(4)   进行文件传输时，FTP 的客户和服务器之间要并行建立控制连接和数据连接，这样设计主 要的好处是？若客户利用多线程技术同时向 FTP 上传 3 个文件，则最少建立多少次连接即 可完成上传？（2 分）