选择题
数据结构部分
- P169 T1 -对，重点----需总结
结论：两个升序的链表要将其合并成----无论是合并升序的链表，还是降序的链表，其最坏情况下的时间复杂度都为O(n+m)<=O(2*max(n,m))~O(max(n,m))
而要把两个升序的链表合并成一个升序的链表的话，只需要尾插法即可
而如果要把两个升序的链表合并成一个降序的链表的话，那么就需要用到头插法
- P169 T6-对，重点----需总结
这题2013与2019年真题应该放在一起讨论
一个是二叉排序树的删除再插入
一个是平衡二叉树的插入再删除
在二叉排序树中删除再插入会有两种情况：
一种是：要删除的是叶子结点，那么直接删除，再插入的时候还会是同一个位置，因为二叉树的形态都没有变化
第二种是：删除的是非叶子结点，那么该二叉树的形态在删除结点之后必定会改变，因为需要用要删除的非叶子结点的前驱或者后继来填补该结点的位置，而一旦树的形态改变了，那么再插入原来删除的结点，必定会插入新的位置。
因此 II 、III是对的 答案选C
P182 T9
①平衡二叉树删除叶子结点后可能会导致失衡，所以进行了调整树，导致树的形态发生了改变，再插入后，就会放到新的位置上
②平衡二叉树删除非叶子结点同样有可能会树的形态发生变化再插入后到新的位置，也有可能过程中形态发生了变化，但是再插入后又调整回原来的形态
- P170 T9-表不是很记得怎么画了
这题我忘记画表的详细过程了，裂开！翻了自己做的笔记才记起来
主要是忘记了Ve(i)是顺着推取max最大值，而Vl(i)是逆着推取最小值，V(i)的取值跟该弧的起点结点的Ve(i)相同，而l(i)是该弧长的终点结点的Vl(i)-该弧长的活动时间。
- P170 T9 错题，很细节，虽然总结过，一不注意就错了！！！
总结详细请看这里！第七章-DS-B树/B+树
错误原因：忘记了根节点最少的关键字是1，最少的分支数是2
我直接把其算成?m/2?-1个关键字，?m/2?个分支了，棋差一招！！！。
计算机组成原理部分
- P170 T9 容易忘记------的知识点
有n为的有效数据位，有k位的校验位，那么n+k<=2k-1,且校验位放在2i-1的位置上，即1，2，4，。。。。。。
码距，如果要检错d位，那么码距为d+1,而如果要纠错d位，那么码距为2d+1
- P171 T20 错题！！
错误原因：不知道条带化是什么东西，Ⅳ又感觉不对也感觉对，但当时是知道Ⅰ和Ⅲ是对的，因为奇偶校验本就是用来提高可靠性的，而磁盘镜像这种东西是复刻的，可以保证数据的安全，就选了C
Cache机制是缓解CPU和主存之间的矛盾和这个磁盘的没关系
条带化类似与低位交叉多模块存储器，用于并行处理数据，加快速度，减少磁盘冲突
- P172 T22 错题！！
DMA传输完数据后还是需要用中断来告诉CPU的，即DMA的预处理和后处理是需要CPU干预的，而数据传输的过程中CPU是无需干预，是由DMA控制器完成的。
- P173 T20 错题！！
这题很细节，把VA->PA的过程都考了
真的是一不小心就入坑了，我选了D/(ㄒoㄒ)/~~
当时想着VA->PA的过程中这三种中有哦！我就选了。。。
但是
发生缺页，那么OS必定已经查过页表了，而处理越界错误是不可能的，因为处理越界错误在发生缺页之前，所以此处已经发生了缺页就不会发生越界错误了。
- P174 T38 错题！！
错误原因：已经忘记了交换机有两种的交换模式了，因为平常考题都是用的存储转发式，这里反其道而行，用直通式，结果直接GG
此外应补充：
综合题
计组部分
第三问开始就不是很会做了
考点：
1）周期=1/频率
2）总线的带宽(最大传输速率)=总线宽度*(总线的时钟频率/n)，n为一次总线操作需要的总线时钟周期数，在这题中，总线的操作均需要1个总线时钟周期
3）总线的突发传送，送首地址后可以连续传输一个数据块
①送首地址时间：5ns
②存储器准备数据时间：根据流水线可得，其流水线流畅后，每经过一个r，r=存储周期/体数，就会完成一个体的存取，而第一个体的存取周期=40ns，之后的体都是流水线，因此其存储器准备数据的时间=40ns+5ns * (8-1)=75ns
③传输数据需要一个总线周期=5ns
因此一次读突发总线事务时间=75+5+5=85ns
4）CPU执行的时间=一条指令所需的执行时间*总的指令数
而一条指令Cache命中的CPI=4，Cache命中所需执行的时间=CPI(命中) * CPU时钟周期 = 4 * 1.25ns=5ns
一条指令Cache不命中时的执行时间= mML ,m为平均每天指令的访存次数，M为Cache的缺失率，L为Cache缺失时突发总线事务所需的执行时间
在这里中，一条指令Cache不命中时的执行时间=1.2 * 85ns * 5%=5.1ns，因此总共的一条指令所需的执行时间=10.1ns。
所以100条指令的CPU所需的执行时间=10.1ns * 100=1010ns
操作系统
好题
3）一个逻辑地址为0000 8000H,因此页号=0000 8H，页号为8，而一个页表项大小为4B，因此8* 4B=32B=0000 0020H，因此
该代码段的物理地址1=0020 0000H+0000 0020H=0020 0020H，而又因为物理地址1和物理地址2也隔了一个页表项，因此
物理地址2=0020 0024H
而因为一个页面的偏移量位12位，因此一个页面的大小=212B=4KB=0000 1000H
因此物理地址3=0090 0000H+0000 1000H=0090 1000H
因为VA和PA位数=32bit，而页内偏移量为12位，所以页框号=32-12=20位，
因此页框号1=0090 0H，页框号2=0090 1H