lionel技术知识整理输出
2023年01月06日
缘起
内容
一、数据结构
- 1、绪论
- 2、线性表
- 顺序表：要先分配一段空间，不管是用数组
int data[100]，还是用int *base=new int[100]两种
- 链表：
- 3、栈、递归、队列（受限的线性表）
- 4、串、稀疏矩阵、广义表
- 5、树与二叉树
- 6、图
- 遍历：
- 广度（队列辅助空间），
- 深度（栈辅助空间），后被访问的顶点，其邻接点先被访问。
- 7、高级数据结构
- B-树（B树）：
- 二叉搜索树的树高会影响效率，平衡二叉树搜索树虽然减少了树高，但还是不行，于是有多路平衡搜索树【一个节点，不再限于只存一个关键字，而是存多个关键字和多个子树】
- 一根m阶B-树满足以下特性：
- 1）每个节点最多有m棵子树
- 2）根节点至少有两根子树
- 3）内部节点（除根和叶子之外的结点）至少有
m/2(取上界）棵子树
- 4）终端节点（叶子）在同一层上，并且不带信息（空指针），通常称为失败节点
- 5）非终端节点的关键字个数比子数个数少1
- B+树（不算传统的树了）
- 一根m阶B+树满足以下特性：
- 1）每个节点最多有m棵子树
- 2）根节点至少有两根子树
- 3）内部节点（除根和叶子之外的结点）至少有
m/2(取上界）棵子树
- 4）终端节点（叶子）在同一层上，并且不带信息（空指针），通常称为失败节点
- 5）非终端节点的关键字个数与子数个数相同，–lionel，这是差异点，6、7是新增-lionel
- 6）倒数第二层节点包含了全部的关键字，节点内部有序且节点间按升序顺序链接
- 7）所有的非终端节点只作为索引部分，节点中仅含子树中的最大（或最小）关键字
- 红黑树
- 平衡二叉树（AVL树）插入和删除需要重新调整平衡，这里可能多达
O(logn)次旋转，与之左右子树高度差不超过1，换成了，左右子树高度差不超过2倍，3次旋转后能达到平衡。
- 红黑树（red-black tree）是满足以下性质的二叉搜索树：
- 1）每个节点是红色或黑色的
- 2）根节点是黑色的
- 3）每个叶子结点是黑色的
- 4）如果一个节点是红色的，则其孩子节点必为黑色
- 5）从任一节点到其后代叶子的路径上，均包含相同数目的黑节点
- 8、排序
- 9、查找
二、操作系统
- 1、绪论
- 2、操作系统运行环境
- 3、进程管理
- 3.1、进程与线程
- 3.2、进程同步与互斥 P是减1，V是加1
- 同步与互斥：
- 临界区与临界区资源：
- 重点：P、V操作，本质上还是得想一下，逻辑上怎么整，然后再定义相关信号量，要好好琢磨，lionel
- 3.3、死锁
- 死锁的4个必要条件：互斥、不可剥夺、请求和保持、循环等待
- 死锁预防：资源的静态分配（不可剥夺）、资源的有序分配（循环等待）
- 死锁避免：对资源申请进行动态检查，银行家算法
- 死锁检测：存在“循环等等”条件
- 死锁解除：剥夺资源、撤销进程
- 资源分配图
- 哲学家就餐
- 4、存储管理
- 这里的存储更多是内存，因为多道程序设计（数据共享、进程通信），有了分区的想法，但如何引入“虚存”，又是如何实现的呢？
- 5、文件管理
- 6、I/O设备管理
三、算法
四、系统系统结构
- 1、绪论
- 2、数据表示、寻址方式与指令系统
- 数据表示：指的是能由计算机硬件识别和引用的数据类型，表现在它有对这种类型的数据进行操作的指令和运算部件。
- 寻址方式：指令按什么方式寻找（或访问）到所需的操作数或信息的。
- 指令系统：是程序设计者看计算机的主要属性，是软、硬件的主要界面，它在很大程度上决定了计算机具有的基本功能。
- 3、存储、中断、总线与I/O系统
- 这里的存储，主要是并行主存系统
- 中断，OS里有
- 总线
- I/O系统，OS里有
- 4、存储体系
- 有点像OS里的存储（内存）管理，应该要多个cache
- 虚拟存储器的管理方式（段式、页式、段页式）
- 地址的映射与变换（全相联、直接、级相联）
- 5、标量处理机
- 6、向量处理机
- 7、多处理机
- 8、数据流计算机与归约机
- 9、中央处理器（这是计算机组成原理里的，5-8面试中不太会吧）
五、C++
六、设计模式
- 0、写在之前
- 在看DP之前，要对面向对象语言的一些特性要熟，主要是virtual
- 1、创建型
- 2、结构型：
- 3、行为型
履历
