软考程序员常考知识点复习

20XX年软考程序员常考知识点复习笔记第一章常考基础知识必会A.排序：排序有几种，各种排序的比较，哪些排序是稳定的，快排的算法;B.查找：哈希查找、二叉树查找、折半查找的对比，哈希映射和哈希表的区别?C.链表和数组的区别，在什么情况下用链表什么情况下用数组?D.栈和队列的区别?E.多态，举例说明;overload和override的区别?F.字符串有关的函数，比如让你写一个拷贝字符串的函数啊，或者字符串反转啊什么的。strcpy和memcpy?G.继承、多继承?H.面向对象有什么好处?I.说说static的与众不同之处，如果一个变量被声明为static，它会被分配在哪里?在什么时候分配空间等?J.什么是虚函数、纯虚函数、虚的析构函数，用途?K.内存泄漏及解决方法?网络部分：OSI模型7层结构，TCP/IP模型结构?B.TCP/UDP区别?C.TCP建立连接的步骤?D.香农定理?20XX年软考程序员常考知识点复习笔记第二章二叉树三种遍历的非递归算法(背诵版)1.先序遍历非递归算法#definemaxsize100

typedefstruct

{

BitreeElem[maxsize];

inttop;

}SqStack;voidPreOrderUnrec(Bitreet)

