查缺补漏 | GXBLOGS

12月23日：

08:30-11:30：思想政治理论

14:00-17:00：外国语

12月24日：

08:30-11:30：数学

14:00-17:00：专业课

高数

不熟不顺，记忆模糊

✔泰勒公式
✔三重积分的计算，计算速度
✔ 斯托克斯公式，都是平面的（考虑cos）？非平面的呢（考虑参数方程）合一投影法
把真题的两种方法都写一下
吃尽天下面
- 拉格朗日乘数法的计算问题_哔哩哔哩_bilibili
✔反常积分判别式
✔场论
✔第一型曲线积分，怎么转参数方程

查看
空间曲线一般式化为参数式：
1、先联立消去一个变量，剩下两个变量好转参数式（关键就是 $\sin^2 t+ \cos^2 t=0$ ）
2、剩下一个，用前面求出来的代入
✔隐函数求导的各种方法
✔中值定理证明题 2017 18
✔欧拉方程 2021，记得还原之前还原的部分
✔ $y = x - \sqrt x$ 的渐近线 ans：不存在
✔拉格朗日乘数法，只算出一个点，还要说明最大还是最小？2018 16 ans：不用，只是这题有边界
✔拉格朗日乘数法计算过程有没有分
✔各种证明题 2018 18
✔ $0^0$ 是多少 ans：考试的时候还是记为1吧
✔微分算子法复习
✔傅里叶级数
✔多元微分极值的定义法
✔重极限的计算，判断
✔二型用不用对称性捏好像从来都没见过
✔反常积分的两个常见模糊了
画不出图怎么办
✔二型曲线曲面的对称性再看看 ans：考试的时候还是不考虑这个了
常见曲线再看看
弧长，侧面积公式p129
书上最难的题之一p159
✔积分判别法
✔ 法向量，切向量怎么求
建立柱面方程和旋转面方程，投影
积分物理题
✔ p119积分不等式

真题模拟题总结

法平面的题，优先把法平面写出来 2018 2
$F'_x(X-x_0)+F'_y(Y-y_0)+F'_z(Z-z_0)=0$
定积分比较大小，积分域相同，比较被积函数，那代值进去更快啊 2018 4
判断相似的选择题，都是先排除不相似的 2018 5
$xy+yz+zx=\frac12[(x+y+z)^2-(x^2+y^2+z^2)]$ 2018 12
A 3 3；B 2 2；C 2 3；D 2 3
$\alpha >0,\beta>0,\lim \limits_{x\to0}x^\alpha\ln^\beta x=0$
穿针引线法 设多项式的最高次项系数大于零.从数轴上最右边的根的右上方开始穿根根据零点的重数的奇偶性决定穿或者不穿,即奇穿偶不穿,或奇穿偶回. 【例如： $y=(x-1)(x-2)^2(x-3)^3(x-4)^4$ 】
斜渐近线的b也得存在，要算
设 $x_1,x_2,…,x_n%,$ 是相应于样本 $X_1，X_2,…,X_n$ 的一组样本值

线代

不熟不顺，记忆模糊

✔向量空间，基 2015(20)、2010(13)、2009(9) 2009(5)
✔二次型熟练度不够 2018 20 2023 21
✔公共解同解
✔基础书p249定理3.7

真题模拟题总结

二次型的坑：x=Cy，C得是可逆矩阵 2018 20
若配方法只有混合项eg: $x_1x_2=0$ ，可以借助平方差公式 $x_1=y_1-y_2;x_2=y_1+y_2;x_3=y_3$
负惯性指数=0，推出：二次型非负

概率

不熟不顺，记忆模糊

✔一维随机变量函数的分布，公式法再看看
✔Z=XY这样的题回去看看880
✔大数定律
✔多维随机变量定义法
✔第一章几个公式，推论再复习看看
✔假设检验 2018 8

真题模拟题总结

泊松分布 0! = 1

操作系统

不熟不顺，记忆模糊

✔ 请求分段存储
✔ 索引结点几个关于存储的题，需要总结一下，还是总犹豫
✔ 段页式存储管理没有像多级页表那样，对页表没有什么要求
✔ 混合索引分配，inode不在内存的话，读iNode要几次磁盘I/O？一次？
✔ 单缓冲、双缓冲计算时间的问题
✔ 如果文件F1的当前计数值为1，建立F1的的硬链接文件F2，再建立F1的符号链接F3，现在删除F1，此时文件F2和F3的计数值分别为？

