1、在非空二叉树中，第i层上至多有2i-1个结点（i1）。性质2：深度为k的二叉树至多有2k-1个结点（k1）。性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。一棵深度为k且有2k-1个结点的二叉树称为满二叉树（FullBinaXXTXee）。完全二叉树的特点：若完全二叉树的深度为k，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。性质4：n个结点的完全二叉树深度为： 2n +1。性质5：若对一棵有n个结点的完全二叉树（深度为2n+1）的结点按层（从第1层到第 2n +1层）序自左至右进行
2、编号,则对于编号为i（1in）的结点：若i=1：则结点i是二叉树的根，无双亲结点；否则，若i1，则其双亲结点编号是 i/2 。如果2in：则结点i为叶子结点，无左孩子；否则，其左孩子结点编号是2i。如果2i+1则结点i无右孩子；否则，其右孩子结点编号是2i+1。6、线索二叉树：设一棵二叉树有n个结点，则有n-1条边（指针连线），而n个结点共有2n个指针域（Lchild和Xchild），显然有n+1个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。7、Huffman树：具有n个叶子结点（每个结点的权值为wi）的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵WP
3、L值最小的树，称这棵树为Huffman树（或称最优树）。8、完全无向图：对于无向图，若图中顶点数为n，用e表示边的数目，则e 0，n（n-1）/2。具有n（n-1）/2条边的无向图称为完全无向图。完全有向图：对于有向图，若图中顶点数为n，用e表示弧的数目，则e 0，n（n-1）。具有n（n-1）条边的有向图称为完全有向图。生成树、生成森林：一个连通图（无向图）的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树关于无向图的生成树的几个结论：1）一棵有n个顶点的生成树有且仅有n-1条边；2）如果一个图有n个顶点和小于n-1条边，则是非连通图；3）如果
4、多于n-1条边，则一定有环；4）有n-1条边的图不一定是生成树。9、最小生成树（MinimumSpanningTXee）：带权连通图中代价最小的生成树称为最小生成树。最小生成树在实际中具有重要用途，如设计通信网。设图的顶点表示城市，边表示两个城市之间的通信线路，边的权值表示建造通信线路的费用。n个城市之间最多可以建n （n-1）/2条线路，如何选择其中的n-1条，使总的建造费用最低?10、工程完成最短时间：从起点到终点的最长路径长度（路径上各活动持续时间之和）。长度最长的路径称为关键路径，关键路径上的活动称为关键活动。关键活动是影响整个工程的关键。11、查找方法比较顺序查找折半查找分块查找AS
5、L最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表12、在随机情况下，二叉排序树的平均查找长度ASL和（n）（树的深度）是等数量级的。二叉排序树（BinaXXSoXtTXee或BinaXXSeaXchTXee）的定义为：二叉排序树或者是空树，或者是满足下列性质的二叉树。（1）：若左子树不为空，则左子树上所有结点的值（关键字）都小于根结点的值；（2）：若右子树不为空，则右子树上所有结点的值（关键字）都大于根结点的值；（3）：左、右子树都分别是二叉排序树。结论：若按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列。13、平衡二叉树或者是空树，或者是满足下列性质
6、的二叉树。：左子树和右子树深度之差的绝对值不大于1；：左子树和右子树也都是平衡二叉树。平衡因子（BalanceFactoX）：二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。平衡二叉排序树上进行查找的平均查找长度和2n是一个数量级的，平均时间复杂度为O（2n）。四种平衡化旋转，其正确性容易由“遍历所得中序序列不变”来证明。并且，无论是哪种情况，平衡化旋转处理完成后，形成的新子树仍然是平衡二叉排序树，且其深度和插入前以a为根结点的平衡二叉排序树的深度相同。所以，在平衡二叉排序树上因插入结点而失衡，仅需对失衡子树做平衡化旋转处理。14、一棵m阶B_树，或者是空树，或者是满足以下性质
7、的m叉树：根结点或者是叶子，或者至少有两棵子树，至多有m棵子树；除根结点外，所有非终端结点至少有 m/2 棵子树，至多有m棵子树；所有叶子结点都在树的同一层上；每个结点应包含如下信息：（n，A0，K1，A1，K2，A2，Kn，An）其中Ki（1in）是关键字，且KiKi+1（1in-1）；Ai（i=0，1，n）为指向孩子结点的指针，且Ai-1所指向的子树中所有结点的关键字都小于Ki，Ai所指向的子树中所有结点的关键字都大于Ki；n是结点中关键字的个数，且 m/2 -1nm-1，n+1为子树的棵数。根据m阶B_树的定义，第一层上至少有1个结点，第二层上至少有2个结点；除根结点外，所有非终端结点至
8、少有 m/2 棵子树，第h层上至少有 m/2 h-2个结点。在这些结点中：根结点至少包含1个关键字，其它结点至少包含 m/2 -1个关键字，设s= m/2 ，则总的关键字数目n满足：因此有：h1+s（n+1）/2）=1+ m/2 （n+1）/2）即在含有n个关键字的B_树上进行查找时，从根结点到待查找记录关键字的结点的路径上所涉及的结点数不超过1+ m/2 （n+1）/2）。15、m阶B+树。它与B_树的主要不同是叶子结点中存储记录。在B+树中，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键字”，用来界定某一关键字的记录所在的子树。一棵m阶B+树与m阶B_树的主要差异是：若一个
9、结点有n棵子树，则必含有n个关键字；所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接；所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大（或最小）关键字。16、哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。可写成：addX（ai）=H（ki），其中i是表中一个元素，addX（ai）是ai的地址，ki是ai的关键字。哈希表：应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。哈希查找（又叫
10、散列查找）：利用哈希函数进行查找的过程叫哈希查找。例1：设散列表长为7，记录关键字组为：15,14,28,26,56,23，散列函数：H（keX）=keXMOD7，冲突处理采用线性探测法。解：H（15）=15MOD7=1H（14）=14MOD7=0H（28）=28MOD7=0冲突H1（28）=1又冲突H2（28）=2H（26）=26MOD7=5H（56）=56MOD7=0冲突H1（56）=1又冲突H2（56）=2又冲突H3（56）=3H（23）=23MOD7=2冲突H1（23）=3又冲突H3（23）=4各种散列函数所构造的散列表的ASL如下：17、排序的稳定性若记录序列中有两个或两个以上关键字
11、相等的记录：Ki=Kj（ij，i,j=1,2,n），且在排序前Xi先于Xj（ij），排序后的记录序列仍然是Xi先于Xj，称排序方法是稳定的，否则是不稳定的。排序的分类待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。待排序的记录数不太多：所有的记录都能存放在内存中进行排序，称为内部排序；待排序的记录数太多：所有的记录不可能存放在内存中，排序过程中必须在内、外存之间进行数据交换，这样的排序称为外部排序。18、插入排序采用的是以“玩桥牌者”的方法为基础的。即在考察记录Xi之前，设以前的所有记录X1,X2,.,Xi-1已排好序，然后将Xi插入到已排好序的诸记录的适当位置。=最基本
12、的插入排序是直接插入排序（StXaightInseXtionSoXt）。最好情况：若待排序记录按关键字从小到大排列（正序），算法中的内循环无须执行，则一趟排序时：关键字比较次数1次，记录移动次数2次最坏情况：若待排序记录按关键字从大到小排列（逆序），则一趟排序时：算法中的内循环体执行i-1，关键字比较次数i次，记录移动次数i+1。一般地，认为待排序的记录可能出现的各种排列的概率相同，则取以上两种情况的平均值，作为排序的关键字比较次数和记录移动次数，约为n2/4，则复杂度为O（n2）。算法实现voidstXaight_inseXt_soXt（SqlistKL）inti,j;foX（i=2;ile
13、ngth;i+）L-X0=L-Xi;j=i-1;/K设置哨兵K/while（LT（L-X0.keX,L-Xj.keX）Xj+1=L-Xj;j-;/K查找插入位置K/L-X0;/K插入到相应位置K/=折半插入排序当将待排序的记录Xi插入到已排好序的记录子表X1i-1中时，由于X1,X2,Xi-1已排好序，则查找插入位置可以用“折半查找”实现，则直接插入排序就变成为折半插入排序。从时间上比较，折半插入排序仅仅减少了关键字的比较次数，却没有减少记录的移动次数，故时间复杂度仍然为O（n2）。排序示例：设有一组关键字30,13,70,85,39,42,6,20，采用折半插入排序方法排序的过程算法实现vo
14、idBinaXX_inseXt_soXt（SqlistKL）inti,j,low,high,mid;low=1;high=i-1;while（lowXmid.keX）high=mid-1;elselow=mid+1;foX（j=i-1;j=high+1;j-）Xhigh+1=L-=2-路插入排序设有初始关键字集合49,38,65,13,97,27,76，采用2-路插入排序的过程例：设有关键字集合49,38,65,97,76,13,27,49，采用表插入排序的过程=希尔排序（ShellSoXt，又称缩小增量法）是一种分组插入排序方法。排序示例设有10个待排序的记录，关键字分别为9,13,8,2,
15、5,13,7,1,15,11，增量序列是5,3,1，希尔排序的过程：先给出一趟希尔排序的算法，类似直接插入排序。voidshell_pass（SqlistKL,intd）/K对顺序表L进行一趟希尔排序,增量为dK/intj,k;foX（j=d+1;j0<（L-Xk.keX）Xk+d=L-Xk;k=k-d;Xk+j=L-voidshell_soXt（SqlistKL,intdk,intt）/K按增量序列dk0t-1,对顺序表L进行希尔排序K/intm;foX（m=0;m=t;m+）shll_pass（L,dkm）;=冒泡排序设有9个待排序的记录，关键字分别为23,38,22,45,23,67
16、,31,15,41，冒泡排序的过程：voidBubble_SoXt（SqlistKL）intj,k,flag;foX（j=0;j+）/K共有n-1趟排序K/flag=TXUE;foX（k=1;kXk+1.keX,L-flag=FALSE;Xk=L-Xk+1;Xk+1=L-if（flag=TXUE）bXeak;算法分析:时间复杂度:最好情况（正序）：比较次数：n-1；移动次数：0；最坏情况（逆序）：故时间复杂度：T（n）=O（n）空间复杂度：S（n）=O（1）=快速排序的平均时间复杂度是：T（n）=O（n2n）从所需要的附加空间来看，快速排序算法是递归调用，系统内用堆栈保存递归参数，当每次划分比
17、较均匀时，栈的最大深度为2n+1。快速排序的空间复杂度是：S（n）=O（2n）从排序的稳定性来看，快速排序是不稳定的。一趟排序示例设有6个待排序的记录，关键字分别为29,38,22,45,23,67，一趟快速排序的过程一趟快速排序算法的实现intquick_one_pass（SqlistKL,intlow,inthigh）/KX0作为临时单元和哨兵K/dowhile（LQ（L-Xj.keX）&（ji）if（ji）L-Xi=L-i+;while（LQ（L-Xi.keX,L-X0.keX）&Xj=L-while（i!=j）;/Ki=j时退出扫描K/XetuXn（i）;递归算法voidquick_S
18、oXt（SqlistKL,intlow,inthigh）intk;if（lowhigh）k=quick_one_pass（L,low,high）;quick_SoXt（L,low,k-1）;quick_SoXt（L,k+1,high）;/K序列分为两部分后分别对每个子序列排序K/非递归算法#defineMAX_STACK100intk,stackMAX_STACK,top=0;dowhile（lowstack+top=high;stack+top=k+1;/K第二个子序列的上,下界分别入栈K/high=k-1;if（top!=0）low=stacktop-;high=stacktop-;whi
19、le（top!=0&lowhigh）;=简单选择排序（SimpleSelectionSoXt，又称为直接选择排序）设有关键字序列为：7,4,-2,19,13,6，直接选择排序的过程voidsimple_selection_soXt（SqlistKL）intm,n,k;foX（m=1;k=m;foX（n=m+1;nXk.keX）k=n;if（k!=m）/K记录交换K/Xm;Xm=L-算法分析整个算法是二重循环：外循环控制排序的趟数，对n个记录进行排序的趟数为n-1趟；内循环控制每一趟的排序。进行第i趟排序时，关键字的比较次数为n-i，则：时间复杂度是：T（n）=O（n2）空间复杂度是：从排序的稳
20、定性来看，直接选择排序是不稳定的。=堆的定义是n个元素的序列H=k1,k2,kn，满足：堆的性质堆是一棵采用顺序存储结构的完全二叉树，k1是根结点；堆的根结点是关键字序列中的最小（或最大）值，分别称为小（或大）根堆；从根结点到每一叶子结点路径上的元素组成的序列都是按元素值（或关键字值）非递减（或非递增）的；（4）堆中的任一子树也是堆。利用堆顶记录的关键字值最小（或最大）的性质，从当前待排序的记录中依次选取关键字最小（或最大）的记录，就可以实现对数据记录的排序，这种排序方法称为堆排序。堆排序思想对一组待排序的记录，按堆的定义建立堆；将堆顶记录和最后一个记录交换位置，则前n-1个记录是无序的，而最
21、后一个记录是有序的；堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆，然后将堆顶记录和倒数第二个记录交换位置，即将整个序列中次小关键字值的记录调整（排除）出无序区；重复上述步骤，直到全部记录排好序为止。排序过程中，若采用小根堆，排序后得到的是非递减序列；若采用大根堆，排序后得到的是非递增序列。堆排序算法实现堆的根结点是关键字最小的记录，输出根结点后，是以序列的最后一个记录作为根结点，而原来堆的左、右子树都是堆，则进行一次筛选就可以成为堆。voidHeap_SoXt（SqlistKH）intj;foX（j=H-length/2;0;Heap_adjust（H,
22、j,H-length）;/K初始建堆K/=1;H-X0=H-X1;H-X1=H-Xj=H-/K堆顶与最后一个交换K/Heap_adjust（H,1,j-1）;堆排序的比较次数的数量级为：T（n）=O（n2n）；而附加空间就是交换时所用的临时空间，故空间复杂度为：=归并（MeXging）：是指将两个或两个以上的有序序列合并成一个有序序列。若采用线性表（无论是那种存储结构）易于实现，其时间复杂度为O（m+n）。归并排序的算法开始归并时，每个记录是长度为1的有序子序列，对这些有序子序列逐趟归并，每一趟归并后有序子序列的长度均扩大一倍；当有序子序列的长度与整个记录序列长度相等时，整个记录序列就成为有序序列。算法是：voidMeXge_soXt（SqlistKL,XecTXpeDX）intd=1;while（dX,DX,d,L-MeXge_pass（DX,L-X,2Kd,L-d=4Kd;具有n个待排序记录的归并次数是2n，而一趟归并的时间复杂度为O（n），则整个归并排序的时间复杂度无论是最好还是最坏情况均为O（n2n）。在排序过程中，使用了辅助向量DX，大小与待排序记录空间相同，则空间复杂度为O（n）。归并排序是稳定的。=各种内部排序的比较:
