数据结构名词解释.docx

《数据结构名词解释.docx》由会员分享，可在线阅读，更多相关《数据结构名词解释.docx（9页珍藏版）》请在第一文库网上搜索。

1、数据结构名词解释一、五星级（已考过）,线性结构：结构中的数据元素之间只存在一对一的关系,搜索二叉树：它或者是一棵空树，或者是具有下列性质的二叉树：若它的 左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右 子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右 子树也分别为二叉排序树,图的最小生成树：一个连通图的生成树是图的极小连通子图，且包含原图中 的所有结点，并且只含尽可能最少的边，这就意味着砍去一条边，生成树就 称为非连通图，加一条边，就会形成图中的一条回路。那么最小生成树指的 就是用最少的边让图连通且边的总长度（权值）之和最短,堆：堆通常是一个可以被看做一棵树的

2、数组对象。并且满足以下性质D堆中某个节点的值总是不大于或不小于其父节点的值；2）堆总是一棵完全二叉树将根结点最大的堆称为大根堆，根结点最小称为小根堆,算法的时间复杂度：是一个函数，它定性描述了该算法的运行时间。或者 说是执行算法所需要的计算工作量，常用大O符号表述，使用这种方式 时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情 况二、五星级（未考）,数据：是信息的载体，是描述客观事物属性的树、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合，包含逻 辑结构、存储结构和数据运算数据类型：是一个值的集合和定

3、义在此集合上的一组操作的总称递归：程序调用自身的编程技巧，构成递归要具备以下情况：子问题须与原始问题为同样的事，且更为简单；不能无限制地调用本身，须有个出口，化简为非递归状况处理非线性结构：结构中的数据元素之间存在一对多、多对多关系ADT :抽象数据类型，是将类型和这个类型相关的操作集合封装在一起的数 据模型空间复杂度：指执行算法所需要的内存空间线性表：是具有相同数据类型的n个数据元素的有限序列顺序表：线性表的顺序存储。特点是表中的逻辑顺序与其物理顺序相同，随 机访问，通过首地址和元素序号在O(I)内就可以找到指定元素，但是在中间 插入或者删除元素，数据元素要移动单链表：线性表的链式存储又称为

4、单链表，它是指通过一组任意的存储单元 来存储线性表中的数据元素。非随机存取，既不能直接找到表中特定的结点, 只能从表头依次遍历，依次查找栈：是一种运算受限，即只允许在一端进行插入或删除操作的线性表，在 函数递归通常用到栈队列：是一种操作受限的线性表，只允许在表的一端进行插入，另一端进行删除(先进先出)，不能随便就读取队列中间的某个数据树：是一种数据结构，它是由n(n = 1 )个有限结点组成一个具有层次关系的集合。它具有以下的特点：每个结点有零个或多个子结点；没有父结 点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点 外，每个子结点可以分为多个不相交的子树；广义表：是一种非线性

5、的数据结构，是线性表的一种推广。即广义表中放松 对表元素的原子限制，容许它们具有其自身结构二叉树：是另一种树形结构，其特点是每个结点至多只有两颗子树，并且二 叉树的子树有左右之分，其次序不可任意颠倒满二叉树：高度为h ,并且含有2h -1个结点的二叉树，即树中的每一层 都含有最多的结点完全二叉树：高度为h ,有n个结点的二叉树，当且仅当其每个结点都与高 度为h的满二叉树中编号为1-n的结点一一对应时，才称为完全二叉树。性 质：叶子结点只能在层次最大的两层上出现；如果有度为1的结点，只能有 1个，且该结点没有右孩子；对于编号为i的结点，左孩子是2i ,右孩子是 2i+1(n),父节点是i/2向下

6、取整;n个结点的完全二叉树的高度为log2An 向下取整加1二叉排序树/二叉查找树/二叉搜索树：一棵二叉树或者是空二叉树，或者是 具有如下性质的：左子树所有结点的关键字都小于根节点的关键字，右子树 上所有结点的关键字均大于根节点的关键字，左子树和右子树又各是一棵二叉排序树带索引的二叉搜索树：基于二叉搜索树的基础上，每个元素拥有一个LeftSiZe域，其值等于该节点左子树的元素数加1 ,同时它给出了该节点在 其子树中的排名线索二叉树：对于n个结点的二叉树，在二叉链存储结构中有n + 1个空链 域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的 指针，这些指针称为线索，加上线索的二

7、叉树称为线索二叉树。哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的 带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼 树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近 平衡二叉树（AVL）:它或者是一颗空树，或者是具有下列性质的二叉 树：它的左右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对 值不超过1。平衡二叉树节点的平衡因子BF只可能是-1 , O或1B树：一棵m阶B树是一棵平衡的m路平衡查找树。它或者是空树，或 者是满足下列性质的树：根结点至少有两个子树；每个结点至多有m棵子 树，即最多包含m-1个关键字;除根结点外的所有非叶子结点至少有m

8、/2 向上取整棵子树；所有的叶子结点都位于同一层。压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存 储空间。目的是为了节省空间优先队列：普通的队列是一种先进先出的数据结构，元素在队列尾追加，而 从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最 高优先级的元素最先删除。优先队列具有最高级先出的行为特征。通常采用堆数据结构来实现。算法的稳定性：如果待排序表中的关键字相同的两个元素，在排序后相对位 置不变，则称为稳定算法。算法的稳定性并不能衡量一个算法的优劣，它只 是对算法的性质进行描述排序：就是重新排列表中的元素，使表中的元素满足按关键字递增或递减的 过程。内部