1; 2
✔ 2015 选择第10题
✔ 2015pv（为什么都不用读写公平啊）
—— 题目要求解决饥饿再写，没要求就都行
✔ 软中断（Soft Interrupt）是计算机系统中一种由软件触发的中断机制，用于处理与操作系统或内核相关的事件和任务。
✔ 会导致磁头臂黏着的算法 2018选只有FCFS
各种表的表项
✔ 信号量到底可不可以直接加减复制，书上只有初始化可以复制，其他时候不行
✔ 2020选择题第三题
✔ 位示图和块号的转化

真题总结

在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少
也会考给出几个实际进程，然后让你给出等待时间最短的调度顺序 —— 2014（填）
信号量
- -x，表示有x个进程在等待 —— 2014（填）、2018（填）
- 取值范围 —— 2017（填）
有快表的题，默认是命中率*(访问快表 + 访问内存) + 不命中率*(访问快表 + 访问慢表 + 访问内存)；有说同时访问的再看吧，820还没见过(命中率*(访问快表 + 访问内存) + 不命中率*(访问慢表 + 访问内存)) —— 2014（填）
页式存储(2)、段式存储(2)、段页式存储(3)的访存次数，请求分页存储的缺页时的操作 —— 2014（填）、2015（填）、2016（选）2019（计算题）
内存逻辑地址转物理地址 —— 2014（填）、2015（填）、2016（分析计算题）、2017（选）、2018（填）
有时候靠的是十进制，那就是用\、%来得到页号、偏移
PCB（重点记忆啊）
- 操作系统是根据进程控制块来对并发执行的进程进行控制和管理 —— 2014（选）
- PCB是进程存在的唯一标志 —— 2018（填）2019（填）
进程调度 —— 2017（填）、2019（计算题）
- 会饥饿的有：短作业优先、优先级、多级反馈队列 —— 2016（选）
- 进程转换不可发生的是（xx态 → xx态）—— 2018（选）
- fock()函数的作用是创建一个新的进程 —— 2019（填）
设备独立性
- 设备独立性的基本含义是指应用程序独立于具体使用的物理设备 —— 2014（选）、2017（选）
- 什么是设备独立性？应如何实现？—— 2016简
文件
- 从用户角度上看，文件系统主要是为了实现按名存取 —— 2014（选）
- 文件的大小取决于文件系统，最大大小取决于保留存储尺寸的位数及文件系统的大小。目录容纳的文件不仅受到磁盘容量的限制，还受文件系统的限制 —— 2015（选）
- 当前工作目录的作用：加快文件的检索速度 —— 2016（选）
- 对一个文件的访问常由用户访问权限和文件属性共同限制 —— 2017（选）
索引结点 + 混合索引

支持文件的最大程度（一般就是按xxKB + xxMB + xxGB…这种结构来写） —— 2014（分析计算题）、2018（填）
访问某个字节需要几次磁盘I/O（题目应该会给出inode是否在内存中）—— 2014（分析计算题）

单缓冲、双缓冲计算时间 —— 2015（填）
信号量初值是多少的问题
互斥一定是1；—— 2015（填）
同步看资源的数目，和制约关系
死锁
- 不会发生死锁的最大进程数 —— 2016（填）、2018（选）
- 死锁预防
  - 破坏互斥条件
  - 破坏请求和保持条件 —— 静态分配
  - 破坏不可剥夺条件
  - 破坏循环等待条件 —— 顺序资源分配 —— 2016（选）
- 死锁避免 —— 2017（选）2019（选）
硬链接、软链接
- 计数值的大小 —— 2015（填）
局部性
- 虚拟存储管理系统的基础是程序的局部性理论 —— 2015（选）
虚拟设备是指采用虚拟技术将一台独占设备转换为若干逻辑设备 —— 2015（选）、2019年（选）
SPOOLing
- SPOOLing技术不需要独占设备 ✘，不需要外围计算机 ✔
- SPOOLing系统主要包括三部分，即输入井和输出井、输入缓冲区和输出缓冲区以及输入进程和输出进程。这三部分由与输入程序、井管理程序和缓输出程序管理，以保证程序的运行
I/O控制方式 —— 2016（选）、2018（选）
- 程序查询方式（程序I/O方式）
- 中断方式
- DMA方式 —— 2017（选）
- 通道方式
磁盘调度 —— 2018（选）
- 当移动臂定位后，由延迟时间来决定执行次序的调度称为旋转调度 —— 2017（填）
表项
- 逻辑设备表LUT| 逻辑设备名 | 设备驱动程序口地址 | 物理设备名 | —— 2019（填）
纯用户型线程操作系统，采用用户进程管理，内核级操作系统，采用操作系统进行管理
文件逻辑结构的对比
- 适合随机访问且易于文件扩展的是索引文件 —— 2016（选）
- 访问速度最快的是顺序文件 —— 2019（填）