{

SqStacks;

StackInit(s);

p=t;

while(p!=null||!StackEmpty(s))

{

while(p!=null)

//遍历左子树

{

visite(p->data);

push(s,p);

p=p->lchild;

}//endwhile

if(!StackEmpty(s))

//通过下一次循环中的内嵌while实现右子树遍历

{

p=pop(s);

p=p->rchild;

}//endif

}//endwhile

}//PreOrderUnrec20XX年软考程序员常考知识点复习笔记第三章2、线性表(1)性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。(2)单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。(3)单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。3、栈与队列你可以问一下自己是不是已经知道了以下几点：(1)栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据(请注意包括：存和取两部分)的特点。(2)递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。(3)栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。(4)循环队列中判队空、队满条件，循环队列中入队与出队(循环队列在插入时也要判断其是否已满，删除时要判断其是否已空)算法。【循环队列的队空队满条件为了方便起见，约定：初始化建空队时，令front=rear=0,当队空时：front=rear，当队满时：front=rear亦成立，因此只凭等式front=rear无法判断队空还是队满。有两种方法处理上述问题：(1)另设一个标志位以区别队列是空还是满。(2)少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。队空时：front=rear，队满时：(rear+1)%maxsize=front】如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。循环队列的主要操作：(1)创建循环队列(2)初始化循环队列(3)判断循环队列是否为空(4)判断循环队列是否为满(5)入队、出队//空出头尾之间的一个元素不用#include#include#defineMAXSIZE100typedefstruct{intelem[MAXSIZE];intfront,rear;}Quque;//定义队头intinitQue(Quque**q)//初始化{(*q)->front=0;(*q)->rear=0;}intisFull(Quque*q){if(q->front==(q->rear+1)%MAXSIZE)//判满(空出一个元素不用)刘勉刚return1;elsereturn0;}intinsertQue(Quque**q,intelem){if(isFull(*q))return-1;(*q)->elem[(*q)->rear]=elem;(*q)->rear=((*q)->rear+1)%MAXSIZE;//插入return0;}intisEmpty(Quque*q){if(q->front==q->rear)//判空return1;elsereturn0;}intdeleteQue(Quque**q,int*pelem){if(isEmpty(*q))return0;*pelem=(*q)->elem[(*q)->front];(*q)->front=((*q)->front+1)%MAXSIZE;return0;}20XX年软考程序员常考知识点复习笔记第四章4、串串一章需要攻破的主要堡垒有：1.串的基本概念，串与线性表的关系(串是其元素均为字符型数据的特殊线性表)，空串与空格串的区别，串相等的条件;2.串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。3.顺序串与链串及块链串的区别和联系，实现方式。4.KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足，明确next数组需要改进。可能进行的考查方式是：求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。5、多维数组和广义表矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。6、树与二叉树树一章的知识点包括：二叉树的概念、性质和存储结构，二叉树遍历的三种算法(递归与非递归)，在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。(1)二叉树的概念、性质和存储结构考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树(左右子树无序)的区别;考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：A.第i层的最多结点数，B.深度为k的二叉树的最多结点数，C.n0=n2+1的性质，D.n个结点的完全二叉树的深度，E.顺序存储二叉树时孩子结点与父结点之间的换算关系(root从1开始，则左为：2*i，右为：2*i+1)。二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。(2)二叉树的三种遍历算法这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来(比如：求叶子个数)，所以，掌握了三种遍历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。(3)可在三种遍历算法的基础上改造完成的其它二叉树算法：求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。(4)线索二叉树：线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题(如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题)。(5)最优二叉树(哈夫曼树)：最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题。(6)树与森林：二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的!即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树。树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根(对于森林而言称作：先序与后序遍历)。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟(称孩子兄弟链表)，而森林也是利用二叉链表存储孩子及兄弟。20XX年软考程序员常考知识点复习笔记第五章9、内部排序考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标(时间复杂度)能否了如指掌。排序方法分类有：插入、选择、交换、归并、计数等五种排序方法。(1)插入排序中又可分为：直接插入、折半插入、2路插入(?)、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找，希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。(2)交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。(3)选择排序可以分为：简单选择、树选择、堆排序。选择排序相对于前面几种排序算法来说，难度大一点。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数;树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大(小)者，最终选出最小(大)数;而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。(4)归并排序，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。(5)基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排序(扑克牌排序)，链式排序(整数排序)。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的。稳定性分析排序算法的稳定性，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。稳定性的好处：若排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些(个人感觉，没有证实)。分析一下常见的排序算法的稳定性，每个都给出简单的理由。(1)冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。(2)选择排序选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列58529，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。(3)插入排序插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。(4)快速排序快速排序有两个方向，左边的i下标一直往右走，当a[i]<=a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j]>a[center_index]。如果i和j都走不动了，i<=j,交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为53343891011，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。(5)归并排序归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏?没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。(6)基数排序基数排序是按照低位先排序，然后收集;再按照高位排序，然后再收集;依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。(7)希尔排序(shell)希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快;当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。(8)堆排序我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1,n/2-2,...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。20XX年软考程序员常考知识点复习笔记第六章10、OSI模型7层结构，TCP/IP模型结构?osi参考模型osi参考模型中的数据封装过程下面的图表试图显示不同的TCP/IP和其他的协议在最初OSI模型中的位置：7应用层例如HTTP、SMTP、SNMP、FTP、Telnet、SIP、SSH、NFS、RTSP、XMPP、Whois、ENRP6表示层例如XDR、ASN.1、SMB、AFP、NCP5会话层例如ASAP、TLS、SSH、ISO8327/CCITTX.225、RPC、NetBIOS、ASP、Winsock、BSDsockets4传输层例如TCP、UDP、RTP、SCTP、SPX、ATP、IL3网络层例如IP、ICMP、IGMP、IPX、BGP、OSPF、RIP、IGRP、EIGRP、ARP、RARP、X.252数据链路层例如Ethernet、Tokenring、HDLC、Framerelay、ISDN、ATM、802.11WiFi、FDDI、PPP1物理层例如wire、radio、fiberoptic、Carrierpigeontcp/ip参考模型tcp/ip参考模型分为四个层次：应用层、传输层、网络互连层和主机到网络层：tcp/ip参考模型的层次结构通常人们认为OSI模型的最上面三层(应用层、表示层和会话层)在TCP/IP组中是一个应用层。由于TCP/IP有一个相对较弱的会话层，由TCP和RTP下的打开和关闭连接组成，并且在TCP和UDP下的各种应用提供不同的端口号，这些功能能够被单个的应用程序(或者那些应用程序所使用的库)增加。与此相似的是，IP是按照将它下面的网络当作一个黑盒子的思想设计的，这样在讨论TCP/IP的时候就可以把它当作一个独立的层。4应用层(OSI5到7层)例如HTTP、FTP、DNS(如BGP和RIP这样的路由协议，尽管由于各种各样的原因它们分别运行在TCP和UDP上，仍然可以将它们看作网络层的一部分)3传输层(OSI4和5层)例如TCP、UDP、RTP、SCTP(如OSPF这样的路由协议，尽管运行在IP上也可以看作是网络层的一部分)2网络互连层(OSI3层)对于TCP/IP来说这是因特网协议(IP)(如ICMP和IGMP这样的必须协议尽管运行在IP上，也仍然可以看作是网络互连层的一部分;ARP不运行在IP上)1网络接口层(OSI1和2层)例如Ethernet、Wi-Fi、MPLS等。应用层该层包括所有和应用程序协同工作，利用基础网络交换应用程序专用的数据的协议。应用层是大多数普通与网络相关的程序为了通过网络与其他程序通信所使用的层。这个层的处理过程是应用特有的;数据从网络相关的程序以这种应用内部使用的格式进行传送，然后被编码成标准协议的格式。一些特定的程序被认为运行在这个层上。它们提供服务直接支持用户应用。这些程序和它们对应的协议包括HTTP(TheWorldWideWeb)、FTP(文件传输)、SMTP(电子邮件)、SSH(安全远程登陆)、DNS(名称<->IP地址寻找)以及许多其他协议。一旦从应用程序来的数据被编码成一个标准的应用层协议，它将被传送到IP栈的下一层。在传输层，应用程序最常用的是TCP或者UDP，并且服务器应用程序经常与一个公开的端口号相联系。服务器应用程序的端口由InternetAssignedNumbersAuthority(IANA)正式地分配，但是现今一些新协议的开发者经常选择它们自己的端口号。由于在同一个系统上很少超过少数几个的服务器应用，端口冲突引起的问题很少。应用软件通常也允许用户强制性地指定端口号作为运行参数。连结外部的客户端程序通常使用系统分配的一个随机端口号。监听一个端口并且然后通过服务器将那个端口发送到应用的另外一个副本以建立对等连结(如IRC上的dcc文件传输)的应用也可以使用一个随机端口，但是应用程序通常允许定义一个特定的端口范围的规范以允许端口能够通过实现网络地址转换(NAT)的路由器映射到内部。每一个应用层(TCP/IP参考模型的最高层)协议一般都会使用到两个传输层协议之一：面向连接的TCP传输控制协议和无连接的包传输的UDP用户数据报文协议。20XX年软考程序员常考知识点复习笔记第七章11、数组和链表的优缺点数组，在内存上给出了连续的空间。链表，内存地址上可以是不连续的，每个链表的节点包括原来的内存和下一个节点的信息(单向的一个，双向链表的话，会有两个)。数组优于链表的:A.内存空间占用的少，因为链表节点会附加上一块或两块下一个节点的信息。但是数组在建立时就固定了。所以也有可能会因为建立的数组过大或不足引起内存上的问题。B.数组内的数据可随机访问，但链表不具备随机访问性。这个很容易理解，数组在内存里是连续的空间，比如如果一个数组地址从100到200，且每个元素占用两个字节，那么100-200之间的任何一个偶数都是数组元素的地址，可以直接访问。链表在内存地址可能是分散的。所以必须通过上一节点中的信息找能找到下一个节点。C.查找速度上。这个也是因为内存地址的连续性的问题，不罗索了。链表优于数组的:A.插入与删除的操作。如果数组的中间插入一个元素，那么这个元素后的所有元素的内存地址都要往后移动。删除的话同理。只有对数据的最后一个元素进行插入删除操作时，才比较快。链表只需要更改有必要更改的节点内的节点信息就够了。并不需要更改节点的内存地址。B.内存地址的利用率方面。不管你内存里还有多少空间，如果没办法一次性给出数组所需的要空间，那就会提示内存不足，磁盘空间整理的原因之一在这里。而链表可以是分散的空间地址。C.链表的扩展性比数组好。因为一个数组建立后所占用的空间大小就是固定的，如果满了就没法扩展，只能新建一个更大空间的数组;而链表不是固定的，可以很方便的扩展。20XX年软考程序员常考知识点复习笔记第八章12、C++操作符优先级:记忆方法：去掉一个最高的，去掉一个最低的，剩下的是一、二、三、赋值;双目运算符中，顺序为算术、关系和逻辑，移位和逻辑位插入其中。--摘自《C语言程序设计实用问答》问题：如何记住运算符的15种优先级和结合性?解答：C语言中运算符种类比较繁多，优先级有15种，结合性有两种。如何记忆两种结合性和15种优先级?下面讲述一种记忆方法。结合性有两种，一种是自左至右，另一种是自右至左，大部分运算符的结合性是自左至右，只有单目运算符、三目运算符的赋值运算符的结合性自右至左。优先级有15种，记忆方法如下：记住一个最高的：构造类型的元素或成员以及小括号。记住一个最低的：逗号运算符。剩余的是一、二、三、赋值——意思是单目、双目、三目和赋值运算符。在诸多运算符中，又分为：算术、关系、逻辑。两种位操作运算符中，移位运算符在算术运算符后边，逻辑位运算符在逻辑运算符的前面。再细分如下：算术运算符*，/，%高于+，-。关系运算符中：>，>=，<和<=高于==，!=。逻辑运算符中，除了逻辑求反(!)是单目外，逻辑与(&&)高于逻辑或(||)。逻辑位运算符中，除了逻辑按位求反(~)外，按位与(&)高于按位半加(^)，高于按位或(|)。PrecedenceOperatorDescriptionExampleOverloadableAssociativity1::ScoperesolutionoperatorClass::age=2;nolefttoright2()Functioncallprintf(“Helloworld\n”);yeslefttoright()Memberinitalizationc_tor(intx,inty):_x(x),_y(y*10){}yes[]Arrayaccessarray[4]=2;yes->Memberaccessfromapointerptr->age=34;yes.Memberaccessfromanobjectobj.age=34;no++Post-incrementfor(inti=0;i<10;i++)cout<<i;yes--Post-decrementfor(inti=10;i>0;i--)cout<<i;yesdynamic_castRuntime-checkedtypeconversionY&y=dynamic_cast<y&>(x);</y&>nostatic_castUncheckedtypeconversionY&y=static_cast<y&>(x);</y&>noreinterpret_castReinterpretingtypeconversionintconst*p=reinterpret_cast(0x1234);noconst_castCastaway/Addconstnessint*q=const_cast(p);notypeidGettypeinformationstd::type_infoconst&t=typeid(x);no3!Logicalnegationif(!done)...yesrighttoleftnotAlternatespellingfor!~Bitwisecomplementflags=~flags;yescomplAlternatespellingfor~++Pre-incrementfor(i=0;i<10;++i)cout<<i;yes--Pre-decrementfor(i=10;i>0;--i)cout<<i;yes-Unaryminusinti=-1;yes+Unaryplusinti=+1;yes*Dereferenceintdata=*intPtr;yes&Addressofint*intPtr=&data;yessizeofSize(ofthetype)oftheoperandinbytessize_ts=sizeof(int);nonewDynamicmemoryallocationlong*pVar=newlong;yesnew[]Dynamicmemoryallocationofarraylong*array=newlong[20];yesdeleteDeallocatingthememorydeletepVar;yesdelete[]Deallocatingthememoryofarraydelete[]array;yes(type)Casttoagiventypeinti=(int)floatNum;yes4->*Memberpointerselectorptr->*var=24;yeslefttoright.*Memberobjectselectorobj.*var=24;no5*Multiplicationinti=2*4;yeslefttoright/Divisionfloatf=10.0/3.0;yes%Modulusintrem=4%3;yes6+Additioninti=2+3;yeslefttoright-Subtractioninti=5-1;yes7<<Bitwiseshiftleftintflags=33<<1;yeslefttoright>>Bitwiseshiftrightintflags=33>>1;yes8<Comparisonless-thanif(i<42)...yeslefttoright<=Comparisonless-than-or-equal-toif(i<=42)...yes>Comparisongreater-thanif(i>42)...yes>=Comparisongreater-than-or-equal-toif(i>=42)...yes9==Comparisonequal-toif(i==42)...yeslefttorighteqAlternatespellingfor==!=Comparisonnot-equal-toif(i!=42)...yesnot_eqAlternatespellingfor!=10&BitwiseANDflags=flags&42;yeslefttorightbitandAlternatespellingfor&11^BitwiseexclusiveOR(XOR)flags=flags^42;yeslefttorightxorAlternatespellingfor^12|Bitwiseinclusive(normal)ORflags=flags|42;yeslefttorightbitorAlternatespellingfor|13&&LogicalANDif(conditionA&&conditionB)...yeslefttorightandAlternatespellingfor&&14||LogicalORif(conditionA||conditionB)...yeslefttorightorAlternatespellingfor||15?:Ternaryconditional(if-then-else)inti=a>b?a:b;norighttoleft16=Assignmentoperatorinta=b;yesrighttoleft+=Incrementandassigna+=3;yes-=Decrementandassignb-=4;yes*=Multiplyandassigna*=5;yes/=Divideandassigna/=2;yes%=Moduloandassigna%=3;yes&=BitwiseANDandassignflags&=new_flags;yesand_eqAlternatespellingfor&=^=Bitwiseexclusiveor(XOR)andassignflags^=new_flags;yesxor_eqAlternatespellingfor^=|=BitwisenormalORandassignflags|=new_flags;yesor_eqAlternatespellingfor|=<<=Bitwiseshiftleftandassignflags<<=2;yes>>=Bitwiseshiftrightandassignflags>>=2;yes17throwthrowexceptionthrowEClass(“Message”);no18,Sequentialevaluationoperatorfor(i=0,j=0;i<10;i++,j++)...yeslefttoright20XX年软考程序员常考知识点复习笔记第九章13、B树、B-树、B+树、B*树、红黑树和trie树(1)B树:即二叉搜索树.1.所有非叶子结点至多拥有两个儿子(Left和Right);2.所有结点各存储一个关键字;3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树;如：B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中;否则，如果查询关键字比结点关键字小，就进入左儿子;如果比结点关键字大，就进入右儿子;如果左儿子或右儿子的指针为空，则报告找不到相应的关键字;如果B树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡)，那么B树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是，改变B树结构(插入与删除结点)不需要移动大段的内存数据，甚至通常是常数开销;如：但B树在经过多次插入与删除后，有可能导致不同的结构：右边也是一个B树，但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的树结构索引;所以，使用B树还要考虑尽可能让B树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题;实际使用的B树都是在原B树的基础上加上平衡算法，即“平衡二叉树”;如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键;平衡算法是一种在B树中插入和删除结点的策略;(2)B-树是一种多路搜