搜索
需要掌握的知识汇总LastUpdate:2007-11-7前面是各种专业知识及里面所需要掌握的各种重点，后面是一些常用的技术点。说明：所有的题目分为以下几个等级，等级只代表了题目对笔试面试来说的重要程度，并不代表其难易程度。☆不常见的问题，可以不掌握；如果简历上写了相关的内容，还是要复习一下。☆☆通常情况下不会考到；如果时间充裕的话还是应该准备一下。☆☆☆属于重点内容，必须要掌握。☆☆☆☆简直是经典问题，几乎必考。一．数据结构1.程序运行中堆和栈的区别。☆☆☆☆栈，就是那些由编译器在需要的时候分配，在不需要的时候自动清除的变量的存储区。里面的变量通常是局部变量、函数参数等。堆，就是那些由new分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个new就要对应一个delete。如果程序员没有释放掉，那么在程序结束后，操作系统会自动回收。更具体的见后面C++部分。2.排序二叉树的增、删、查等基本操作。☆☆先把二叉树的基本思路和大致操作方法看一下书，然后敲敲代码练习一下。这里我写了一个二叉树的增、查、删功能，写得不是很简洁。#includecstdlib#includeiostreamusingnamespacestd;typedefstructp{intvalue;structp*left;structp*right;}Point;intaddPoint(Point**root,inttargetValue){if(*root==NULL){*root=newPoint();(*root)-left=(*root)-right=NULL;(*root)-value=targetValue;return0;}Point*p=*root;Point*q=*root;while(p!=NULL){q=p;if(q-valuetargetValue)p=q-right;elseif(q-valuetargetValue)p=q-left;elsereturn0;}p=newPoint();p-left=p-right=NULL;p-value=targetValue;if(q-valuetargetValue)q-right=p;elseif(q-valuetargetValue)q-left=p;return0;}intshowTree(Point*p){if(p==NULL)return0;showTree(p-left);coutp-value;showTree(p-right);return0;}intdelPoint(Point**root,inttargetValue){if(*root==NULL)return1;//首先找到要删除的节点Point*p=*root;Point*q=p;while(p!=NULL){if(p-value==targetValue)break;q=p;if(q-valuetargetValue)p=q-right;elseif(q-valuetargetValue)p=q-left;}//如果没有对应值，则退出if(p==NULL)return1;//如果p没有右子树，则直接将左子树上移if(p-right==NULL){if(q-valuetargetValue)q-right=p-left;elseif(q-valuetargetValue)q-left=p-left;deletep;return0;}//如果p有右子树，则使用p的后继替换pPoint*r=p-right;Point*s=p;while(r-left!=NULL){s=r;r=r-left;}if(s==p){s-right=r-right;}else{s-left=r-right;}if(p==*root)*root=r;else{if(q-valuetargetValue)q-right=r;elseif(q-valuetargetValue)q-left=r;}r-left=p-left;r-right=p-right;deletep;return0;}intmain(intargc,char*argv[]){Point*mainRoot=NULL;intvalues[]={10,5,4,2,7,1,20,2,31,5};for(inti=0;i10;i++){addPoint(&mainRoot,values[i]);}showTree(mainRoot);coutendl;delPoint(&mainRoot,20);showTree(mainRoot);coutendl;system(PAUSE);return0;}3.什么是线索二叉树。☆☆当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。为了区分一个结点的指针是指向其儿子的指针，还是指向其前驱或后继结点的线索，可在每个结点中增加两个线索标志。线索二叉树是一种逻辑结构。4.什么是哈夫曼编码。☆☆☆哈夫曼编码(HuffmanCoding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损耗压缩。5.KMP算法的思路。☆这个看数据结构的课本吧，记住next与nextval两个数组的计算方式。记住下面这个例子：pos:1234567value:abcabdbnext:0111231求next数组的程序属于经典，如果要去百度、微软、谷歌则必须熟记：voidcalculateNext(constchar*str){intlength=strlen(str);int*next=newint[length+1];intj=1,k=0;next[1]=0;while(jlength){if(k==0||str[j-1]==str[k-1]){j++;k++;next[j]=k;}else{k=next[k];}}}6.二叉树的非递归遍历方法，只掌握前、中序遍历即可，后序遍历较为复杂。☆以下是例子代码。voidBinaryTree::PreTravel(PTreeNodenode){stackPTreeNode*st=newstackPTreeNode();PTreeNodep=node;while(p!=NULL||!st-empty()){if(p!=NULL){AccessData(p-data);st-push(p);p=p-left;}else{//p==NULL,!st-empty()p=st-top()-right;st-pop();}}deletest;}voidBinaryTree::InTravel(PTreeNodenode){stackPTreeNode*st=newstackPTreeNode();PTreeNodep=node;while(p!=NULL||!st-empty()){if(p!=NULL){st-push(p);p=p-left;}else{p=st-top();AccessData(p-data);st-pop();p=p-right;}}deletest;}voidBinaryTree::PostTravel(PTreeNodenode){stackPTreeNode*st=newstackPTreeNode();mapPTreeNode,intm;PTreeNodep=node;while(p!=NULL||!st-empty()){if(p!=NULL){st-push(p);m.insert(mapPTreeNode,int::value_type(p,0));p=p-left;}else{PTreeNodetmp=st-top();m[tmp]++;if(m[tmp]==1){p=tmp-right;}elseif(m[tmp]==2){st-pop();AccessData(tmp-data);}}}}7.二叉树与森林的相互转换。☆☆树（树林）转换成二叉树时结果是唯一的。其转换可以递归的描述如下：若树（树林）为空，则二叉树为空；否则，树（树林）中第一棵树的根是二叉树的根，第一棵树除去根结点后的子树林是二叉树的左子树，树林中除去第一棵树后的树林形成二叉树的右子树。二叉树转换成树（树林）时结果也是唯一的。其转换可以递归的描述，若二叉树为空，则树（树林）为空；否则，二叉树的根是树（树林）中第一棵树的根，二叉树的左子树构成树（树林）中第一棵树除去根结点后的子树林，二叉树的右子树构成树林中除去第一棵树后的树林。8.根据二叉树的前序、中序遍历，计算树的后序遍历。☆☆☆思路：根据前两种遍历，分析出树的结构，然后写出后序遍历。如果题目只给出前序和后序遍历，是无法确定中序遍历的。9.图有哪些存储方式。☆☆☆数组表示法、邻接表、十字链表、邻接多重表这是几种最常见的图的存储表示。10.计算图的最小生成树的两种算法。☆☆Prim和Kruskal，记住大体思路即可。11.什么是图的拓扑排序。☆☆☆对一个有向无回路图进行拓扑排序。有向无回路图又称为dag。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G包含(u,v)，则在序列中u出现在v之前（如果图是有回路的就不可能存在这样的线性序列)。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。12.关键路径的求法。☆☆对于一个项目而言，只有项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径（CriticalPath），组成关键路径的活动称为关键活动。其通常做法是：1）将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列；2）用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图；3）用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差；4）找出所有时差为零的活动所组成的路线，即为关键路径；5）识别出准关键路径，为网络优化提供约束条件；13.图中两点的最短路径的两种算法的思路，各自的复杂度。☆☆☆Dijkstra（迪杰斯特拉）和Floyd（弗洛伊德），分别为O(n^2)和O(n^3)。14.内存分配的三种策略，各自的优缺点。☆☆☆1）首次拟合法2）最佳拟合法3）最差拟合法优缺点随便讲讲就好了（各有不同的长处，适用于不同的场合）。15.各种排序算法（选择排序、插入排序、冒泡排序、快速排序、二叉排序、希尔Shell排序、堆排序、归并排序、基数排序）的时间、空间复杂度，以及是否稳定。☆☆☆☆算法平均时间最坏情况空间是否稳定简单排序O(n^2)O(n^2)O(1)是快速排序O(nlogn)O(n^2)O(longn)否堆排序O(nlogn)O(nlogn)O(1)否归并排序O(nlogn)O(nlogn)O(n)否基数排序O(d(n+rdO(d(n+rdO(rd)是))))16.哈希散列的原理，以及冲突解决的几种策略。☆☆☆哈希的构造方法：直接地址法、数字分析法、平方取中法、折叠法、除留余数法。冲突的处理方法：开放地址法、再哈希法、链式地址法、17.多路平衡归并排序的实现，败者树的基本原理。☆☆败者树是多路平衡归并的实现方式，