9、排序：排序期间元素全部放在内存中的排序外部排序：排序期间元素无法全部同时存放在内存中，必须在排序过程中根 据要求不断在在内、外存之间移动的排序无向完全图：如果任意两个顶点之间都存在边，则称该图为无向完全图。含 有n个顶点，有n(n-1)2条边；有向完全图：如果任意两个顶点之间都存在方向相反的两条弧，则成为有向 完全图，n个顶点有n(n-1)条边极大连通子图：在无向图中，极大连通子图二连通分量；如果是连通的，则 极大连通子图就是其本身，如果非连通，则有多个极大连通子图，即多个连 通分量；在有向图中，极大连通子图二强连通分量，如果是强连通的，则极 大连通子图就是其本身，如果不强连通，有个极大连通子

10、图，即多多个强连 通分量极小连通子图：连通图的生成树是包含全部顶点的一个极小连通子图 有向图：若E是有向边(也称为弧)的有限集合时，图G为有向图 无向图：若E是无向边(也称为边)的有限集合时，图G为无向图 简单路径：如果路径上的各顶点均不互相重复，称这样的路径为简单路径简单回路：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路 广度优先搜索(BFS):类似二叉树层序遍历，基本思想是：首先访问起始 顶点V ,接着由V出发，依次访问V的各个未访问过的邻接顶点w1、w2， 再从这些顶点出发访问他们所有未被访问过的邻接顶点，以此类推，直到图 中的所有顶点都被访问过为止深度优先搜索

11、(DFS):类似树的先序遍历，基本思想是：首先访问图中某 一起始顶点V ,然后由V出发，访问邻接且未被访问的任一顶点w1,在访问 与w1邻接且未被访问的任一顶点w2,重复，直到不再再继续向下访问，依 次初回到最近被访问到的顶点，若它还有邻接顶点未被访问过，则从该点开 始继续上述搜索过程，直到所有顶点均被访问为止最短路径：把从一个顶点到另一个顶点的一条路径上所经过边上的权值之和 定义为该路径的带权路径长度，最短的那条带权路径也称为最短路径拓扑排序：有向图G = (VzE)zV里结点的线性序列(vi1,vi2,vin),如果满足： 在G中从结点Vi到Vj有一条路径，则序列中结点Vi必先于结点Vj

12、,称这 样的线性序列为一拓扑序列。AOV网如果用有向无环图表示一个工程其顶点表示活动用有向边 表示活动Vi必须先于Vj的关系则将这种有向图称为顶点表示活动的网络， 记为AOV网AOE网：在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值 表示完成该活动的开销，则这种有向图为用边表示活动的网络，即AOE网 关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径称为关键 路径 三、四星级（自己总结的）,数据元素：是数据的基本单位，由若干数据项组成。比如学生记录是个数据 元素，它由学号、姓名、性别等数据项组成,数据的逻辑结构：数据元素之间的逻辑关系，它与数据的存储无关，分为线 性和非线性

13、,线性结构包含线性表；线性表又分为受限、推广、一般线性表，推广有数组 和广义表，受限有栈、队列、串,非线性结构包含集合、树形结构（一对多）、图状（多对多）,数据的存储结构：数据结构在计算机中的表示，也成为物理结构，它包含数 据元素的表示和关系的表示,顺序存储：把逻辑相邻的元素存储在物理位置也相邻的存储单元中，优点是 随机存取，缺点是只能使用相邻的一整块存储单元,链式存储：不要求逻辑上相邻的在物理位置也相邻，借助指针表示元素的逻 辑关系，优点是充分利用存储空间，缺点是指针会占用空间，而且只能顺序 存取,索引存储：存储元素时，附加建立索引表，优点是速度快，缺点是索引表会 占据空间,散列存储：根据元

14、素的关键字直接计算出该元素的存储地址。优点是检索、 增加和删除节点都很快，缺点是会有冲突,双链表：它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。 所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点 循环单链表：跟单链表区别在于，最后一个结点的指针不是NULLz而改为 指向头结点，从而整个链表形成一个环。（因此判空条件不是头结点是否为 空，而是它是否等于头指针）循环双链表：在循环单链表的基础上，多了前驱指针，并且头结点的前驱是 尾结点静态链表：借助数组来描述线性表的链式存储结构共享栈：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数 据空间，将

15、两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间 的中间延伸循环队列：把顺序队列臆造成一个环状空间，即把存储队列元素的表从逻辑 上看成一个环，也是为了克服假溢出的现象双端队列：是指允许两端都可以进行入队和出队操作输出受限的双端队列：只允许一段进行插入和删除，另一端只允许插入输入受限的双端队列：只允许一段进行插入和删除，另一端只允许删除特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零 元素的分布有一定规律性的矩阵。常见的有上（下）三角矩阵、对称矩阵、 对角矩阵等稀疏矩阵：矩阵元素个数相对于矩阵中非零元素个数来说非常多，这样的矩 阵称为稀疏矩阵。应用于三元组表和十字链表B

16、+树：B+树是应文件系统所需而出的一种B树的变型树。一棵m阶的B+树和m阶的B-树的差异在于：有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。查找：在数据集合中找满足某种条件的数据元素的过程称为查找查找表：用于查找的数据的集合称为查找表静态查找表：只涉及查询某个元素是否在查找表中，或者检索某个特定的元 素的各种属性，不需要再查找表中插入或者删除数据。静态查找表有顺序查 找、