zhangyugege/programmerinterview

程序员面试基础知识（小零碎）数据结构，算法，计网，设计模式，操作系统

programmerInterview

程序员面试基础知识（小零碎）数据结构，算法，计网，设计模式，操作系统

算法、数据结构

一：算法

1. 算法的几个特征是什么。

2. 算法复杂性的定义。大O、θ、Ω、小o分别表示的含义。

3. 递归算法的定义、递归算法的两要素。

4. 分治算法的**，经典的分治算法(全排列、二分搜索、归并排序、快速排序、线性时间选择、最接近点对问题)。

5. 动态规划算法解题框架，动态规划算法的两个要素是什么？备忘录方法是什么？

6. 经典的动态规划问题(矩阵连乘问题、最长公共子序列问题、0-1背包问题)。

7. 贪心算法的**，贪心算法的两个要素。

8. 经典的贪心问题(活动安排问题、背包问题、装载问题、哈夫曼编码、单源最短路径、最小生成树问题)。

9. 回溯法的**，回溯法中有哪两种典型的模型。

10. 经典的回溯算法(n后问题、0-1背包问题、旅行售货商问题)。

11. 分支限界法**，有哪两种分支限界法。

12. 经典的分支限界算法(0-1背包问题、旅行售货商问题)。

二：数据结构

1. 数据结构的定义。

2. 栈的两个应用：括号匹配和表达式的计算。是怎么应用的？表达式计算用的是哪种表达方式？有什么好处?

3. 字符串匹配算法：朴素的匹配算法、KMP算法。

4. 二叉树前序、中序、后序递归遍历算法。二叉树前序非递归遍历算法。

5. 堆，建堆算法，堆的插入和删除算法，堆排序。

6. 哈希。哈希函数的有哪些种？余数的取法？ 处理冲突的方法？ 闭散列方法有哪些？

7. 二叉搜索树的搜索、插入、删除。时间复杂度。

8. 二叉平衡树的插入结点的原理，有哪几种旋转方式？分别适用于哪种情况。分析二叉平衡树的时间复杂度。

9. 红黑树的定义，红黑树的性能分析和与二叉平衡树的比较。

10. 图有哪些储存表示。

11. 链表插入排序、链表归并排序。

12. 常见的有哪几种排序算法，试比较其时间复杂度，以及是否稳定，及各自使用的情形。

13. 常用分配排序有哪几种？ 基数排序的定义，分类及原理。

14. B树、B+树、Trie的概念及用途，添加删除结点的原理。

基础篇：操作系统、计算机网络、设计模式【山科大牛陈磊整理】

一：操作系统

1. 进程的有哪几种状态，状态转换图，及导致转换的事件。

2. 进程与线程的区别。

3. 进程通信的几种方式。

4. 线程同步几种方式。(一定要会写生产者、消费者问题，完全消化理解)

5. 线程的实现方式. (也就是用户线程与内核线程的区别)

6. 用户态和核心态的区别。

7. 用户栈和内核栈的区别。

8. 内存池、进程池、线程池。(c++程序员必须掌握)

9. 死锁的概念，导致死锁的原因.

10. 导致死锁的四个必要条件。

11. 处理死锁的四个方式。

12. 预防死锁的方法、避免死锁的方法。

13. 进程调度算法。

14. Windows内存管理的方式(块式、页式、段式、段页式).

15. 内存连续分配方式采用的几种算法及各自优劣。

16. 动态链接及静态链接.

17. 基本分页、请求分页储存管理方式。

18. 基本分段、请求分段储存管理方式。

19. 分段分页方式的比较各自优缺点。

20. 几种页面置换算法，会算所需换页数。(LRU用程序如何实现？)

21. 虚拟内存的定义及实现方式。

22. 操作系统的四个特性。

23. DMA。

24. Spooling。

25. 外存分配的几种方式，及各种优劣。

二：计算机网络

1. 电路交换与分组交换的区别？ 优劣对比。

2. OSI有哪几层，会画出来，知道主要几层的各自作用。

3. TCP/IP有哪几层，会画出来，知道所有层数的作用，会列举各层主要的协议名称。

4. 硬件(MAC)地址的概念及作用。

5. ARP协议的用途 及算法、在哪一层上会使用arp ？

6. CRC冗余校验算法，反码和检验算法。

7. 如何实现透明传输。

8. 知道各个层使用的是哪个数据交换设备。（交换机、路由器、网关）

9. 路由表的内容。

10. 分组转发算法。

11. IP报文的格式，格式的各个字段的含义要理解。

12. MTU的概念，啥叫路径MTU？ MTU发现机制，TraceRoute(了解)。

13. RIP协议的概念 及算法。

14. ICMP协议的主要功能。

15. 组播和多播的概念，IGMP的用途。

16. Ping协议的实现原理，ping 命令格式。

17. 子网划分的概念，子网掩码。

18. IP地址的分类，如何划分的，及会计算各类地址支持的主机数。

19. DNS的概念，用途，DNS查询的实现算法。

20. TCP与UDP的概念，相互的区别及优劣。

21. UDP报文的格式，字段的意义。

22. TCP 报文的格式，字段的意义。

23. TCP通过哪些措施，保证传输可靠？

24. 三次握手，四次断开过程。

25. TIME_WAIT状态的概念及意义。

26. 滑动窗口协议 与 停止等待协议的区别。

27. TCP的流量控制和拥塞控制实现原理(会画拥塞控制的典型图)。

28. TCP的快速重传与快速恢复算法。

29. TFTP 与 FTP的区别。

30. 阻塞方式和非阻塞方式，阻塞connect与非阻塞connect。(比较难，有兴趣可以了解)

31. HTTP基本格式。（java程序员必须掌握）

三：设计模式

1. 各种常用模式的用途，使用方法。

2. 单例模式的双重检查实现。

3. MVC模式