2011年408真题复盘

紫色标记是认为有一定的思维难度或重点总结

红色标记是这次刷真题做错的

记录自己对题目的一些想法与联系，可能并不太关注题目本身。

摘自知乎老哥：“我做历年真题时，绝大部分是130~139，只有一两年上140，看着好像很高，实际确实也挺高的，因为真题中的选择题和大题大部分你是做过的，王道课后习题里有。所以貌似绝大部分最后能上110的做历年真题时平均得分是130多，我做历年真题中选择题时绝大部分错的选择题数在5道以内，只有一两年错了6道，有部分年份一道也没错。做历年真题时得高分别飘，因为和最终考试时得分差别可能有点大。”
 

此话深得我心，看过太多408内容都能学懂但是最后分很低很低，自己应该也是这么个情况。而且此次还是二刷真题，争取吃透每一道题，冲120.

1. for循环括号内部的n/2可以看出和n一个数量级，那么执行语句是log2级别
2. 把所有可能排列出来即可
3. 循环队列这个知识点是真的恶心，隔一段时间不看就忘了。队头指针指向的是第一个元素，队尾指针指向的是队尾元素的下一个元素或者队尾指针指向的就是队尾元素，这一点题目一般会说明。此题进队之后front和rear都是指向A[0]，而进队是rear变（rear+1）%Maxsize，故可以得知选B。
4. 用总结点数和总分支数的关系，总结点数为度为0，1，2的结点数之和，度为1的结点数为0或者1，这三个等式即可解的。
5. 这道题我的做法是根据选项的中序序列和题干的前序序列把树形确定下来，然后发现只有C选项不满足题干后序序列。答案中给出了一个关键解法，前序序列和后序序列相反，不可能存在一个结点同时存在左右孩子，故二叉树的高度为4。
6. 二叉树无右孩子，树则无右兄弟，注意到每个分支的结点必有一个孩子结点是无右兄弟的，一共有1895个分支结点，加上根结点（不存在父结点，但是也无右兄弟）。此外此题还可用特殊法，叶节点在最后一层，每层只有一个分支结点。
7. 采用画图法，满足二叉查找树的特性即可。这一点在2021年真题中用算法题考察
8. 顶点不重复出现的为简单路径，显然回路的第一个顶点和最后一个顶点相同，故不是简单路径。注意简单回路是只有第一个顶点和最后一个顶点相同的回路。
9. 这题没注意到是增大，本来想全选的，没这个答案，实际上是减少装填因子才对。
10. 快排，堆排，希尔排序采用顺序存储。
11. 考察堆排序的调整堆方法
12. IPC是CPI的倒数。
13. 考察float的IEEE 754标准
14. ROM和RAM都能随机存取。CD-ROM是只读型光盘存储器，不是ROM
15. MAR应保证访问到整个主存地址空间
16. 转移指令相对寻址程序浮动；多道程序基址寻址编制浮动程序，循环程序变址寻址数组问题。转相浮，多基制，循变数
17. 无符号数用不到OF和SF，排除ABD。
18. RISC的三个特征。
19. 空指令PC也会自动加一
20. 握手应答信号明显是控制信号
21. 为1代表能屏蔽谁，必须要能屏蔽自己。
22. 程序查询I/O方式
23. 明显是高响应比优先，整个是周转时间最少的算法
24. 命令接口在用户态执行，其他三个明显内核态。
25. 属于线程的栈是独享的
26. I/O系统层次
27. 银行家算法安全序列问题
28. 注意题目说的可能两字
29. 对换区大小和进程的优先级都与抖动无关
30. 编译形成不完整逻辑地址，链接形成完整逻辑地址，装入形成物理地址
31. 单缓冲区MAX{1，3}+2，流水线时多3。双缓冲区MAX{1，2+3},流水线多加2+3
32. 进程执行结果分析
33. TCP/IP模型认为可靠性是端到端的问题
34. 波特率与比特率的关系
35. SR采用逐个确认机制，选择重传机制
36. ACK帧是CSMA/CA避免冲突的机制之一
37. 2009年的大题第三问路由聚合，一样的内容放到2011年小题考察
38. 广播地址，所有主机，一共2个都能收到
39. 考察三报文握手
40. 考察TCP连接的确认机制