需要掌握的知识汇总
Last Update: 2007-11-7
前面是各种专业知识及里面所需要掌握的各种重点，后面是一些常用的技术点。 说明：所有的题目分为以下几个等级，等级只代表了题目对笔试面试来说的重要程度，并不代表其难易程度。 ☆ 不常见的问题，可以不掌握；如果简历上写了相关的内容，还是要复习一下。 ☆☆ 通常情况下不会考到；如果时间充裕的话还是应该准备一下。 ☆☆☆ 属于重点内容，必须要掌握。 ☆☆☆☆ 简直是经典问题，几乎必考。
一．数据结构
1. 程序运行中堆和栈的区别。☆☆☆☆
栈，就是那些由编译器在需要的时候分配，在不需要的时候自动清除的变量的存储区。里面的变量通常是局部变量、函数参数等。
堆，就是那些由new分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个new就要对应一个delete。如果程序员没有释放掉，那么在程序结束后，操作系统会自动回收。
更具体的见后面C++部分。 2. 排序二叉树的增、删、查等基本操作。☆☆
先把二叉树的基本思路和大致操作方法看一下书，然后敲敲代码练习一下。 这里我写了一个二叉树的增、查、删功能，写得不是很简洁。
#include 当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。 存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。为了区分一个结点的指针是指向其儿子的指针，还是指向其前驱或后继结点的线索，可在每个结点中增加两个线索标志。 线索二叉树是一种逻辑结构。 4. 什么是哈夫曼编码。☆☆☆ 哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称\"熵编码法\"），用于数据的无损耗压缩。 5. KMP算法的思路。☆ 这个看数据结构的课本吧，记住next与nextval两个数组的计算方式。 记住下面这个例子： pos: 1 2 3 4 5 6 7 value: a b c a b d b next: 0 1 1 1 2 3 1 求next数组的程序属于经典，如果要去百度、微软、谷歌则必须熟记： void calculateNext(const char * str) { int length = strlen(str); int * next = new int[length +1]; int j = 1, k = 0; next[1] = 0; while (j < length) { if( k==0 || str[j-1] == str[k-1]) { j++; k++; next[j] = k; } else { k = next[k]; } } } 6. 二叉树的非递归遍历方法，只掌握前、中序遍历即可，后序遍历较为复杂。☆ 以下是例子代码。 void BinaryTree::PreTravel(PTreeNode node) { stack 7. 二叉树与森林的相互转换。☆☆ 树（树林）转换成二叉树时结果是唯一的。其转换可以递归的描述如下：若树（树林）为空，则二叉树为空；否则，树（树林）中第一棵树的根是二叉树的根，第一棵树除去根结点后的子树林是二叉树的左子树，树林中除去第一棵树后的树林形成二叉树的右子树。 二叉树转换成树（树林）时结果也是唯一的。 其转换可以递归的描述，若二叉树为空，则树（树林）为空；否则，二叉树的根是树（树林）中第一棵树的根，二叉树的左子树构成树（树林）中第一棵树除去根结点后的子树林，二叉树的右子树构成树林中除去第一棵树后的树林。 8. 根据二叉树的前序、中序遍历，计算树的后序遍历。☆☆☆ 思路：根据前两种遍历，分析出树的结构，然后写出后序遍历。如果题目只给出前序和后序遍历，是无法确定中序遍历的。 9. 图有哪些存储方式。☆☆☆ 数组表示法、邻接表、十字链表、邻接多重表 这是几种最常见的图的存储表示。 10. 计算图的最小生成树的两种算法。☆☆ Prim和Kruskal，记住大体思路即可。 11. 什么是图的拓扑排序。☆☆☆ 对一个有向无回路图进行拓扑排序。有向无回路图又称为dag。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G包含(u,v)，则在序列中u出现在v之前（如果图是有回路的就不可能存在这样的线性序列)。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。 12. 关键路径的求法。☆☆ 对于一个项目而言，只有项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径（Critical Path），组成关键路径的活动称为关键活动。其通常做法是： 1） 将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列； 2） 用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图； 3） 用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差； 4） 找出所有时差为零的活动所组成的路线，即为关键路径； 5） 识别出准关键路径，为网络优化提供约束条件； 13. 图中两点的最短路径的两种算法的思路，各自的复杂度。☆☆☆ Dijkstra（迪杰斯特拉）和Floyd（弗洛伊德），分别为O(n^2)和O(n^3)。 14. 内存分配的三种策略，各自的优缺点。☆☆☆ 1）首次拟合法 2）最佳拟合法 3）最差拟合法 优缺点随便讲讲就好了（各有不同的长处，适用于不同的场合）。 15. 各种排序算法（选择排序、插入排序、冒泡排序、快速排序、二叉排序、希尔Shell排 序、堆排序、归并排序、基数排序）的时间、空间复杂度，以及是否稳定。☆☆☆☆ 算法 简单排序 快速排序 堆排序 归并排序 基数排序 平均时间 O(n^2) O(nlogn) O(nlogn) O(nlogn) O(d(n+rd最坏情况 O(n^2) O(n^2) O(nlogn) O(nlogn) O(d(n+rd空间 O(1) O(longn) O(1) O(n) O(rd) 是否稳定 是 否 否 否 是 )) )) 16. 哈希散列的原理，以及冲突解决的几种策略。☆☆☆ 哈希的构造方法：直接地址法、数字分析法、平方取中法、折叠法、除留余数法。 冲突的处理方法：开放地址法、再哈希法、链式地址法、 17. 多路平衡归并排序的实现，败者树的基本原理。☆☆ 败者树是多路平衡归并的实现方式，具体的内容了解即可。 18. 置换-选择排序的原理。☆☆ 是多路平衡归并排序的一种改进方法，也是在所有需要掌握的知识中唯一的外部排序方法，在进行大数据量排序时需要使用。 19. 最佳归并树的生成，即哈夫曼树。☆ 与哈夫曼编码的思路一致，N路平衡归并时稍有扩展。 二．计算机网络 20. OSI七层模型的结构。TCP/IP协议的结构。☆☆☆☆ OSI模型：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层。 TCP/IP模型：物理链路层、网络层、传输层、应用层。 21. 数据链路层的作用，以及编码成帧的几种方式。☆☆ 作用：将上层的所有包结构的数据拆开，作为一个网络比特流提交到物理层进行传输。 成帧的方式：1）字符计数法（已经不再使用）、2）含字节填充的分界符法、3）含比特填充的分界标识法、4）物理层编码违例法（需要物理层的支持） 22. 滑动窗口协议的大致原理。☆☆ 注意此算法在数据链路层和传输层均出现了，大致思路了解即可。 23. 网络层的作用。☆☆☆ 网络层的两大功能：路由选择、拥塞控制。（选择题中很可能会考） 24. IP地址的分类方法，子网掩码的概念，计算一个子网内的机器数。☆☆ 通常是计算题，知道通过子网掩码转换IP地址的方法即可。 25. 虚电路子网与数据报子网的区别。☆☆☆ 虚电路常用于其服务方式为面向连接的子网中。虚电路的想法是避免对发送的每一个分组都必须进行路由选择。取而代之的方法是，当建立连接时，从源端机器到目的端机器的路由就作为连接建立的一部分加以保存，此路由用于传送连接上的所有数据，这与电话系统的工作原理完全一样。当释放连接时，虚电路也随之撤销。 与之相反， 对于数据报通信子网， 即使其服务方式是面向连接的，也不预先选择路由。发出的每个分组所选择的路由于其前面发出的分组，后续的分组可以走不同的路由。虽然数据报通信子网必须做更多的工作，但它比虚电路式通信子网更健壮，更容易处理传送失败和拥塞。 26. 传输层的作用。☆☆☆ 传输层是OSI中最重要, 最关键的一层,是唯一负责总体的数据传输和数据控制的一层.传输层提供端到端的交换数据的机制.传输层对会话层等高三层提供可靠的传输服务,对网络层提供可靠的目的地站点信息。 传输层主要负责连接的建立、保持与释放。 27. TCP与UDP协议的各自优缺点。☆☆☆☆ TCP 缺点： 非常复杂；它必须提供可靠性（确认），数据流（握手），流控制（窗口），中断数据流等功能。所有这些都增加了TCP的复杂性而且减少了协议的功能。而且开销比较大 优点：TCP 是十分成熟的协议，它可以保证点对点传输数据的可靠性，而且是按照顺序，也不会有重复。另外。TCP的特点之一是提供体积可变的滑动窗口机制，支持端到端的流量控制 UDP 缺点：当使用UDP协议传输信息流时，用户应用程序必须负责解决数据报排序，差错确认等问题。 优点：在少量数据的传输时，使用UDP协议传输信息流，可以减少TCP连接的过程，提高工作效率。 28. 交换机和路由器分别的实现原理是什么？分别在哪个层次上面实现的？☆☆☆ 一般意义上说交换机是工作在数据链路层。但随着科技的发展，现在有了三层交换机，三层交换机已经扩展到了网络层。也就是说：它等于“数据链路层 + 部分网络层”。交换机中传的是帧。通过存储转发来实现的。 路由器是工作在网络层。路由器中传的是IP数据报。主要是选址和路由。 三．数据库系统 29. E-R图的一些基本画法。☆ E-R模型中的三个主要概念：实体集、联系集和属性。 实体集：具有相同类型及共享相同性质的实体集合。而相应的实体集中每一个元素就是实体。这个概念对应到面向对象中就是class-object概念， 而我们野可以想象，实体集还会有继承的概念（虽然我暂时还无法想象在数据库中如何实现实体集的继承）。 联系集：联系是指实体之间的相互关联，而同类型的关系组成的集合就是关系集。在通常的数据库系统中，联系可以表现为两种，一种是联系表，而另一种就可能是一个简单的sql语句。 属性，值和域：实体是通过一组属性来表示的，属性就是每个成员所具有的描述性性质，而每个实体的所有属性都有一个值， 每一个属性的取值范围就称作该属性的域。 至于画法，看书了解一下即可。 30. 简述DBMS的功能。☆☆ 大致可以分为查询处理器和存储管理器两层。 查询处理器中主要包括DDL解释器、DML编译器；存储管理器主要包括权限及完整性管理器、事务管理器、文件管理器等。 31. SQL语言分为DDL和DML两种，简述二者的含义。☆☆ DML(Data Manipulation Language)数据操纵语言命令使用户能够查询数据库以及操作已有数据库中的数据。如insert, delete, update, select等都是DML. DDL语句用语定义和管理数据库中的对象，如create, alter和drop. DDL操作是隐性提交的，不能rollback。 32. 超码、候选码、主码这几个概念的区别。☆☆ 超码：在实体集中任何可以唯一标识实体的属性集合都叫做超码，所以，根据这个定义，任何超码的超集也都是超码。 候选码：任意真子集都不能成为超码的超码叫做候选码。 主码：数据库设计者选中的候选码。 33. 视图与索引的区别。☆☆☆ 视图不是实际存在的，是虚拟表；索引是在物理上存在的。 34. 索引有哪些类型？☆☆☆ 按存储结构：有序索引 —— B+树索引和线性索引 散列索引 —— 静态索引和动态索引 按存储位臵：聚集索引 非聚集索引 35. 数据库数据的完整性有哪三种类型？其中参照完整性主要表现在哪些地方？☆☆ 数据库完整性（Database Integrity）是指数据库中数据的正确性和相容性。数据库完整性由各种各样的完整性约束来保证，因此可以说数据库完整性设计就是数据库完整性约束的设计。数据库完整性约束可以通过DBMS或应用程序来实现，基于DBMS的完整性约束作为模式的一部分存入数据库中。 三种类型： 1、实体完整性。实体完整性是通过主码（PRIMARY KEY）的定义来实现的。 2、参照完整性（或引用完整性）。参照完整性基于外键与主键之间或外键与唯一键之间的关系。 3、用户自定义完整性。使用非空约束、对属性的CHECK约束、对元组的CHECK约束、触发器等来实现。 36. 写一些较为复杂的SQL查询语句（通常是面试数据库类型的工作时才需要掌握）☆ 对SQL熟悉即可，需要了解的关键字：count、sum、having、exists、group by、outter join、first N、distinct等。 37. 什么是数据平凡依赖。☆ 就是指自然能够推出的依赖关系。例如 AB -> A 在任何情况下都成立。 38. 第三范式与BCNF范式的各自概念，有哪些区别？能否举出一些实际的例子。☆☆ 如果F+中的所有形如α->β的函数依赖（其中α∈R且β∈R）都满足至少以下条件之一： α->β是平凡依赖 α是R的一个超码 β-α中的每个属性A都包含在R的一个候选码中 则函数依赖集F属于第三范式。 如果F+中的所有形如α->β的函数依赖（其中α∈R且β∈R）都满足至少以下条件之一： α->β是平凡依赖 α是R的一个超码 则函数依赖集F属于BCNF范式。 BCNF给人的感觉，就是最最基本的每个表使用主键来确认一条记录；第三范式给人的感觉，就是非主键的部分已经不存在冗余，但在主键的内部仍有冗余信息（比如使用两个字段做主键，但其实一个字段就已经够了）。 39. 事务的概念是什么，包含了哪四个特性。☆☆☆☆ 事务就是一个单元的工作，包括一系列的操作这些操作要么全部成功，要么全部失败。事务确保多个数据的修改作为一个单元来处理。 基本特性：原子性、一致性、隔离性、持久性。（选择题中极有可能出现） 40. 冲突可串行化、视图可串行化的区别。☆☆☆ 冲突等价：如果调度S可以经过一系列非冲突指令交换转换成S’，我们称S和S’是冲突等价的。 冲突可串行化：当一个调度S与一个串行调度冲突等价时，则称该调度S是冲突可串行化的。 视图可串行化：考虑关于某个事务集的两个调度S，S'，若调度S，S'满足以下条件，则称它们是视图等价的： 对于每个数据项Q ，若事务Ti在调度S中读取了Q的初始值，那么Ti在调度 S'中也必须读取Q的初始值 对于每个数据项Q ，若事务Ti在调度S中执行了read(Q)，并且读取的值是由 Tj产生的，那么Ti在调度S'中读取的Q值也必须是由Tj产生的 对于每个数据项Q ，若在调度S中有事务执行了最后的write(Q)，则在调度S' 中该事务也必须执行最后的write(Q) 当一个调度S与一个串行调度视图等价时，则称该调度S是冲突可串行化的。 41. 基于锁的并发控制协议的实现原理。☆☆☆ 了解一下共享/互斥锁协议、两阶段锁协议。 两阶段锁协议可以保证冲突可串行化，但不能保证无死锁。 42. 基于时间戳的并发控制协议的实现原理。☆☆ 书上，了解即可。 时间戳排序协议可以保证无死锁，保证冲突可串行化。 存在满足两阶段锁协议却不满足时间戳协议的调度。 43. 基于日志的数据恢复方式有哪几种方式。☆☆☆ 延迟数据库修改、立即更新、检查点。 四．操作系统 44. 操作系统的内核大致包含哪几个部分。☆☆ 进程控制、内存管理、文件系统、外围接口 45. 画出进程的状态转换图。（三状态图、 五状态图）☆☆☆☆ 把状态转换图记牢。尤其要记清状态间的转换关系。（见右图） 46. 线程与进程的区别。☆☆☆☆ 进程是具有一定功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个单位. 线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源. 一个线程可以创建和撤销另一个线程;同一个进程中的多个线程之间可以并发执行 47. 什么是信号量。☆☆☆ 信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。 一般来说，信号量S≥0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S≤0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进 程，使之运行下去。 48. 读者-写者问题的大致代码思路。☆ 理解即可。 49. 什么是管程。☆ 管程是管理进程间同步的机制，它保证进程互斥的访问共享变量，并且提供了一个方便的阻塞和唤醒进程的机构。 50. UNIX下，进程间通信有哪几种方式。☆☆☆☆ 管道、FIFO（也叫系统管道）、消息队列、信号量、共享内存。 51. 几种常见的进程调度算法的思路。☆☆☆ 先进先出调度算法（抢占式，非抢占式）、 优先级调度算法、 时间片轮转算法、 最短进程优先调度算法、 最短剩余时间优先调度算法。 52. 造成死锁的必要条件有哪些。☆☆☆☆ 产生死锁的四个必要条件： （1） 互斥条件：一个资源每次只能被一个进程使用。 （2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。 （3） 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。 （4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。 这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。 53. 使用银行家算法判断每个状态是否会死锁。☆ 银行家算法是一种最有代表性的避免死锁的算法。 要解释银行家算法，必须先解释操作系统安全状态和不安全状态。 安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。 不安全状态:不存在一个安全序列。不安全状态一定导致死锁。 那么什么是安全序列呢？ 安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。 银行家算法： 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进 程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。 54. 内存分配策略有哪几种？各有哪些优缺点。（这个问题在数据结构中也出现过）☆☆☆ 1）首次拟合法 2）最佳拟合法 3）最差拟合法 55. 内存分配时，页面置换算法有哪几种？☆☆ 1）最佳臵换法（不可能实现） 2）最近未使用臵换算法 3）先进先出臵换算法 4）最少使用臵换算法 56. 虚拟内存管理中，快表和页表如何使用。☆ 页表和快表的数据项的结构是一样的,都由一个虚页号,一个实页和一些其它的标志组成.页表和快表的不同点在于大小不同,快表比页表小得多,里面放的是最常用的页表项,可以看作是页表的高速缓冲区.当快表不存在时就用页表进行地址转换,否则使用快表. 57. 常用的文件逻辑结构有哪些？☆ 顺序文件、索引顺序文件、索引文件、哈希文件。 58. 文件按照用途可以分为哪几类？☆ 系统文件、用户文件、库文件。 59. UNIX中，文件包括哪几种类型？☆ 普通文件、目录文件、特殊文件（外围设备等）、管道文件。 五．编译原理 60. 编译器的两种实现方法。☆☆ 编译和解释。目前绝大多数编译器采用的是第一种方式。 61. 编译的过程大致有哪些步骤。☆☆☆ 词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。 62. 文法有哪些类型？分别有哪些特点？（0、1、2、3型）☆☆☆ 0型文法：自然语言。 1型文法：上下文有关文法。 2型文法：上下文无关文法。 3型文法：正则文法，又分为左线性文法和右线性文法。 BNF范式的表达能力等价于上下文无关文法 63. 什么是左线性、右线性文法？☆☆ 左线性文法：形如A->Ba的文法 右线性文法：形如A->aB的文法 . 最左、最右推导树，以及句柄、短语、直接短语的概念？☆ 任何一步推导过程σ→β(其中σ、β是句型)都是对σ中的最左(最右)非终结符进行替换，这种推导为最左(最右)推导。在形式语言中，最右推导常被称为规范推导。 S是文法的开始符号，αβδ是文法G的一个句型。如果有S→αAδ，且A→β，则称β是句型αβδ相对于非终符A的短语。特别是如有Aβ，则称β是句型αβδ相对于规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。 素短语是一个短语，它至少包含一个终结符，并除自身外不包含其他的素短语。 这里有一道例题： S－＞a|b|(T) T->TdS|S Vt={a,b,d,(,)}.Vn={S,T},S是开始符 句型(Sd(T)db)是S的一个_____，其中___是句柄;____是最左素短语；____是该句型的直接短语，_____是短语。 供选择的答案 A：①最左推导 ②最右推导 ③规范推导 ④推导 B：①S ②b ③(T) ④Sd(T) C：①S ②b ③(T) ④Sd(T) D：①S ②S，(T)，b③S，(T)，TdS，b ④(Sd(T)db) E：①(Sd(T)db) ②d(T) ③Td ④Sd(T)d 答案： 1、推导(仅仅是推导，既不是最左，也不是最右，也不是规范推导) 2、S 3、(T) 4、S,(T),b 5、（Sd(T)db） 65. 句型分析的两种方法的大致思路？☆☆ 自顶向下的分析法、自底向上的分析法（移进-归约法） 66. 通过给出的正则文法，画出对应的有限自动机。☆ 这个是形式语言课程的问题了。 67. 如何对一个文法进行消除左递归处理。（例如 S->Sa, S->b）☆☆ 这个较简单，看看书即可。 68. 什么是LL(1)、LR(0)、LALR(1)、LR(1)文法。☆ 这类题目通常比较BT，可以暂时放弃。 69. 符号表的作用域范围，在编译期（静态存储）和运行期（栈式存储）分别如何计算？☆ ☆☆ 可以对应C语言中变量的作用域范围，非常好理解。 六．汇编原理 70. 补码的计算方法。☆☆☆ 补码 = （取反）原码 + 1 71. X86系统的寻址方式有哪些？☆☆☆ 立即寻址方式、寄存器寻址方式、直接寻址方式、寄存器间接寻址方式、寄存器相对寻址方式、基址变址寻址方式、………… 其他问题如果不是面试硬件公司就不需要看了。 七．软件工程 72. CMMI 中软件成熟度的五个阶段。☆☆ 1． 初始级 软件过程是无序的，有时甚至是混乱的，对过程几乎没有定义，成功取决于个人努力。管理是反应式的。 2． 已管理级 建立了基本的项目管理过程来跟踪费用、进度和功能特性。制定了必要的过程纪律，能重复早先类似应用项目取得的成功经验。 3． 已定义级 已将软件管理和工程两方面的过程文档化、标准化，并综合成该组织的标准软件过程。所有项目均使用经批准、剪裁的标准软件过程来开发和维护软件，软件产品的生产在整个软件过程是可见的。 4． 量化管理级 分析对软件过程和产品质量的详细度量数据，对软件过程和产品都有定量的理解与控制。管理有一个作出结论的客观依据，管理能够在定量的范围内预测性能。 5． 优化管理级 过程的量化反馈和先进的新思想、新技术促使过程持续不断改进。 每个等级都被分解为过程域，特殊目标和特殊实践，通用目标、通用实践和共同特性： 每个等级都有几个过程区域组成，这几个过程域共同形成一种软件过程能力。每个过程域，都有一些特殊目标和通用目标，通过相应的特殊实践和通用实践来实现这些目标。当一个过程域的所有特殊实践和通用实践都按要求得到实施，就能实现该过程域的目标。 73. 瀑布模型的概念及描述，以及它有哪些演化模型。☆☆☆☆ 总体来讲，瀑布开发模型可以分为六个不同的阶段，其定义如下： 1.需求分析 2.设计 3.实现 4.测试 5.安装 6.维护 快速原型方法可以克服瀑布模型的缺点，减少由于软件需求不明确带来的开发风险。 增量模型在各个阶段并不交付一个可运行的完整产品，而是交付满足客户需求的一个子集的可运行产品。整个产品被分解成若干个构件，开发人员逐个构件地交付产品，这样做的好处是软件开发可以较好地适应变化，客户可以不断地看到所开发的软件，从而降低开发风险。 螺旋模型由风险驱动，强调可选方案和约束条件从而支持软件的重用，有助于将软件质量作为特殊目标融入产品开发之中。 74. 已知风险和可预测风险的区别。☆☆ 按照风险的可预测性划分，可以划分为已知风险、可预测风险和不可预测风险。 [1]已知风险是在严格分析项目计划后就能够明确的那些经常发生的、而且后果亦可预见的风险。 [2]可预测风险是根据经验，可以预见其发生，但不可预见其后果的风险。 [3]不可预测风险是有可能发生，但其发生的可能性具有不可预见性的风险。 75. UML图有哪些类型，分别从哪些角度描述软件。☆☆☆ a)用例图(Use Case Diagram)，描述系统功能； b)类图(Class Diagram)，描述系统的静态结构； c)对象图(Object Diagram)，描述系统在某个时刻的静态结构； d)时序图(Sequence Diagram)，按时间顺序描述系统元素间的交互； e)协作图(Collaboration Diagram)，按照时间和空间顺序描述系统元素间的交互和他们之间的关系； f)状态图(State Diagram)，描述了系统元素的状态条件和响应； g)活动图(Activity Diagram)，描述了系统元素的活动； h)组件图(Component Diagram)，描述了实现系统的元素的组织； i)配臵图(Deployment Diagram)，描述了环境元素的配臵，并把实现系统的元素映射到配臵上。 76. 白盒测试（结构测试）包含哪几种测试方法？☆☆☆ 基本路径测试、控制结构测试 77. 黑盒测试（功能测试）包含哪几种测试方法？☆☆☆ 等价划分、边界值分析、比较测试、正交数组测试等等 八．设计模式 这部分没有太多可讲的，主要是把各种主要的模式看一下，知道大概的设计思路。 78. 创建型模式：☆☆ 简单工程模式、工厂方法模式、抽象工厂模式、单例模式、多例模式、原始模型模式 79. 结构模式：☆☆ 适配器模式、合成模式、装饰模式、代理模式、享元模式、门面模式、桥梁模式 80. 行为模式：☆☆ 不变模式、策略模式、模板方法模式、观察者模式、责任链模式、命令模式、状态模式、访问者模式、调停者模式 九．C语言及C++ 81. C++堆、栈、自由存储区、全局/静态存储区和常量存储区的各自区别。☆☆☆☆ 在C++中，内存分成5个区，他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。 栈，就是那些由编译器在需要的时候分配，在不需要的时候自动清楚的变量的存储区。里面的变量通常是局部变量、函数参数等。 堆，就是那些由new分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个new就要对应一个delete。如果程序员没有释放掉，那么在程序结束后，操作系统会自动回收。 自由存储区，就是那些由malloc等分配的内存块，他和堆是十分相似的，不过它是用free来结束自己的生命的。 全局/静态存储区，全局变量和静态变量被分配到同一块内存中，在以前的C语言中，全局变量又分为初始化的和未初始化的，在C++里面没有这个区分了，他们共同占用同一块内存区。 常量存储区，这是一块比较特殊的存储区，他们里面存放的是常量，不允许修改（当然，你要通过非正当手段也可以修改，而且方法很多） 82. 什么是动态联编？与静态联编的区别？☆☆☆ 静态联编（静态绑定）：静态联编是指联编工作出现在编译连接阶段，这种联编又称早期联编，因为这种联编过程是在程序开始运行之前完成的。 动态联编（动态绑定）：编译程序在编译阶段并不能确切知道将要调用的函数，只有在程序执行时才能确定将要调用的函数，为此要确切知道该调用的函数，要求联编工作要在程 序运行时进行，这种在程序运行时进行联编工作被称为动态联编，或称动态绑定，又叫晚期联编。C++规定动态联编是在虚函数的支持下实现的。 83. 虚函数是怎样实现的？普通函数与虚函数、纯虚函数有哪些区别？☆☆☆ 虚函数使用虚表实现，基本思想是给每个含有虚函数的类一个虚表，在调用函数时，从虚表中找出相应的函数。如在上述代码中，Base的虚表只有一项Base::f(int i)，而Derived的虚表也只含有一项Derived::f(int i)。虚表指针在类中存放的位臵相同，当通过指针或引用调用一个虚函数时，程序通过虚表地址找到虚表，再从虚表中取出相应的虚函数。编译期间的代码相同，运行时的结果取决于动态指向的对象。 虚函数表既有继承性又有多态性。每个派生类的vtbl继承了它各个基类的vtbl，如果基类vtbl中包含某一项，则其派生类的vtbl中也将包含同样的一项，但是两项的值可能不同。如果派生类重载(override)了该项对应的虚函数，则派生类vtbl的该项指向重载后的虚函数，没有重载的话，则沿用基类的值。 纯虚函数是一种特殊的虚函数，带有纯虚函数的类称为抽象类。抽象类是一种特殊的类，它是为了抽象和设计的目的而建立的，它处于继承层次结构的较上层。抽象类是不能定义对象的，在实际中为了强调一个类是抽象类，可将该类的构造函数说明为保护的访问控制权限。 84. 为什么没有虚构造函数？☆☆ 这是一道较有综合性的题目，根据自己掌握的知识分析，只要说的有道理即可。 85. 成员初始化列表是什么概念？在构造时的顺序是什么？☆☆☆ 基础问题，可以看一下C++ Primer Plus。需要注意的是，初始化时的顺序是按照成员在类中声明的顺序初始化的，而并非在初始化列表中的排列顺序。 86. 多重继承时，可能会产生哪些问题？如何才能尽量避免？☆☆☆ 钻石继承，在系统庞大时很难以避免，最好的办法是通过语言的约束，例如JAVA的“多重接口单一继承”。 87. 在什么情况下需要用到友元？☆☆ 只要理解友元的定义即可。 88. 重载、覆盖和隐藏有哪些区别？☆☆☆☆ 重载的特征： （1）相同的范围（在同一个类中）； （2）函数名字相同； （3）参数不同； （4）virtual关键字可有可无。 覆盖的特征： （1）不同的范围（分别位于派生类与基类）； （2）函数名字相同； （3）参数相同； （4）基类函数必须有virtual关键字。 隐藏是指派生类的函数屏蔽了与其同名的基类函数，规则如下： （1）如果派生类的函数与基类的函数同名，但是参数不同。此时，不论有无virtual 关键字，基类的函数将被隐藏（注意别与重载混淆）。 （2）如果派生类的函数与基类的函数同名，并且参数也相同，但是基类函数没有virtual关键字。此时，基类的函数被隐藏（注意别与覆盖混淆）。 . 重载与模板特化的匹配规则哪个优先级高？☆ 规则较复杂，需要记住的一句话：在函数匹配时，将优先进行非模板参数的函数匹配，如果没有匹配结果再进行模板参数的函数匹配。 90. 可以在构造函数中调用虚函数么？会出现什么问题？☆☆ 也是一道综合题。 91. 在C语言中，static的作用有哪些？☆☆☆☆ 这个简单的问题很少有人能回答完全。在C语言中，关键字static有三个明显的作用： 1). 在函数体，一个被声明为静态的变量在这一函数被调用过程中维持其值不变。 2). 在模块内（但在函数体外），一个被声明为静态的变量可以被模块内所用函数访问，但不能被模块外其它函数访问。它是一个本地的全局变量。 3). 在模块内，一个被声明为静态的函数只可被这一模块内的其它函数调用。那就是，这个函数被在声明它的模块的本地范围内使用。 大多数应试者能正确回答第一部分，一部分能正确回答第二部分，同是很少的人能懂得第三部分。这是一个应试者的严重的缺点，因为他显然不懂得本地化数据和代码范围的好处和重要性。 92. 在C语言中，const关键字的作用有哪些？const int a; int const a; const int * a; int *const a;以上四句话的区别？☆☆☆☆ （1）修饰一般常量 int const x=2; 或const int x=2; （2）修饰常数组 int const a[5]={1, 2, 3, 4, 5}; const int a[5]={1, 2, 3, 4, 5}; （3）修饰常对象 class A; const A a; A const a; 定义常对象时，同样要进行初始化，并且该对象不能再被更新，修饰符const可以放在类名后面，也可以放在类名前面。 （4）修饰常指针 const int *A; file://const修饰指向的对象，A可变，A指向的对象不可变 int const *A; file://const修饰指向的对象，A可变，A指向的对象不可变 int *const A; file://const修饰指针A， A不可变，A指向的对象可变 const int *const A; file://指针A和A指向的对象都不可变 （5）修饰常引用 const double & v; （6）修饰函数的常参数 void Fun(const int Var); 告诉编译器Var在函数体中的无法改变，从而防止了使用者的一些无意的或错误的修改。 （7）修饰函数的返回值： const int Fun1(); const MyClass Fun2(); （8）修饰类的成员函数： class ClassName { public: int Fun() const; ..... }； （9）在另一连接文件中引用const常量 extern const int i; file://正确的引用 extern const int j=10; file://错误！常量不可以被再次赋值 93. 一个参数既可以是const还可以是volatile吗？解释为什么。☆☆ 是的。一个例子是只读的状态寄存器。它是volatile因为它可能被意想不到地改变。它是const因为程序不应该试图去修改它。 94. 关于“++”“+=”等操作符的计算过程，例如 x = x++; 的运算结果。☆☆☆ x=1; x=x++ 的运行结果是1，知道即可。 十．JAVA知识 95. 面向对象编程的三个基本特点。☆☆☆☆ 封装、继承、多态。 96. final, finally, finalize的区别。 ☆☆☆ 三个关键字完全不同，只要都知道即可解答。 final 类似于C语言中的const；finally用于try/catch异常处理；finallize是对象资源回收，在Object类中实现。 97. HashMap和Hashtable的区别。☆☆☆ Hashtable和HashMap类有三个重要的不同之处: 第一个不同主要是历史原因。Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现。 最重要的不同是Hashtable的方法是同步的，而HashMap的方法不是。这就意味着，虽然你可以不用采取任何特殊的行为就可以在一个多线程的应用程序中用一个Hashtable，但你必须同样地为一个HashMap提供外同步。一个方便的方法就是利用Collections类的静态的synchronizedMap()方法，它创建一个线程安全的Map对象， 并把它作为一个封装的对象来返回。这个对象的方法可以让你同步访问潜在的HashMap。这么做的结果就是当你不需要同步时，你不能切断Hashtable中的同步（比如在一个单线程的应用程序中），而且同步增加了很多处理费用。 第三点不同是，只有HashTable可以让你将空值作为一个表的条目的key或value。HashMap中只有一条记录可以是一个空的key，但任意数量的条目可以是空的value。这就是说，如果在表中没有发现搜索键，或者如果发现了搜索键，但它是一个空的值，那么get()将返回null。如果有必要，用containKey()方法来区别这两种情况。 98. Collection 和 Collections的区别。☆☆☆ Collection是集合类的上级接口，继承与他的接口主要有Set 和List. Collections是针对集合类的一个帮助类，他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 99. 垃圾收集器的工作原理。☆☆☆☆ GC即垃圾收集机制是指JVM用于释放那些不再使用的对象所占用的内存。JAVA语言并不要求JVM有GC，也没有规定GC如何工作。不过常用的JVM都有GC，而且大多数GC都使用类似的算法管理内存和执行收集操作。GC通过确定对象是否被活动对象引用来确定是否收集该对象。GC首先要判断该对象是否是时候可以收集。两种常用的方法是引用计数和对象引用遍历。 引用计数: 引用计数存储对特定对象的所有引用数，也就是说，当应用程序创建引用以及引用超出范围时，JVM必须适当增减引用数。当某对象的引用数为0时，便可以进行垃圾收集。 对象引用遍历: 早期的JVM使用引用计数，现在大多数JVM采用对象引用遍历。对象引用遍历从一组对象开始，沿着整个对象图上的每条链接，递归确定可到达（REACHABLE）的对象。如果某对象不能从这些根对象的一个（至少一个）到达，则将它作为垃圾收集。 100. sleep() 和 wait() 有什么区别？☆☆☆ sleep()方法是使线程停止一段时间的方法。在sleep 时间间隔期满后，线程不一定立即恢复执行。这是因为在那个时刻，其它线程可能正在运行而且没有被调度为放弃执行，除非(a)“醒来”的线程具有更高的优先级；(b)正在运行的线程因为其它原因而阻塞 wait()是线程交互时，如果线程对一个同步对象x 发出一个wait()调用，该线程会暂停执行，被调对象进入等待状态，直到被唤醒或等待时间到。 101. 当一个对象被当作参数传递到一个方法后，此方法可改变这个对象的属性，并可返回 变化后的结果，那么这里到底是值传递还是引用传递？☆☆☆ 是值传递。Java 编程语言只由值传递参数。当一个对象实例作为一个参数被传递到方法中时，参数的值就是对该对象的引用。对象的内容可以在被调用的方法中改变，但对象的引用是永远不会改变的。 102. 线程的基本概念、线程的基本状态以及状态之间的关系。☆☆☆ 1. 创建状态(new Thread) 执行下列语句时，线程就处于创建状态： Thread myThread = new MyThreadClass( ); 当一个线程处于创建状态时，它仅仅是一个空的线程对象，系统不为它分配资源。 2. 可运行状态( Runnable ) Thread myThread = new MyThreadClass( ); myThread.start( ); 当一个线程处于可运行状态时，系统为这个线程分配了它需的系统资源，安排其运行并调用线程运行方法，这样就使得该线程处于可运行( Runnable )状态。需要注意的是这一状态并不是运行中状态（Running )，因为线程也许实际上并未真正运行。由于很多计算机都是单处理器的，所以要在同一时刻运行所有的处于可运行状态的线程是不可能的，Java的运行系统必须实现调度来保证这些线程共享处理器。 3. 不可运行状态（Not Runnable） 进入不可运行状态的原因有如下几条： 1) 调用了sleep（）方法; 2) 调用了suspend（）方法; 3) 为等候一个条件变量，线程调用wait（）方法; 4) 输入输出流中发生线程阻塞; 不可运行状态也称为阻塞状态（Blocked）。因为某种原因（输入/输出、等待消息或其它阻塞情况），系统不能执行线程的状态。这时即使处理器空闲，也不能执行该线程。 4. 死亡状态（Dead） 线程的终止一般可通过两种方法实现：自然撤消（线程执行完）或是被停止（调用stop()方法）。目前不推荐通过调用stop()来终止线程的执行，而是让线程执行完。 103. XML有哪些解析技术？区别是什么？☆☆ 1、DOM:处理大型文件时其性能下降的非常厉害。这个问题是由DOM的树结构所造成的，这种结构占用的内存较多，而且 DOM 必须在解析文件之前把整个文档装入内存,适合对 XML 的随机访问 2、SAX:不同于DOM,SAX是事件驱动型的XML解析方式。 它顺序读取XML文件，不需要一次全部装载整个文件。当遇到像文件开头，文档结束，或者标签开头与标签结束时，它会触发一个事件，用户通过在其回调事件中写入处理代码来处理XML文件，适合对XML的顺序访问。 104. EJB与 JAVA BEAN的区别？☆☆☆ JAVA BEAN 是可复用的组件，对JAVA BEAN并没有严格的规范，理论上讲，任何一个JAVA类都可以是一个BEAN。但通常情况下，由于JAVA BEAN是被容器所创建（如TOMCAT)的，所以JAVA BEAN应具有一个无参的构造器，另外，通常JAVA BEAN还要实现SERIALIZABLE接口用于实现BEAN的持久性。JAVA BEAN实际上相当于微软COM模型中的本地进程内COM组件，它是不能被跨进程访问的。 ENTERPRISE JAVA BEAN 相当于DCOM，即分布式组件。它是基于JAVA的远程方法调用（RMI）技术的，所以EJB可以被远程访问（跨进程、跨计算机）。但EJB必须被布署在诸如WEBSPERE、WEBLOGIC这样的容器中，EJB客户从不直接访问真正的EJB组件，而是通过其容器访问。EJB容器是EJB组件的代理，EJB组件由容器所创建和管理。客户通过容器来访问真正的EJB组件。 105. EJB的角色和三个对象。☆☆ 一个完整的基于EJB的分布式计算结构由六个角色组成，这六个角色可以由不同的开发商提供，每个角色所作的工作必须遵循Sun公司提供的EJB规范，以保证彼此之间的兼 容性。这六个角色分别是EJB组件开发者（Enterprise Bean Provider） 、应用组合者（Application Assembler）、部署者（Deployer）、EJB 服务器提供者（EJB Server Provider）、EJB 容器提供者（EJB Container Provider）、系统管理员（System Administrator） 三个对象：Remote（Local）接口、Home（LocalHome）接口，Bean类 106. 什么是J2EE。☆☆ J2EE是一套全然不同于传统应用开发的技术架构，包含许多组件，主要可简化且规范应用系统的开发与部署，进而提高可移植性、安全与再用价值。 J2EE的核心规范是 Enterprise Java Beans（EJBs）。EJB依照特性的不同，目前共分为三种，分别是Session Bean、Entity Bean，以及 Message Driven Bean 。其中 Session Bean 与Entity Bean 算是EJB的始祖，这两种EJB规格在EJB 1.x版本推出时就已经存在，而Message Driven Bean则是出现在EJB 2.0的规格之中。 J2EE的各种组件、服务和API：Servlet、JSP、EJB、JDBC、JMS、JNDI、JTA、JCA、JMX、JAXR、SAAJ。 107. MVC的各部分都有哪些技术实现？☆☆☆ \"Model\" 代表的是应用的业务逻辑，通过JavaBean，EJB组件、SPRING/HIBERNATE实现； \"View\" 是应用的表示面，由JSP页面产生，通过JSP(JSF)+STRUTS(WEBWORK)实现； \"Controller\" 是提供应用的处理过程控制,通过Servlet实现。 十一. Linux及Unix知识 此类问题比较杂，基本上分为“命令使用”和“系统原理”两类，前者主要要靠经验了。 108. 基本命令的使用。☆☆☆ 掌握 ls cat tar grep chmod chown 这几个基本命令的常用方法，要尽量熟练使用各种参数。 109. 进程的用户态、内核态的区别。☆☆ 用系统调用时进入内核态。Linux对硬件的操作只能在内核态，这可以通过写驱动程序来控制。在用户态操作硬件会造成core dump。 要注意区分系统调用和一般的函数。系统调用由内核提供，如read()、write()、open()等。而一般的函数由软件包中的函数库提供，如sin()、cos()等。在语法上两者没有区别。 一般情况：系统调用运行在核心态，函数运行在用户态。但也有一些函数在内部使用了系统调用（如fopen），这样的函数在调用系统调用是进入核心态，其他时候运行在用户态。 十三. 非技术性问题 110. 我们为什么要雇请你呢？ 有的面试只有这么一个问题 。 111. 你认为自己最大的弱点是什么？ 绝对不要自作聪明地回答“我最大的缺点是过于追求完美”，有的人以为这样回答会显得自己比较出色，但事实上，他已经岌岌可危了。 112. 你最喜欢的大学课程是什么？为什么？ 说和你要应聘的职位相关的课程吧，表现一下自己的热诚没有什么坏处。 113. 你能为我们公司带来什么呢？ 假如你可以的话，试着告诉他们你可以减低他们的费用——“我已经接受过MicroSoft Access和Word的培训，立刻就可以上岗工作”（他们在那边可能想：Access培训要花$540Word要花$445,这小子能为我们省下$1000的培训费用呢。 114. 最能概括你自己的三个词是什么？ 经常用的三个词是：适应能力强，有责任心和做事有始终，结合具体例子向主考官解释，使他们觉得你具有发展潜力。 115. 你对我们公司有什么认识？ 说几件你知道的事，其中至少有一样是“销售额为多少多少”之类。 116. 你是怎么知道我们招聘这个职位的呢？ 如果你是从公司内部某人处打听回来的消息，记得提及他的名字，公司不说偏袒内部关系不代表它不存在。 117. 你心目中的英雄是谁？ 最好的答案是你的朋友或者家人，尽量避免说及名人。 118. 你有什么问题吗？ 一定要提问。 119. 你过去的上级是个怎么样的人？ 别贬低过去的上司，提一下他的长处和不足。 120. 你的业余爱好是什么？ 找一些富于团体合作精神的，这里有一个真实的故事：有人被否决掉，因为他的爱好是深海潜水。主考官说：因为这是一项单人活动，我不敢肯定他能否适应团体工作。 121. 你现在能把过去做过的工作做得更好吗？ “事后诸葛亮地说……”记得回答前先说这句话。 122. 作为被面试者给我打一下分 试着列出四个优点和一个非常非常非常小的缺点，（可以抱怨一下设施，没有明确责任人的缺点是不会有人介意的）。 123. 告诉我三件关于这公司的事情。 你应该知道十件和公司有关的事情，他问你三件你回答四件，他问你四件你回答五件。
因篇幅问题不能全部显示，请点此查看更多更全内容