2016 年真题

已知表头元素为 c 的单链表在内存中的存储状态如下表所示。现将 f 存放于 1014H 处并插入单链表，若 f 在逻辑上位于 a 和 e 之间，则 a,e,f 的 “链接地址” 依次是（ ）。

已知一个带有表头结点的双向循环链表 L，结点结构为 prev|data|next，prev 和 next 分别是指向其直接前驱和直接后继结点的指针。现要删除指针 p 所指的结点，正确的语句序列是（ ）。

设有下图所示的火车车轨，入口到出口之间有 n 条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为 1-9 的 9 列列车，驶入的次序依次是 8, 4, 2, 5, 3, 9, 1, 6, 7。若期望驶出的次序依次为 1~9，则 n 至少是（ ）。

有一个 100 阶的三对角矩阵 $M$ ，其元素 $m_{i,j}(1\le i\le 100,1\le j\le 100)$  按行优先依次压缩存入下标从 0 开始的一维数组 N 中。元素 $m_{30,30}$  在数组 N 中的下标是（ ）。

A. 86 B. 87 C. 88 D. 89

查看答案与解析

正确答案：B

正确答案：B

参考三对角矩阵，采用压缩存储，将 3 条对角线上的元素按行优先方式存放在一 维数组 B 中，且 $a_{1,1}$ 存放于 B[0] 中，其存储形式如下所示：

可以计算矩阵 A 中 3 条对角线上的元素 $a_{i,j}$ ( $1\le i,j\le n,|i-j|\le 1$ ) 在一维数组 B 中存放的下标为 $k=2i+j-3$ 。

解法一：针对该题，仅需将数字逐一代入公式里面即可：k=2x30+30-3 = 87, 结果为 87。

解法二：观察上图的三对角矩阵不难发现，第一行有两个元素，剩下的在元素 $m_{30,30}$ 所在行之前的 28 行（注意下标 $1\le i\le 100$ 、 $1\le j\le 100$ ）中每行都有 3 个元素，而 $m_{30,30}$ 之前仅有一个元素 $m_{30,29}$ , 那么不难发现元素 $m_{30,30}$ 在数组 N 中的下标是：2+28x3+2-1 = 87。

收藏

若森林 F 有 15 条边、25 个结点，则 F 包含树的个数是（ ）。

下列选项中，不是下图深度优先搜索序列的是（）

若将 n 个顶点 e 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（）

使用迪杰斯特拉（Djkstra）算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（ ）。

在有 n(n>1000) 个元素的升序数组 A 中查找关键字 x。查找算法的伪代码如下所示。

k = 0;
while (k < n 且 A[k] < x) k = k + 3;
if (k < n 且 A[k] == x) 查找成功；
else if (k - 1 < n 且 A[k - 1] == x) 查找成功；
else if (k - 2 < n 且 A[k - 2] == x) 查找成功；
else 查找失败；

本算法与折半查找算法相比，有可能具有更少比较次数的情形是（）

B+ 树不同于 B 树的特点之一是（）

对 10TB 的数据文件进行排序，应使用的方法是（）

将高级语言源程序转换为机器目标代码文件的程序是（ ）。

有如下 C 语言程序段

short si = -32767;
unsigned short usi = si;

执行上述两条语句后，usi 的值为（ ）。

某计算机字长为 32 位，按字节编址，采用小端 (Little Endian) 方式存放数据，假定有一个 double 型变量，其机器数表示为 1122 3344 5566 7788H 存放在 0000 8040H 开始的连续存储单元中，则存储单元 0000 8046H 中存放的是（ ）。

有如下 C 语言程序段：

for (k = 0; k < 1000; k++)
    a[k] = a[k] + 32;

若数组 a 以及变量 k 均为 int 型，int 型数据占 4B，数据 Cache 采用直接映射方式，数据区大小是 1KB，块大小是 16B，该程序段执行前 Cache 为空，则该程序段执行过程中，访问数组 a 的 Cache 的缺失率是（ ）。

某存储器容量为 64KB，按字节编址，地址 4000H～5FFFH 为 ROM 区，其余为 RAM 区。若采用 8K×4 位的 SRAM 芯片进行设计，则需要该芯片的数量是（ ）。