简答题汇总

考试最常考的题型就是为什么引入什么什么，所以这类的知识点要多背一点

在存储管理中，什么是重定位？为什么要引入重定位技术？ —— 2014

查看解析

因为源程序经过编译、链接产生的装入模块是从0开始编址的，地址都是相对于起始地址的相对地址。在装入内存时，分配到的内存的起始地址一般不为0，所以实际物理地址和装入模块中的相对地址不同。为了程序的正确运行，需要进行重定位

为什么要引入动态重定位？如何实现？—— 课后题

答：a.程序在运行过程中经常要在内存中移动位置，为了保证这些被移动了的程序还能正常执行，必须对程序和数据的地址加以修改，即重定位。引入重定位的目的就是为了满足程序的这种需要。
　　b.要在不影响指令执行速度的同时实现地址变换，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。

什么是临界资源、死锁？若采用以下算法解决哲学家进餐问题，是否会导致死锁？为什么？（10分） —— 2015

查看解析

临界资源：必须互斥使用的资源。（2分）
死锁：多个进程因为竞争资源或执行时推进顺序不当、或互相通信而永久阻塞的现象，若无外力作用，这种现象将永久保持下去。（2分）
该算法不会导致死锁。（3分）
因为该算法破坏了死锁的四个必要条件之一 —— 循环等待条件。该算法的实质是对每个临界资源——餐刀进行编号，保证每个哲学家按照从小到大的次序依次申请资源，从而不会产生循环等待现象。（3分）

文件物理结构是指一个文件在外存上的存储组织形式，主要有连续结构、链接结构、和索引结构三种，请分别简述它们的优缺点。 —— 2015、2017

查看解析

（1）连续结构
优点：可以随机访问磁盘，访问速度快。
缺点：要求有连续的存储空间，易产生内部碎片，磁盘利用率低，且不利于文件增长扩充。

（2）链接结构
优点：不要求连续的存储空间，磁盘利用率高，有利于文件的增长扩充。
缺点：只适合顺序访问，不适合随机访问；文件数据块之间靠指针链接，可靠性差；指针信息的存放消耗外存。

（3）索引结构
优点：既支持顺序访问，又支持随机访问，查找效率高；便于文件的删除；易于实现文件的拓展
缺点：索引表占用一定的存储空间。

PCB的主要存储内容是什么？为什么说PCB是进程存在的唯一标志？ —— 2016、2020

查看解析

PCB是用来保存进程运行期间相关的数据，主要存储的内容为进程标识符、处理机状态，进程调度信息，进程控制信息等。
在进程整个生命周期中，系统总是通过PCB对进程进行控制，也就是说系统是根据进程的PCB，而不是别的什么而感知到该进程的存在，所以说PCB是进程存在的唯一标志。

什么是虚拟存储器？如何实现页式虚拟存储器？ —— 2016

查看解析

虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统，其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度。
页式虚拟存储器是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的。它允许只装入部分页面，以后再通过调页功能和页面置换功能，把即将运行的页面调入内存，同时把暂时不运行的页面换到外存上。实现请求调页和置换功能，系统还需要提供必要的硬件和软件的支持。

什么是设备独立性？应如何实现？ —— 2016、2020

查看解析

为何要引入设备独立性？如何实现设备独立性? —— 课后题

现代操作系统为了提高系统的可适应性和可扩展性，都实现了设备独立性或设备无关性。基本含义是应用程序独立于具体使用的物理设备，应用程序以逻辑设备名请求使用某类设备。实现了设备独立性功能可带来两方面的好处:（1）设备分配时的灵活性；(2)易于实现I/O 重定向。
为了实现设备的独立性，应引入逻辑设备和物理设备概念。在应用程序中，使用逻辑设备名请求使用某类设备：系统执行时是使用物理设备名。鉴于驱动程序是与硬件或设备紧密相关的软件，必须在驱动程序之上设置一层设备独立性软件，执行所有设备的公有操作、完成逻辑设备名到物理设备名的转换（为此应设置一张逻辑设备表）并向用户层（或文件层）软件提供统一接口，从而实现设备的独立性。

