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 中的下标是（ ）。

若森林 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 查询的最少和最多次数分别是（ ）。