2013

感受

1、2012年的大题在2013年的小题（T1）会出现

2、码字太慢了，能不能导入一下词库？以及能否双拼加上偏旁法？

3、又出现了！2012-T46到了2013关联起T26了（文件系统的直接索引结构）

4、没想到大题做得很难受，得分情况倒是比想象得要好一点，出题人在设计得分点的时候还是很人性的。

5、没想到做到第五套卷子，得分忽然就从60+到了90+，主要还是选择题错误率一下子降下来了，感动啊！

——20230720

要补的功课

• [x] AOE网的最早最迟问题

• [ ] 海明码怎么去纠错检错？

• [ ] 操作系统里“文件”这一章

选择题

T3 (不会)平衡二叉树

• [x] 一定是完全二叉树？ 一定是顺序遍历的？怎么建立的平衡二叉树？ ——
  • 首先是二叉排序树，按照二叉排序树来插入。
  • 失衡时，按照LL、RR、LR、RL的方法来调整。

参考2010-T4：

参考一下这个教程：https://blog.csdn.net/fxkcsdn/article/details/81674653 LL,LR,RL,RR是插入后有4层的，而如果只有三层的是另一回事儿。

LL/RR/LR/RL的对象不是插入的那个结点，而是插入的那个结点的父结点。——父结点没有爷结点怎么办？——也不是

LL/RR/LR/RL本质上是，从根结点开始往下找（错了，是从插入的结点开始往上找），第一个左右失衡的“根结点”，它的L子树深度大于R子树2，即为第一个L。L里面L子树深度大于R子树1，即为第二个L。 怎么旋转？LL,RR，根结点让位于孩子结点，LR,RL根结点让位于孙子结点。

• [ ] AVL树的删除结点，怎么旋转？

T4（不确定）

• [x] 带权路径长度是叶子结点的边数*叶子结点的权 之和 吗？？——对的，这是树的最短带权路径
  • 问题是树的最短带权路径——哈夫曼树
  • 但是正常地构建三叉树，发现会少一个第二层的结点——要补充虚叶结点，使得缺少的结点是叶子结点
• [ ] 要补充多少个虚结点？？没看懂？？

T5

• [x] 线索二叉树？——按照遍历需要产生的二叉树。没有左/右孩子时有空指针了才产生对应的线索，指向对应的前驱、后继
• [x] 后序是指按照后序遍历来生成线索？——对的，线索二叉树有先序、中序、后序

T6

• [x] 二叉排序树是一定要左子树比自己小，右子树比自己大吗？——是的，这就是二叉排序树
• [x] 如果删除二叉排序树中的非叶子结点，怎么调整——只有左子树或右子树都好说；若左右子树都有呢？——用直接后继（或直接前驱）替代，删掉这个前驱或者后继也就是递归一次。

T9（不确定）

• [x] 它是问 单独减去就能起作用的 活动之集合 还是说 俩同时减去才能其作用？——后者
• [ ] 点里的权和边权的区别？
  AOV(vertex)没有边权
  AVE（edge）才有边权，v是事件，e是活动，，但是依然有点搞不懂？
• [x] 搞清楚路径、简单路径、关键路径的区别 以及前两者与回路 、简单回路的异同——2011年考过