文件物理结构是指一个文件在外存上的存储组织形式，那么何谓文件的混合索引结构？其主要优点是什么？ —— 2016

查看解析

混合索引分配方式是指将多种索引分配方式结合而成的分配方式。常见的是采用直接地址和一级索引联合的分配方式，或两级索引分配方式，甚至三级索引分配方式。（课后题的答案，解析太烂了）

优点是可以随机访问，易于文件的增删。

系统发生死锁的充分必要条件是什么？如何预防死锁、解决死锁？ —— 2017

查看解析

产生死锁的必要条件是：互斥条件、请求和保持条件、非剥夺条件、循环等待条件。

产生死锁的充分条件是：当且仅当系统的资源分配图是不可完全简化的，该充分条件被称为死锁定理。

预防死锁是通过破坏死锁产生的四个必要条件一个或者几个，以避免死锁的发生。

破坏互斥条件：在系统中取消互斥条件，由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证，因此主要破坏产生死锁的其他三个条件。
破坏请求和保持条件：若要破坏请求和保持条件，进程在运行前，必须一次性申请所有资源。若系统有足够的资源，便可把其所需要的所有资源分配给进程，则进程在运行期间不会提出资源要求，若只要有一种资源不能满足进程的要求，就让进程等待，且进程在等待期间不占有任何资源，于是破坏了请求和保持条件。
破坏不可剥夺条件：为了破坏非剥夺条件，要求当一个已经保持某些非剥夺资源的进程，提出新的资源请求而不能得到满足时，必须释放已经保持的所有资源，这就破坏了非剥夺条件。
破坏循环等待条件：破坏“循环等待”条件的一种方法，是将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序(升序)提出，也就是资源的有序分配策略，这样做就能保证系统不出现死锁

为什么要在设备管理中引入缓冲技术？缓冲区的类型有哪些？ —— 2017

查看解析

引入缓冲区的目的主要有:

缓和 CPU 与IO 设备间速度不匹配的矛盾
减少对 CPU 的中断频率，放宽对 CPU 中断响应时间的限制
解决数据粒度不匹配的问题
提高 CPU 和I/O 设备之间的并行性

缓冲区的类型有：单缓冲、双缓冲、循环缓冲、缓冲池

单缓冲：在 CPU 和外设之间设置了一个缓冲区，当有数据交换时，先把数据发往缓冲区，再从缓冲区读数据
双缓冲：具有两个缓冲，当一个进程正往一个缓冲区读数据的时候，操作系统可能正在读或写另一个缓冲区
循环缓冲: 具有多个缓冲区的组合，它更加能够缓和 CPU 和外设之间速度不匹配的问题。
缓冲池: 由多个系统公用的缓冲区组成

死锁预防与避免死锁的区别 —— 2018

查看解析

预防死锁是通过破坏死锁产生的四个必要条件一个或者几个，以避免死锁的发生。

破坏互斥条件：在系统中取消互斥条件，由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证，因此主要破坏产生死锁的其他三个条件。
破坏请求和保持条件：若要破坏请求和保持条件，进程在运行前，必须一次性申请所有资源。若系统有足够的资源，便可把其所需要的所有资源分配给进程，则进程在运行期间不会提出资源要求，若只要有一种资源不能满足进程的要求，就让进程等待，且进程在等待期间不占有任何资源，于是破坏了请求和保持条件。
破坏不可剥夺条件：为了破坏非剥夺条件，要求当一个已经保持某些非剥夺资源的进程，提出新的资源请求而不能得到满足时，必须释放已经保持的所有资源，这就破坏了非剥夺条件。
破坏循环等待条件：破坏“循环等待”条件的一种方法，是将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序(升序)提出，也就是资源的有序分配策略，这样做就能保证系统不出现死锁

死锁避免是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。一般使用的是银行家算法。

抖动原因，怎样解决 —— 2018
什么是抖动，减少抖动的措施？—— 2019

查看解析

抖动的定义：在页面置换过程中，刚刚换出的页面马上又要换入主存，刚刚换入的页面又要换出主存，这种频繁的页面调度行为叫做抖动
抖动的原因：某个进程频繁访问的页面数目高于可用的物理块数。

解决方案：增加物理块(对先进先出算法不管用)；选择适当的页面置换算法

系统怎样实现文件共享，共有几种方式，各有什么特点 —— 2018、2019

查看解析