某指令格式如下所示。

其中 M 为寻址方式，I 为变址寄存器编号，D 为形式地址。若采用先变址后间址的寻址方式，则操作数的有效地址是（ ）。

某计算机主存空间为 4GB，字长为 32 位，按字节编址，采用 32 位定长指令字格式，若指令按字边界对齐存放，则程序计数器 (PC) 和指令寄存器 (IR) 的位数至少分别是（ ）。

在无转发机制的五段基本流水线中，下列指令序列存在数据冒险的指令对是（ ）。

I1: add R1, R2, R3;         // (R2)+(R3)→R1
I2: add R5, R2, R4;         // (R2)+(R4)→R5
I3: add R4, R5, R3;         // (R5)+(R3)→R4
I4: add R5, R2, R6;         // (R2)+(R6)→R5

单周期处理器中所有指令的指令周期为一个时钟周期。下列关干单周期处理器的叙述中，错误的是（ ）。

下列关于总线设计的叙述中的叙述中，错误的是（ ）。

异常是指令执行过程中在处理器内部发生的特殊事件，中断是来自处理器外部的请求事件。下列关于中断或异常情况的叙述中，错误的是（ ）。

下列关于批处理系统的叙述中，正确的是（  ）

Ⅰ.批处理系统允许多个用户与计算机直接交互

Ⅱ.批处理系统分为单道批处理系统和多道批处理系统

Ⅲ.中断技术使得多道批处理系统和 I/O 设备可与 CPU 并行工作

某单 CPU 系统中有输入和输出设备各 1 台，现有 3 个并发执行的作业，每个作业的输入、计算和输出时间均分别为 2ms，3ms 和 4ms，且都按输入、计算和输出的顺序执行，则执行完 3 个作业需要的时间最少是（）。

系统中有 $3$ 个不同的临界资源 $R_1$ 、 $R_2$ 和 $R_3$ ，被 $4$ 个进程 $p_1$ 、 $p_2$ 、 $p_3$ 及 $p_4$ 共享。各进程对资源的需求为： $p_1$ 申请 $R_1$ 和 $R_2$ ， $p_2$ 申请 $R_2$ 和 $R_3$ ， $p_3$ 申请 $R_1$ 和 $R_3$ ， $p_4$ 申请 $R_2$ 。若系统出现死锁，则处于死锁状态的进程数至少是（ ）。

某系统采用改进型 CLOCK 置换算法，页表项中字段 A 为访问位，M 为修改位。A=0 表示页最近没有被访问，A=1 表示页最近被访问过。M=0 表示页没有被修改过，M=1 表示页被修改过。按 (A, M) 所有可能的取值，将页分为四类：(0, 0)、(1, 0)、(0, 1) 和 (1, 1)，则该算法淘汰页的次序为（ ）。

使用 TSL (Test and Set Lock) 指令实现进程互斥的伪代码如下所示。

do {
    ...
    while (TSL(&lock));
    critical section;
    lock = FALSE;
    ...
} while (TRUE);

下列与该实现机制相关的叙述中，正确的是（ ）。

某进程的段表内容如下所示。

当访问段号为 2、段内地址为 400 的逻辑地址时，进行地址转换的结果是（ ）。

某进程访问页面的序列如下所示。

若工作集的窗口大小为 6，则在 t 时刻的工作集为（ ）。

进程 P1 和 P2 均包含并发执行的线程，部分伪代码描述如下所示。

int x = 0;
Thread1()
{
    int a;
    a = 1; x += 1;
}
Thread2()
{
    int a;
    a = 2; x += 2;
}

int x = 0;
Thread3()
{
    int a;
    a = x; x += 3;
}
Thread4()
{
    int b;
    b = x; x += 4;
}

下列选项中，需要互斥执行的操作是（ ）。

下列关于 SPOOLing 技术的叙述中，错误的是（ ）。

下列关于管程的叙述中，错误的是（ ）。

在 OSI 参考模型中，R1、Switch、Hub 实现的最高功能层分别是（ ）。

若连接 R2 和 R3 链路的频率带宽为 8 kHz，信噪比为 30 dB，该链路实际数据传输速率约为理论最大数据传输速率的 50％，则该链路的实际数据传输速率约是（ ）。

