sspku_exam

北大软微 考题回忆

2019 秋

陈向群 操作系统

一

1. 中断与异常差别，举例说明
2. 以时钟中断为例，说明中断处理过程（包括硬件和OS的处理）
3. 系统调用的设计和实现

二

1. 进程PCB的作用，创建PCB的过程，Linux加快此过程的技术
2. 进程的调度切换与PCB的关联
3. 基于多级反馈调度队列设计一个调度算法。说明你的算法怎么让IO进程优先？怎么防止饥饿？

三

1. 48位虚拟地址空间，一页4KB，设计页表结构，并画出地址转换的流程。
2. 关于页缓冲技术的一道题，里面的图没法回忆了

四

8GB U盘，一簇512B，FAT16格式，文件系统分成了5部分

| ① | ② | ③ | ④ | ⑤ |

1. ①-⑤分别是什么
2. 用什么管理空闲区？如何知道根目录的位置？
3. FAT1占多少簇
4. 给了你一堆创建文件/目录的操作，画文件系统分布，这个课上讲过
5. 现在要读4里面某个文件的第2600字节，说明过程

五

1. 锁，信号量，管程的联系与区别
2. 用管程解决问题。超市100辆推车，进来要先刷卡扣押金来领取推车，如果没车了只能等，离开要刷卡退押金，归还推车。

郁莲 算法分析与设计

作业题都要搞懂，别抱侥幸心理。我觉得不会考运输问题这种纯手工画图没水平的题目，结果还真考了，和出题老师配合的不是很好，妥妥的跪了。

1. 线性规划easy
2. 贪心easy
3. 回溯，与习题5.11哨兵布置问题类似
4. 分支限界法解线性规划
5. 运输问题
6. m个长L的有序列表，要求将它们合并成一个有序。写出顺序归并，二分归并伪码，最差时间复杂度，求该问题最差时间复杂度下界。可参考习题8.4

莫同 云计算

5个选择，6个判断，每个5分，较容易，不是那种抠细节的题，上课听讲即可

3道大题，每题15分

1. 画出GFS架构，写出各模块和运行机制
2. mapreduce 矩阵相乘，lab2里有
3. 叙述Kafka消息发布和消费机制