基于索引结点的共享方式(硬连接)
不同目录下使用相同索引结点，在索引结点中再增加一个计数值来统计指向该索引结点的目录项个数，只有计数值为1时才可删除该索引结点，若计数值大于1删除时把计数值减1即可，增加共享时计数值加 1。
优点：实现文件的异名共享
缺点：当文件被多个用户共享时，文件拥有者不能删除文件。
在硬连接中，目录项中只有文件名，指向的是共同的索引结点，索引结点再指向文件，所以一个文件名修改索引结点，其他所有文件名的索引结点都被修改了，因为所有文件名指向同一个索引结点。
利用符号链实现文件共享(软连接)
相当于把共享文件的路径副本复制过来(并不拥有文件)，并且只有在文件试图去访问时才会更新其路径副本。
优点：解决了文件拥有者不能够删除共享了的文件的问题
缺点：当其他用户要访问共享文件时，需要逐层查找目录，开销较大。

2019：软链接硬链接是什么？主要区别是什么？

区别：只要有一个硬链接存在，物理文件就不会被清除。硬链接和原文件是“平等”的，只删除一个不能使文件真正被删除；如果软链接创建时指定的那个目录被“删除”，则无法访问物理文件。软链接是附属于原文件的，删除、更改原文件路径后软链接将失效。

什么是快表？说明利用快表的地址转换过程是怎么样的？ —— 2019

查看解析

快表的定义：系统设置了一个小容量的高速缓冲存储器，用来存放页表的一部分，即快表，可以一次访问主存完成读/写，大大缩短地址转换时间，从而提高查找速度。

地址转换过程：按照逻辑地址中的页号查快表，若该页已存在快表中，则由页架号和单元号形成绝对地址，若该页不在快表中，则再查主存页表，与单元号形成绝对地址，同时将该页登记到快表中，当快表填满后，又要登记新页时，则需要按照一定替换策略淘汰一个旧的登记项

SPOOLing系统组成部分，工作原理是什么？ —— 2019

查看解析

组成部分：SPOOLing 系统主要有以下三部分:

输入井和输出井。这是在磁盘上开辟的两个大存储空间。输入并是模拟脱机输入时的磁盘设备，用于暂存 I/Q 设备输入的数据；输出并是模拟脱机输出时的磁盘，用于暂存用户程序的输出数据。
输入缓冲区和输出缓冲区。为了缓和和 CPU 和磁盘之间速度不匹配的矛盾，在内存中要开辟两个缓冲区；输入缓冲区和输出缓冲区。输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井。输出缓冲区用与暂存从输出并送来的数据，以后在传送给输出设备。
输入进程和输入进程。这里利用两个进程来模拟脱机I/O 时的外围控制机。其中，输入进程模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井，当CPU 需要输入数据时，直接从输入井读入内存；输出进程模拟脱机输出时的外围控制机，把用户要求输出的数据从先内存送到输出井，待输出设备空闲时，在将输出井中的数据经过输出缓冲区送到输出设备上。

工作原理：SPOOLing 是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。它的核心思想是以联机的方式得到脱机的效果。低速设备经通道和外设在主机内存的缓冲存储器与高速设备相联，该高速设备通常是辅存。为了存放从低速设备上输入的信息，或者存放将要输出到低速设备上的信息(来自内存)，在辅存分别开辟一固定区域，叫“输出井”(对输出)，或者“输入井”(对输入)。简单来说就是在内存中形成缓冲区，在高级设备形成输出井和输入井，传递的时候，从低速设备传入缓冲区，再传到高速设备的输入井，再从高速设备的输出井，传到缓冲区，再传到低速设备。在多道程序下，利用其中一道或两道模拟脱机输入/输出中的外围控制机的功能，以达到假脱机的目的。可以把独占的设备变成共享的虚拟设备，从而提高独占设备的利用率。

什么是局部性原理？局部性原理的具体体现？

查看解析

时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因是由于在程序中存在着大量的循环操作。

空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

具体体现：数组，循环结构

多级反馈调度算法的思想和特点. —— 2021

查看解析

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展。

思想:
a. 该算法设置多个就绪队列，队列优先级依次降低，第一级最高(优先级调度算法体现)。
b. 前 n-1个队列都采用FCFS 调度算法，最后一个队列采用时间片调度算法进行调度，而且每个队列采用的时间片大小不一，优先级越高时间片越短(时间片轮转法的体现)。
c. 新进程先放入第一级队列,时间片完后,若该进程没有执行完则放入第二级队列,依次下降到最后一级队列。
d. 优先级高的队列可抢占 CPU，只有优先级高的队列为空的时候才可以允许优先级低的队列。
e. 必须设置为抢占。