https://blog.csdn.net/ws_Ando/article/details/83006456#:~:text=AOV%E7%BD%91%E2%80%94%E2%80%94%E7%B1%BB%E4%BC%BC%E4%BA%8E%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F%E7%9A%84%E6%A0%B7%E5%AD%90%EF%BC%8C%E5%8D%B3%E7%94%A8%E6%9C%89%E5%90%91%E5%9B%BE%E6%9D%A5%E6%8F%8F%E8%BF%B0%E5%92%8C%E5%88%86%E6%9E%90%E4%B8%80%E9%A1%B9%E5%B7%A5%E7%A8%8B%E5%92%8C%E8%AE%A1%E5%88%92%E7%9A%84%E5%AE%9E%E6%96%BD%E8%BF%87%E7%A8%8B%E3%80%82%20AOE%E7%BD%91%E2%80%94%E2%80%94%E5%8D%B3%E5%9C%A8AOV%E7%BD%91%E4%B8%8A%E5%8A%A0%E4%B8%8A%E6%9D%83%E9%87%8D%EF%BC%8C%E6%9C%89%E5%90%91%E5%9B%BE%E4%B8%AD%E4%BB%A5%20%E9%A1%B6%E7%82%B9%E8%A1%A8%E7%A4%BA%E4%BA%8B%E4%BB%B6%20%EF%BC%8C%20%E6%9C%89%E5%90%91%E8%BE%B9%E4%BB%A3%E8%A1%A8%E6%B4%BB%E5%8A%A8,%EF%BC%8C%E8%BE%B9%E4%B8%8A%E7%9A%84%20%E6%9D%83%E9%87%8D%E4%BB%A3%E8%A1%A8%E6%B4%BB%E5%8A%A8%E6%8C%81%E7%BB%AD%E7%9A%84%E6%97%B6%E9%97%B4%E3%80%82%20AOE%E7%BD%91%E4%B8%8EAOV%E7%BD%91%E7%9A%84%E5%8C%BA%E5%88%AB%E5%9C%A8%E4%BA%8E%EF%BC%9AAOE%E7%BD%91%E4%B8%8D%E4%BB%85%E4%BB%85%E5%85%B3%E5%BF%83%E6%95%B4%E4%B8%AA%E5%B7%A5%E7%A8%8B%E4%B8%AD%E5%90%84%E4%B8%AA%E8%87%AA%E5%B7%A5%E7%A8%8B%E7%9A%84%E5%AE%9E%E6%96%BD%E5%85%88%E5%90%8E%E9%A1%BA%E5%BA%8F%EF%BC%8C%E5%90%8C%E6%97%B6%E4%B9%9F%E5%85%B3%E5%BF%83%E6%95%B4%E4%B8%AA%E5%B7%A5%E7%A8%8B%E5%AE%8C%E6%88%90%E7%9A%84%E6%9C%80%E7%9F%AD%E6%97%B6%E9%97%B4%E3%80%82%20AOE%E7%BD%91%E7%9A%84%E7%89%B9%E7%82%B9%EF%BC%9A%E5%8F%AA%E6%9C%89%E4%B8%80%E4%B8%AA%E8%B5%B7%E7%82%B9%E5%92%8C%E4%B8%80%E4%B8%AA%E7%BB%88%E7%82%B9%20%E5%85%B3%E9%94%AE%E8%B7%AF%E5%BE%84%E7%AE%97%E6%B3%95%EF%BC%9A%20%E5%85%B3%E9%94%AE%E8%B7%AF%E5%BE%84%EF%BC%9AAOE%E7%BD%91%E4%B8%AD%EF%BC%8C%E4%BB%8E%E8%B5%B7%E7%82%B9%E5%88%B0%E7%BB%88%E7%82%B9%E6%9C%80%E9%95%BF%E7%9A%84%E8%B7%AF%E5%BE%84%E9%95%BF%E5%BA%A6%EF%BC%88%E7%94%B1%E4%BA%8E%E8%A6%81%E5%B0%86%E6%89%80%E6%9C%89%E7%9A%84%E6%B4%BB%E5%8A%A8%E9%83%BD%E5%AE%8C%E6%88%90%E6%89%8D%E7%AE%97%E6%98%AF%E7%BB%93%E6%9D%9F%EF%BC%8C%E6%89%80%E4%BB%A5%E5%8F%AA%E6%9C%89%E6%8C%89%E7%85%A7%E6%9C%80%E9%95%BF%E6%97%B6%E9%97%B4%E7%9A%84%E6%B4%BB%E5%8A%A8%E8%B7%AF%E5%BE%84%E6%9D%A5%E8%AE%A1%E7%AE%97%E3%80%82

T10（不会）

• [ ] 关键字包不包括根的？
• [ ] 怎么确定第二层有几个结点？
• [ ] m阶是说有m个孩子结点，还是说叶子结点有m个（或者m-1个）关键字？
• [ ] 如果是前者，那么怎么确定每一层的结点有多少个关键字（孩子结点）？

T11（不确定）

• [x] 基数排序是按照栈存储还是队列存储？——用队列来收集

T14（确定）

• [x] [x1]=1111 0100 x=1000 1100 =-12 -24=1001 1000
  [x2]=1110 1000 直接补码也可，左移空出来的补0——如何光看补码就知道是否溢出？ —— 左移，正常是丢1补0，溢出是丢0

  [y1]=1011 0000 y=1101 0000=-80 -40=1010 1000 ——右移， 正常是丢0补1，溢出是丢1
  [y2]=1101 1000 直接补码也可——右移空出来的补的是1而不是0
  -64=1100 0000 [-64]=1100 0000