若主机 H2 向主机 H4 发送 1 个数据帧，主机 H4 向主机 H2 立即发送一个确认帧，则除 H4 外，从物理层上能够收到该确认帧的主机还有（ ）。

若 Hub 再生比特流过程中，会产生 1.535μs 延时，信号传播速度为 200m/μs，不考虑以太网帧的前导码，则 H3 与 H4 之间理论上可以相距的最远距离是（ ）。

假设 R1、R2、R3 采用 RIP 协议交换路由信息，且均已收敛。若 R3 检测到网络 201.1.2.0/25 不可达，并向 R2 通告一次新的距离向量，则 R2 更新后，其到达该网络的距离是（ ）。

假设连接 R1、R2 和 R3 之间的点对点链路使用 201.1.3.x/30 地址，当 H3 访问 Web 服务器 S 时，R2 转发出去的封装 HTTP 请求报文的 IP 分组的源 IP 地址和目的 IP 地址分别是（ ）。

假设 H1 与 H2 的默认网关和子网掩码均分别配置为 192.168.3.1 和 255.255.255.128，H3 与 H4 的默认网关和子网掩码均分别配置为 192.168.3.254 和 255.255.255.128，则下列现象中可能发生的是（ ）。

假设所有域名服务器均采用迭代查询方式进行域名解析。当 H4 访问规范域名为 www.abc.xyz.com 的网站时，域名服务器 201.1.1.1 在完成该域名解析过程中，可能发出 DNS 查询的最少和最多次数分别是（ ）。

假设题 33～41 图中的 H3 访问 Web 服务器 S 时，S 为新建的 TCP 连接分配了 20 KB (K=1 024) 的接收缓存，最大段长 MSS=1 KB，平均往返时间 RTT=200 ms。H3 建立连接时的初始序号为 100，且持续以 MSS 大小的段向 S 发送数据，拥塞窗口初始阈值为 32 KB；S 对收到的每个段进行确认，并通告新的接收窗口。假定 TCP 连接建立完成后，S 端的 TCP 接收缓存仅有数据存入而无数据取出。请回答下列问题。

(1) 在 TCP 连接建立过程中，H3 收到的 S 发送过来的第二次握手 TCP 段的 SYN 和 ACK 标志位的值分别是多少？确认序号是多少？

(2) H3 收到的第 8 个确认段所通告的接收窗口是多少？此时 H3 的拥塞窗口变为多少？H3 的发送窗口变为多少？

(3) 当 H3 的发送窗口等于 0 时，下一个待发送的数据段序号是多少？H3 从发送第 1 个数据段到发送窗口等于 0 时刻为止，平均数据传输速率是多少（忽略段的传输延时）？

(4) 若 H3 与 S 之间通信已经结束，在 t 时刻 H3 请求断开该连接，则从 t 时刻起，S 释放该连接的最短时间是多少？

如果一棵非空  $k$ （ $k\ge 2$ ） 叉树 $T$ 中每个非叶结点都有 $k$  个孩子，则称 $T$  为正则 $k$  叉树。请回答下列问题并给出推导过程。

(1) 若  $T$  有  $m$  个非叶结点，则  $T$  中的叶结点有多少个？

(2) 若  $T$  的高度为  $h$  （单结点的树  $h=1$  ），则  $T$  的结点数最多为多少个？最少为多少个？

已知由  $n(n\ge 2)$  个正整数构成的集合  $$\begin{gathered} A= \\ {a}_k|0\le k<n \end{gathered}$$  ，将其划分为两个不相交的子集  $A_1$  和  $A_2$  ，元素个数分别是  $n_1$  和  $n_2$  ，  $A_1$  和  $A_2$  中元素之和分别为  $S_1$  和  $S_2$  。设计一个尽可能高效的划分算法，满足  $|n_1-n_2|$  最小且  $|S_1-S_2|$  最大。要求：

(1) 给出算法的基本设计思想。

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

(3) 说明你所设计算法的时间复杂度和空间复杂度。

