2018年南京大学842数据结构、软件工程、操作系统和计算机网络考研真题（回忆版）
赞个人品，趁热回忆下真题。今年的题感觉和17年的难度差不多，数据结构依旧没有算法题（准备了那么多呀），除了软工题型也都是之前见过的题型，唯独操作系统的那个UNIX进程的那个，是期末试卷的一道选择题，当时看时就没懂，也就没印象了。软工的题型一直很活，很少有原题，两道大题蒙着答的。总的来讲都是比较基础的，有很多原题，期末试卷中那些难的题都没有考。名词解释感觉重在理解名词的含义，没必要死背，考前各科整理了n多个名词解释，一直因为这个性价比最低的背不下来感到没谱，结果考试要么是比较简单的（如计网的），要么是压根就没整理到的（OS的就没整理到）。PV算法的话感觉把课件上那几个都掌握了，也就没问题了（注：我是跨考的，有些语言描述可能不规范，望谅解）
数据结构（45分）
一、填空（3×5）
1．一个t叉树，有n个叶子节点，s个非叶子节点，写出n和s的关系
2．快速排序最坏情况下时间复杂度
3．给出二叉树前序序列和中序序列，写出后序序列
4．赫夫曼树，n个叶子节点，求总的节点个数
5．一个平衡二叉树，加入一个关键字后，重新调整为平衡二叉树
二、大题（10×3）
1．对关键码序列{23，17，12，61，26，8，70，75，53}，用堆排序方法进行排序，画出排序过程中所建的初始堆，以及输出前三个关键码过程的示意图。（要求建立的堆为任一父母结点的关键码都小于其子女结点的关键码）
2．请画出往下图的5阶B-树中插入一个关键码390后得到的B-树，以及再删除关键码100后得到的B-树。
3．按Dijkstra方法计算从顶点1到其它顶点的最短路径。按路径递增顺序写出先后计算出的最短路径（包括起止点和途径各点）及该路径长度。
软件工程（45分）
一、问答题（5×5）
1．说明下工程和科学的区别（政治题走错片场了吧？）
2．什么是集成测试，什么是单元测试，单元测试用例和集成测试用例有什么区别
3．功能性需求和非功能性需求
4．写出四个体系结构视角
5．质量模型的可用性
二、大题（10×2）
1．一个购房评估系统，一个类中含有两个功能，一个是输入存款、月工资、月花销、想要购房面积……完后得出可以购房的面积和首付款，另一个功能是根据面积和首都得出一个各小区的的房价列表，供用户参考，问这种设计合理吗？不合理的话画出设计类图并写出类的定义（含属性和方法）
2．一个计算税费的问题，根据什么一堆经济的指标什么印花税、公证费、契税、委托办理手续费、房屋买卖手续费啥的，计算出税费，各地的计算方法不同，要求能够灵活扩展，按照一种设计模式设计，画出设计类图并写出关键接口定义。
操作系统（35分）
一、名词解释（2X3）
1．特权指令
2．内部碎片
3．程序的局部性原理
二、大题
1．（4分）UNIX系统有一个主函数
问最多可再产生多少个进程？并画出家族树
2．（3分）在一个操作系统的inode节点中分别含有10个直接地址的索引和一、二、三级间接索引。若设每个盘块有512B大小，每个盘块中可存放128个盘块地址，则一个20MB的文件占用多少个间接盘块？
3．（3分）请画出经典的三状态进程模型及其状态转换图，并解释各个转化过程
4．（4分）一个进程在磁盘上包含8个虚拟页（0号~7号），在主存中固定分配给3个页框（frame），给出访问顺序，写出LRU和FIFO算法分别在这三个帧上的页，并计算主存的缺页次数。
5．（4分）设系统中有4种类型的资源（A、B、C、D）和5个进程（P0、P1、P2、P3、P4），A资源的总量为3，B资源的总量为12，C资源的总量为14，D资源的总量为14。在T0时刻系统中个资源使用情况的状态如下表所示，系统采用银行家算法实施死锁避
免策略。
试问：T0时刻的各资源剩余数量为多少？T0时刻的是否为安全状态？若是，请给出其中可能的一种安全序列，并依照该序列，写出各资源的回收步骤。
6．（8分）PV算法，理发师问题。理发店理有一位理发师、一把理发椅和n把供等候，理发的顾客坐的椅子，如果没有顾客，理发师便在理发椅上睡觉，一个顾客到来时，它必须叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开，使用PV操作求解该问题
计算机网络（25分）
一、名词解释（3×5）
2018考研政治真题1．TCP/IP
2．RIP
3．NAT
4．DNS
5．FTP
二、问答题（5×2）
1．简述三次握手过程并说明为什么要进行第三次握手？
2．比较LSP（链路状态协议）和DVP（距离矢量协议）的区别（感谢三楼提醒，查了下确实是，因为复习的少，一直认为RIP就是距离矢量协议，OSPF是链路状态协议，原来是分总的关系）