2018 845真题回忆

( 感谢成长中的懒羊羊，咸鱼，18-as...... 欢迎大家补充或修改

TO未来几年的学弟学妹们： 845的选择题越来越少，从以前的40个到17年的30个再到18年的20个，大题目逐渐变为110分。规定时间内做完难度较大，所以平时复习时一定要熟练掌握重点知识。

) 20道选择（40分） loading... 数据结构

单链表实现优先级队列，插入的复杂度最坏多少。o(1)还是o(n)

堆的调整

算法分析 2的2次方的n次方和2的n次方，渐进复杂度度关系比较 o(),theta（）,欧姆（） 谁属于谁 p,np,npc,np-hard之间的关系,说法正确的是 b.一个问题能同时是p和np c一个问题被证明是np,那么它必不是np-hard d.是np则不是np-hard

操作系统

ICS cache容量大小计算（8路组相联，回写，随机替换） 计算机网络 html在7层模型哪一层 表示层 应用层....

20.能存储转发且不改变数据帧的设备是哪个 路由器， hub ，网桥，ATM交换机

9道大题

4道数据结构（18年考察了手动写过程，写算法思想写具体代码，分析算法复杂度，分析最坏情况比较次数） 21. 给含7个数的序列手动建立AVL树； 实现AVL上查找指定节点x并给出复杂度 22. 链地址法建立哈希表 画图；求平均查找成功次数；求平均失败查找次数 23.在一个无重复元素的先递增后递减的序列上找元素x 设计一个算法尽可能使比较次数少； 分析最坏情况的比较次数 24.电网铺设，要使任意两城市都能用上 写出图的邻家矩阵； 手写一种最小方案，并求出最小代价； 写出算法思想； 设计找出所有关键边(具体描述忘了，大概是删掉这条边最小生成树的cost变大)的算法（7分）

3道操作系统 25.（7分）简述虚拟存储管理的原理，举一个例子:用足够小的内存却能使多个并发进程能用很大的存储空间 26.（7分）银行家算法 5个进程4个资源,max,available都给出。有3个请求资源,require分别给出（都未达到max），给出一个合理地顺序满足这3个进程的请求，使得不可能出现死锁 27.pv操作 独木桥问题，一方过完另一方才能过，且桥上认识最多为12人

一道ICS 28.（25分）大综合（8-9问） 题干给了c代码和汇编代码 main.c test.c:sum函数 问题: 简要说明可执行文件生成过程； 一些寄存器里放了啥变量，具体内存地址放了啥，某几句汇编代码对应c代码中的啥语句; 为啥要include stdio.h printf函数从用户态到内核态的过程

一道网络
29.（14分）（8-9问） 图中有2台路由器，2台主机，u采用TCP协议 a-x-y-b(图写成字母就这样) 告诉每一段的传播速度,求RTT 告诉每一段的链路速度，中间有分用的 tcp滑动窗口原理和作用 各种条件求最大吞吐率 简述慢恢复型拥塞控制算法的原理；指出其缺点并提出改进