这个列表用来检查基础知识挺好的，只是感到压力很大！
来源：http://blog.renren.com/blog/232287273/799725113
最近有熟人找工作。贴出来一份本科生应该会的知识点总结吧。找工作的同学也可以帮我加一些内容，可能会有遗漏。同时也算是本科生的一个总结吧，在大学四年应该要学点什么东西回家吧。
粗体是比较重要，但是经常被人遗漏的一些知识点。斜体是有点偏的东西，有点难，会则好，不会有兴趣的可以看看。没兴趣没必要看了。
暂时这些，想起来再加。
基础知识
CPU：主频，Cache
内存：内存到CPU有较大latency
磁盘：机械装置。磁盘结构，工作原理。磁盘操作：read/write/seek三个操作。扇区大小：512Bytes，新硬盘已经有4K扇区的了。
磁盘中有NVRAM做Cache
知道什么是RAID，RAID的几种配置。
数据结构
每个数据结构都应该知道：为什么要有这个数据结构，能做什么不能做什么，空间复杂度和每种操作的时间复杂度。简单的数据结构要很熟练的写出代码或伪代码。
数组
链表（单向，双向/环形）
二项堆。要求要会用数组实现。
哈希表
Bloom Filter（经常被人忽略的一个重要的东西）
并查集 （Union Find Set）
字典树（Trie/Prefix Tree）
二叉搜索树（最普通的那个）
AVL Tree
Red Black Tree（不要求会写……太复杂了，知道和AVL Tree的区别就好）
B-Tree B+-Tree （最好知道两者的区别，尤其要求要会写，知道为什么B-Tree会比AVL/RBTree快）
Skew/Leftist Heap(用来做merge的heap）
Splay
算法
二分搜索（一定要会！别小看了，代码不是很好写）
各种排序：
冒泡排序（也还是看一看吧……）
quick sort
merge sort（数据量远远大于内存容量的时候排序最佳）
heap sort
bucket sort
radix sort （异常重要。Google笔试之一：N个数，每个都是[0, N^2)，O(N)时间内排序）
搜索（深度优先，广度优先。要求熟练）
动态规划（Dynamic Programming）（最优子结构来加速）Bellman-Ford的那个定理最好能弄明白
Dijkstra/Floyd/Bellman-Ford最短路径算法
网络流（好吧……至今我反正是没在项目中用到过……但是应该还是会用的）
语言
这块东西都非常重要！除了斜体以外都重视一下。
C的一些知识：
#include是预处理，是把头文件拷贝到当前行。注意include hell，注意头文件一定要#ifndef #define #endif
static意义。static还可以保证symbol不被export。可以避免链接时重名。（因为C没有namespace）
内存：stack和heap。Heap在Programming Language里面会说。C里面就realloc/malloc/free就够了，也可以了解一下calloc。
Near和far已经不再使用了。（这货从来没在unix上存在过吧？）
内嵌汇编（反正我是不会，随查随用）
void foo()和void foo(void)在函数声明时候是不同的（这个和C++不一样）
weak symbol（这个我也没搞懂）
C的symbol table不会做像C++一样做Name Mangling 。可以直接根据函数名称来用里面的函数（dlopen/LoadLibaray）
Sequence Point是什么。要知道
volatile的语义（一会还会在体系结构里面出现）
C++的一些知识：
别告诉面试官你精通C++
C++是多根继承
知道啥是virtual function，知道有virtual table的存在。
Constructor的时候不要virtual function（要知道为什么）
Destructor的时候不要throw（要知道为什么）
Destructor要virtual，如果你打算别人继承你的话。
New/free就是malloc加constructor和destructor
有个叫placement new的语法，让你直接调用constructor
Name Hiding （有点恶心的东西）
C++会做name mangling，把函数重命名。
除了public继承，还有private继承。（我不会T.T）
有virtual继承，为了解决多继承对象冗余的。太恶心，一般人不会用。
template是个过于灵活的东西，它有图灵完整性（这个知道一下即可），也就是说，任何编程能解决的问题，C++可以在编译期搞定。（假设没有编译器自己的限制）
template不能把成员方法的实现写在.cpp文件里。（除非编译器支持export关键字，但是目前没有支持的编译器）
最简单的container style template要会用要会写。STL那些container要会用！Std::vector, std::list, std::map…
Design Pattern和Modern Design Pattern（重口）那些东西会一点就行。
Singleton（会单线程的即可，多线程的略重口）
知道啥叫Wrapper/Adapter，这个很简单。就是用另外一个借口包装一下而已么。
知道Factory这个Pattern
Policy Based Design。Modern那书里面口味最轻的。
了解一下Prototype, Bridge什么的就够了。用的不多。
编译期算出来fibonacci数列的第N项……编译期输出素数序列……（呃……口味重一些）
知道啥是boost，最好会用boost::thread，boost::function的库。
Java一些知识：
Java相对来说和谐很多了。没啥好说的。
Java是单根继承。没多继承。可以implements几个interface。但是interface明显是纯虚的。
Java有个东西叫Reflection的，需要知道，需要会用。
Java的很多东西都要用到上面提到的design pattern，但是其实这东西就会那几个常见的就可以了。
Java可以写GUI程序。有两大比较时髦的库，一个是swing，一个是SWT。最好会一个。
Java可以写Web程序，有Java Servlet标准和JDBC标准。熟悉一下即可。
很多库，会也行，不会也行。问题不大。什么hibernate, JPA. Spring/Guice(我喜欢用), Struts等……
呃，不会写web程序但是需要知道tomcat是啥吧……类似的还有jetty和glassfish等。
操作系统
进程，什么是进程。（呜，具体定义不必太具体）
什么是用户态什么是内核态。为什么会有两个态。（为了安全）
进程通过系统调用让内核做一些事情。最好知道系统调用发生了什么。系统调用是CPU辅助的，不是普通的系统调用。
知道什么是虚拟内存。知道内存是分页的。
虚拟内存怎么实现的：需要知道有个东西叫做页表。Page Table
知道CPU对虚拟内存要有支持。（具体：MMU，soft tlb (MIPS)/ hard tlb (x86)。x86下是CR3寄存器，MIPS下是写入和读取tlb entry）
知道x86下，虚拟内存地址空间是4G，Linux下内核态1G用户态3G。Windows一般是2G/2G。所以linux 32位下，分配2.7-2.8G内存以后基本就没法再分配了。Windows下这个限制会更大。（所以才要用64位系统嘛……-w-）
需要知道世界上有个叫做mmap/CreateMapping的东西!（为啥大家都不知道？）
什么是线程。线程模型和进程的区别（共享heap……当然stack不可能是共享的……）
什么是Fiber，为什么Fiber不能直接用来实现线程。
知道什么是mutex。知道race condition。知道这货多恶心多难写。（写了10000行多线程代码做毕设的泪流满面……）
知道mutex乱加后果是很严重的。（deadlock。Thread1: lock(A), lock(B) Thread2: lock(B), lock(A)）
知道怎么用mutex(lock/trylock/unlock)实现read/write lock。
知道有个东西叫做condition variable。知道这货的来源是一个叫做monitor的模型。
知道pthread怎么用……pthread_create/pthread_mutex_lock/pthread_cond_wait。这个一定要会，花不了多长时间的。
知道fork()，知道vfork()。知道Linux上fork的实现很快。NT上CreateProcess很慢。
知道什么是时间片，什么叫分时调度。几种常见的调度……Round Robin什么的
知道什么叫swap。进程中的虚拟内存用的太多了，物理内存没那么大。
知道虚拟内存可以被swap到disk。
有个东西叫做I/O cache，读写磁盘的时候会用内存存住一些来加速访问。
I/O cache的内存有限，所以要page replacement algorithm。虚拟内存中哪页内存到disk也是这个问题。
常见的page replacement algorithm有LRU等（知道LIRS，ARC会很管用哦……)
文件系统。这个要会用！
Open/read/write/seek/close/opendir/readdir/closedir/stat等等……都要会
最好也要会pread/pwrite。多线程的读写文件的时候有用。
知道什么是data什么是meta data。（文件内容是data，非文件内容是meta data）
知道FAT文件系统，知道它为啥烂。了解一些时髦的文件系统，如果ext3/xfs。了解一下就够了，没必要都懂。
网络
主要Application Layer用的比较多。当然啦，我是说软件开发的职位，网络工程师那就明显不同了。
需要了解HTTP。现在随便一个地方就做网站，HTTP协议是至少要知道的。知道什么是GET/POST，知道有cookie这个东西。
知道SSL是什么。
写过网络程序……知道什么bind()/listen()/accept()/connect()，这些要会用。（参数记不清没事）
知道DHCP
会换DNS是什么。知道ssh是什么。（潜台词……会翻墙）
知道有个traceroute可以用，知道有个wireshark可以用。
知道TCP和UDP的区别
简单知道TCP的怎么保证数据完整性的。知道TCP怎么握手的（SYN/SYN_ACK/ACK)，知道怎么断开的(FIN/FIN_ACK)，知道主动断开会出现TCP_TIME_WAIT这个状态。（这个状态在Linux下会持续一分钟……）
知道TCP的几种congestion control（太难了……不会）
Programming Language
好吧，编译器前端是我的软肋。但是我个人认为它比较理论，不太实用。（但是似乎国内课本一直比较强调这些？）反正我用到的编译器的parser都是手写的，不过如果你真的不幸找到了一份编译器前端的工作……如MS,Apple,IBM，反正你的日子也不好过:)。所以呢……
只要知道FSM/LL/LALR就够了。状态优化，AST生成和优化，flex,bison我觉得可以统统无视掉了。就从IR产生后了解就好了。
编译器几种常见的优化，要知道。比如用寄存器，而不是每次都访问内存，（顺便，扔掉你的8086汇编知识。x86和x86_64有好多通用寄存器的）比如将定长循环展开，比如inline某些短的函数。
知道什么叫强类型和弱类型。以及类型检查，类型推导(type inference)
然后就是多而复杂的runtime知识。
知道什么叫libc，知道malloc的一些实现细节：（百度面试题）小的内存chunk从Heap分配，大内存走mmap。知道over_commit_ratio
知道malloc是线程安全的，多线程调用malloc的时候不用上锁。知道malloc在有些特殊情况下可以很慢，是个潜在的性能瓶颈。知道如何优化。（用给力的malloc实现，如google的tcmalloc，facebook/bsd的jemalloc；fixed size object可以自己手动写内存池）
知道jvm是什么东西……（就是那个叫做java的程序……= =）
知道靠谱的jvm在运行.class文件的时候是有可能编译成本地代码运行的（我是说x86机器代码），这个功能叫做JIT(Just In Time Compile)。所以面试的时候别犯傻的说java慢是因为java解析执行！
Java有GC。Sun JVM里面有很多GC算法。
GC算法的本质要知道，就是对象互相引用形成一个图，然后我们知道当前要用的一些对象（比如在stack上的，比如JVM本身持有的root object），然后求子图的连通性。和这些要用对象连通的对象就是有用的对象，剩下的就是垃圾。
常见的算法要知道：mark and swap, mark and copy, mark and compact，知道什么是generational GC。
Sun JVM里面的一些算法如果知道更好。
数据库
数据库是最复杂的系统之一了。所以我也没打算自己把它弄懂-_-
SQL应该会吧，最基本的不能忘。高级的呢……用的时候再查吧。
transaction的性质-ACID
知道为了保证transaction的性质有数据库各个层次的锁。row lock, table lock什么的
各种方向的锁，S/X/U至少要知道，所谓的compability matrix要看得懂。
transaction具体实现要知道一些。了解即可。
知道journal/shadow paging这两个approach
知道journal具体怎么工作的。
undo/redo log。（顺便提一下file system也有这个东西，但是很多file system只有redo log，没有undo，因为没必要保证高consistency，也必要保证很高的scalability）
最后，知道ARIES这个名字。算法具体不用了解。
传统的DB现在其实都不行了，DBMS这方面的research都表明，现在硬件快起来以后，传统数据库的很多资源很浪费。现在有了各种NOSQL（其实是no relation）数据库。
总之，最重要的是transaction，别老看SQL什么的。
体系结构
体系结构对程序员来说是偏理论的知识了，但是需要尽可能深入的了解一些东西，理论扎实写程序才快嘛。这里我列出一些本科学过的有点用途的理论知识，当然随着深入，理论知识会越来越有用，当然也就完全不局限这点东西了。
知道CPU是多周期的，流水线作业的。
知道对CPU来说……Cache大是很王道的……知道存在instruction cache和data cache
知道CPU有寄存器……知道有特殊寄存器和通用寄存器……（MIPS也存在特殊寄存器的！当然要用特殊指令写入，读取……这块内容被课本无情的阉割掉了）
知道世界上存在RISC CPU………………（-_-|||）
知道有x86有浮点寄存器。（某面试题……32位下void pass_a_double(double* d)和void pass_a_double(double d)哪个快……后者，虽然多拷贝了4个字节，但是传入的时候会优化成浮点寄存器）
volatile的语义。可变的，所以每次读写都会直接写入内存（或者cache），编译器不允许做任何优化到寄存器的优化。
知道乱序执行，知道CPU有多线程技术来回切换/多套原件。知道CPU有多核……（喂…………）
知道SIMD是什么概念。会用最好。（我不会）
知道CPU里面内存访问是有Cache的，这也是为什么BTree会比rbtree/avltree快！同理，很多数据结构都要尽量”成块”，这样减少了CPU的cache miss。
知道有branch prediction就行。
知道CPU对操作系统提供了很多支持……比如系统调用，虚拟内存。（如果能知道是怎么提供的更好）
知道x86提供了虚拟化支持，对操作系统或者虚拟机有直接支持。跑虚拟机会快一些。（要是你能娓娓道来怎么支持的………………直接找intel让他们给你发offer吧，或者去世界TOP10的学校读PHD没问题了………………-_-|||）
AI
AI的面试知识也不少，但是我不做那块东西。对于码农知道一些也无坏处吧，我认识的一个朋友他现在就要对AI有点了解的码农……
知道A*是什么算法，知道heuristic search的理论要求（就那个不等式就行……）
逻辑推理？我也不知道有没有用哎……DPLL什么的似乎还用过一次？@.@
first order logic的一些科普知识……-w-主要是防止面试官问你悖论相关的问题。哦耶。
基本的概率要会计算吧！条件概率，bayes公式不能忘记！
会点随机更好，知道markov chain是啥就行……
知道HMM，Viterbi算法（其实就是DP……）。（好吧HMM我也忘得差不多了）
知道bayesian network，知道mcmc。（我从来没用上过……不码这方面的东西的说）
总结
四年过去了，总要学点东西吧……很多人都说计算机四年什么都没学，或者学的东西从来没有用上过。我觉得应该还是他们不知道哪些重要哪些不重要吧。我们学校的教学首先内容落后，其次重点都放在理论上，很多实际的东西大家没有接触过，不知道应该会哪些知识。我作为一个小小的码农，就说说我四年学到的这些基础知识，这些基础知识都是码代码的时候用过的，但愿对你有用。
