数据结构基础复习.ppt

数据结构考研辅导 基础复习,浙江大学计算机学院,内容提纲,考研概述,考察目标理解数据结构的基本概念：掌握数据结构的逻辑结构、存储结构及其差异，以及各种基本操作的实现。在掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。能够选择合适的数据结构和方法进行问题求解。,考研概述,考试形式整卷满分为150分，考试时间为180分钟数据结构占45分，估计用时4550分钟单选题：40题2分/题，估计占10题20分左右，建议用时不超过2分钟/题综合题：70分，估计占2题共2025分，建议用时不超过10分钟/题,考研概述,复习计划基础理论复习例题详解题目范围：真题1套+模拟题9套+补充题模拟题第10套将用于最后一天模拟考试,6,基础内容复习数据结构（C语言版），严蔚敏、吴伟民，清华大学出版社,线性表、堆栈、队列、数组树与图查找与排序,线性表、堆栈、队列、数组,线性表定义：n个数据元素的有限序列基本操作：随机访问、插入、删除、前驱、后继、倒序等实现方式：顺序存储：数组,Loc(ai),Loc(ai+1)=Loc(ai)+l,Loc(ai)=Loc(a1)+?,(i-1)*l,线性表实现方式：顺序存储：数组,线性表、堆栈、队列、数组,是一种随机存取的存储结构，方便随机存取第i个数据元素,插入、删除复杂度为O(n)，需要移动大量元素,自测题在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：访问第i个结点(1in)和求第i个结点的直接前驱(2in)在第i个结点后插入一个新结点（1in）删除第i个结点（1in）将n个结点从小到大排序,线性表、堆栈、队列、数组,线性表、堆栈、队列、数组,线性表实现方式：链式存储：链表,线性链表,头指针H=19,若 p-data=ai 则 p-next-data=ai+1,typedef struct LNode ElemType data;struct LNode*next;LNode,*LinkList;,有时附加头结点,自测题线性表若采用链式存储结构时，要求内存中可用存储单元的地址:必须是连续的部分地址必须是连续的一定是不连续的连续或不连续都可以,线性表、堆栈、队列、数组,线性表、堆栈、队列、数组,线性表实现方式：链式存储：链表 线性链表,插入、删除复杂度为O(1)，仅需修改指针而不需要移动元素,是一种非随机存取的存储结构，不方便随机存取第i个数据元素,*静态链表（p.31-35）,自测题下面的叙述不正确的是（）线性表在链式存储时，查找第i个元素的时间同i的值成正比线性表在链式存储时，查找第i个元素的时间同i的值无关线性表在顺序存储时，查找第i个元素的时间同i 的值成正比线性表在顺序存储时，查找第i个元素的时间同i的值无关,线性表、堆栈、队列、数组,自测题在一个单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行：s-next=p;p-next=s;s-next=p-next;p-next=s;s-next=p-next;p=s;p-next=s;s-next=p;,线性表、堆栈、队列、数组,自测题在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是：p=p-next;p-next=p-next-next;p-next=p;p=p-next-next;,线性表、堆栈、队列、数组,x,p,线性表、堆栈、队列、数组,线性表实现方式：链式存储：链表 循环链表,双向链表,有时设尾指针可简化某些操作，如两表合并。,自测题设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。单链表 单循环链表 带尾指针的单循环链表 带头结点的双循环链表,线性表、堆栈、队列、数组,自测题将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？单链表 单循环链表 带尾指针的单循环链表 带头结点的双循环链表,线性表、堆栈、队列、数组,tmp=La-next;La-next=Lb-next;Lb-next=tmp;,19,线性表、堆栈、队列、数组,线性表练习1：分别实现数组、单链表、循环链表、双向链表的插入和删除操作。练习2：实现单链表的原地逆转。练习3：分别用一元多项式的两种表示实现多项式加法。,自测题给定2个带有表头结点的单链表的头指针L1和L2，结点结构为。假设这2个链表的结点已经按Data域递增有序，请设计算法把它们合并成一个按Data域递增有序的链表。注意：算法不能使用额外的结点空间。,线性表、堆栈、队列、数组,算法思路为顺序比较L1和L2当前所指的两结点的Data域，将小的那个结点从原链表摘除，贴到合并链表的尾部。如此进行到至少其中一个链表为空。若此时另一个链表不为空，则将另一个链表整个贴到合并链表的尾部。注意原始2个链表有2个头结点，合并后只保留一个，需要释放另一个的空间。,List MergeSortedLists(List L1,List L2)List L=L1;List Tail=L2;L1=L1-Next;L2=L2-Next;free(Tail);Tail=L;/释放第二个链表的表头，并将新链表的表尾指针Tail初始化while(L1,自测题给定2个带有表头结点的单链表的头指针L1和L2，结点结构为。假设这2个链表的结点已经按Data域递增有序，请设计算法把它们合并成一个按Data域递减有序的链表。注意：算法不能使用额外的结点空间。,线性表、堆栈、队列、数组,解题的基本思路不变，只要将原来的表尾插入改为表头插入即可。当然，当其中一个链表为空而另一个链表不为空时，不能直接将剩余链表贴到表尾，而必须将剩余结点一个一个插入表头。,自测题若L1和L2是有序数组，其结点已经按Data域递增有序，请设计算法把它们合并成一个按Data域递增有序的数组。注意：要求将L2并入L1，并且要求移动元素的次数尽可能少。,线性表、堆栈、队列、数组,必须事先算好合并后L1的长度，然后从L1的最终尾部向前插入元素。插入过程与前面算法类似，但是是从尾部开始比较L1和L2相应元素大小，将较大的元素先插入到后面的位置。,void MergeSortedArrays(ElementType L1,int N1,ElementType L2,int N2)int p1,p2,cur;p1=N1-1;/p1指向L1当前处理的元素位置p2=N2-1;/p2指向L2当前处理的元素位置cur=N1+N2-1;/cur指向下一个要插入的元素在L1中的最终位置while(p1=0),堆栈概念：后进先出，限定仅在表尾进行插入删除的线性表。表示与实现：顺序栈：数组，top+，top-链栈：链表，top即为头指针应用：括号匹配检验、表达式求值、n阶Hanoi塔问题（典型递归）、迷宫问题,线性表、堆栈、队列、数组,自测题判定一个栈ST(最多元素为m0)为空的条件是：ST-top!=0ST-top=0ST-top!=m0ST-top=m0,线性表、堆栈、队列、数组,自测题有六个元素以6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？5 4 3 6 1 2 4 5 3 1 2 6 3 4 6 5 2 1 2 3 4 1 5 6,线性表、堆栈、队列、数组,自测题若一个栈的输入序列为1，2，3，n，输出序列的第一个元素是i，则第j个输出元素是：i j 1 i j j i 1 不确定的,线性表、堆栈、队列、数组,队列概念：先进先出，限定仅在队尾进行插入、仅在队头进行删除的线性表。表示与实现：顺序队列：循环数组，(rear+1)%N,(front+1)%N链栈：链表，front为头指针，rear为尾指针应用：离散事件模拟,线性表、堆栈、队列、数组,自测题循环队列用数组A0,N1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是：(rear-front+N)%Nrear-front+1rear-front-1rear-front,线性表、堆栈、队列、数组,自测题栈和队列的共同特点是：都是先进后出 都是先进先出 只允许在同一端点处插入和删除 没有共同点,线性表、堆栈、队列、数组,数组 特殊矩阵的压缩存储对称矩阵：,线性表、堆栈、队列、数组,*上（下）三角矩阵同理存储，或许多存储一个常数（若另一半矩阵元素是非零常数）。,线性表、堆栈、队列、数组,数组 特殊矩阵的压缩存储m对角矩阵：,稀疏矩阵：,线性表、堆栈、队列、数组,数组 特殊矩阵的压缩存储稀疏矩阵：三元组顺序表：以行序为主序，顺序排列为三元组的1维数组，并存行数、列数、非0元个数。,typedef struct inti,j;ElemTypev;Triple;typedef union TripledataMAXSIZE+1;intnrow,ncol,ntotal;Sparse_Matrix;,线性表、堆栈、队列、数组,数组 特殊矩阵的压缩存储稀疏矩阵：三元组顺序表：快速转置,对每列扫描整个数组：O(ncolntotal),如何一步到位，放入正确位置？,numcol 第col列中非0元个数；cpotcol 第col列中第1个非0元在转置矩阵中的位置；,cpot1=1;cpotcol=cpotcol-1+numcol-1;,4,2,O(ncol+ntotal),线性表、堆栈、队列、数组,数组 特殊矩阵的压缩存储稀疏矩阵：行逻辑链接的顺序表：矩阵相乘,typedef struct TripledataMAXSIZE+1;intrposMAXRC+1;intnrow,ncol,ntotal;Sparse_Matrix;,各行第1个非0元在数组中的位置,设 M=A B，则有,关键：对每个A.datap，找所有B.dataq，满足(A.datap.j=B.dataq.i)，将(A.datap.vB.dataq.v)累加到相应的临时行向量，最后压缩到M中。,O(ArowBcol+AtotalBtotal/Brow),线性表、堆栈、队列、数组,数组 特殊矩阵的压缩存储稀疏矩阵：十字链表：矩阵相加,计算 A+B 的复杂度为 O(Atotal+Btotal),自测题设稀疏矩阵A有t个非零元素，用二维数组存储时占用m*n个单元。问稀疏矩阵的三元组表示法在什么情况下比二维数组存储节省空间？t m*nt m*n/3 t m*n/3 1t m*n 1,线性表、堆栈、队列、数组,树与图,树与二叉树的概念树的概念：度(degree)；层(level)注意：根为第1层；深度(depth)结点的最大层次。二叉树的概念：左右有序性质1：第i层最多有2i-1个结点。性质2：深度为k的二叉树最多有2k-1个结点。性质3：若n0为叶子数，n2为度为2的结点数，则有 n0=n2+1。性质4：具有n个结点的完全二叉树的深度为 log2n+1。,树与二叉树的概念二叉树的概念：性质5：对有n个结点且顺序编号的完全二叉树，其任一结点 i 有,树与图,二叉树的存储结构顺序存储结构：数组 仅适用于完全二叉树链式存储结构：在含有n个结点的二叉链表中有 个空链域。二叉树的遍历先序、中序、后序、层次,树与图,Parent,1,2,3,4,5,6,7,n+1,自测题一棵完全二叉树共有2435个结点，则其中度为0的结点数为？12181217 不确定812,树与图,388+210 388/2=1218,自测题在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于 2h 12h+12h 1 2h,树与图,自测题结点中序遍历为xyz的不同二叉树，它有几种不同状态？3 4 5 6,树与图,自测题前序遍历和中序遍历结果相同的二叉树为 一般二叉树 只有根结点的二叉树 所有结点只有左子树的二叉树 所有结点只有右子树的二叉树,树与图,自测题前序遍历和后序遍历结果相同的二叉树为 一般二叉树 只有根结点的二叉树 所有结点只有左子树的二叉树 所有结点只有右子树的二叉树,树与图,自测题已知中序遍历和前序遍历结果，给出算法求后序遍历结果。,树与图,（1）从前序遍历结果推断该树的树根。（2）找出左子树和右子树的中序和前序遍历结果。（3）重复上述过程，找出左、右子树的根结点，并逐步往下扩展，直到生成一颗完整的二叉树。,左,左,右,右,OutPostOrder(PreOrder,InOrder)/已知前序序列PreOrder、中序序列InOrder，求后序序列 1）应用前述方法，从序列PreOrder和InOrder中推断出：树的根r;左子树的前序遍历序列PreOrderLeft和中序遍历序列InOrderLeft;右子树的前序遍历序列PreOrderRight和中序遍历序列InOrderRight;2）递归OutPostOrder(PreOrderLeft,InOrderLeft);3）递归OutPostOrder(PreOrderRight,InOrderRight);4）输出 r;,自测题下面是某二叉树三种遍历的部分结果，请画出相应的二叉树。前序:_B_F_ICEH_G 中序:D_KFIA_EJC_ 后序:_K_FBHJ_G_A,树与图,A,B,D,K,D,I,H,J,G,E,C,自测题在任意一颗二叉树中，任何两个叶结点在先序、中序、后序中的相对次序怎样？不变 不一样 不能确定 以上都不是,树与图,线索二叉树概念：,树与图,0:Lchild指向左孩子1:Lchild指向前驱,0:Rchild指向右孩子1:Rchild指向后继,中序遍历：A+B C D,中序线索二叉树,树与图,线索二叉树构造：中序：增加pre指针，指向刚访问过的结点后序：须增加Parent指针域优点：遍历不需要堆栈。若经常需要遍历二叉树或查找结点在遍历序列中的前驱和后继，则应采用线索链表作为存储结构。,二叉排序树定义：左 根 右；左右均为二叉排序树。重要操作：查找、插入、删除（分3种情况）问题：树深与插入顺序相关，最坏情况蜕变为单支树，达到 O(n)。,树与图,平衡二叉树(AVL)：保证树深 O(log n)定义：BF=D(左)D(右)。则AVL树上所有结点的BF只能是-1、0、1。旋转：单向左旋,树与图,0,平衡二叉树(AVL)旋转：单向右旋,树与图,0,平衡二叉树(AVL)旋转：双向旋转（先左后右）,树与图,平衡二叉树(AVL)旋转：双向旋转（先右后左）,树与图,自测题若AVL树的深度是6，则该树的最少结点数是？13172033,树与图,N6=N5+N4+1N5=N4+N3+1N4=N3+N2+1N3=N2+N1+1N2=2,N1=1,Nh=Nh-1+Nh-2+1,树和森林树的存储结构：双亲表示法 找双亲和根结点容易，但找孩子必须遍历数组。孩子表示法 适合涉及 孩子的操作，但不方便找 双亲。,树与图,树和森林树的存储结构：孩子兄弟表示法（二叉树表示法）,树与图,树和森林森林与二叉树的转换森林F=T1 T2.Tm-二叉树B=(R,LB,RB)二叉树B=(R,LB,RB)-森林F=T1 T2.Tm,树与图,if(!F)B=NULL;else R=root(T1);LB=T11 T12.T1m1;RB=T2.Tm;,if(!B)F=NULL;else root(T1)=R;T11 T12.T1m1=LB;T2.Tm=RB;,树和森林树和森林的遍历树的遍历：先根（次序）遍历=二叉树的先序遍历后根（次序）遍历=二叉树的中序遍历森林的遍历：先序遍历=二叉树的先序遍历中序遍历=二叉树的中序遍历,树与图,自测题设森林F对应的二叉树为B，它有m个结点。B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是？m-nm-n-1n+1 无法确定,树与图,n,自测题树最适合用来表示有序数据元素 无序数据元素 元素之间无联系的数据 元素之间有分支层次关系,树与图,树的应用等价类问题：给定集合S的n个元素，以及m个形如(x,y)的等价偶对，求S的等价类划分。,树与图,初始化n个只包含1个元素的子集;while(读入x,y)if(!(Find(x)=Find(y)Union 两集合;,树的应用等价类问题Union by size 根记录(-结点数)，小树并入大树Find+压缩路径 将Find路径上的结点都变成根的孩子,树与图,Union(2,10),-10,10,Find(9),10,10,*等价划分n元集合的复杂度为 O(n(n),(n)4对通常见到的n成立。,哈夫曼(Huffman)树和哈夫曼编码哈夫曼树：带权路径长度最小的二叉树,树与图,路径长度=7 2+5 2+2 2+4 2=36,路径长度=7 3+5 3+2 1+4 2=46,路径长度=7 1+5 2+2 3+4 3=35,哈夫曼(Huffman)树和哈夫曼编码哈夫曼树的构造将n个带权结点作为n棵只有根的二叉树的森林；选2棵根权值最小的树，作为左右子树构造新树，新根的权值=左右子树根权值的和；将上述2棵树删除，将新树加入森林；重复第2、3步，直到只剩1棵树，即是哈夫曼树。,树与图,哈夫曼(Huffman)树和哈夫曼编码哈夫曼编码例：aaaxuaxz 一般被存为8个字符，占64字节。但因只有4个不同字符，故可编码为 a=00,u=01,x=10,z=11，只需要占16个字节。若采用哈夫曼编码 a=0,u=110,x=10,z=111，则得到 00010110010111，只需要占14个字节。注意：任一字符的编码都不是另一字符编码的前缀 前缀编码。,树与图,哈夫曼(Huffman)树和哈夫曼编码哈夫曼编码的构造：将字符出现频率作为权重，构造哈夫曼树，并按左0右1编码。例：aaaxuaxz,树与图,a=0 x=10u=110z=111,思考：给定编码，如何判断是否哈夫曼编码？,自测题哈夫曼树有n个叶结点，则该树共有多少个结点？2n2n-12n+1 不能确定,树与图,N0=nN1=02*N2=N 1 N=N0+N1+N2N=?,图的概念（p.156-160）图的存储及基本操作邻接矩阵法无向图顶点的度有向图顶点的度网,树与图,图的存储及基本操作邻接表法,树与图,*边稀疏时节省空间，但判断任意两顶点是否有弧相连时，则不如邻接矩阵方便。,自测题具有n个顶点的无向图最多有几条边？n(n-1)/2n(n+1)/2n2/2 2n,树与图,自测题在一个图中，所有点的度数之和等于所有边的数目的多少倍？1/2124,树与图,自测题一个无向图采用邻接矩阵存储，该邻接矩阵一定是一个_对称矩阵对角矩阵三角矩阵稀疏矩阵,树与图,树与图,自测题从邻接矩阵 可以看出，该图共有（）个顶点；如果是有向图该图共有（）条弧；如果是无向图，则共有（）条边 9,5,53,4,26,3,31,2,2,图的遍历深度优先(DFS)：类似于树的先序遍历。递归，需要堆栈。邻接矩阵 O(n2)；邻接表 O(n+e)。广度优先(BFS)：类似于树的层次遍历。需要队列。时间复杂度与DFS相同。,树与图,自测题已知无向图为G=(V,E)，其中，顶点集合为V=v1,v2,v3,v4,v5,v6,v7，边的集合为E=(v1,v2),(v1,v3),(v2,v4),(v2,v6),(v4,v5),(v4,v7),(v5,v6)，请分别给出根据该邻接表从顶点v1出发进行深度优先搜索与广度优先搜索后的顶点序列。当有多种选择时，按序号先后访问。深度优先搜索序列：v1,v2,v4,v5,v6,v7,v3广度优先搜索序列：v1,v2,v3,v4,v6,v5,v7,树与图,图的基本应用及其复杂度分析最小（代价）生成树普里姆(Prim)算法：一棵树的生长,树与图,*复杂度为 O(n2)，与边数无关，适合于求边稠密的网的最小生成树。,图的基本应用及其复杂度分析最小（代价）生成树克鲁斯卡尔(Kruskal)算法：森林的生长,树与图,*适合于求边稀疏的网的最小生成树，复杂度为 O(e log e)。,自测题已知一个带权连通图G=(V,E)，其中顶点集合为V=1,2,3,4,5，其邻接矩阵如图，求出其所有可能的最小生成树。,树与图,图的基本应用及其复杂度分析最短路径单源（带权）最短路：迪杰斯特拉(Dijkstra)算法 贪心，按长度递增生成，当新顶点使路径更短时，更新路径，O(n2)。多源（带权）最短路：弗洛伊德(Floyd)算法 O(n3)，但比重复Dijkstra算法简单。,树与图,图的基本应用及其复杂度分析拓扑排序：有向无环图(DAG)的应用之一选一个无前驱顶点输出；删除该顶点以及所有以之为尾的弧；重复第1、2步，直到全部顶点输出，或不存在无前驱顶点(说明有环)。注意：拓扑排序可方便检查有向图中是否存在环；确定无环时，也可用DFS进行拓扑排序，退出DFS的顺序即为逆向的拓扑序；DFS可方便检查无向图中是否存在环(若遇到回边即有环)。,树与图,图的基本应用及其复杂度分析关键路径：AOE网 带权DAG,树与图,2,3,2,3,自测题判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用_求关键路径的方法 求最短路径的Dijkstra方法 深度优先遍历算法 广度优先遍历算法,树与图,自测题弗洛伊德(Floyd)算法是求图中每一对结点之间最短路径的算法。请描述该算法，并且回答：如何用该算法判断图是否有回路？请说明理由。,树与图,检查对角元DN 1 ii，若存在非的对角元，就表明图中有回路。因为若DN 1 ii非，说明存在某个k，使得Dkii的值被更新为（Dk 1 ik+Dk 1 ki），即存在一条从i到k、再从k到i的路径。,自测题如何判断图中有负回路（即回路中边的权值之和为负数）？请说明理由。,树与图,将对角元Costii初始化为0，当Dk ii0时，图中必存在负回路。,查找与排序,查找概念：静态查找动态查找（随时插入删除）平均查找长度=PiCi，其中Pi为查找第i个记录的概率，满足Pi=1；Ci是找到第i个记录需要比较的次数。当查找不成功的情况也考虑在内时，平均查找长度是（成功+不成功）的平均查找长度。,查找顺序查找法：逐个比较。若对n个记录做等概率查找（即Pi=1/n），则平均查找长度为不成功的查找必定进行n+1次比较。设成功与不成功概率相同，都是1/2n，则平均查找长度为缺点：效率低优点：简单、适用面广 对结构无要求，不要求有序，也适用于链表。,查找与排序,(n+1)/2。,3(n+1)/4。,查找折半查找法：有序表的查找成功查找的最多比较次数为等概率成功查找的平均查找长度为优点：效率高缺点：只适用于有序表，且不适用于线性链表,查找与排序,log2n+1。,(1+1/n)log2(n+1)-1。,查找B树：平衡多路查找树,查找与排序,每个结点至多有m棵子树；若根不是叶子，则至少有2棵子树；除根之外所有非叶子结点至少有m/2棵子树；所有非叶子结点包含(n,p0,K1,p1,K2,p2,.,Kn,pn),其中Ki为关键字且有序（递增）,pi所指子树中所有关键字Kn。所有叶子在同一层，为NULL。,47,23,在有N个关键字的m阶B树上进行查找，从根结点到关键字所在结点的路径上涉及的结点数不超过,查找B树：插入、删除,查找与排序,30,30,30 37,26,26 30 37,85,61 70 85,70,7,3 7 12,最小值,50,最小值,61,53,61,50,自测题下面关于m阶B树说法正确的是（）每个结点至少有两棵非空子树树中每个结点至多有m一1个关键字所有叶子在同一层上当插入一个数据项引起B树结点分裂后，树长高一层,查找与排序,自测题B-树中叶子结点数s与关键字数n的关系是s=n/2s=n-1s=n+1 无法确定,查找与排序,设B-树第i个结点的子树数为Ci，则该结点的关键字数Ni=Ci-1。对于有k个结点的B-树：n=Ni=(Ci-1)=Ci-k 每个结点（除根结点）都是一棵子树：Ci=(k-1)+s,查找散列(Hash)表及其查找关键问题：设计哈希函数解决同义词冲突哈希函数：（任一关键字等概率映射到任一地址的哈希函数是均匀(Uniform)的）各种方法（p.253-256，其中key%p最常见）冲突处理开放定址法：线性、二次（）、伪随机探测再散列再哈希法（冲突时计算另一个哈希函数地址）链地址法（同义词链表）,查找与排序,查找散列(Hash)表及其查找查找分析装填因子哈希表的平均查找长度是 的函数，而不是 n 的函数从非链地址处理冲突的哈希表中删除一个记录，须在该记录的位置上填入一个特殊符号，以免找不到在它之后填入的同义词对于预先知道且规模不大的关键字集，应尽力设计不发生冲突的完美哈希函数,查找与排序,自测题下面关于哈希查找的说法正确的是（）哈希函数构造的越复杂越好，因为这样随机性好，冲突小 除留余数法是所有哈希函数中最好的 不存在特别好与坏的哈希函数，要视情况而定若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可,查找与排序,自测题设有一组记录的关键字为 19，14，23，1，68，20，84，27，55，11，10，79，用链地址法构造散列表，散列函数为H（key）=key MOD 13，散列地址为1的链中有几个记录？1234,查找与排序,自测题设哈希表长m14，哈希函数H（key）key11。表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空。如果用二次探测再散列处理冲突，关键字为49的结点的地址是 8359,查找与排序,内部排序概念基本操作：比较+移动存储方式：数组：必须移动记录静态链表：表排序，仅修改指针数组+地址：地址排序，然后调整记录位置稳定的排序法：关键字等值的记录在排序前后的先后位置不变,查找与排序,内部排序插入排序直接插入排序：理扑克牌的过程。正序最快O(n)，逆序最慢O(n2)，平均O(n2)。折半插入排序：查找的过程用“折半查找”，减少了比较次数，但移动次数不变，还是O(n2)。气泡排序(bubble sort)每趟比较相临记录，最大值沉入水底。复杂度与直接插入排序类似。,查找与排序,自测题用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是哪个？94,32,40,90,80,46,21,6932,40,21,46,69,94,90,8021,32,46,40,80,69,90,9490,69,80,46,21,32,94,40,查找与排序,自测题若用冒泡排序方法对序列 10,14,26,29,41,52 从大到小排序，需进行多少次比较？3101525,查找与排序,5+4+3+2+1=15,内部排序简单选择排序方法：每次从未排序的序列中（i n1）找关键字最小的记录，与第 i 个记录交换。复杂度：移动少，正序不动，逆序 O(n)；但比较次数恒为 n(n1)/2。总复杂度还是 O(n2)。,查找与排序,内部排序希尔(Shell)排序方法：对分割出的若干子序列分别进行直接插入排序，直到基本有序，再对全部记录进行一次直接插入排序。所用时间是增量序列的函数增量序列的取法：注意应使增量序列中的值没有除1以外的公因子，并且最后一个增量必须等于1。,查找与排序,内部排序快速排序方法：以枢轴（支点）将记录分割为两部分，递归注意：不同教材处理支点位置的方法不同平均时间复杂度为O(nlogn)，且常数因子在同数量级的此类排序法中最小需要栈空间实现递归，最坏情况深度可达n。若每趟排序后先对长度短的子序列递归，则栈的最大深度为O(logn),查找与排序,内部排序堆排序堆：完全二叉树，对应一维数组。任一非叶子结点的值不大于（或不小于）其孩子结点的值。根结点必包含最小（或最大）值。堆的建立：自底向上反复“筛选”的过程。排序：反复调整“大顶堆”，将顶换到末尾。最坏复杂度 O(nlogn)，且仅需1个额外辅助空间。,查找与排序,自测题设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果？a，g，h，m，n，p，q，x，z a，g，m，h，q，n，p，x，z g，m，q，a，n，p，x，h，z h，g，m，p，a，n，q，x，z,查找与排序,内部排序归并排序(merge sort)非递归实现：2路归并复杂度 O(nlogn)，需要 O(n)额外空间稳定很少用于内部排序,查找与排序,内部排序基数排序多关键字排序：(K0,K1,.,Kd-1)最高位优先法MSD：必须逐层分割成子序列，分别排序最低位优先法LSD：不分子序列，对每个Ki都是整个序列参加排序。若对Ki(0id-2)的不同值，Ki+1均取相同值（例如扑克牌不同面值对应相同花色），则可不用比较关键字排序的方法，而是通过“分配”和“收集”实现排序链式基数排序：K=(K0,K1,.,Kd-1)，如13=(1,3)分解出的每个Ki都在相同范围内，按LSD反复分配、收集即可。分配 O(n)+收集 O(r)*d趟分配和收集；O(r+n)空间,查找与排序,内部排序各种内部排序算法的比较,查找与排序,内部排序各种内部排序算法的比较平均时间：快速排序最优，但其最坏情况不好。归并在 n 大时比堆排序快，但需要空间多。直接插入排序在基本有序或 n 小时好用。基数排序适合 n 大而关键字小的排序；若关键字也大，且大多数K0不同，则也可用MSD。基数排序和简单排序（插入、气泡、选择）是稳定的；快速排序、堆排序、希尔排序是不稳定的。一般比较相邻关键字的算法是稳定的。比较排序最坏情况下的最好复杂度为 O(nlogn)。,查找与排序,自测题以顺序表为存储结构，在300000个任意排序的数据中选择前100个最大值，下列哪种算法最快？快速排序堆排序归并排序插入排序,查找与排序,自测题在内部排序中，排序不稳定的有插入排序冒泡排序快速排序归并排序,查找与排序,