数据结构概念名词解释大全.docx

数据结构概念名词解释大全 数据结构是计算机科学的基础概念之一，指的是对客观事物的符号表示。数据元素是数据的基本单位，也称节点（node）或记录（record）。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据项是有独立含义的数据最小单位，也称域(field)。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 根据数据元素间关系的基本特性，有四种基本数据结构： 1. 集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 2. 线性结构：结构中的数据元素之间存在一个对一个的关系。 3. 树形结构：结构中的数据元素之间存在一个对多个的关系。 4. 图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。 逻辑结构是抽象反映数据元素之间的逻辑关系，是算法设计的基础。物理结构是数据结构在计算机中的表示，是算法实现的基础。存储结构分为顺序存储结构和链式存储结构。 算法是对特定问题求解步骤的一种描述。算法的五个重要特性是：有穷性、确定性、可行性、输入和输出。算法设计的原则或要求是正确性、可读性、健壮性、效率与低存储量需求。 衡量算法效率的方法有事后统计法和事前分析估算法。算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n))，称 T (n) 为算法的渐近时间复杂度。算法运行时间的衡量准则是以基本操作在算法中重复执行的次数。 栈是一种限定仅在表尾进行插入或删除操作的线性表。队列是一种只能在队首进行删除、队尾进行插入的线性表。串是由零个或多个字符组成的有限序列。 树是一种特殊的数据结构，结点包含一个数据元素及若干指向其子树的分支。树的度是树中所有结点的度的最大值。叶子结点是度为零的结点。分支结点是度大于零的结点。树的深度是树中叶子结点所在的最大层次。 森林是m棵互不相交的树的集合。二叉树的性质有四点：在二叉树的第 i 层上至多有 2i-1 个结点；深度为 k 的二叉树上至多含 2k-1 个结点；对任何一棵二叉树，若它含有 n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1；具有 n 个结点的完全二叉树的深度为  log2n +1。 满二叉树是指的是深度为 k 且含有 2k-1 个结点的二叉树。完全二叉树是树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。 路径长度是路径上分支的数目。树的路径长度是树根到每个结点的路径长度之和。树的带权路径长度是树中所有叶子结点的带权路径长度之和，记作：WPL(T) = wklk。 关键路径是路径长度最长的路径。顶点是数据元素 vi 称为顶点。边、弧是顶点之间的直接连线。在无向图中称为边，在有向图中称为弧。弧头、弧尾是带箭头的一端称为弧头，不带箭头的一端称为弧尾。 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。通常有两条遍历图的路径：深度优先搜索和广度优先搜索。 排序的分类有内部排序和外部排序。内部排序是待排序记录存放在内存。外部排序是排序过程中需对外存进行访问的排序。按排序依据原则有插入排序、交换排序、选择排序、归并排序和基数排序等。 ADT 是抽象数据型，是一个数学模型和在该模型上定义的操作的集合。线性表是一种特殊的数据结构，是由 n(n≥0)个相同类型的元素组成的有序集合。栈是一种限定性数据结构，是一种限定只在表尾进行插入和删除操作的线性表。队列是一种先进先出的线性表。串是一种特殊的线性表，是一个有限的字符序列。