特点:
存在饥饿问题。当新进程不断到来，进入较高优先级队列，CPU忙于运行高优先级队列中的进程，低优先级队列中的进程将长时间得不到调度，产生饥饿现象。是一个目前公认能较好的应对各类用户作业的算法。

多级反馈调度算法是怎么实现短进程和长进程公平处理的? —— 2021

查看解析

多级反馈调度算法每个队列的优先级不同，优先级高的队列可以抢占 CPU，若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。进程先到达第一级队列，操作系统为每个进程分配时间片，根据先来先服务调度算法进行调度，时间片使用完的进程调度到下一级队列，当前队列中没有调度的进程时，调度次级优先级队列中的进程，如此重复。这样长进程不会一直等待，短进程可以在使用较少时间片的情况下先完成，从而达到公平处理。

PV题总结

生产者消费者问题
- 变形1：缓冲区
  一个缓冲区的内容需要被每个消费者消费一次才算空 —— 2014 2016
  解决办法：
读者写者问题

变形1：桥
变形2：单向道路 —— 2015

数据结构

不熟不顺，记忆模糊

✔空间复杂度
✔prim 和 kruscal的算法过程和时间复杂度
✔平衡二叉树的具体代码 ans: 不看了，没必要
✔线索二叉树
✔弗洛伊德算法的过程
✔ 算法题中的哈希表怎么写 2017 算法题第一题 ans：不写，用排序来解决统计的问题
✔ 关键路径的双记号标记法是啥 2018简答题6
✔ 拓扑排序算法题 / 算法思想
✔ 填空题中写 xx 条件的时候是写 =，还是==
✔ 栈为空的条件写什么 0
表达式求值以及课后题3.8
✔ kruskal和prim算法哪个可以用来求无权图的最短路 ans：都不行
✔ 广义表怎么画
✔ 二叉树的非递归后序遍历 ans：感觉没必要会
✔ 强连通分量代码
✔ 基数排序
✔ 分块查找
✔ 除留余数法
✔ 哈希表查找不成功 ans:每个位置每个位置看

真题汇总

逻辑结构分为线性结构和非线性结构 —— 2015（填）、2018（填）2019（选择）
链表
- 插入操作 —— 2015（填）
- 合并升序单链表 —— 2015（算）2018（算）
- 设计单循环链表作为队列 —— 2016（简）、2019（简）
- 设计实现栈 —— 2019（简）
- 单链表实现队列，队头指针指向头结点 —— 2017（简）
- 链表逆置 —— 2019（选）
线性表
- 顺序存储插入和删除的移动个数 —— 2015（选）、2017（选）2019（填）
- O(1)空间复杂度，改变元素位置 —— 2016（算）、2019（算法题）
- O(n)时间复杂度统计 —— 2019（简）

时间复杂度、空间复杂度、稳定性几个排序算法的时间空间复杂度 —— 2015（填、选）、2018（填）、2019（选）

排序方法	平均时间	最坏情况	辅助存储	稳定性
插入排序	$O(n^2)$	$O(n^2)$	$O(1)$
希尔排序	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$
简单选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
快速排序	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不稳定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n)$
基数排序	$O(d(n+rd))$	$O(d(n+rd))$	$O(rd)$

循环队列
- 队空条件 front == rear —— 2015（填）、2018（选）
- 队满条件(rear+1)%MAX_SIZE == front —— 2017（填）
  （牺牲一个单元）另外两种方法是设置标记、设置计数器
二叉树
- n个结点的树高至少为 —— 2015（填）、2017（选），2019（填）
- $n_0=n_2+1$ 的证明（不会的话就把能知道的等式列出来加加减减）—— 2015（简）
- 交换二叉树的左右子树（翻转二叉树）—— 2015（算）、2017（算）
- 判断B是不是A的子结构 —— 2018（算）
- 二叉排序树的插入 —— 2019（算）
- 线索二叉树
  - 画图题 | | val | | 一个结点画三个域，没有前后线索可以不画箭头 —— 2016（简）
  - 线索二叉树是一种物理结构 —— 2017（选）
  - 指向前驱 tag == 1 —— 2017（选）
- 可还原二叉树的必须要有中序，然后随便搭配前序和后序其中一个，没有层序 —— 2015（选）、2018（选）
哈夫曼树
- 计算带权路径长度 —— 2015（填）
- 画图 —— 2017（简）
无向图
- n个顶点最多 $C_n^2$ 条边 —— 2015（填）
- 生成树
  - 最小生成树
  - 深度优先生成树 / 广度优先生成树（都优先按邻接表来）—— 2015（简）
