数据结构期末复习题纲

复习提纲第一章数据结构概述基本概念与术语（P3）1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科.2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合2．数据元素是数据的基本单位3．数据对象相同性质的数据元素的集合4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作.（1）数据的逻辑结构指数据元素之间固有的逻辑关系.（2）数据的存储结构指数据元素及其关系在计算机内的表示( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等.5.时间复杂度分析--------------------------------------------------------------------------------------------------------------------1、名词解释：数据结构、二元组2、根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型。

3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。

4、以下程序段的时间复杂度为___O(N2)_____。

int i,j,x;for(i=0;i<n:i++) n+1for(j=0;j<n;j++) n+1x+=i;------------------------------------------------------------------------------------------------------------------ 第二章线性表1.顺序表结构由n(n>=0)个具有相同性质的数据元素a1,a2,a3……,an组成的有穷序列//顺序表结构#define MAXSIZE 100typedef int DataType;Typedef struct{DataType items[MAXSIZE];Int length;}Sqlist,*LinkList;//初始化链表void InitList(LinkList *L){(*L)=(LinkList)malloc(sizeof(LNode));if(!L){cout<<”初始化失败!”;return;(*L)->next=NULL;}//插入数据void InsertList(LinkList L,int pos,DataType x){ LinkList p=L,q;int i=0;while(p&&i<pos-1){p=p->next;i++;}if(!p||i>pos-1){cout<<”插入位置错误”;return;}InitList(&q);q->next=p->next;p->next=q;q->data=x;}//销毁链表void DestoryList(LinkList L){LinkList t;while(L){t=L;L=L->next;free(t);}}//遍历链表void TraverseList(LinkList L){LinkList t=L;while(L){t=t->next;cout<<t->data<<” ”;}cout<<endl;}//删除元素void DeleteList(LinkList L,int pos){LinkList p=L,q;int i=0;while(p&&i<pos-1){p=p->next;i++;if(!p||i>pos-1){cout<<”删除位置错误!!”;return;}q=p->next;p->next=q->next;free(q):}第三章栈和队列1.栈（1）栈的结构与定义（2）顺序栈操作算法：入栈、出栈、判断栈空等（3）链栈的结构与定义2.队列（1）队列的定义----------------------------------------------------------------------------------------------------------------1、一个栈的入栈序列为“ABCDE”，则以下不可能的出栈序列是（）A. BCDAEB. EDACBC. BCADED. AEDCB2、栈的顺序表示仲，用TOP表示栈顶元素，那么栈空的条件是（）A. TOP==STACKSIZEB. TOP==1C. TOP==0D. TOP==-13、允许在一端插入，在另一端删除的线性表称为____队列____。

数据结构复习资料复习提纲知识要点归纳数据结构复习资料：复习提纲知识要点归纳一、数据结构概述1. 数据结构的定义和作用2. 常见的数据结构类型3. 数据结构与算法的关系二、线性结构1. 数组的概念及其特点2. 链表的概念及其分类3. 栈的定义和基本操作4. 队列的定义和基本操作三、树结构1. 树的基本概念及定义2. 二叉树的性质和遍历方式3. 平衡二叉树的概念及应用4. 堆的定义和基本操作四、图结构1. 图的基本概念及表示方法2. 图的遍历算法：深度优先搜索和广度优先搜索3. 最短路径算法及其应用4. 最小生成树算法及其应用五、查找与排序1. 查找算法的分类及其特点2. 顺序查找和二分查找算法3. 哈希查找算法及其应用4. 常见的排序算法：冒泡排序、插入排序、选择排序、归并排序、快速排序六、高级数据结构1. 图的高级算法：拓扑排序和关键路径2. 并查集的定义和操作3. 线段树的概念及其应用4. Trie树的概念及其应用七、应用案例1. 使用数据结构解决实际问题的案例介绍2. 如何选择适合的数据结构和算法八、复杂度分析1. 时间复杂度和空间复杂度的定义2. 如何进行复杂度分析3. 常见算法的复杂度比较九、常见问题及解决方法1. 数据结构相关的常见问题解答2. 如何优化算法的性能十、总结与展望1. 数据结构学习的重要性和难点2. 对未来数据结构的发展趋势的展望以上是数据结构复习资料的复习提纲知识要点归纳。

希望能够帮助你进行复习和回顾，加深对数据结构的理解和掌握。

在学习过程中，要注重理论与实践相结合，多进行编程练习和实际应用，提高数据结构的实际运用能力。

祝你复习顺利，取得好成绩！。

考试题型选择题：21分填空题：18分判断题：15分简答题：26分算法题：20分什么是数据元素？组成数据的成分数据什么是数据项?什么是数据结构？是由数据元素依据某种逻辑联系组织起来的严格地说，数据元素与结点是一回事吗？no什么是算法的时间复杂度？程序运行从开始到结束所需要的时间什么是大O表示法？使用大O记号表示的算法的时间复杂度，称为算法的渐近时间复杂度。

什么是顺序存储结构？什么是链式存储结构？什么是顺序表？在顺序表上进行插入和删除操作的算法复杂度是多少？O(n)哪些算法的实施只能在顺序表上进行？什么是栈和队列？堆栈（栈）：限定插入和删除操作都在表同一端进行的线性表队列：限定在表的一端插入，在表的另一端删除的线性表怎样实现链式栈和链式队列？怎样判断一个出栈序列是否合法?因为对于出栈序列中的每一个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的怎样将中缀表达式转换成后缀表达式?（1）从左到右扫描中缀表达式，遇到#转（6）；（2）遇到操作数直接输出；（不进栈）（3）遇到“）”，则连续出栈输出，直到遇到“（”为止（“（”出栈但不输出）；否则（4）若是其它操作符，则与栈顶的操作符比较优先级；若优先级小于栈顶的优先级，则连续出栈输出，直到大于等于结束，操作符进栈；（5）转（1）；（6）输出栈中剩余操作符(#除外)。

什么是循环链表？循环链表是另一种形式的链式存贮结构。

它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

什么是循环队列？克服"假溢出"现象将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。

存储在其中的队列称为循环队列循环队列为空或满的条件是什么？当front==rear 时为空队列，当(rear+1) % MaxSize ==front 时为满队列满队列时实际仍有一个元素的空间未使用什么是单链表？每个节点都有一个指针域的链表叫单链表什么是带表头结点的单链表？链表的前面有个空表头为什么要引入表头结点？方便在表的最前面进行插入和删除什么是满二叉树？高度为h的二叉树恰好有2h –1个结点什么是完全二叉树？一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。

2010年复习提纲第一章数据、数据结构的概念；基本逻辑结构的种类；集合线性树形图状基本存储方式的种类；顺序链式散列索引算法、算法的时间复杂度以及其计算。

算法的五大特性：输入输出确定性有穷性有效性时间复杂度的计算：忽略常数与中间变量，循环套循环用乘法第二章线性表的概念；顺序存储和链接存储的线性表的数据结构、特性；顺序存储的特性：查找方便，不易扩充链接存储的特性：插入删除方便顺序存储和链接存储的线性表的基本算法：创建、插入、查找、删除等；链表的其他形式（带表头、循环、双向、双向循环等）的概念及基本算法（与一般链表的不同处）。

带表头：便于其后结点执行标准化操作循环：首尾相接双向：既可以查找前继又可以查找后继双向循环：结合以上两点链表逆转；第二章相关算法列举如下1.。

顺序线性表的插入Int sq_insert(int list[],int *p_n,int i,int x) { Int j;If(i<0||i>*p_n) return(1);If(*p_n==MAXSIZE) return(2);For(j=*p_n;j>I;j--)List[j]=list[j-1];List[i]=x;(*p_n)++;Return(0);} 2.顺序线性表的删除Int sq_delete(int list[],int *p_n,int i) {Int j;If(i<0||i>=*p_n) return(1);For(j=i+1;j<*p_n;j++)List[j-1]=list[j];(*p_n)--;Return(0);}3.链式线性表的创建NODE *create_link_list(int n){ int i;NODE *p,*q;NODE *p_head;if(n==0) return(NULL);p_head=new(NODE);p_head->data=-1;p=p_head;for(i=1;i<=n;i++){printf("请输入第%d个节点的值\n",i);q=new(NODE);scanf("%d",&(q->data));p->link=q;p=q;}q->link=NULL;return(p_head);/*返回的是假头*/ ※4．链式线性表的插入(i之后)Int insert(NODE* *p_head,int i,int a) { int n=0;NODE *p,*q,*r;p=*p_head;if(i<1) return(0);while((p!=NULL)&&(n<i)){If(p->data!=-1) n++;q=p;p=p->link;}r=new(NODE);r->data=a;r->link=q->link;q->link=r;}※5.链式线性表的删除int del(NODE* *p_head,int I) { NODE *p,*q;int n=0;p=*p_head;if(i<1) return(0);while((p!=NULL)&&(n<i)){If(p->data!=-1) n++;q=p;p=p->link;}if(p==NULL) return(0);q->link=p->link;delete(p);return(1);} 6．单链表的逆置NODE * reverse(NODE *head) {NODE *p,*q;P=head->next;Head->next=NULL;While(p){Q=p->next;p->next=head->next;head->next=p;p=q;}return(head);}7．试写一高效的算法，删除表中所有大于mink且小于maxk的元素Void Delete_between(int a[],int mink,int maxk){p=L;while(p->next->data<=mink) p=p->next;(本循环结束时p是最后一个不大于mink的元素)if(p->next)（如果还有比mink更大的元素）{q=p->next;while(q->data<maxk) q=q->next;（本循环结束时q 是第一个不小于maxk 的元素）p->next=q;}}第三章栈与队列的概念；栈：只允许在一端进行插入和删除的线性表队列：只允许在一端进行插入，且只允许在另一端进行删除的线性表顺序栈和链栈的数据结构与基本算法；顺序队列（尤其是循环队列）和链队列的数据结构与基本算法；栈的应用算法；如何判断顺序栈的空与满、如何判断循环队列的空与满；判断顺序栈的空与满：若top的初始值是-1 则判空条件是if(top==-1) 判满条件是if(top==MAXN)若top的初始值是0 则判空条件是if(top==0) 判满条件是if(top==MAXN-1)判断循环队列的空与满{Head=0,tail=0;判断循环队列的空与满的条件都是if(head==tail)}中缀表达式与后缀表达式规则以及两者间的转换。

复习提纲：第一章：1．数据结构的基本概念；2．数据结构的4类基本结构及其特性；3．存储结构的分类及特点；4．算法的时间复杂度计算；第二章：1．线性表的基本概念；2．线性表的顺序存储结构的特点和插入删除算法；3．顺序存储结构的应用；4．单循环链表的存储结构特点，链表空的判断方法、插入、删除结点算法实现，报数游戏算法实现；5．双链表的存储特点，插入、删除结点算法实现。

第三章：1．栈的特点、对同一序列根据栈的特点进行不同入栈、出栈操作所得结果的判断；栈的实现的相关操作；2．顺序栈的4各要素和相关操作关键语句；链栈的4个要素和相关操作关键语句；3．了解队列的特点和可执行的基本操作，并能做相关判断；4．顺序循环队列的队空、队满判断条件，入队、出队操作的相关关键语句；5．顺序循环队列中对同一序列根据队列进行不同的入队、出队操作后队头和队尾指针的变化判断。

第四章：1．串的定义、串长的定义和计算、子串个数计算（注意区分：子串与非空且不同于S本身的子串）；2．串的模式匹配（区分BF算法和KMP算法），掌握使用KMP算法计算next数组的值，并且要求掌握匹配过程（BF和KMP的匹配过程不同！）。

前三章程序重点掌握作业四、作业五、作业六、作业八、作业九第五章：1．特殊矩阵的压缩存储地址计算，稀疏矩阵的压缩存储结构图。

2．广义表的定义、区分原子和子表，求表头和表尾，深度和层次计算，存储结构图绘制；3．提供一广义表，写出通过head()和tail()操作求出某个原子的表达式。

4．注意：取表头时即广义表的第一个元素，外面不再加括号；而取表尾时，要将除表头元素外的其他元素一起用圆括号括起来，即将原广义表去掉表头；第六章：1．树的定义和相关基本术语；2．树的表示和各种存储结构的表示；3．二叉树的定义和结点形态；4．熟练使用二叉树的性质进行相关计算；5．掌握提供边集画树及树的存储结构图并将树转换为二叉树；6．根据后序遍历和中序遍历的序列画出二叉树直观图，并给出其先序遍历的序列，画出线索二叉树存储结构图；7．根据二叉树的顺序存储结构图，画出二叉树及二叉链存储结构图，并给出该二叉树转换后的森林。

数据结构复习提纲第一章绪论1．基本术语：数据，数据元素，数据对象，数据结构及其分类。

2．什么是算法？算法的特性。

3．时间复杂度及其简单计算。

第二章线性表1．线性表的定义，线性表的存储结构常有哪几种？各有何优缺点？2．顺序表的类型说明及其基本操作算法的实现3．链表结构的类型说明及其基本操作算法的实现。

表空条件，申请结点，插入，删除操作语句。

第三章栈和队列1．栈的定义及其特点。

队列的定义及其特点。

2．顺序栈的类型说明及其算法实现。

栈空，栈满条件，入栈出栈操作语句。

3．循环队列的类型说明及其算法实现。

队空，队满条件，入队出队操作，计算队列的长度语句。

第五章数组与广义表1．二维数组的两种存储方式及地址计算。

2．矩阵的压缩存储，对称矩阵，三角矩阵的地址计算。

3．什么是稀疏矩阵？稀疏矩阵的两种存储结构，算法的实现。

4．广义表的定义。

广义表的两种存储结构，广义表的表头，表尾计算第六章树和二叉树1．树的概念与定义。

2．二叉树。

满二叉树，完全二叉树的定义，二叉树的性质及其证明。

3．二叉树的存储结构及其类型说明。

4．二叉树的三种遍历及其递归算法实现。

5．树的三种存储结构。

6．树，森林与二叉树的转换。

7．哈夫曼树的定义。

哈夫曼树的构造及其哈夫曼编码。

第七章图1．图的定义及其术语。

2．图的存储结构。

邻接表，邻接矩阵。

3．图的深度，广度遍历及其应用4．最小生成树的两种构造算法。

5．什么是AOV网？拓扑排序的定义及其方法。

6．求关键路径的算法及其计算。

7．从源点到其余各顶点的最短路径的算法及其计算。

8．各对顶点的最短路径的算法及其计算。

第九章查找1．顺序表的查找算法及其算法实现ASL计算。

2．有序表的查找算法及其算法实现。

ASL计算3．二叉排序树的定义，特点，构造及其查找算法的实现ASL 计算。

4．B-树的定义，插入，删除，构造。

5．哈希函数，哈希冲突的定义。

构造哈希函数的方法，解决冲突的方法。

6．给出哈希函数，哈希冲突的解决方法，构造哈希表ASL计算。

数据结构复习大纲第一章绪论1. 数据结构的基本概念和术语1.1 数据、数据元素、数据项、数据结构等基本概念1.2 数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系1.3 数据结构的两大逻辑结构和四种常用的存储表示方法2. 算法的描述和分析2.1 算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念2.2 算法描述和算法分析的方法，对于一般算法能分析出时间复杂度第二章线性表1. 线性表的逻辑结构1.1 线性表的逻辑结构特征2. 线性表的顺序存储结构2.1 顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系2.2 顺序表上的插入、删除操作及其平均时间性能分析3. 线性表的链式存储结构3.1 链表如何表示线性表中元素之间的逻辑关系3.2 链表中头指针和头结点的使用3.3 单链表、双（向）链表、循环链表链接方式上的区别3.4 单链表上实现的建表、查找、插入和删除4. 顺序表和链表的比较4.1 顺序表和链表的主要优缺点4.2 针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能第三章栈和队列1.栈的逻辑结构、存储结构及其相关算法1.1 栈的逻辑结构特点，栈与线性表的异同1.2 顺序栈和链栈上实现的进栈、退栈等基本算法1.3 栈的“上溢”和“下溢”的概念及其判别条件2. 队列的逻辑结构、存储结构及其相关算法2.1 队列的逻辑结构特点，队列与线性表的异同2.2 顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法2.3 队列的“上溢”和“下溢”的概念及其判别条件2.4 使用数组实现的循环队列取代普通的顺序队列的原因2.5 循环队列中对边界条件的处理方法3. 栈和队列的应用3.1 栈和队列的特点，什么样的情况下能够使用栈或队列3.2 表达式求值的算法思想，及栈变化情况。

第四章串、数组和广义表1.串1.1 串的有关概念及基本运算1.2 串与线性表的关系2.多维数组2.1 多维数组的逻辑结构特征2.2 多维数组的顺序存储结构及地址计算方式2.3 数组是一种随机存取结构的原因2.4 矩阵的压缩存储（对称矩阵、三角矩阵、稀疏矩阵）的表示方式和对应的地址计算方式。

复习提纲第一章数据结构概述基本概念与术语（P3）1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科.2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合2．数据元素是数据的基本单位3．数据对象相同性质的数据元素的集合4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系.（2）数据的存储结构指数据元素及其关系在计算机内的表示( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等.5.时间复杂度分析--------------------------------------------------------------------------------------------------------------------1、名词解释：数据结构、二元组2、根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型。

3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。

4、以下程序段的时间复杂度为___O(N2)_____。

int i,j,x;for(i=0;i<n:i++) n+1for(j=0;j<n;j++) n+1x+=i;------------------------------------------------------------------------------------------------------------------第二章线性表1.顺序表结构由n(n>=0)个具有相同性质的数据元素a1,a2,a3……,an组成的有穷序列//顺序表结构#define MAXSIZE 100typedef int DataType;Typedef struct{DataType items[MAXSIZE];Int length;}Sqlist,*LinkList;//初始化链表void InitList(LinkList *L){(*L)=(LinkList)malloc(sizeof(LNode));if(!L){cout<<”初始化失败!”;return;}(*L)->next=NULL;}//插入数据void InsertList(LinkList L,int pos,DataType x){LinkList p=L,q;int i=0;while(p&&i<pos-1){p=p->next;i++;}if(!p||i>pos-1){cout<<”插入位置错误”;return;}InitList(&q);q->next=p->next;p->next=q;q->data=x;}//销毁链表void DestoryList(LinkList L){LinkList t;while(L){t=L;L=L->next;free(t);}}//遍历链表void TraverseList(LinkList L){LinkList t=L;while(L){t=t->next;cout<<t->data<<” ”;}cout<<endl;}//删除元素void DeleteList(LinkList L,int pos){LinkList p=L,q;int i=0;while(p&&i<pos-1){p=p->next;i++;}if(!p||i>pos-1){cout<<”删除位置错误!!”;return;}q=p->next;p->next=q->next;free(q):}第三章栈和队列1.栈（1）栈的结构与定义（2）顺序栈操作算法：入栈、出栈、判断栈空等（3）链栈的结构与定义2.队列（1）队列的定义----------------------------------------------------------------------------------------------------------------1、一个栈的入栈序列为“ABCDE”，则以下不可能的出栈序列是（）A. BCDAEB. EDACBC. BCADED. AEDCB2、栈的顺序表示仲，用TOP表示栈顶元素，那么栈空的条件是（）A. TOP==STACKSIZEB. TOP==1C. TOP==0D. TOP==-13、允许在一端插入，在另一端删除的线性表称为____队列____。

数据结构与算法复习提纲（详细版）一、数学知识复习1、对数（重要公式：XA=B当且仅当A=logXB；关键思路：将对数转化成为指数分析）2、级数（重要公式：∑Ai和∑iA；关键思路：同时乘上某个系数再相减）3、证明方法（数学归纳法和反证法：三个关键步骤（归纳基础、归纳假设、归纳证明））二、C++类1、构造函数（使用默认参数的构造函数；初始化列表）2、访问函数和修改函数（关键字const）3、接口与实现的分离（声明与实现必须精确匹配，两个例外：默认参数和explicit）三、C++细节1、参数传递（一般情形：单向传递/引用：双向传递/常引用：避免大对象的拷贝）2、★三大函数（当数据成员含有指针类型，三大函数必须显式给出；避免浅复制）⑴、析构函数（形式：~类名（）/作用：释放资源）⑵、复制构造函数（形式：类名（const 类名rhs）/作用：利用已有对象复制一个新对象）⑶、operator=（形式：const 类名operator=（const 类名rhs）/作用：赋值）四、模板1、★函数模板定义（template <typename 虚拟类型comparable> 通用函数定义）2、★类模板⑴、定义（template <typename 类型参数object> class 类模板名）</typename> </typename>⑵、调用（class 类模板名<实际参数> 对象名（参数））</实际参数>3、函数对象（定义一个包含零个数据成员和一个成员函数的类，然后传递该类的实例）五、矩阵1、基本思想（矩阵利用向量的向量来实现，即vector<vector object> array）2、典型代码分析（包括构造函数和operator[]重载）</vector>第二章算法分析一、数学基础1、重要定义⑴、f（N）=Ο（g（N））（若存在正常数C和n0，使得当N≥n0时，有f（N）≤Cg（N））⑵、f（N）=Ω（g（N））、f（N）=Θ（g （N））和f（N）=ο（g（N）））2、★重要工具⑴、性质：logkN=O（N）⑵、洛比塔法则：判断两个函数的相对增长率二、最大子列和问题1、算法Ⅰ⑴、算法思想（i表示序列起点，j表示序列终点，k从i扫描到j）⑵、★时间复杂度分析（注意分析方法：∑（i：0~N-1）∑（j：i~N-1）∑（k：i~j））⑶、★算法的缺陷（重复计算）2、算法Ⅱ算法思想（i表示序列起点，j表示序列终点（省略辅助变量k））3、算法Ⅲ⑴、★分治策略（递归程序：传递数组和左右边界，后者界定了数组要被处理的范围/单行驱动程序：传递数组和0，N-1而启动递归程序）⑵、算法思想（递归出口分析；最大子序列和的三种可能情况）⑶、★时间复杂度分析（重要公式：T（N）=2T（N/2）+N）4、算法Ⅳ（任何负的子序列不可能是最优子序列的前缀）三、折半搜索1、概念：折半查找（在已排好序的队列中查找数X）2、算法思想（关键是分析low、high和mid）第三章表、栈和队列一、STL中的向量和表（STL，Standard Template Library，标准模板库）1、STL定义了vector（向量）和list（双向链表）两个类模板2、★★迭代器（iterator）⑴、迭代器的作用（位置标记）⑵、迭代器的声明（典例：vector<object>::iterator）⑶、迭代器的重要方法（STL定义了一对方法：iterator begin（）、iterator end（）（返回最后一项的后面位置）、*itr（返回itr所指位置的对象的引用））⑷、const_iterator（保证*itr返回常引用）二、★向量的实现1、数据成员（theSize：元素个数/theCapacity：容量/objects：基本数组）2、构造函数和三大函数（重点分析operator=；复制构造函数与operator=的区别与联系）3、两个基本操作（reserve（改变容量）和resize（改变大小））4、重要操作（push_back和pop_back）三、表的实现1、Node类（数据成员：data、prev和next/重点：构造函数）2、const_iterator类（数据成员：current/运算符重载：operator*，前后置++，==和!=）3、iterator类（const_iterator的子类；注意两者唯一的区别）4、list类⑴、数据成员（theSize，头结点和尾结点（注意指向的位置））⑵、构造函数和三大函数（关键：利用init例程，创建空双向链表）⑶、基本操作（insert和erase操作）⑷、重要操作（push_front、push_back、pop_front和pop_back）四、栈ADT1、栈的顺序实现⑴、★重要概念：base和top（base：始终指向栈底位置/top：指向栈顶元素的下一个位置）⑵、★重要条件（栈空条件：top=base；栈满条件：top-base=stackSize）2、栈的应用（分析算法思想：首先创建一个空栈并顺序读入符号）⑴、平衡符号（关键：三种出错情况）⑵、后缀表达式（遇见数则压栈；遇见操作符则连续两次弹栈，计算后再压栈）⑶、中缀到后缀的转换（遇见数输出/遇见操作符，级别高则入栈，否则一直弹栈直到遇见级别更低的操作符/遇见（，入栈，直到遇见），则将（）之间的所有操作符弹栈）五、队列ADT（循环队列）1、★重要概念：头指针和尾指针（front：指向对头元素；rear：指向队尾元素下一个位置）2、★重要操作：入队和出队（入队rear++；出队front++）3、★重要条件（队空条件：front=rear；队满条件：front=（rear+1）%maxSize第四章树一、二叉查找树1、二叉查找树的概念（对于每个结点X，左子树中的所有结点的值<x，右子树> X）2、二叉查找树结点类BinaryNode（element、left和right）3、★二叉查找树的类模板⑴、数据成员（根结点root）</x，右子树>⑵、析构函数和operator=（分别采用makeEmpty和clone例程）⑶、基本操作（contains、findMIn和findMax操作）（分别利用递归和非递归方式实现）⑷、重要操作（insert和remove操作）二、AVL树（平衡二叉树）1、★AVL树的概念和性质（空树的高度为-1）⑴、概念：AVL树（双重条件：二叉查找树，且每个结点的左右子树高度差至多为1）⑵、性质（高度h的AVL树，最少结点数s （h）=s（h-1）+s（h-2）+1））2、★★AVL树的四种基本旋转（关键：作图分析）⑴、理论分析：（当插入一个新结点时，通过旋转可以保持这棵树仍然是AVL树）⑵、实际分析：（一字形：使用单旋转；Z字形：使用双旋转）⑶、典例分析：（P107：倒序插入10～16）3、★★AVL树的插入算法⑴、AVL树的结点类AvlNode（同标准BinaryNode相比，增加一个height字段）⑵、AVL树的插入操作（利用height（）例程和四种基本旋转）⑶、基本操作（右旋转（rotateWithLeftChild）；左右旋转（doubleWithLeftChild））三、伸展树1、伸展树的基本思想（当一个结点被访问以后，它就要通过一系列旋转被推至根）2、伸展树的效率（平均摊还时间为O（logN））3、基本操作（一字形旋转和Z字形旋转）（通过P114典例分析）四、树的遍历（使用递归实现）1、中序遍历二叉查找树2、利用后序遍历计算树的高度五、B树（M叉查找树的一种实现方式；磁盘的访问代价太高）1、重要概念：M阶B树（叶结点：数据；非叶结点：键/根、非根和叶结点的限制）2、基本操作（插入：分裂方式/删除：领养和合并方式）六、标准库中的set和map（了解内容）1、set（排序后的，没有重复值的容器）2、map（排序后的，由键和值组成的项的集合）（典例：map<string，vector> <string> ：：const_iterator itr；）</string> </string，vector>第五章散列一、★★链地址法1、基本思想（将hash值相同的所有记录保存在同一个线性链表中）2、实现链地址法的HashTable类模板⑴、数据成员（thelists（链表数组）和currentsize（已存储结点个数））⑵、核心操作：myhash（）（散列到合适位置）⑶、基本操作：makeEmpty（）和contains（）（关键：利用find例程）⑷、重要操作：insert（）和remove（）二、★★探测法1、基本思想（hi（x）=（hash（x）+f（i））mod TableSize；其中f为冲突解决函数）2、线性探测法和平方探测法（f（i）=i；f（i）=i2）3、实现探测法的HashTable类模板⑴、数据成员（HashEntry（通过HashType）定义；数组array和currentsize）⑵、核心操作：findPos（）（若x存在，返回位置；否则返回待插入位置）⑶、基本操作：makeEmpty（）（关键：打上EMPTY 标记）⑷、重要操作：insert（）和remove（）三、★再散列（3个基本步骤：备份；增容并初始化；拷贝）1、链地址法的再散列2、探测法的再散列数据结构与算法复习提纲（详细版）.doc 将本文的Word文档下载到电脑，方便复制、编辑、收藏和打印支付<i>7</i> 元已有<i id="dl">10</i> 人下载本文链接：（转载请注明文章优先队列（堆）一、★★二叉堆1、基本概念：二叉堆（双重条件：完全二叉树；且堆序（任意结点小于它的所有后裔））2、二叉堆的类模板（BinaryHeap）⑴、数据成员（数组array；currentSize（当前堆的大小））⑵、基本操作：（插入和删除操作必须考虑特殊情况）Ⅰ、insert操作（关键：上滤）Ⅱ、deleteMin操作（两种格式）（关键：下滤；调用percolateDown例程）⑶、重要操作：buildHeap操作（从而得出构造函数）3、重要定理：高为h的满二叉树的结点的高度和为2h+1-1-（h+1）（分析证明）4、基本概念：d堆（二叉堆的简单推广）二、★★左式堆1、★★基本概念和性质⑴、概念：零路径长npl（null path length，the shortest path from x to a node with null point）Ⅰ、重要性质：结点X的npl=min（左右孩子的npl）+1Ⅱ、初值分析：npl（null）=0；npl（叶结点；度为1的结点）=1⑵、重要概念：左式堆（双重条件：堆序；且npl（左孩子）=npl （右孩子））⑶、定理：在右路径上有r个结点的左式堆至少有2r-1个结点（左侧全部铺满）2、★★左式堆的类模板（LeftistHeap）⑴、数据成员（LeftistNode *root；左式堆结点LeftistNode增加一个npl字段）⑵、关键操作：merge操作（驱动程序加两个merge完成；思想：大的合并到小的右子树）⑶、重要操作：insert操作和deleteMin 操作3、斜堆（斜堆与左式堆的关系，类似伸展树与AVL树的关系）⑴、概念：斜堆（具有堆序性质的二叉树）（即左式堆去掉npl限制）⑵、基本操作：merge（除右路径上最后一个结点，每次合并都必须交换）三、★★二项队列1、基本概念和性质⑴、概念：二项树（双重条件：堆序；Bk的递归定义）⑵、重要概念：二项队列（由若干棵二项树构成）⑶、重要性质（二项队列的两个性质：每个高度上至多有一棵二项树；可以用二项树的集合唯一表示任意大小的优先队列）2、★★二项队列的类模板（BinomialQueue）⑴、结点类BinomialNode（孩子兄弟表示法：leftchild指向结点最多的子树；rightsibling）⑵、数据成员（指针数组theTrees；currentSize（按递减方式存放））⑶、核心操作：combineTrees（同等高度的合并；保持堆序性质）⑷、基本操作：merge（三个步骤：resize、carry和whichcase、清空（currentSize的作用））⑸、重要操作：findMinIndex（寻找最小项）和deleteMin（H2：deletedTree和deletedQueue）第七章排序一、★插入排序1、算法思想（插入到前面有序序列）2、插入算法（关键：分析清楚边界情况（i控制插入趟数，j控制每趟中的插入位置））二、一些简单排序算法的下界1、逆序的概念、性质（一次相邻结点的交换，逆序改变1；逆序数=插入算法比较次数））2、定理：N个互异元素的数组，其平均逆序数为N（N-1）/43、定理：通过交换相邻元素进行排序的任何算法平均需要Ω（N2）时间三、希尔排序（ShellSort，缩减增量排序）1、算法思想（由若干趟Hk排序构成；每趟Hk排序使用插入算法）2、使用希尔增量的希尔排序（关键：三重循环（gap表Shell增量，i和j作用同插入排序）3、定理：使用希尔增量的希尔排序的最坏运行时间为Ω（N2）（注意构造和严格证明）四、★堆排序（heapSort）1、算法思想（两个步骤：创建大堆；首尾交换并下滤）2、堆排序算法（关键：基于二叉堆的buildHeap和percolateDown （修改为大堆））五、★★归并排序（mergeSort）1、算法思想（分治算法；合并两个已排序的表）2、归并算法（由驱动程序、mergeSort和merge构成；关键：tempArray临时数组；而merge包含三个while和一个拷贝）3、★算法分析（关键公式：T（N）=2T（N/2）+N，叠缩求和法）六、★★快速排序（quickSort）1、算法思想（分治算法：选取枢纽元素pivot；将S分割S1和S2；对S1和S2递归调用）2、快速算法（median3（关键：3元素中值法选取枢纽元素）；quickSort（关键：i向右搜索第一个≥pivot的结点，j相反操作（注意i和j起始位置）；还原pivot并从i处分割）3、★★算法分析（关键公式：T（N）=T（i）+T（N-i-1）+CN）（i为S1中元素个数）七、其它1、间接排序（解决comparable对象复制代价太高的问题）2、定理：只使用元素间比较的任何排序算法需要Ω（NlogN）次比较3、桶排序（前提条件（正整数）和算法思想）4、外部排序⑴、外部排序的概念（大文件的排序，排序过程中需要进行多次的内、外存之间的交换）⑵、基本思想（归并算法）第八章不相交集一、基本操作1、find（x）操作（查找操作：返回x所属的集合）2、unionSets（S1，S2）操作（求并操作：求集合S1和S2的并）二、DisjSets类（不相交集类）1、基本思想（利用树表示每个集合，根表示这个集合的名称；整个集合表示为一颗森林）2、基本数据结构（关键：双亲表示法）⑴、数据成员（数组S：（S[i]为i的双亲，其中-1表示根））⑵、构造函数（数组S全部初始化为-1）⑶、基本操作：find（）操作和unionSets（）操作3、算法分析（unionSets操作为O（1），find操作的最坏情形为O（1））三、灵巧求并算法第八章不相交集类一、基本概念1、关系R：A Relation R is defined on a set S is for every pair （a，b），a，b∈S，either True or False.2、等价关系：满足自反、对称和传递等三条性质的关系3、等价类（更准确的名称为：集合S上的R关系等价类）等价类的作用：形成对集合S的一个划分（即：根据关系R将集合S划分为S1，S2，S3??等等）二、基本操作1、find（x）操作：Return the name of set containing a givenelement. 2、unionSets（S1，S2）操作：（求并操作）Union two disjoint sets S1，S2（对两个不相交的非空集合S1和S2求并）三、不相交集类的基本数据结构1、数据结构的表示⑴、Use a tree to represent each set，the root can be used to name the set.（利用树来表示每一个集合，而且利用该树的根结点来表示这个集合的名称）⑵、这样，整个集合S可表示为一颗森林2、数据结构的实现采用双亲表示法实现（注意：双亲表示法是利用数组来存贮一棵树）其中：⑴、S[i]表示元素i的双亲结点⑵、若i是根结点，则S[i]＝－13、★★不相交集类的算法实现（包括类的定义、构造函数的实现以及两个基本操作find和unionSets的实现）4、★算法分析⑴、unionSets操作的时间复杂度为O（1）⑵、find操作的最坏时间复杂度为O（N）Ⅰ、unionSets操作和find操作在算法效率上是一对矛盾的操作Ⅱ、连续的求并操作，在最坏情况下会建立起一棵深度为N-1的树Ⅲ、一般情况下，运行时间使针对连续混和使用M个指令来计算的在这种情况下，M次连续操作在最坏情形下可能花费O（MN）时间四、算法的改进1、union Sets操作的改进⑴、按大小求并（与按高度求并非常类似）⑵、按高度求并（保证将比较浅的子树并入比较深的子树）思路1：可利用每个根的数据元素来存贮整颗子树高度的负值思路2：为了同原算法类定义和构造函数实现的兼容，我们假定只有一个根结点的树的高度为－1，依此类推⑶、★算法分析两种算法都将find操作的时间复杂度改进为O（log N）（给出详细的证明）（另外的一个结论是：对于连续M个指令，平均需要O（M）时间，但最坏情形还是O（M log N））2、find操作的改进－路径压缩（Path compression）⑴、路径压缩的概念：Every node on the path from x to the root has its parent changed to the root. （从x到根的路径上每一个结点都使它的父结点变成根）⑵、★路径压缩的算法实现⑶、结论：路径压缩与按大小求并完全兼容，与按高度求并部分兼容五、按秩求并和路径压缩的最坏情形1、秩（rank）的概念：一个结点的秩，是指以该结点为根结点的子树的高度2、几个重要引理⑴、引理1：当执行一系列union指令以后，一个秩为r的结点必然至少有2r个后裔结点（包括它自己）⑵、引理2：秩为r的结点至多有N/2r个⑶、引理3：在求并查找算法的任意时刻，从树叶到根结点路径上的结点的秩单调增加3、★重要定理：当使用求并探测法和路径压缩时，算法在最坏情况下需要的时间为O（α（M，N））其中，α（M，N）是Ackermann函数的逆（推论：任意次序的M=Ω（N）次union/find操作花费的总运行时间为O（M log*N））六、迷宫问题1、算法思想：对于随机选中的一堵墙，使用union/find操作2、算法分析：时间复杂度为O（N log*N）图论算法一、图的表示1、邻接矩阵（adjacent matrix）表示法（分析优缺点）2、★邻接表（adjacency list）Ⅰ、对每一个顶点，使用一个链表来存放与之邻接的所有顶点Ⅱ、图的邻接表的一种简单的表示方式：Vector <vertex> array （使用一个数组来存放所有的顶点）</vertex>二、拓扑排序1、概念：拓扑排序是对有向无环图的顶点的一种排序2、★★拓扑排序的算法思想（可以使用Stack或者Queue来实现）⑴、计算每一个顶点的入度⑵、将所有入度为0的顶点放入一个初始为空的队列中⑶、若队列非空，则v出队，且所有与v邻接的顶点的入度减1⑷、若有顶点的入度降为0，则该顶点入队3、★拓扑排序的算法（使用伪码描述）（注意：利用一个辅助变量来判断是否出现回路）4、★算法分析：时间复杂度为O（|E|+|V|）三、最短路径1、无权最短路径（加权最短路径的特殊情形）⑴、采用广度优先搜索（Breadth CFirst Search）的策略（层次遍历的推广）⑵、★Vert ex的数据结构Ⅰ、known：当一个顶点被访问以后，其known置为true Ⅱ、dist：从s到该顶点的距离Ⅲ、path：引起dist变化的最后顶点（通过追溯path，可以得到s到该顶点的完整最短路径）⑶、★无权最短路径的算法思想和算法（关键：使用一个队列来实现）⑷、算法分析：时间复杂度为O（|E|+|V|）2、加权最短路径⑴、贪心算法（greed algorithm）Ⅰ、Solve the problem in stages（分阶段进行）Ⅱ、每个阶段都把出现的方案当成最优的解决方案⑵、、★★Dijkstra算法思想和算法Ⅰ、对所有结点初始化Ⅱ、在所有known标记为false的结点中，寻找一个其dist值最小的结点Ⅲ、扫描与v邻接的所有known标记为false的结点w，分析是否有必要update其dist值Ⅳ、更新w的path⑶、★★Dijkstra的算法分析Ⅰ、常规方法：通过扫描存放顶点的数组来寻找最小值，时间是O（|E|+|V|2）Ⅱ、使用优先队列的deleteMin方法寻找最小值：，其时间是O（|E|log|V|＋|V|log|V|）3、具有负边值的图⑴、★算法思想和算法：综合了无权最短路径（采用队列）和Dijkstra算法（需要update）的思想Ⅰ、不需要再设置known来判断结点是否已经被访问过Ⅱ、扫描与v邻接的所有结点w，分析是否有必要update其dist 值，再分析w是否入队⑵、★算法分析：时间是O（|E|×|V|）（给出详细证明）4、无环图⑴、★算法思想以Dijkstra算法作为基础，但是顶点的选取采用拓扑原则（而不是寻找dist值最小的顶点）⑵、基本概念：动作结点图和事件结点图（注意：两者的转换方法）⑶、基本概念：最早完成时间，最晚完成时间，松弛时间（分析其计算公式）⑷、基本概念：关键路径－由零松弛边组成的路径四、网络流问题1、概念：最大流问题设有向图G＝（V，E）的每条边表示边容量，求从给定的源点s 到汇点t可通过的最大流量2、算法思想⑴、辅助工具：流图（初始：每条边均为0）和残余图（初始：等于原图）⑵、从残余图中选择一条增长路径（关键：对流图和残余图进行调整）⑶、算法一直运行到没有增长路径为止五、最小生成树1、基本概念和性质⑴、生成树的概念和性质概念：Spanning tree is a tree formed from graph edges that connects all vertices of G. 性质：生成树的边数为N－1 ⑵、最小生成树的概念和性质MST性质：若（u，v）是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边（u，v）的最小生成树2、Prim算法⑴、★Prim算法的基本思想：设G=（V，E），TE是G上最小生成树的边的集合Ⅰ、初始：U={u0}，TE={}Ⅱ、从所有的（u，v）中寻找一条代价最小的边（u0，v0），其中u0∈U，v0∈V－U Ⅲ、U=U∪{u0}，TE=TE∪（u0，v0）Ⅳ、上述操作一直做到U=V为止⑵、★★Prim算法Ⅰ、同Dijkstra算法非常类似，唯一区别在于dv的含义和更新方法不同（这里dv是指从v到所有known顶点的最短边）Ⅱ、注意：如何获取最后的最小生成树和计算出其代价3、Kruskal算法⑴、★★Kruskal算法的基本思想和算法Ⅰ、使用优先队列来存放所有的边Ⅱ、利用等价类的思想来决定（u，v）边是应该添加还是舍弃⑵、Kruskal的算法分析：同Prim算法一样，其时间复杂度为（|E|log|V|）六、深度优先搜索的应用1、深度优先搜索（DFS，Depth-first search）（DFS是对前序遍历的推广）⑴、★DFS算法思想和算法通常情况下，DFS算法均由两个模板构成Ⅰ、外围模板：针对整个图G进行（初始化，再扫描结点，若unvisited则调用核心模板）Ⅱ、核心模板：是一个从指定顶点开始的，非常简练的DFS递归程序⑵、DFS算法分析：时间复杂度为O （|E|+|V|）2、无向图⑴、★概念：前序编号（对图G进行DFS，图中的各个顶点被依次访问的顺序编号）⑵、★概念：DFS树（深度优先生成树）对图G进行DFS以后，图中的所有边被分成两大类：前向边和后向边其中所有的前向边构成了DFS树⑶、算法思想和算法（分析以上概念的算法实现）3、无向图的双连通性⑴、概念：双连通性和割点⑵、★low（v）的概念和计算方法Low（v）是顶点v可到达的最低顶点编号（关键：计算low的三条法则）⑶、割点的判断条件若顶点v存在一个孩子结点w，有low（w）=num（v），则v必然是一个割点⑷、★算法：寻找连通图中的所有割点该算法通过对图的两次遍历而实现（一次前序遍历和一次后序遍历）Ⅰ、结点Vertex包含以下域：visited，num，low，parent Ⅱ、首先计算图G的每个顶点的前序编号（计算出num和parent）Ⅲ、利用一趟后序遍历对各个顶点计算low，并判断是否割点4、欧拉回路⑴、概念：欧拉环游和欧拉回路⑵、欧拉定理：任何一个连通图存在欧拉回路的充分必要条件是图中所有顶点的度为偶数⑶、★欧拉回路的算法思想Ⅰ、数据结构的设计：遍历的路径采用链表保存；为避免重复扫描邻接表，对每一个邻接表必须保留最后扫描到的边Ⅱ、对给定的顶点进行一次DFSⅢ、选定一个拼接点，从该顶点开始进行DFS Ⅳ、上述步骤重复进行，直到所有的边都被遍历⑷、欧拉回路的算法和算法分析：时间复杂度为O（|E|+|V|）5、有向图⑴、按照与无向图相同的策略，对有向图进行DFS （若图G非强连通的，则产生DFS森林）⑵、有向图DFS的虚边有三种类型（无向图只有一种，即后向边）后向边、前向边和交叉边⑶、对有向图进行DFS的一个作用是：判断该有向图是否无环图法则如下：一个有向图是无环图当且仅当它没有后向边6、查找强分支⑴、★查找强分支的算法思想：两次DFSⅠ、首先对图G进行第一次DFS，得到DFS森林（通过对DFS的后序遍历得到每个顶点的后序编号；并且将G 的所有边反向得到GR）Ⅱ、再对GR进行第二次DFS，总是在编号最高的顶点开始一次新的深度优先搜索⑵、★定理：按照上述算法生成的DFS森林中的每棵树都是一个强连通的分支（分析其证明）七、NP完全性介绍1、P问题指保证以多项式时间运行的算法2、不可判定问题⑴、可以证明：计算机不可能解决所有的问题，这些不可能解出的问题称为不可判定问题⑵、著名的不可判定问题：停机问题Ⅰ、什么是停机问题？Ⅱ、停机问题的实质是：一个程序很难检查它自己3、NP类⑴、NP类代表非确定型多项式时间这类问题在难度上稍逊于不可判定问题⑵、判断一个问题是否NP问题的方法如果我们能在多项式时间内证明一个问题的任意“是”的实例是正确的，那么这个问题就属于NP类典例：哈密尔顿回路问题就是一个NP问题⑶、NP类同其它集合的关系Ⅰ、性质：NP类包括P类，即包括所有具有多项式时间解的问题Ⅱ、性质：不是所有的可判定问题都是NP问题（即NP问题并不是不可判定问题的补集）典例：无哈密尔顿回路问题显然是一个可判定问题，但不是NP问题4、NP完全问题⑴、NP完全问题是NP问题的一个子集⑵、重要性质：NP中的任何一个问题都可以多项式地归约成NP 完全问题⑶、证明一个问题是NP完全问题的方法Ⅰ、首先证明该问题是NP问题Ⅱ、然后将一个适当的NP问题变换到此问题典例：假设哈密尔顿回路问题是一个NP完全问题，证明旅行商问题也是一个NP完全问题第十章算法设计技巧一、贪心算法1、★贪心算法（greed algorithm）⑴、Solve the problem in stages（分阶段进行）⑵、每个阶段都把出现的方案当成最优的解决方案（当算法终止时，希望局部最优成为全局最优）2、调度问题⑴、★调度问题的概念：将作业平均完成的时间最小化（假设：非抢占调度，即一旦开始一个作业，就必须把该作业运行完）⑵、多处理器情形Ⅰ、实现步骤：（首先排序，然后按顺序开始作业，处理器之间轮流分配作业）Ⅱ、证明：按照这种算法思想实现的，一定是最优解⑶、将最后完成时间最小化（这是一个NP完全问题）3、赫夫曼（Huffman）编码⑴、概念：满树和前缀码⑵、赫夫曼编码的算法思想（频率出现高的字符编码要短）⑶、★赫夫曼编码的算法和算法分析（采用优先队列时，运行时间为O（ClogC））4、装箱问题⑴、基本概念Ⅰ、★概念：装箱问题（将物品装到最少数量的箱子中）Ⅱ、★概念：联机装箱（每一件物品必须放入一个箱子之后才能处理下一个物品）⑵、联机算法Ⅰ、重要性质：对于联机装箱问题不存在最优算法（分析其证明）Ⅱ、★定理一：任意联机装箱算法的下界为4M/3（分析其证明）⑶、下项适配Ⅰ、下项适配的基本思想（能放入当前箱子则放，否则开辟一个新的箱子）Ⅱ、★定理二：下项适配算法的上界为2M（分析其证明）⑷、首次适配Ⅰ、首次适配的基本思想（扫描并寻找第一个能放入的箱子，否则开辟一个新箱子）Ⅱ、定理三：首次适配算法的上界为17M/10 ⑸、最佳适配最佳适配的基本思想和上界分析（放入所有能够容纳它的最满的箱子中）⑹、脱机装箱Ⅰ、★首次适配递减的算法思想（首先排序，然后再使用首次适配算法）Ⅱ、引理一：大小至多是1/3（分析其证明）Ⅲ、引理二、个数至多是M-1（放入其它箱子中的物品个数至多是M-1，分析其证明）Ⅳ、★定理四、首次适配递减算法的上界是（4M+1）/3 Ⅴ、定理五、首次适配递减算法的上界可以缩减为11M/9+4二、分治算法1、分治算法（divide and conquer）⑴、★分治算法的基本思想：分治算法由两个阶段构成Ⅰ、分：递归解决较小的问题Ⅱ、治：从子问题的解构建原问题的解⑵、分治算法的特性（至少含有两个递归调用，且子问题是不相交的）2、分治算法的运行时间K⑴、★定理六：方程T（N）=aT（N/b）+O（N）的解（分析其。