408计算机专业统考真题节选

选择题：

1. 将一个 10 * 10 对称矩阵 M 的上三角部分的元素素(1≤i≤j≤10) 按列优先存入 C 语言的一维数组 N 中，元素7,2在 N 中的下标是：

A、15     B、16     C、22     D、23

2. 对空栈 S 进行 Push 与 Pop 操作，入栈序列 a, b, c, d, e 经过 Push，Push，Pop，Push，Pop，Push，Push，Pop 操作后得到的出栈序列是

A、b, a, c     B、b, a, e     C、b, c, a    D、b, c, e

3. 对于任意一棵高度为 5 且有 10 个节点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是：

A、31    B、16    C、15    D、10

4. 依次将关键字 5，6，9，13，8，2，12，15 插入初始为空的 4 阶 B 树后，根节点中包含的关键字是：

A、8    B、6，9     C、8，13     D、9，12

5. 在按字节编址，采用小端方式的 32 位计算机中，按边界对齐方式为以下 C 语言结构型变量 a 分配存储空间。

Struct record{

short   x1;

int    x2;

} a;

若 a 的首地址为 2020 FE00H，a 的成员变量 x2 的机器数为 1234 0000H，则其中34H 所在存储单元的地址是：

A、2020 FE03H   B、2020 FE04H   C、2020 FE05H   D、2020 FE06H

6. 若主机甲与主机乙建立 TCP 连接时发送的 SYN 段中的序号为 1000，在断开连接时，甲发送给乙的 FIN 段中的序号为5001，则在无任何重传的情况下，甲向乙已经发送的应用层数据的字节数为：

A、4002     B、4001      C、4000     D、3999

大题

1. 定义三元组（a, b, c）（a,b,c 均为正数）的距离 D=|a-b|+|b-c|+|c-a|. 给定 3 个非空整数集合 S1, S2 ,S3, 按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组（a, b, c）（a∈S1,b∈S2,c∈S3）中的最小距离。例如 S1={-1, 0, 9}, S2=｛-25，-10，10，11｝，S3=｛2，9，17，30，41｝则最小距离为2，相应的三元组为（9，10，9）要求：

（1）给出算法的基本设计思想；

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

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

2. 假定主存地址为 32 位，按字节编址，指令 Cache 和数据 Cache 与主存之间均采用8路组相联映射方式，直写（Write Through）写策略和 LRU 替换算法，主存块大小为 64B，数据区容量各为 32KB。开始时 Cache 均为空，请回答下列问题：

（1）Cache 每一行中标记（Tag）、LRU 位各占几位？是否有修改位？

（2）有如下 C 语言程序段：

for ( k = 0 ; k < 1024 ; k++ )

S[k] = 2 * s[k];

若数组 S 及其变量 k 均为 int 型，int 型数据占 4B，变量 k 分配在寄存器中，数组 s 在主存中的起始地址为 0080 00C0H，则该程序段执行过程中，访问数组 S 的数据 Cache 缺失次数为多少？

（3）若 CPU 最先开始的访问操作是读取主存单元 0001 003H 中的指令，简要说明从Cache 中访问该指令的过程，包括 Cache 缺失处理过程。

3. 现有 5 个操作 A、B、C、D 和 E，操作 C 必须在 A 和 B 完成后执行，操作 E 必须在 C 和 D 完成后执行，请使用信号量的 wait(), signal(),操作（P、 V 操作） 描述上述操作之间的同步关系，并说明所用信号量及其初值。 作者：研晟考研 https://www.bilibili.com/read/cv12993153 出处：bilibili