• [x] 如果是正数的补码，是不是也是左移补0，右移补1？ ———— 正数的原码、补码，左移右移都是丢0补0.如果丢1就出错

https://blog.csdn.net/vanliujian/article/details/110354887

T15（不会）

• [ ] 海明码和散列函数的关系？
• [x] 海明码的位数和校验对象的位数的关系？——校验位k，数据位n，要想表示某一位出错，满足$$2^{k}-1>=n+k $$

https://www.cnblogs.com/lesroad/p/8688634.html

T17（不确定）

• [x] 十种寻址方式？4（直接、寄存器寻址，两个间接）+2（隐含、立即）+3（偏移寻址，包括基址、相对、变址）
• [x] 变址寻址是偏移寻址还是直接变？ ——偏移寻址

T18

• [x] 四级指令流水线 是“四个指令阶段” 还是“流水线上最多四条指令”？——四个指令阶段

T19

• [x] 那几个标准、协议？？

PCIE就是要取代PCI和AGP，他们是连接主机和外设——局部总线，而USB可以连接设备和IO接口。

T21

• [x] 磁盘控制器延迟 ，跟那三个哪个有关？——就是在读取时加上去

• [x] 4KB是一个磁道里的吗？——当作是的

T23

• [x] 目录和目录项的异同？

  1、目录不是路径

  2、目录项就是FCB（包括文件时间、权限等等描述信息）——一个文件一个目录项

  3、目录就是目录项的集合表（表示了很多个文件）

T24

• [x] 只有顺序存储支持 随机存取吗？——目前看是的

T26

• [x] 索引结点总数和地址项的个数 有什么异同？——

《操作系统》P239、P248
1、一个文件有一个FCB（包括文件名和索引结点），也就是一个文件对应一个索引结点——索引结点总数只是说明文件总数，与单个文件大小无关
2、文件怎么存？10个直接地址（可以理解为1个地址存1个磁盘块号），间接地址（该地址也就是一个磁盘块里存着好多好多盘号），所以索引级数越多，一个一级地址就存更多盘块了

T30

• [x] 什么叫越界错误？ ——比如int a[3];但是a[3]=1
• [x] 处理越界错误具体是指什么？ ——需要越界中断来处理，需要内核态

T31

• [x] 响应比怎么算——————(等+处理)/处理
• [x] 这题用响应比算还是123 132 213 231 312 321 穷举法来算？————都不是，占用IO较多的就优先，响应比等等首先是要明确给了高响应比调度算法才行，但是具体咋做，应该要参考王道书P77之类的例题才行。

T32

• [x] 系统处于安全/不安全状态 是指什么？——安全是指对于这群进程，能够找到一个序列使之顺利完成。
  有个很重要的结论（记住）——安全状态一定不发生死锁；不安全状态可能发生死锁（进程不一定会使用到最大需求量）。

• [x] 银行家算法——每个进程必须先声明一个最大需求量，然后每次都测试已经占有的资源和本次申请的资源之和是否超过上限（累积贷款上限）
  所以银行家算法只是引入了一个“需求量”而已，并不能预防死锁（破坏了四个条件之一），但是说是“避免死锁”的算法。

• [x] 死锁的必要条件？？请求和保持？ ——死锁的产生有四个必要条件：资源互斥使用、进程未使用完资源不被剥夺、请求并保持、循环等待。

T34

• [x] 10BaseT用的是 ——曼彻斯特编码（前低后高为1或者反过来）

T36

• [x] CSMA/CA和CSMA/CD会不会发生冲突？——都可能会发生（毕竟是动态信道了，检测到说明已经有了冲突了）

T38

• [x] IP分组的大小范围？46~500B？ ——46-1500B
• [x] 直通交换——和存储转发相对应。不是存下全部内容再转发，而是只检测目的地址6B，然后就打开通道转发了。

T39

• [x] TCP建立了连接以后——ack是期望获得的下一个序号，所以A发给B，seq=x，ack=y，那么说明B发给A的最后一个序列是y-1，所以B发给A的下一个TCP报文段是seq=y，ack=x+报文段长度