笔试题整理

第一题：前缀tree

假设某段通信电文仅由 6 个字母 ABCDEF 组成，

字母在电文中出现的频率分别为2，3，7，15，4，6。

根据这些频率作为权值构造哈夫曼编码，

最终构造出的哈夫曼树带权路径长度与字母 B 的哈夫曼编码分别为______。(这里假定左节点的值小于右节点的值)

答案

长度：37+22+9+5+3=86

编码：1011

分析：

step1. 创建一个优先级队列（小）

【2 3】 4 6 7 15 step2. 重复 pop 2个最小的，然后累计和添加进去
[4 5 6 7 15
[6 7] 9 15
9 13 15
15 22

step3 左节点的值小于右节点的值

进程的关系

并发进程执行的相对速度是______。 -与进程调度策略有关

分析：抢占协作

抢占式多任务处理（Preemption）是计算机操作系统中，一种实现多任务处理（multi task）的方式，

相对于协作式多任务处理而言。

协作式环境下，下一个进程被调度的前提是当前进程主动放弃时间片；

抢占式环境下，操作系统完全决定进程调度方案，操作系统可以剥夺耗时长的进程的时间片，提供给其它进程。

只要有一个优先级更高的任务就绪，它就可以中断当前优先级较低的任务的执行

new

答案 a

大小段

举例来说，数值0x2211使用两个字节储存：高位字节是0x22，低位字节是0x11。

大端字节序：高位字节在前，低位字节在后，这是人类读写数值的方法。

小端字节序：低位字节在前，高位字节在后，即以0x1122形式储存。

https://www.ruanyifeng.com/blog/2016/11/byte-order.html

算法

写一个函数,输入一个二叉树,树中每个节点存放了一个整数值,函数返回这棵二叉树中相差最大的两个节点间的差值绝对值。

虚拟内存

有一个虚拟存储系统，若进程在内存中占3页（开始时内存为空），若采用先进先出（FIFO）页面淘汰算法，

当执行如下访问页号序列后1，2，3，4，5, 1，2，5，1，2，3，4，5，会发生多少缺页？

分析

D，10。 FIFO，发生缺页时的调入顺序即为淘汰顺序

1、访问1，缺页，调入1，内存中为    1， ，；

2、访问2，缺页，调入2，内存中为   1，2，；

3、 访问3，缺页，调入3，内存中为 1，2，3；

4、 访问4，缺页，调入4，淘汰1，内存中为 4，2，3；

5、 访问5，缺页，调入5，淘汰2，内存中为 4，5，3；

6、 访问1，缺页，调入1，淘汰3，内存中为 4，5，1；

7、 访问2，缺页，调入2，淘汰4，内存中为 2，5，1；

8、 访问5，不缺页，内存中为 2，5，1；

9、 访问1，不缺页，内存中为 2，5，1；

10、 访问2，不缺页，内存中为 2，5，1；

11、访问3，缺页，调入3，淘汰5，内存中为 2，3，1；

12、访问4，缺页，调入4，淘汰1，内存中为 2，3，4；

13、访问5，缺页，调入5，淘汰2，内存中为 5，3，4；