计算机知识补充（算法、数据结构、计算机网络）

算法

一般情况下，算法的基本操作重复执行的次数是模块 n 的某一个函数 f(n)，因此，算法的时间复杂度记做：T(n)=O(f(n))。
一个程序的空间复杂度是指运行完一个程序所需内存的大小。一个算法所需的存储空间用 f(n) 表示：S(n)=O(f(n))。其中 n 为问题的规模，S(n)表示空间复杂度。

1.  排序
      冒泡排序
      简单选择排序
      直接插入排序
      折半插入排序
      希尔排序
      快速排序
      归并排序
      堆排序
      基数排序
      堆排序
      计数排序
各种排序的时间复杂度，空间复杂度，是否稳定，时间复杂度是否与初始序列有关?
2.  查找：二分查找，lower_bound, upper_bound
3. 分治与递归：逆序对数，大数相加，大数相乘
4.贪婪算法
5. 动态规划:背包问题，找零钱问题，最长公共子序列（LCS）
6. BFS，DFS,最短路径（Dijkstra算法，Floyd算法）
7. 字符串匹配算法：KMP算法，BM算法，Sunday算法
8. 补充：Top-K算法，Bitmap算法, Bloom Filter算法，一致性哈希算法，8数码问题（A*算法,B*算法，IDA*算法）

数据结构

线性表：数组，栈（先进后出，表末端出入或者删除），队列（先进后出），链表特点以及应用场景。
数组：老鼠走迷宫问题，稀疏矩阵压缩
链表：单链表逆序，单链表去重，单链表删除结点(仅给出删除结点),两个链表交叉求交叉点，判断单链表是否有环以及确定环的入口结点。
二叉树：二叉树的遍历(递归，非递归），层次遍历；
二叉树求深度，宽度；二叉树镜像；创建二叉树；
哈夫曼树，哈夫曼编码。BST, AVL(AVL单侧旋转，双侧旋转),红黑树(红黑树的特征)。
图：邻接矩阵，邻接表，拓扑排序，最小生成树，trie树
补充：跳跃表，hashtable

# 操作系统
操作系统加载流程？
进程与线程的区别和联系？
进程的常见状态？以及各种状态之间的转换条件？
静态链接与动态链接的优缺点？
死锁？死锁产生的条件？预防、避免死锁的方法？
进程间通信的方式？各种方式的区别以及应用场景？
经典同步问题解法：生产者与消费者问题，哲学家进餐问题，读者写者问题。
线程同步的方式？各种方式的区别？
虚拟内存？使用虚拟内存的优点？
Linux下进程的内存布局？
页面置换算法？LRU Cache算法？
Linux IO多路复用的机制：select,poll,epoll。三种复用机制的区别与联系？

计算机网络

OSI 7层网络模型中各层的名称及其作用？
TCP/IP 4层网络模型名称及其作用？
OSI 7层网络中各层的常见协议以及协议作用？
OSI网络模型中工作在各个层次的物理设备以及其作用？
IP层功能？如何用int型变量保存一个IPv4地址？
TCP协议（重点）：TCP3次握手，4次挥手详细过程。TCP滑动窗口，拥塞控制，流量控制原理。TCP 建立、断开连接过程中13中状态以及各种状态之间的转换条件？ TCP粘包问题？如何解决？
UDP协议：头信息？使用场景？如何使用UDP建立可靠连接？
http协议：各个版本的区别？http请求头，响应头常用属性？常用状态码及其含义？
socket编程：服务端，客户端建立TCP连接调用那些函数？分别对应什么状态？
Linux 常用网络命令的原理：ping, traceroute
浏览器中点击一个超链接到显示对应页面的全过程？
DNS的作用？什么时候使用TCP?什么时候使用UDP?

# 数据库
MySQL中MyISAM与InnoDB的区别？
MySQL中索引内部实现是什么？MyISAM和InnoDB中使用的B+树有什么区别？B树和B+树的区别？
SQL常用查询语句的使用？各种连接（外连接，内连接，全连接）的区别？
数据库范式？1,2,3，BCNF,4, 5
事务？事务的特点？事务的四个隔离级别，各个级别解决的问题？
索引？适合创建索引的条件？不适合创建索引的条件？
索引优化策略？五个优化级别
存储过程？
触发器？
日志

最后编辑于：2020.07.29 16:59:51