程序员软考专用复习资料

1、常考基础必知必会A.排序：排序有几种，各种排序的比较，哪些排序是稳定的，快排的算法；B.查找：哈希查找、二叉树查找、折半查找的对比，哈希映射和哈希表的区别C.链表和数组的区别，在什么情况下用链表什么情况下用数组？D.栈和队列的区别？E.多态，举例说明;overload和override的区别?strcpyF.字符串有关的函数，比如让你写一个拷贝字符串的函数啊，或者字符串反转啊什么的。和memcpy?G.继承、多继承？H.面向对象有什么好处？? 在什么时候分I.说说static的与众不同之处，如果一个变量被声明为static,它会被分配在哪里配空间等？J.什么是虚函数、纯虚函数、虚的析构函数，用

2、途？K.内存泄漏及解决方法？网络部分：OSI模型7层结本TCP/IP模型Z勾？B. TCP/UDP区另IC. TCP建立连接的步骤？D.香农定理？二叉树三种遍历白非递归算法(背诵版)1.先序遍历非递归算法#definemaxsize100typedefstructBitreeElemmaxsize;inttop;SqStack;voidPreOrderUnrec(Bitreet)SqStacks;StackInit(s);p=t;while(p!=null|!StackEmpty(s)while(p!=null)序遍历非递归算法#definemaxsize100typedefstructBit

