笔试时间：2022年9月1日

1 单选

1）缓存作用于哪两层之间

CPU RAM ROM 内存 硬盘

2）5 8 3 4 7 6一趟快排后的结果

3）A[0][0]在644位处，A[2][2]在676位处，一个元素占一位，问A[3][3]在第几位

4）内部异常（内中断）分为故障fault、陷阱trap和终止abort。下列叙述错误的是：

A 内部异常的检测由CPU内部逻辑实现
B 内部异常处理后返回到发生异常的指令继续执行
C 内部异常的相应发生在指令执行过程中
D 内部异常的产生与当前执行指令有关

5）有关数据冗余，下列说法错误的是：

A 分类存储可以有效减少数据冗余，但会增加数据查找复杂性
B 数据冗余通常是由数据库设计引起的
C 设计阶段一定要最大可能避免数据冗余，最好没有数据冗余
D 数据库中，数据存在副本的现象就是数据冗余

6）会受到散列的堆积（聚集）现象影响的是：

A 散列函数
B 平均查找长度
C 装填因子
D 存储效率

7）散列表有0-8空间，散列函数为 K mod 9，用线性探测法存储（12，21，43，5，39），最后39会存储在哪个下标？

8）与10.110.12.29，掩码为255.255.255.254属于一个网段的是：

A 10.110.12.30
B 10.110.12.31
C 10.110.12.32
D 10.110.12.0

9）地主手牌：大王、A、8、7、4、4、3

农民手牌：2、A、10、10、7、6

地主当前应该出什么牌才能确保赢？

其它不记得了……

2 填空

1）嵌套循环计算循环次数（回忆起来才发现这题我竟然做错了！）

2）后缀表达式求值

3）aaaabbcd的哈夫曼编码长度

4）U\V\W\X\Y分别是小于10的自然数，满足UVWXY * 4 = YXWVU。问UVWXY是多少

5）连续自然数之和为1000的有几组？

6）16位操作系统的寻址空间为多少KB？

3 编程（核心模式）

1）移动-1到数组末尾

将所有的-1移动到数组末尾，并且保持序列稳定性。要求在原数组上操作。

输入用例：

-1 2 0 -1 5

输出用例：

2 0 5 -1 -1

2）完全二叉树的最近公共祖先

找到一个完全二叉树（用数组表示，不是树的结构）两个值的公共祖先。如果没有该值的结点，返回-1

输入用例1：

[5, 2, 4, 1, 6, 9, 0, 3] 3, 6

输出用例1：

2

输入用例2：

[8, 2, 5, 6, 4, 7, 1, 3] 2, 3

输出用例2：

2