数据结构部分
一、前提：二叉树，目标：输出只有一个子树的节点的个数，写出算法，并分析时间复杂度（15分）这题遍历一遍就行
二、有些二叉搜索树在最坏情况下查找的时间复杂度也有o(logn)，请举出两种例子，并且分析复杂度为 o(logn)的情况（10分）大概是平衡二叉树和完全二叉树吧23333
三、算法填空（15分） 有两小题，第一题是弗洛伊德算法的填空，看懂了代码就很容易填出来；第二题稍微难一点，是变种的归并排序，就是在某一临界值以后开始用插入排序，而且他归并排序的low，mid，high这三个写的花里胡哨的，实际上看懂了就没什么区别，也就是说一次考了两个排序，这题看代码的对称性也不难，他挖的空都是对称的，另外19年的算法填空填的是迪杰斯特拉的伪代码，现在填的是弗洛伊德，是不是下次就是普利姆算法或者克鲁斯卡尔算法了2333
四、找出数组中最大的k个数，要求复杂度为 o(n)，写出算法并分析复杂度（20分）这是2019年的原题，考前我特意百度了一下，没想到他直接拿来做真题。主要是用堆排序的思想或者快速排序的思想 ，快速排序每次划分不是枢轴值左边的小右边的大吗，所以如果枢轴值正好右边有k个值，那么右边的就都是最大的k个数，不过还是堆排序简单一点
软件工程部分
五、概念题（每题6分）
- CMMI的连续型和阶段型的区别（说实话我不知道，我编的）
- 回归测试的概念（PPT上有我背了）
- 调试与测试的关系（直接对应考纲，我背了）
- 开闭原则（直接对应考纲，我背了）
- 耦合的基本类型至少说三个（总共7个我都背了）
六、画图题（这里分数白给）
（1）类图（15分） 计算机可以分为笔记本电脑和台式机，现在有主板、硬盘、内存、显示器、键盘、鼠标、无线鼠标、有线鼠标、机械鼠标、光电鼠标、蓝牙鼠标，请画出类之间的关系，不需要写属性，需要假设的地方在图中注明，如假设计算机只有一个显示器
（2）状态图（15分） 空调开机进入自检状态，检测不通过进入错误状态并且亮红灯，检测通过默认进入制冷状态，按遥控器模式切换可以在制冷、制热、吹风切换，制冷可以设置温度，并有温度监控程序，室温低于设定温度则停止制冷，高于则开始制冷；制热则反过来；吹风就只能吹风，没有其他功能
CSAPP部分
七、指令集体系
（1）简述指令集体系结构在计算机系统中的位置和作用（10分）
（2）简述risc和cisc的特点（10分）
（3）简述risc指令集的设计和amdahl定理的联系（10分）