考研数据结构名词解释大全

考研数据结构名词解释大全一、绪论1.1数据数据是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。它是计算机程序加工的原料。1.2数据元素数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。也被称为记录。1.3数据项数据项是构成数据元素的不可分割的最小单位，它描述了数据元素的某个属性。1.4数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合。它包括三个方面的内容：数据元素之间的逻辑关系（逻辑结构）、数据元素及其关系在计算机中的存储方式（存储结构），以及施加在该数据结构上的操作（运算）。1.5逻辑结构逻辑结构是指数据元素之间的相互关系，它独立于数据的存储介质。常见的逻辑结构有集合结构、线性结构、树形结构和图状结构（网状结构）。1.6物理结构/存储结构物理结构或存储结构是指数据的逻辑结构在计算机中的具体表示方式，即数据元素及其关系在计算机存储器中的存储形式。主要的存储结构有顺序存储、链式存储、索引存储和散列存储。1.7数据类型数据类型是一个值的集合以及定义在这个值集上的一组操作的总称。它规定了程序中变量或表达式的取值范围和所能执行的操作。1.8抽象数据类型(ADT)抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。它强调数据的逻辑特性，而不关心其在计算机内部的具体表示和实现细节，即只描述数据对象集和相关操作集“是什么”，而不涉及“如何做到”。二、线性表2.1线性表线性表是具有相同特性的数据元素的一个有限序列。在线性表中，数据元素之间存在着一对一的线性关系，即除第一个和最后一个元素外，每个元素有且仅有一个直接前驱和一个直接后继。2.2顺序表顺序表是线性表的顺序存储结构，它是用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素在物理位置上也相邻。2.3链表链表是线性表的链式存储结构，它不要求逻辑上相邻的元素在物理位置上也相邻，而是通过“指针”或“引用”来表示元素之间的逻辑关系。2.4单链表单链表是链表的一种基本形式，每个节点除了存储数据元素外，只包含一个指向其后继节点的指针（或引用）。2.5双链表双链表是每个节点除了存储数据元素外，还包含两个指针（或引用），分别指向其前驱节点和后继节点。2.6循环链表循环链表是一种首尾相接的链表，其最后一个节点的指针（或引用）指向第一个节点（对于单循环链表），或者头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点（对于双循环链表）。2.7栈栈是一种特殊的线性表，它只允许在表的一端（通常称为栈顶）进行插入和删除操作。栈的操作遵循“后进先出”（LIFO）的原则。2.8队列队列是一种特殊的线性表，它只允许在表的一端（队尾）进行插入操作，而在另一端（队头）进行删除操作。队列的操作遵循“先进先出”（FIFO）的原则。2.9循环队列循环队列是为了解决顺序存储队列可能出现的“假溢出”问题而设计的。它将存储队列的数组视为一个首尾相接的圆环，通过巧妙的指针（队头指针和队尾指针）管理，使得队列空间得到充分利用。2.10链栈链栈是采用链式存储结构实现的栈。通常以单链表的形式实现，栈顶指针即为链表的头指针。2.11链队列链队列是采用链式存储结构实现的队列。通常用一个带有头指针和尾指针的单链表来表示，头指针指向队头节点，尾指针指向队尾节点。2.12串串（字符串）是由零个或多个字符组成的有限序列。串中字符的个数称为串的长度，长度为零的串称为空串。三、树与二叉树3.1树树是一种非线性的数据结构，它由n（n≥0）个节点组成。当n=0时，称为空树；当n>0时，有且仅有一个特定的称为根的节点，其余节点可分为m（m≥0）个互不相交的有限集，每个集合本身又是一棵树，称为根的子树。3.2节点的度树中一个节点拥有的子树数目称为该节点的度。3.3树的度树中所有节点的度的最大值称为树的度。3.4叶子节点度为零的节点称为叶子节点或终端节点。3.5分支节点度不为零的节点称为分支节点或非终端节点。3.6孩子节点与双亲节点在树中，一个节点的子树的根节点称为该节点的孩子节点（或子节点），相应地，该节点称为孩子节点的双亲节点（或父节点）。3.7兄弟节点具有相同双亲的节点互为兄弟节点。3.8节点的层次从根节点开始定义，根节点为第一层，根的孩子节点为第二层，以此类推。3.9树的深度/高度树中节点的最大层次数称为树的深度或高度。3.10二叉树二叉树是另一种树形结构，它的特点是每个节点至多只有两棵子树（即二叉树中不存在度大于2的节点），并且子树有左右之分，其次序不能任意颠倒。3.11满二叉树满二叉树是指深度为k且含有2^k-1个节点的二叉树。在满二叉树中，每层节点都达到最大数。3.12完全二叉树完全二叉树是指深度为k，有n个节点的二叉树，当且仅当其中的节点与深度为k的满二叉树中编号从1至n的节点一一对应时，称为完全二叉树。3.13二叉树的遍历二叉树的遍历是指按某种顺序访问二叉树中的每个节点，使得每个节点被访问一次且仅被访问一次。常见的遍历方法有先序遍历、中序遍历和后序遍历，以及层次遍历。3.14先序遍历先序遍历（根左右）：访问根节点，然后递归地先序遍历左子树，再递归地先序遍历右子树。3.15中序遍历中序遍历（左根右）：递归地中序遍历左子树，访问根节点，再递归地中序遍历右子树。3.16后序遍历后序遍历（左右根）：递归地后序遍历左子树，递归地后序遍历右子树，最后访问根节点。3.17线索二叉树线索二叉树是一种对二叉树进行改进的存储结构。在二叉树的节点上增加线索（指向其前驱或后继节点的指针），使得在遍历过程中无需使用栈或递归，就能方便地找到某个节点的前驱和后继。3.18哈夫曼树（最优二叉树）哈夫曼树是指给定n个权值作为n个叶子节点，构造一棵二叉树，使得该树的带权路径长度达到最小。哈夫曼树常用于数据压缩等领域。3.19哈夫曼编码哈夫曼编码是一种基于哈夫曼树的前缀编码方式。在哈夫曼树中，从根节点到叶子节点的路径上，左分支标记为0，右分支标记为1，叶子节点对应的编码即为从根到该叶子的路径上的标记序列。哈夫曼编码能使编码总长度最短，且保证无歧义解码。3.20二叉排序树(BST)二叉排序树（又称二叉查找树）是一种特殊的二叉树，它或者是空树，或者具有以下性质：若其左子树非空，则左子树上所有节点的值均小于根节点的值；若其右子树非空，则右子树上所有节点的值均大于根节点的值；其左、右子树也分别为二叉排序树。3.21平衡二叉树(AVL树)平衡二叉树是一种特殊的二叉排序树，它要求树上任一节点的左子树和右子树的深度之差（平衡因子）的绝对值不超过1。目的是为了保证二叉排序树的查找效率。四、图4.1图图是由顶点集V和边集E组成的数据结构。其中，顶点集V是有限的非空集合；边集E是由V中顶点的无序对（无向边）或有序对（有向边）构成的有限集合。4.2有向图若图中所有的边都是有方向的（即边是顶点的有序对），则称该图为有向图。4.3无向图若图中所有的边都是无方向的（即边是顶点的无序对），则称该图为无向图。4.4顶点的度在无向图中，顶点的度是指依附于该顶点的边的数目。在有向图中，顶点的度分为入度和出度，入度是指以该顶点为终点的边的数目，出度是指以该顶点为起点的边的数目，顶点的度等于其入度与出度之和。4.5路径在图中，从一个顶点到另一个顶点所经过的顶点序列（连同相关的边）称为路径。4.6路径长度路径上的边的数目称为路径长度。对于带权图，路径长度是路径上各条边的权值之和。4.7回路/环起点和终点相同的路径称为回路或环。4.8简单路径路径中顶点不重复出现的路径称为简单路径。4.9连通图在无向图中，如果从顶点u到顶点v有路径，则称u和v是连通的。如果图中任意两个顶点都是连通的，则称该无向图为连通图。4.10强连通图在有向图中，如果对于每一对顶点u和v，都存在从u到v和从v到u的路径，则称该有向图为强连通图。4.11连通分量无向图的极大连通子图称为该图的连通分量。4.12邻接矩阵邻接矩阵是图的一种存储结构。对于一个具有n个顶点的图，用一个n×n的矩阵来表示顶点间的相邻关系。矩阵的元素表示顶点间是否有边（或弧）相连，以及边上的权值（对于带权图）。4.13邻接表邻接表是图的另一种常用存储结构。它为图中的每个顶点建立一个单链表，链表中的每个节点表示依附于该顶点的边（或弧），包含邻接顶点的信息和指向下一条边的指针。4.14深度优先搜索(DFS)深度优先搜索是一种图的遍历算法。其基本思想是：从图中某个顶点v出发，访问v，然后依次从v的未被访问的邻接点出发进行深度优先搜索，直至图中所有和v有路径相通的顶点都被访问到。4.15广度优先搜索(BFS)广度优先搜索是另一种图的遍历算法。其基本思想是：从图中某个顶点v出发，访问v，然后依次访问v的所有未被访问的邻接点，再按这些邻接点被访问的先后顺序依次访问它们的邻接点，直至图中所有和v有路径相通的顶点都被访问到。4.16最小生成树(MST)对于一个连通的带权无向图，其生成树是包含图中所有顶点的一个极小连通子图。最小生成树是指所有可能的生成树中，带权路径长度之和最小的那棵生成树。4.17最短路径在带权图中，从一个顶点（源点）到另一个顶点（终点）的所有路径中，路径上各边的权值之和最小的路径称为最短路径。4.18拓扑排序拓扑排序是对有向无环图（DAG）的顶点进行排序，使得对于图中任意一条有向边u->v，在排序序列中u都出现在v之前。拓扑排序常用于任务调度等场景。五、查找5.1查找查找是指在数据集合中寻找满足某种条件的数据元素的过程。5.2平均查找长度(ASL)平均查找长度是衡量查找算法效率的重要指标，它是指在查找过程中，为找到目标元素所需进行的关键字比较次数的期望值。5.3顺序查找顺序查找（线性查找）是一种最简单的查找方法。它从表的一端开始，依次将每个元素的关键字与给定值进行比较，直到找到匹配的元素或查遍整个表。5.4折半查找(二分查找)折半查找是一种高效的查找方法，但要求查找表必须是有序的顺序表。它的基本思想是：将给定值与表中间位置的元素关键字进行比较，若相等则查找成功；若给定值小于中间元素关键字，则在表的前半部分继续查找；否则在表的后半部分继续查找，重复上述过程，直至查找成功或确定表中无该元素。5.5分块查找(索引顺序查找)分块查找是一种结合了顺序查找和折半查找优点的查找方法。它将查找表分成若干块，块内元素可以无序，但块之间必须有序。先通过索引表确定待查元素可能所在的块，然后在该块内进行顺序查找。5.6二叉排序树查找利用二叉排序树的特性进行查找。在二叉排序树中，从根节点开始，若给定值等于根节点的关键字，则查找成功；若给定值小于根节点的关键字，则在左子树中继续查找；否则在右子树中继续查找。5.7平衡二叉树查找平衡二叉树（AVL树）是一种保持平衡的二叉排序树。在平衡二叉树上进行查找，其平均查找长度与logn同阶，具有较高的效率。5.8B-树B-树是一种多路平衡查找树，常用于文件系统中。一棵m阶B-树或为空树，或为满足特定条件的m叉树，其核心特点是每个节点可以有多个关键字和多个子树，且始终保持树的平衡。5.9B+树5.10哈希表(散列表)哈希表是一种通过哈希函数将关键字映射到表中存储位置来进行访问的数据结构。理想情况下，哈希查找可以在常数时间内完成。5.11哈希函数哈希函数是哈希表的核心，它将关键字映射为哈希表中的存储地址。一个好的哈希函数应能使关键字均匀地分布在哈希表中，以减少冲突。5.12冲突(碰撞)在哈希表中，不同的关键字通过哈希函数可能得到相同的存储地址，这种现象称为冲突或碰撞。5.13处理冲突的方法六、排序6.1排序排序是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列的过程。6.2稳定排序与不稳定排序如果在待