3、reeElemmaxsize;inttop;SqStack;voidInOrderUnrec(Bitreet)SqStacks;StackInit(s);p=t;while(p!=null|!StackEmpty(s)while(p!=null)序遍历非递归算法#definemaxsize100typedefenumL,Rtagtype;typedefstructBitreeptr;tagtypetag;stacknode;typedefstructstacknodeElemmaxsize;inttop;SqStack;ag=R)x=pop(s);p=;visite(p-data);ag=R;

4、tr-rchild;while (!StackEmpty(s);序遍历非递归算法#definemaxsize100typedefenumL,Rtagtype;typedefstructBitreeptr;tagtypetag;stacknode;typedefstructstacknodeElemmaxsize;inttop;SqStack;ag=R)x=pop(s);p=;visite(p-data);ag=R;tr-rchild;while(!StackEmpty(s);串的基本概念，串与线性表的关系(串是其元素均为字符型数据的特殊线性表)，空串与空格串的区别，串相等的条件；2 .串的基本

5、操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。3 .顺序串与链串及块链串的区别和联系，实现方式。4. KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足，明确next数组需要改进。可能进行的考查方式是：求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。5、多维数组和广义表矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。

6、掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。6、树与二叉树树一章的知识点包括：二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。（1）二叉树的概念、性质和存储结构考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树（左右子树无序）的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：A.第i层的最多结点数，B.深度为k的二叉树的

7、最多结点数，=n2+1的性质，个结点的完全二叉树的深度，E.顺序存储二叉树时孩子结点与父结点之间的换算关系（root从1开始，则左为：2*i,右为：2*i+1）。二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。（2）二叉树的三种遍历算法这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种

8、递归算法改造而来(比如：求叶子个数)，所以，掌握了三种遍历的非递归算法后，对付诸如：利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。(3)可在三种遍历算法的基础上改造完成的其它二叉树算法：求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。(4)线索二叉树：线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带

9、来资源耗尽的危险，为了避免此类情况,线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题(如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题)。(5)最优二叉树(哈夫曼树):最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题。(6)树与森林：二叉树是一种特殊的树，这种特殊不仅仅在

10、于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树。树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根（对于森林而言称作：先序与后序遍历）。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。7、图1 .图的基本概念：图的定义和特点，无向图

11、，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。2 .图的几种存储形式：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。在考查时，有的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。3 .考查图的两种遍历算法：深度遍历和广度遍历深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：求最长的最短路径问题”和判断两顶点间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度

12、遍历算法。4 .生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法。考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。5 .拓扑排序问题:拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说,种是从前向后”的排序，一种是从后向前”排。当然，后一种排序出来的结果是逆拓扑有序”的。6 .关键路径问题：这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径；二是最早时间是什么意思、如何求；三是最晚时间是什么意思、如何求。简单地说，最早时间是通过从前向后”的方法求的，而

13、最晚时间是通过从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。7 .最短路径问题：与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径(单源最短路径)；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是

14、旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法，注意区分。8、查找(search);静态查找与动态查找的含义及区先弄清楚以下几个概念：关键字、主关键字、次关键字的含义另I；平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的SL值，应该记住。一般将search分为三类：在顺序表上的查找；在树表上的查找；在哈希表上的查找。（1）线性表上的查找：主要分为三种线性结构：顺序表传统查找方法：逐个比较；有序顺序表一一二分查找法（注意适用条件以及其递归实现方法）;索引顺序表一一对索引结构，采用索引查找算法。注意这三种表下的

15、ASL值以及三种算法的实现。（2）树表上的查找：树表主要分为以下几种：二叉排序树（即二叉查找树），平衡二叉查找树（AVL科）,B树，键树。其中，尤以前两种结构为重，也有部分名校偏爱考B树的。由于二叉排序树与平衡二叉树是一种特殊的二叉树。二叉排序树，简言之，就是左小右大”，它的中序遍历结果是一个递增的有序序列。平衡二叉排序树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡排序二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二叉排序树，判断某棵二叉树是否二叉排序树”这算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡

16、二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉.排序树。除B树的查找算法外，应该特另注意一下B树的插入和删除算法，因为这两种算法涉及到B树结点的分裂和合并，是一个难点。键树(keywordtree),又称数字搜索树(digitalsearchtree)或字符树。trie树也可说等同于键树或属于键树的一种。键树特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。(3)基于哈希表的查找算法：哈希译自“hash词，意为散列”或杂凑”。哈希表查找的基本思想是：根据当前待

17、查找数据的特征，以记录关键字为自变量，设计一个function,该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。9、内部排序考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标(时间复杂度)能否了如指掌。排序方法分类有：插入、选择、交换、归并、计数等五种排序方法。(1)插入排序中又可分为：直接插入、折半插入、2路插入(?)、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找，希尔排序，是通过控制每次参与排序的数的总范围由小到大”的增量

18、来实现排序效率提高的目的。(2)交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。(3)选择排序可以分为：简单选择、树选择、堆排序。选择排序相对于前面几种排序算法来说，难度大一点。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数树选择，是通过锦标赛”类似的思想，让两数相比，不断淘汰较大（小）者，最终选出最小（大）数;而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。（4）归并排序，是通过归并”这种操

19、作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。（5）基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序（扑克牌排序），链式排序（整数排序）。基数排序的核心思想也是利用基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌

20、握的。.1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。冒泡排序插入排序二路插入排序希尔排序快速排序选择排序归并排序堆排序算法的C/C+实现#includeusingnamespacestd;m,Rm+1.high,先将它们合并到一个局部的暂存向量R1（相当于输出堆）中，待合并完成后将R1复制回Rlow.high中。时间复杂度o(nlogn)空间复杂度o(n)比较次数？*/voidmerge(intarray口,inti,

21、intm,intn)intj,k；intiStart=i,iEnd=n;intarrayDest256;for(j=m+1,k=i;i=m&j=n;+k)if(arrayiarrayj)arrayDestk=arrayi+;elsearrayDestk=arrayj+;if(i=m)for(;k=n;k+,i+)arrayDestk=arrayi;if(j=n)for(;k=n;k+,j+)arrayDestk=arrayj;for(j=iStart;j=iEnd;j+)arrayj=arrayDestj;voidmerge_sort(intarray,ints,intt)intm;if(st

22、)m=(s+t)/2;merge_sort(array,s,m);merge_sort(array,m+1,t);merge(array,s,m,t);/*堆排序算法思想：堆排序(HeapSort)是指利用堆(heaps)这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于(或者大于)它的父节点。时间复杂度o(nlogn)空间复杂度o(1)比较次数：较多*/voidheap_adjust(intarray,inti,intlen)intrc=array;for(intj=2*i;jif(jlen&arrayj=arrayj)break;a

23、rrayi=arrayj;i=j;arrayi=rc;voidheap_sort(intarray,intlen)inti;for(i=(len-1)i=0;i-)heap_adjust(array,i,len);for(i=(len-1);i0;i-)swap(array0,arrayi);内存空间占用的少，因为链表节点会附加上一块或两块下一个节点的信但是数组在建立时就固定了。所以也有可能会因为建立的数组过大或不足引起内存上的问题。B.数组内的数据可随机访问，但链表不具备随机访问性。这个很容易理解，数组在内存里是连续的空间，比如如果一个数组地址从100到200,且每个元素占用两个字节，那么1

24、00-200之间的任何一个偶数都是数组元素的地址，可以直接访问。链表在内存地址可能是分散的。所以必须通过上一节点中的信息找能找到下一个节点。C.查找速度上。这个也是因为内存地址的连续性的问题，不罗索了。链表优于数组的：A.插入与删除的操作。如果数组的中间插入一个元素，那么这个元素后的所有元素的内存地址都要往后移动。删除的话同理。只有对数据的最后一个元素进行插入删除操作时，才比较快。链表只需要更改有必要更改的节点内的节点信息就够了。并不需要更改节点的内存地址。B.内存地址的利用率方面。不管你内存里还有多少空间，如果没办法一次性给出数组所需的要空间，那就会提示内存不足，磁盘空间整理的原因之一在这里

25、。而链表可以是分散的空间地址。C.链表的扩展性比数组好。因为一个数组建立后所占用的空间大小就是固定的，如果满了就没法扩展，只能新建一个更大空间的数组；而链表不是固定的，可以很方便的扩展。12、C+操作符优先级：记忆方法：去掉一个最高的，去掉一个最低的，剩下的是一、二、三、赋值；双目运算符中，顺序为算术、关系和逻辑，移位和逻辑位插入其中。-摘自C语言程序设计实用问答问题：如何记住运算符的15种优先级和结合性？解答：C语言中运算符种类比较繁多，优先级有15种，结合性有两种。如何记忆两种结合性和15种优先级？下面讲述一种记忆方法。结合性有两种，一种是自左至右，另一种是自右至左，大部分运算符的结合性是

26、自左至右，只有单目运算符、三目运算符的赋值运算符的结合性自右至左。优先级有15种，记忆方法如下：记住一个最高的：构造类型的元素或成员以及小括号。记住一个最低的：逗号运算符。剩余的是一、二、三、赋值意思是单目、双目、三目和赋值运算符。在诸多运算符中，又分为：算术、关系、逻辑。两种位操作运算符中，移位运算符在算术运算符后边，逻辑位运算符在逻辑运算符的前面。再细分如下：算术运算符*,/,%高于+,-。关系运算符中：,=,和Memberaccessfromapointerptr-age=34;yes.Memberaccessfromanobject=34;no+Post-incrementfor(in

27、ti=0;i10;i+)cout0;i-)couti;yesdynamic_castRuntime-checkedtypeconversionY&y=dynamic_cast(x);nostatic_castUncheckedtypeconversionY&y=static_cast(x);noreinterpret_castReinterpretingtypeconversionintconst*p=reinterpret_cast(0x1234);noconst_castCastaway/Addconstnessint*q=const_cast(p);notypeidGettypeinfo

28、rmationstd:type_infoconst&t=typeid(x);no111i13iiI!Logicalnegationif(!done).yesrighttoleftnotAlternatespellingfor!Bitwisecomplementflags=flags;yescomplAlternatespellingfor+Pre-incrementfor(i=0;i10;+i)cout0;-i)cout*Memberpointerselectorptr-*var=24;yeslefttoright.*Memberobjectselectorobj.*var=24;no15*M