int partition(int a[], int low, int high) {
  int l = low;
  int r = high;
  int pivot = a[l];
  while (l < r) {
    while (l < r && a[r] >= pivot) {
      r--;
    }
    a[l] = a[r];
    while (l < r && a[l] <= pivot) {
      l++;
    }
    a[r] = a[l];
  }
  a[l] = pivot;
  return l;
}

// 按照第 k 个元素进行分区
void quickSelect(int a[], int low, int high, int k) {
  if (low < high) {
    int pivotIndex = partition(a, low, high);
    if (pivotIndex == k) {
      return
    } else if (pivotIndex < k) {
      quickSelect(a, pivotIndex+1, high, k);
    } else {
      quickSelect(a, low, pivotIndex-1, k);
    }
  }
}

// 空间复杂度：O(1)
// 时间复杂度：O(n)
void solve(int a[], int n) {
  quickSelect(a, 0, n-1, n/2);
  int S1 = 0;
  int S2 = 0;
  for (int i = 0; i < n/2; i++) {
    S1 += a[i];
  }
  for (int i = n/2; i < n; i++) {
    S2 += a[i];
  }
  return S2 - S1;
}

假定 CPU 主频为 50MHz，CPI 为 4。设备 D 采用异步串行通信方式向主机传送 7 位 ASCII 字符，通信规程中有 1 位奇校验位和 1 位停止位，从 D 接收启动命令到字符送入 I/O 端口需要 0.5ms。请回答下列问题，要求说明理由。

(1) 每传送一个字符，在异步串行通信线上共需传输多少位？在设备 D 持续工作过程中，每秒钟最多可向 I/O 端口送入多少个字符？

(2) 设备 D 采用中断方式进行输入/输出，示意图如下∶

I/O 端口每收到一个字符申请一次中断，中断响应需 10 个时钟周期，中断服务程序共有 20 条指令，其中第 15 条指令启动 D 工作。若 CPU 需从 D 读取 1000 个字符，则完成这一任务所需时间大约是多少个时钟周期？CPU 用于完成这一任务的时间大约是多少个时钟周期？在中断响应阶段 CPU 进行了哪些操作？

某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为 32 位，物理地址为 24 位，页大小为 8KB；TLB 采用全相联映射；Cache 数据区大小为 64KB，按 2 路组相联方式组织，主存块大小为 64B。存储访问过程的示意图如下。

请回答下列问题。

(1) 图中字段 A～G 的位数各是多少？TLB 标记字段 B 中存放的是什么信息？

(2) 将块号为 4099 的主存块装入到 Cache 中时，所映射的 Cache 组号是多少？对应的 H 字段内容是什么？

(3) Cache 缺失处理的时间开销大还是缺页处理的时间开销大？为什么？

(4) 为什么 Cache 可以采用直写 (Write Through) 策略，而修改页面内容时总是采用回写 (Write Back) 策略？

某进程调度程序采用基于优先数 (priority) 的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个 nice 作为静态优先数。为了动态调整优先数，引入运行时间 cpuTime 和等待时间 waitTime，初值均为 0。进程处于执行态时，cpuTime 定时加 1，且 waitTime 置 0；进程处于就绪态时，cpuTime 置 0，waitTime 定时加 1。请回答下列问题。

(1) 若调度程序只将 nice 的值作为进程的优先数，即 priority=nice，则可能会出现饥饿现象，为什么？

(2) 使用 nice、cpuTime 和 waitTime 设计一种动态优先数计算方法，以避免产生饥饿现象，并说明 waitTime 的作用。

某磁盘文件系统使用链接分配方式组织文件，簇大小为 4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表 FAT 中。

(1) 假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中 dir、dir1 是目录，file1、file2 是用户文件。请给出所有目录文件的内容。

(2) 若 FAT 的每个表项仅存放簇号，占 2 个字节，则 FAT 的最大长度为多少字节？该文件系统支持的文件长度最大是多少？

(3) 系统通过目录文件和 FAT 实现对文件的按名存取，说明 file1 的 106、108 两个簇号分别存放在 FAT 的哪个表项中。

(4) 假设仅 FAT 和 dir 目录文件已读入内存，若需将文件 dir/dir1/file1 的第 5000 个字节读入内存，则要访问哪几个簇？