- 领接表的空间复杂度O(n + 2e)
快排
- 排序过程 —— 2015（填）、2018（选）
折半查找

查找过程 —— 2017（选）

二路归并算法的排序过程 —— 2019（选）
广义表

取表头（头元素） / 取表尾（除了头元素的其他，注意空元素）—— 2015（选）、2018（选）

栈

出栈顺序 —— 2015（选）、2018（选）
用双栈实现队列 leetcode —— 2018（简）

查看算法思想

Stack1 (用于入队列)：用于存储进入队列的元素。
Stack2 (用于辅助出队列)：用于辅助出队列操作。

Enqueue 操作：
1. 当需要入队列时，直接将元素压入 Stack1 中。

Dequeue 操作：
1. 检查 Stack2 是否为空，若不为空，则直接从 Stack2 弹出栈顶元素。
2. 如果 Stack2 为空，则将 Stack1 中的元素逐个弹出并压入 Stack2 中，使得 Stack2 的顺序与队列顺序相反。
3. 然后从 Stack2 弹出栈顶元素，即为队列中的第一个元素。

Peek（获取队首元素）操作：
1. 执行类似于 Dequeue 的操作，但不删除栈顶元素，而是返回栈顶元素。

isEmpty 操作：
1. 如果 Stack1 和 Stack2 都为空，则队列为空。

prim 和 kruskal —— 2015（选）、2017（填）、2018（填）
- prim 边稠密 $O(n^2)$
- kruskal 边稀疏 $O(e\log e)$
关键路径
- 源点到汇点最长的路径 —— 2015（选）、2017（选）
哈希表
- 考画图（表项为 | 地址 | key | 查找次数 |），然后算 $ASL_{查找成功}$ $A S L_{查找成功}$
  - 线性探测法 —— 2019（简）
  - 二次探测法（先正的再负的），是需要加完代入哈希函数中重新计算的 —— 2015（选）
  - 溢出区（按顺序放）—— 2016（简）
堆排序
- 考画图
  - 插入（插入到末尾，然后不断和父亲交换上浮）—— 2015（选）
  - 删除（没有这个操作）
  - 初始建堆（每个非叶子结点下缀到底）
  - 取出堆顶元素（和最后一个元素交换，然后下缀到底）
平衡二叉树
- 考画图
  - 初始建树（全部插入完再调整 还是边插入边调整？看题目要求吧）—— 2016（简）2018（简），2019（简）
  - 单步插入调整 —— 2015（简）
拓扑排序
- 列出拓扑序 —— 2015（简）
- 算法题 / 算法思想 —— 2019（简）
- 检测是否有环 —— 2020（简）
最短路 —— 2019（选）
- Floyd —— 2016（简）、2018（填）
- dijkstra 的求解过程—— 2019（简）

英语

做题顺序

英一: 作文-阅读-新题型-完型-翻译

我的问题

每次排除了只剩最后一个选项，就会自我暗示这是对的
情态动词后面的内容要注意
破折号 ——xxx—— 啥意思
千万别跳读
虽然说积累话题是好事，但是千万别先入为主，因为不同文章对待同一个问题的态度可能大相径庭
一定一定要回文中找到每个选项的每个部分的同义改写
不要只局限于一段

新题型

小标题题 15-20mins 2016 2020 2021 2022

一般七个选五个

做题思路:
1.先通读标题，记住标题对文章进行整体理解
2.做题时不必拘泥于原文的顺序最好先易后难。具体做的时候关注段首和转折后 (有转折看转折)，找出语段特征。
3.作出最终判断时，必须要找到明确的匹配关系。(即同义替换或复现)

解题分析：
1、分析语段特征，找出重点句,
2、抓句子主干
3、寻找匹配关系

课后总结

一、小标题题做题思路
1、先通读标题，记住标题对文章进行整体理解
2、做题时不必拘泥于原文的顺序，最好先易后难。具体做的时候关注段首
和转折后(转折后优先)，找出语段特征。
3、作出最终判断时，必须要找到明确的匹配关系。(即同义替换或复现)

二、小标题题总结
1、明确标题共性特征(比如动宾结构需明确动作发出者)
2、转折后重要不变，若无明确匹配关系，通读全段，重点读标题对应结构
(如标题为动宾，则快速浏览原文动宾结构)
3、明确的匹配关系可能包含同义替换、复现、正话反说、反话正说

