数据结构基础知识整理

数据结构基础知识整理*名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。*2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。*3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。*4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。*5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。*6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且其余每个结点只有一个直接前趋和一个直接后继。*7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。*8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。*9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。*10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。*11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而实现是要在存储结构上进行。*12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。*13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻物理位置上来反映结点间逻辑关系。*14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结点的直接后继结点。头指针是它的充分必要的信息。单链表是一种单向的结构。*15、双链表：每个结点中增加了一个prior，用来指向该点的直接前趋结点。它是一种双向、对称的结构。*16、循环链表：是一种首尾相接的链表。单循环链表形成一个next链环，而双循环链表形成next链环和prior链环。*17、存储密度：是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。顺序表的存储密度为1，而链表的存储密度小于1。*18、栈：只允许在一端进行插入、删除运算的线性表，称为“栈”（stack）。*19、LIFO表：即后进先出表，修改操作按后进先出的原则进行。譬如栈就是一种LIFO表。*20、顺序栈：采用顺序存储结构的栈，称为顺序栈。*21、链栈：采用链式存储结构的栈，称为链栈。*22、队列：只允许在一端进行插入、另一端进行删除运算的线性表，称为“队列”（queue）。*23、FIFO表：即先进先出表。譬如队列就是一种FIFO表。*24、顺序队列：采用顺序存储结构的队列，称为顺序队列。*25、循环队列：为克服顺序队列中假上溢现象，将向量空间想象为一个首尾相接的圆环，这种向量称为循环向量，存储在其中的队列称为循环队列。*26、链队列：采用链式存储结构的队列，称为链队列。*27、字符串：由零个或多个字符组成的有限序列，一般高为S=“a1，a2，…an”。*28、空白串：由一个或多个空格组成的串称为空白串。*29、空串：长度为零的串称为空串，它不包括任何字符。*30、顺序串：串的顺序存储结构简称的为顺序串。*31、链式串：串的链式存储结构简称为链式串。*32、模式匹配：子串的定位运算又称为串的模式匹配。*33、对称矩阵：元素满足aij=aji（0≤i,j≤n）的矩阵。*34、三角矩阵：主对角线以上或以下的元素（不包括对角线）均为常数的矩阵。*35、带状矩阵：所有非零元素均集中在以主对角线为中心的带状区域的矩阵。*36、稀疏矩阵：非零元素远远少于矩阵元素的矩阵。*37、广义表：有n个元素a1,a2…an组成的有限序列，其中n可以是原子或一个广义表。*38、三元组表：若线性表顺序存储的每一个结点均是三元组，那么该线性表的存储结构称为三元组表。*39、行表：记录稀疏矩阵中每行非零元素在三元组表中的起始位置的表称为行表。*40、内部排序：假设给定含有n个记录（R1,R2……,Rn）的文件，其相应的关键字为（K1，K2，……,Kn）,则排序是确定一个排列（P(1),P(2),……P(n)），使得（Kp(1))≤Kp(2)≤……≤Kp(n)），从而得到有序文件（R*p(1),Rp(2),……,Rp(n)）。整个排序过程都在内存中进行的排序即为内部排序。*41、稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然保持不变，则这处排序方法是稳定的。*42、就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O(1),则称为就地排序。*43、堆：n个关键字序列K1，K2，……,Kn，称为堆，当且仅当序列满足如下性质：Ki≤K2i，且Ki≤K2i＋1或Ki≥K2i，且Ki≥K2i＋1。*44、查找：即给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。*45、动态查找表：若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表。*46、静态查找表：若在查找的同时不对表做修改操作（如插入和删除），则相应的表称之为静态查找表。*47、内查找：若整个查找过程都在内存中进行，则称之为内查找。*48、外查找：若查找过程中需要访问外存，则称之为内查找。*49、平均查找长度：ASL＝∑pici，其中n是结点的个数；pi是查找第i个结点的概率；ci是找到第i个结点所需要进行的比较次数。*50、散列函数：在关键字和表地址之间建立的对应关系h称为散列函数。*51、冲突：两个不同的关键字，其散列函数值相同，因而被映射到同一个表位置上的现象称为冲突。*52、同义词：发生冲突的两个关键字称为该散列函数的同义词。*53、装填因子：设m和n分别表示表长和表中填入的结点数，则将ɑ=n/m定义为散列表的装填因子。*二、填空*1、数据的存储结构可用四种基本的存储方法表示，它们分别是顺序存储方法、链接、索引、散列。2、数据的运算最常用的有五种，检索、插入、删除、更新、排序。*3、一个算法的效率可分为时间和空间效率。4、数据结构按逻辑结构可分为线性结构和非线性结构。线性结构反映结点间的逻辑关系是一对一的，非线性是多对多的。*5、顺序表相对于链表的优点有节省存储和随机存储。6、链表相对于顺序表的优点有插入和删除操作方便。*7、按顺序存储方法存储的线性表称为顺序表，按链式存储方法存储的线性表称为链表。8、线性表中结点的集合是有限的，结点间的关系是一对一的。*9、在n个结点的顺序表中插入(删除)一个结点需平均移动n/2（(n-1)/2）个结点，具体的移动次数取决于表长n和插入（删除）位置i。*10、在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。*11、在民个结点的单链表中要删除已知结点*p，需找到它的直接前趋结点的地址，其时间复杂度为O(n)。*12、在双链有中要删除已知结点*p，其时间复杂度为O(1)。*13、在单链表中要在已知结点*p之前插入一新结点，仍需找到*p的直接前趋结点的地址，其时间复杂度为O(n)；而在双链表中，完成同样操作其时间复杂庶O(1)。*14、在循环链表中，可根据在一结点的地址遍历整个链表，而单链表中需知道头指针才能遍历链表。15、在栈中存取数据遵从后进先出的原则，队列中则是先进先出。*16、栈结构中，允许插入、删除的一端称为栈顶，另一瑞称为栈底；在队列中，允许插入的称为队尾，允许删除的一端称为队首。*17、在有n个元素的栈中，进栈和退栈操作的复杂度为O(1)和O(1)。*18、设长度为n的链队列用单循环链表示，若只设头指针，则入队和出队操作的时间复杂度分别为O(n)和O(1)；若只设尾指针，则O(1)和O(1)。*19、通常在程序中使用串可分为串变量和串常量；而串按存储方式又可分为顺序串和链式串。20、链式存储与顺序存储的相互串匹配算法的效率相同。*21、成功匹配的起始位置称为有效位移，所有匹配不成功称为无效位移；NaivestrMatch返回的是第1个有效位移。*22、串的朴素匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)m,n为主串长，m为子串长。*23、对于数组An×m，其元素aij按行优先与列优先存储的地址之差为(i-1)(n-1)-(j-1)(m-1).(两次存储的LOC(a11)相同.)*24、特殊矩阵是指非零或零元素分布有一定规律的矩阵。25、多维数组的存储方式有顺序和链式。26、递归表是指允许递归的广义表，纯表是指与树对应的广义表。*27、任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可是广义表而表尾必定是广义表。*28、表的长度是指广义表元素的个数，表的深度是指广义表展开后扩号的层数。29、树中结点的最大层次称为树的深度（高度）。*30、若有一棵二叉排序树，则按照中序遍历顺序将产生一个有序序列。31、由一棵二叉树的前序序列和中序可惟一确定这棵二叉树。*32、将一棵树转换成一棵二叉树后，二叉树的根结点没有右子树。33、图有邻接矩阵、邻接表等存储结构，遍历图有深度优先（DFT）和广度优先（BFT）等方法。*34、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。35、如果n个顶点的图是一个环，则它有n个生成树。*36、n个顶点e条边的图用邻接矩阵（邻接表）存储，则空间复杂度为O(n2)（O(n+e)）。37、稀疏（稠密）图G，采用邻接表（邻接矩阵）存储较省空间。*38、图的逆邻接表存储结构只适用于有向图。39、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是将邻接矩阵的第i行全置0、*40、n个顶点e条边的图用邻接矩阵（邻接表）存储，深度优先遍历的时间复杂度为O(n2)（O(n+e)）。（广度优先时间复杂度同上。）*41、图的BFS生成树的树高比DFS生成树的树高小或相等。*42、用Prim（Kruskal）算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O(n2)（O(elog2e)）。*43、稀疏（稠密）图G的最小生成树，最好用Kruskal（Prim）算法求解。*44、用迪杰斯特拉（Dijkstra）算法求n个顶点e条边的图中的某一顶点到其余各顶点间最短路径的时间复杂度为O(n2)。*45、用Dijkstra算法求某一顶点到其余各顶点间最短路径是按路径长度递增的次序来得到最短路径的。*46、拓扑排序算法是通过重复选择具有0个前趋顶点的过程来完成的。47、拓扑排序输出的顶点数小于有向的顶点数，刚该图一定存在环。*48、对n个顶点e条边的图进行拓扑排序，算法的时间复杂度为O(n+e)。*49、在插入和选择排序中，若初始数据基本正序，则选用插入；若初始反序，则选用选择。*50、在堆排序和快速排序中，初始记录接近正序或反序，则用堆，初始无序则用快速。*51、在堆、快速和归并排序中，只考虑存储空间，先选堆，其次快速，最后并归；只从排序结果的稳定性考虑，则先并归；只从平均情况下最快考虑，先选快速；只从最坏考虑并要节省内在，则先堆。*52、大多数排序算法都有两个基本操作：比较两上关键字的大小和改变指向记录的指针或移动记录本身。*53、散列法存储的基本思想是由关键字的值决定数据的存储地址。54、散列表的查找效率主要取决于散列表造表是时选取的散列函数和处理的方法。*55、当所有结点的权值都相等时，用这些结点构造的二叉树的特点是只有右子树。56、m阶B-树每一个结点的子树都小于或