南京大学软件工程2018真题.docx

2018年南京大学软件工程 842真题（回忆版）
数据结构
填空（3X5）
1、 一个t叉树，有n个叶子节点,s个非叶子节点，写出n和s的关系
2、 快速排序最坏情况下时间复杂度
3、 给出二叉树前序序列和中序序列，写出后序序列
2018年南京大学软件工程 842真题（回忆版）
数据结构
填空（3X5）
1、 一个t叉树，有n个叶子节点,s个非叶子节点，写出n和s的关系
2、 快速排序最坏情况下时间复杂度
3、 给出二叉树前序序列和中序序列，写出后序序列
4、 赫夫曼树,n个叶子节点，求总的节点个数
5、 一个平衡二叉树，加入一个关键字后，重新调整为平衡二叉树
大题（10X3）
1、 对关键码序列{ 23， 17， 12， 61， 26， 8， 70， 75， 53 }, 用堆排序 方法进行排序，画出排序过程中所建的初始堆，以及输出前三个关键码 过程的示意图。（要求建立的堆为任一父母结点的关键码都小于其子女 结点的关键码）
答：
2、 请画出往下图的5阶B-树中插入一个关键码390后得到的B-树，以 及再删除关键码100后得到的B-树。
3、 按Dijkstra方法计算从顶点1到其它顶点的最短路径。按路径递增 顺序写出先后计算出的最短路径（包括起止点和途径各点）及该路径长 度。
软件工程
问答题（ 5X5）
1、说明下工程和科学的区别（政治题走错片场了吧？）
2、什么是集成测试，什么是单元测试，单元测试用例和集成测试用例
有什么区别
3、功能性需求和非功能性需求
4、写出四个体系结构视角
5、质量模型的可用性
大题（10X2）
1、 一个购房评估系统，一个类中含有两个功能，一个是输入存款、月
工资、月花销、想要购房面积……完后得出可以购房的面积和首付款，
另一个功能是根据面积和首 都得出一个各小区的的房价列表，供用户 参考，问这种设计合理吗？不合理的话画出设计类图并写出类的定义
（含属性和方法）
2、 一个计算税费的问题，根据什么一堆经济的指标什么印花税、公证 费、契税、委托办理手续费、房屋买卖手续费啥的，计算出税费，各地 的计算方法不同，要求能够灵活扩展，按照一种设计模式设计，画出设 计类图并写出关键接口定义。
操作系统
名词解释（2X3）
1 、特权指令
2、内部碎片
3、 程序的局部性原理
大题
1 、（ 4 分） UNIX 系统有一个主函数
main{
fork （）； /*<-pc（程序计数器）,进程A
fork（）；
fork（）；
} 问最多最多可再产生多少个进程？并画出家族树（都不懂说的是啥）
2、 （ 3 分）在一个操作系统的 inode 节点中分别含有 10 个直接地址的 索引和一、二、三级间接索引。若设每个盘块有512B大小，每个盘块 中可存放128个盘块地址，贝U—个20MB的文件占用多少个间接盘块？
3、 （3 分）请画出经典的三状态进程模型及其状态转换图，并解释各 个转化过程
4、 （4 分）一个进程在磁盘上包含8 个虚拟页（0 号~7 号），在主存中固
定分配给3个页框（frame）,给出访问顺序，写出LRU和FIFO算法 分 别在这三个帧上的页，并计算主存的缺页次数。
5、 （4分）设系统中有4种类型的资源（A、B、C、D）