三、小标题题解题分析
1、分析语段特征，找出重点句
2、抓句子主干
3、寻找匹配关系

排序题 2010 2011 2014 2017 2018 2019 2023

（一）考点分析
语段特征词 —— 体现语段的连贯性和一致性

逻辑关系词 (能体现上下文逻辑，非句内逻辑) ;
展开
我们家有四口人，分别是爸爸、妈妈、C 和我。
A.狗狗 B.壁炉 C.姐姐 D.奥特曼
小明和小强有着截然不同的性格，小明性格温和，C ，小强性格暴躁
A.因为 B但是 C.相反 D.例如

重要重要重要：
- 对立关系
转折: however，but，yet，nevertheless，or
让步: although, though，even though(尽管)，even if, much as=as (虽然、尽管)，while，
whereas
其他: against(反对)，instead (of) (然而), rather than (而不是)，ignoring (忽略、忽视)，on
the contrary, by contrast (相反的)
- 并列关系
and, as well as, while (而，而且)，or (或者)，meanwhile (同时)，similarly(类似，相似)，
likewise (同样的)，simultaneously (同时的)
- 因果关系
表原因的词: because, in that, now that, since, as, for, as a result of, considering, in
response to (对…作出反应)
表结果的词: so that, such that, as a result, lead to, consequently, therefore, hence, thus,
so
注意:原因结果词在一句话中只能出现
- 总分关系
for example, for instance, such as, including
- 递进关系
still, also, indeed, furthermore(进一步)，moreover（而且，此外)，highlighting(突出，强调)
- 时间顺序关系
as, while, when(当), in the meanwhile, meanwhile (与此同时), at first, finally
代词 (一定是充当指代功能的代词) ;

展开
It, she, he, they, we
such, this, that, these, those+ n. 优质代词（该名词一定在上文出现过，可用作做题线索）

请辨析： It is kind to help others. (形式主语，非代词）
It is the educated that have claimed to give up ambition.（强调句型，非代词）
冠词+名词 (说明该名词在上文中出现或存在同义词)

展开
不那么好用，看看就是：
a+n. 代表该名词在文中第一次出现
the+n. 代表该名词在文中第二次或之后出现
前后句子意思的衔接 (只需看懂基本表达）
如果前后意思读不懂，则考虑单词复现 1）专有名词 2）普通名词 3）动词

(二）做题步骤

每个选项首尾句中找语段特征词，如果全文第一段未确定，则优先确定第一
段选项; （第一段第一句没有语段特征词）
根据固定选项首尾句中的语段特征词去确定未固定选项的位置，注意复现关系;
根据未固定选项首尾句中的语段特征词去确定未固定选项的位置【每年一般有两个这样的】
当很难确定AB两项谁前谁后时，判断A尾+B首和B尾+A首，哪个更合理选哪个

（三）方法论总结

优质代词优先做（such, this, that, these, those)；
其次借助逻辑关系词做题；
当没有1.2.中的词时，考虑复现，但复现务必对文章语义有一定了解，不能只找对应的词。

小结：优质代词>逻辑关系词>复现（语义）
冠词仅作检查，不主要用来做题

七选五 2012 2013 2015

（一）做题步骤

读每个选项第一句，划出语段特征词，根据意思推测上文内容或可能复现的词;
根据选项在文中的位置来确定读选项的上一句还是下一句，还是上下句都读;
运用原文内容与选项的意思的连贯性、一致性做出最终判断

优质代词优先做 > 逻辑关系词 > 复现

语段特征词不考虑复现

翻译

大雁：

首先要明确出题人的要求：正确通顺完整，但是老师改的快，所以一定一定要通顺，一切为通顺让步：

首先要根据单词本来的意思，想象和延伸
eg：老鼠 develop 一个传染病 -> 老鼠患了一个传染病
但是如果我不知道这个单词什么意思，那就找相关单词搭配翻译，就是瞎说，怎么通顺怎么说
eg：科学家——这些结构（就可以填：研究、剖析、调查）
再就是往上下文寻找提示和线索
找不到就想文章的中心
最后，大词瞎胡说，小词装作没看见（大词就是主谓宾上的词，小词就是修饰，非主干的词）
ps：一个大词别空着，错了只扣0.5，一个小词不翻译不扣分，两到三个才扣0.5

翻译速成：20min精华，无废话！_哔哩哔哩_bilibili：