29、ultiplicationinti=2*4;yeslefttoright/Divisionfloatf=/;yes%Modulusintrem=4%3;yes16+Additioninti=2+3;yeslefttoright-Subtractioninti=5-1;yes17Bitwiseshiftleftintflags=33Bitwiseshiftrightintflags=331;yes8Comparisonless-thanif(i42)yeslefttoright=Comparisonless-than-or-equal-toif(iComparisongreater-thanif

30、(i42).yes=Comparisongreater-than-or-equal-toif(i=42).yes191=Comparisonequal-toif(i=42).yeslefttorighteqAlternatespellingfor=!=Comparisonnot-equal-toif(i!=42).yesnot_eqAlternatespellingfor!=110&BitwiseANDflags=flags&42;yeslefttorightbitandAlternatespellingfor&111ABitwiseexclusiveOR(XOR)flags=flagsa42

31、;yeslefttorightxorAlternatespellingforA12IBitwiseinclusive(normal)ORflags=flags|42;yeslefttorightbitorAlternatespellingfor|q13&LogicalANDif(conditionA&conditionB).yeslefttorightandAlternatespellingfor&r-14IILogicalORif(conditionA|conditionB).yeslefttorightorAlternatespellingfor|115?:Ternarycondition

32、al(if-then-else)inti=ab?a:b;norighttoleft1111111I161111i=Assignmentoperatorinta=b;yesrighttoleft+=Incrementandassigna+=3;yes-=Decrementandassignb-=4;yes*=Multiplyandassigna*=5;yes/=Divideandassigna/=2;yes%=Moduloandassigna%=3;yes&=BitwiseANDandassignflags&=new_flags;yesand_eqAlternatespellingfor&=A=

33、Bitwiseexclusiveor(XOR)andassignflagsa=new_flags;yesxor_eqAlternatespellingforA=|=BitwisenormalORandassignflags|=new_flags;yesor_eqAlternatespellingfor|=Bitwiseshiftleftandassignflags=Bitwiseshiftrightandassignflags=2;yesi17throwthrowexceptionthrowEClass(Message);no118,Sequentialevaluationoperatorfo

34、r(i=0,j=0;i2;2 .根结点的儿子数为2,M;3 .除根结点以外的非叶子结点的儿子数为M/2,M;4 .每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）5 .非叶子结点的关键字个数=指向儿子的指针个数-1；6 .非叶子结点的关键字：K1,K2,，KM-1;且KiKi+1;7 .非叶子结点的指针：P1,P2,，PM；其中P1指向关键字小于K1的子树，PM指向关键字大于KM-1的子树，其它Pi指向关键字属于（Ki-1,Ki）的子树；8 .所有叶子结点位于同一层；如：（M=3）B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，

35、否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；B-树的特性：1 .关键字集合分布在整颗树中；2 .任何一个关键字出现且只出现在一个结点中；3 .搜索有可能在非叶子结点结束；4 .其搜索性能等价于在关键字全集内做一次二分查找5 .自动层次控制由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：其中，M为设定的非叶子结点最多子树个数，N为关键字总数；所以B-树的性能总是等彳于二分查找（与M值无关），也就没有B树平衡的问题；由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除

36、结点时，需将两个不足M/2的兄弟结点合并；（3）B+树B+树是B-树的变体，也是一种多路搜索树：1 .其定义基本与B-树同，除了：2 .非叶子结点的子树指针与关键字个数相同；3 .非叶子结点的子树指针Pi,指向关键字值属于Ki,Ki+1）的子树（B-树是开区间）；5 .为所有叶子结点增加一个链指针；6 .所有关键字都在叶子结点出现；如：（M=3）B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；B+的特性:1 .所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的2 .不可能在非叶子

37、结点命中；3 .非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；4 .更适合文件索引系统；（4）B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为（2/3）*M,即块的最低使用率为2/3（代替B+树白1/2）;B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，

38、再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）;如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；所以，B*树分配新结点的概率比B+树要低，空间使用率更高；（5）红黑树红黑树（Red-BlackTree）是二叉搜索树（BinarySearchTree）的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后）。而红黑树在每一次插入或删除节点之后都会花O(logN)的时间来对树的结构作修改，以保持树的平衡。也就是说，红黑树的查找方法与二叉搜索树完全一

39、样；插入和删除节点的的方法前半部分节与二叉搜索树完全一样，而后半部分添加了一些修改树的结构的操作。map就是采用红黑树存储的，红黑树(RBTree)是平衡二叉树，其优点就是树到叶子节点深度一致，查找的效率也就一样，为logN。在实行查找，插入，删除的效率都一致，而当是全部静态数据时，没有太多优势，可能采用hash表各合适。相对来说，hash_map是一个hashtable占用内存更多，查找效率高一些，但是hash的时间比较费时。总体而言，hash_map查找速度会比map快，而且查找速度基本和数据数据量大小无关，属于常数级别；而map的查找速度是log(n)级别。并不一定常数就比10g(n)小

40、，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且hash_map的构造速度较慢。现在知道如何选择了吗？权衡三个因素：查找速度，数据量，内存使用。红黑树的每个节点上的属性除了有一个key、3个指针：parent、Ichild、rchild以外，还多了一个属性：coloro它只能是两种颜色：红或黑。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下4点性质：1 .

41、根节点是黑色的。2 .空节点是黑色的(红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL,而是指向一个定义好的空节点)。3 .红色节点的父、左子、右子节点都是黑色。4 .在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。(6)trie树Trie树，即DoubleArray字典查找树，既可用于一般的字典搜索，也可用于索引查找。每个节点相当于DFA的一个状态，终止状态为查找结束。有序查找的过程相当于状态的不断转换对于给定的一个字符串a1,a2,a3,an则采用TRIE树搜索经过n次搜索即可完成一次查找。不过好像还是没有B树的搜索效率

42、高，B树搜索算法复杂度为10gt(n+1/2).当t趋向大，搜索效率变得高效。Trie树的优点举例已知n个由小写字母构成的平均长度为10的单词，判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法：1 .最容易想到的：即从字符串集中从头往后搜，看每个字符串是否为字符串集中某个字符串的前缀，复杂度为O(nA2)o2 .使用hash:我彳门用hash存下所有字符串的所有的前缀子串。建立存有子串hash的复杂度为O(n*len)。查询的复杂度为O(n)*O(1)=O(n)。3 .使用trie：因为当查询如字符串abc是否为某个字符串的前缀时，显然以b,c,d.等不是以a开头的字符串就不用查找

43、了。所以建立trie的复杂度为O(n*len),而建立+查询在trie中是可以同时执行的，建立的过程也就可以成为查询的过程，hash就不能实现这个功能。所以总的复杂度为O(n*len),实际查询的复杂度只是O(len)。解释一下hash为什么不能将建立与查询同时执行，例如有串：911,911456输入，如果要同时执行建立与查询，过程就是查询911,没有，然后存入9、91、911,查询911456,没有然后存入9114、91145、911456,而程序没有记忆功能，并不知道911在输入数据中出现过。所以用hash必须先存入所有子串，然后for循环查询。而trie树便可以，存入911后，已经记录9

44、11为出现的字符串，在存入911456的过程中就能发现而输出答案；倒过来亦可以，先存入911456,在存入911时，当指针指向最后一个1时，程序会发现这个1已经存在，说明911必定是某个字符串的前缀，该思想是我在做pku上的3630中发现的，详见本文配套的入门练习小结B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点;所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的

45、索引；B+树总是到叶子结点才命中；B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3;14、最小生成树算法之Prim算法（C+实现）在无向带权连通图G中，如果一个连通子树包含所有顶点，并且连接这些顶点的边权之和最小，那么这个连通子图就是G的最小生成树。求最小生成树的一个常见算法是Prim算法，该算法的基本思想是：1）设置两个集合V和S,任意选择一个顶点作为起始顶点，将起始顶点放入集合S,其余顶点存入集合V中；S和V中边(即为最小生成树的中的一2)然后使用贪心策略，选择一条长度最短并且端点分别在条边)，将这条边在V中的端点加入到集合S中；3)循环执行第2)

46、步直到S中包含了所有顶点。O(NA2)的时间复杂根据以上思想我们很快可以给出一个O(NA3)的算法，即选择一条最短边需要度，具体实现代码如下：.，n，c皿为(i，j)的权，打印最小生成树的每条边*/voidprim(intcMAXVEXMAXVEX,intn)inti,j,k,min,lowcostMAXVEX,closestMAXVEX;for(i=2;i=n;i+)/*从顶点1开始*/lowcosti=c1i;closesti=1;closest1=0;for(i=2;i=n;i+)/*从U之外求离U中某一顶点最近的顶点*/min=MAXCOST;j=1;k=i;while(j=n)if(

47、lowcostjmin=lowcostj;k=j；j+；printf(%d,%d)”,closestk,k);/*打印边*/closestk=0;/*k假如到U中*/for(j=2;jif(closestj!=0&ckjLOWCOSTJ)lowcostj=ckj;closestj=k;问题：1）为何两个for循环都是从下标2开始的？尤其是第二个想不通。答：因为Prim算法可以任选起点，通常选定点1为起点，也就是说点1一开始就在U里面了,自然不必出现在第二个循环（在V-U中寻找点）中。2） lowcost数组顾名思义知道是存放最小代价信息的数组，但是具体的说lowcost放着是什么的最小代价，比

48、如lowcosti=c1i;表示的是什么意思（我要带i的语言描述）?答：存放的是当前从点集U到点集V-U的最短边长，lowcosti=c1i是初始化，开始时点集U中只有点1,因此当前点集U到点集V-U的各最短边长lowcosti就等于点1到点i的边权。3） closesti=1又是什么含意呢？答：closesti记录对应lowcosti的边的起点，因为lowcosti是当前终点为i的各条边中的最小值,再加上一个closesti记录起点，就能确定最小生成树的边了。closesti=1是初始化，自然每一个边都是从点1出发的。?4）求教第二个for循环的整层循环是写什么，我要每一行的注释。到底是在作什么答:for(i=