数据结构名词解释

第一章

数据
数据是描述客观事物的符号 , 是能够被计算机输入 , 识别 , 处理的各种符号 , 是
计算机化的信息。
数据项
数据不可分割的最小单位 , 一个元素由若干个数据项构成。
数据元素
它是组成数据的基本单位 , 是数据集合中的个体 , 在计算机程序中 , 通常作为一
个整体进行考虑和处理。
数据对象
是性质相同的数据元素的集合 , 是数据的一个子集。
数据处理
是指对数据进行查找 , 插入 , 删除, 合并 , 排序, 统计以及简单计算等的操作过
程。
数据结构
是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示 ( 即
数据的逻辑结构和物理结构 ), 并对这种结构定义相适应的运算 , 设计出相应的
算法, 且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
数据类型
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型
是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决
于它的一组逻辑特性 , 而与其在计算机内部如何表示和实现无关。
９. 算法
解决一个问题的方法和步骤。
时间复杂度
T(N) ＝O(F(N)), 它表示随问题规模Ｎ增大 , 算法执行时间增长率与 F(N) 的增长
率相同 ,F(N) 算法的时间复杂性。
原地工作
算法执行时 , 若额外空间相对于输入数据量来说是常数 , 则称此算法为原地工
作。
线性表
一种数据结构 , 是 N(N>=0)个同质元素的有限序列 , 除首尾元素外 , 每个元素有
唯一的前驱和唯一的后继。
队列
是一种受限线性表 , 是先进先出的线性表
循环队列
在队列的顺序存储结构中 , 把存储空间的首尾逻辑上相连 , 构成一个环 , 使得存
储空间上只要有空余的地址 , 就可以继续进行入队列操作 , 极大利用了物理空
间。用头部和尾部两个指示器表示队列头和队列尾 , 插入在尾部进行 , 删除在头
部进行。
单链表
每一个数据元素 , 都需用两部分来存储：一部分用于存放数据元素值 , 称为数据
域；另一部分用于存放直接后继结点的地址 ( 指针), 称为指针域 , 元素的存储空
间可以连续 , 也可以是不连续的。而数据元素之间的逻辑关系由指针域来确定。
双向链表
线性表采用链式存储时 , 每个结点除一个数据域外 , 包含两个指针域 , 一个指向
该结点的直接后继 , 一个指向该结点的直接前驱 , 这种方式构成的链表 , 即为双
向链表。
希尔排序
是插入排序的一种 , 又叫缩小增量排序 , 先按增量进行分组 , 组内插入排序 , 然
后每次缩短增量 , 再进行分组和组内插入排序 , 直到增量为 1 时, 进行最后一
次排序止。
完全图
任何一个有 N 个结点的无向图 , 若其边数为 N(N-1)/2, 则这个无向图就是完全
图
广度遍历
按层次编历方式 , 从某一点 V0 开始遍历它的所有邻接点 V1,V2……, 再依次访
问 V1,V2.. 的所有未被访问过的邻接点 , 直到所有的点均遍历完成
关键字
数据元素的某个数据项的值 , 用它可以标识列表的一个或一组元素。
串
串是字符线性的有限集合。
子串
串中任意个连续的字符组成的子序列称作该串的子串。
栈

是一种受限线性表 , 是插入和删除操作在同一端进行的 , 是后进先出的线性表。

第六章

树
树是 n(n>=0) 个结点的有限集。在任意一棵非空树中：
(1) 有且仅有一个特殊的称为根的结点 ;
(2) 当 n>1时, 其余结点可分成 m(m>0)个互不相交的有限集 T1,T2,...,Tm, 其中
每一个集合本身又是一棵树 , 并且称为根的子树。
结点

结点不仅包含数据元素，而且包含指向子树的分支
叶子结点
度为 0 的结点 , 即没有后继的结点 .
非终端结点

又叫作分支节点，指度不为0的结点，有后继的节点
二叉树
二叉树是每个结点至多有两个孩子结点的一种树。其中两个孩子结点分别被称
为左孩子结点和右孩子结点。
子孙
子孙结点以某结点为根的子树中的任一结点都称为该结点的子孙。
孩子结点与双亲结点
树中某个结点的子树的根结点称为该结点的孩子结点。相反 , 称该结点为孩子
结点的双亲结点。
结点的度
树的某个结点的分支 ( 子树) 个数叫做该结点的度。
树的度
树的度是树中所有结点的最大度数。
平衡因子
结点的左子树深度与右子树深度之差。
生成树
一个连通图的生成树是指一个极小连通子图 , 它含有图中的全部顶点 ,N-1 条
边。
满二叉树
如果所有的分支结点都有左右孩子结点，并且叶子节点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。

（严版）深度为 K,且有 2^K -1 个结点的二叉树称为满二叉树
完全二叉树
对满二叉树的结点从上到下 , 从左到右进行依次进行编号 , 若有一棵二叉树的每一个结点都与深度为 K 的满二叉树中编号都一一对应时 , 只是最后一层不满 ,称做完全二叉树 .
堂兄弟
同一层上不同双亲的结点 , 互称堂兄弟 .
兄弟

同一个双亲的孩子之间互为兄弟
祖先
一个结点的祖先是指从根结点到该结点的路径上的所有结点。
层次

从跟开始，根为第一层，根的孩子为第二层，跟的孩子的孩子为第三层，以此类推
树的高度
树中所有结点的层次的最大值 .
结点的深度（从上往下）

从根结点到该结点路径上的结点数
结点的高度（从下往上）

从某结点往下走可能到达多个叶子结点，对应了多条通往这些叶子结点的路径，其中最长的那条路径上结点的个数即为该结点在树中的高度
有序树

树中结点的子树从左到右是有次序的，不能交换
无序树

树中结点的子树没有顺序，可以任意交换
丰满树

丰满树即理想平衡树，要求除最底层外，其他层都是满的
森林

若干棵互不相交的树的集合
顺序存储结构

按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素
层次遍历

要进行层次遍历，需要建立一个循环队列，先将二叉树头节点入队列，然后出队列，访问该结点，如果它有左子树，则将左子树的根节点入队；如果它有右子树，则将右子树的根节点入队。然后出队列，对出对节点访问。如此反复，直至队列为空为止。
路径

路径是指从书中的一个结点到另一个结点的分支所构成的路线
路径长度

路径长度是指路径长的分支数目
树的路径长度

树中每个结点到根结点的路径长度之和。根到每个结点的路径长度的最大值应是树的高度减一
带权路径长度

结点具有权值，从该结点到根之间的路径长度乘以结点的权值，就是该结点的带权路径长度
树的带权路径长度 (WPL)
树中所有叶子结点的带权路径长度之和 .
结点的带权路径长度
该结点到树根之间的路径长度与结点上权的乘积。
哈夫曼树的特点
1. 权值越大的结点，距离根节点越近
2. 树中没有度为1的结点。这列数又叫作正则（严格）二叉树
3. 树的带权路径长度最短
前缀编码

如果在一个编码方案中，任何一个编码都不是其他任何编码的前缀（最左子串），则称该编码是前缀编码。

其他知识点

二叉树是一种逻辑结构，但线索二叉树是加上线索后的链表结构，即它是二叉树在计算机内
部的一种存储结构，所以是一种物理结构。

第七章图

图
图是顶点与边的集合。为了与树形结构进行区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对。若两个顶点之间存在着一条边，则表示这两个顶点具有相邻关系。一般表示为一个二元组 , 即, 图 G=(V,E), 各个顶点之间
是多对多的关系。
有向图

每条边都是由方向

无向图

每条边都没有方向

在有向图中，通常将边称为弧，含箭头的一端称为弧头，另一端称为弧尾。

图中顶点的度
顶点 V的度是图中和顶点 V相关联的边的数目。包括入度和出度两种。
有向完全图
任何一个有 N 个结点的有向图 , 若其弧个数为 N(N-1) 个, 则这个有向图就是有
向完全图。
无向完全图

若无向图中有n个顶点，则最多有n(n-1)/2条边（任意两个顶点之间都有一条边），将具有n(n-1)/2条边的无向图称为无向完全图。
路径

在一个图中，路径为相邻定点序偶所构成的序列。路径长度是指路径上边的数目。

简单路径
在用一个顶点序列表示一条路径时 , 若序列中没有相同的顶点重复出现 , 则称
其为简单路径。
回路

若一条路径中第一个顶点和最后一个顶点相同，则这条路径是一条回路
简单回路
除了第一个顶点和最后一个顶点之外 , 其余顶点均不相同的回路称为简单回
路。
连通

在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。
连通图
对于无向图 , 若 V1到 V2有路径 , 称 V1V2是连通的 , 若图中任意两点都是连通的 ,
则称该无向图是连通图。
连通分量
对于一个无向图 , 其极大连通子图叫做该图一个连通分量。
强连通图
对于一个有向图 , 每两个顶点之间都有路径 , 称该图为强连通图。
强连通分量
有向图的极大强连通子图 , 称为有向图的强连通分量。
权

图中每条边都可以附有一个对应的数，这种与边相关的数称为权。权可以表示从一个顶点到另一个顶点的距离或者花费的代价

边上带有权的图称为带权图，也称为网。

极大连通子图

从一个顶点开始作为一个子图，逐个添加和这个子图有边相连的顶点，直到所有相连的顶点都被纳入图中，所生成的子图就是极大连通子图。

邻接表：

邻接表是图的一种链式存储结构，邻接表由单链表的表头形成的顶点表和单链表其余结点形成的边表两部分组成。一般顶点表存放定点信息和指向第一个边结点指针，边表结点存放与当前顶点相邻接顶点的序号和指向下一个边结点的指针。反映的是顶点出度的情况。
逆邻接表：反映的是顶点的入度情况。
普利姆算法（prime）

从图中任意取出一个顶点，把它当成一棵树，然后从与这棵树相接的边中选出一条最短（权值最小）的边，并将这条边及其所连接的顶点也并入到这棵树中，此时得到了一棵有两个顶点的树。然后从与这棵树相接的边中选取一条一条最短的边，并将这条边及其所连顶点并入到当前树中，得到一棵有3个顶点的树，以此类推，直到图中所有顶点都被并入到树中为止，此时得到的生成树就是最小生成树。

克鲁斯卡尔

将图中边按照权值从小到大排序，然后从最小边开始扫描各边，并检测当前边是否为侯选边，即是否该边的并入会构成回路，如不构成回路，则将该边并入到当前生成树中，直到所有边都被检测完为止。

AOV网

活动在定点上的网是一种可以形象地反映出整个工程中各个活动之间的先后关系的有向图。AOV网是一种以顶点表示活动，边无权值，以边表示活动的先后次序且没有回路的有向图。

AOE网

AOE网的边表示活动，边有权值，便表示活动的持续时间；顶点表示事件，事件是图中新活动开始或者旧活动结束的标志。

关键路径

在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径

第八章

物理结构 ( 存储结构 )
物理结构又称为数据的存储结构 , 是指数据的逻辑结构在计算机中的映像 ( 表
示), 即数据结构在计算机中的存储方法。
线索
在二叉树中 , 利用空余的指针指向二叉树某种遍历方式的结点的前驱和后继 ,
这种指向前驱和后继的指针 , 叫线索。
线索二叉树
对二叉树以某种次序进行遍历并加上线索的过程叫做线索化。线索化了的二叉
树称为线索二叉树。
广义表
广义表简称表 , 是零个或多个原子表所组成的有限序列。
插入排序
在一个已排好序的记录子集的基础上 , 每一步将下一个待排序的记录有序地插
入到已排好序记录的子集上 , 直到将所有待排记录全部插入为止。
数据结构
数据结构是数据元素的集合以及定义在该集合上的关系。
模式匹配
子串的定位操作称作串的模式匹配。
单循环链表
是单链表的另一种形式 , 它是一个首尾相接的链表 , 表中最后一个结点的指针
域由 null 改为指向头结点或线性表的第一个结点 , 整个链表形成了一个环．
线索
在二叉树的存储结构中 , 必有Ｎ＋１个空域 , 利用这些空域存放某种遍历的前
驱和后继 , 其中指向前驱和后继的指针叫线索．
折半查找
对于顺序存储的有序表 , 先取中间位置的记录关键字与所给的关键字进行比较 ,
若相等 , 则查找成功 , 否则, 若给定的关键字比中间的关键字大 , 在原表的后半
部分比较 , 反之, 在原表的前半部分比较 , 如此反复 , 逐步缩小范围 , 直到找到为
止, 或找不到 , 最后查找范围为空．
最小生成树
在图 G的所有生成树中 , 树权值最小的那棵生成树 , 称作最小生成树．
广度优先搜索 (BFS)
首先访问出发点 v, 接着依次访问 v 的所有邻接点 w1,w2,…,wt, 然后再依次访
问与 wl,w2, …,wt 邻接的所有未曾访问过的顶点。依此类推 , 直至图中所有和
源点 v 有路径相通的顶点都已访问到为止。此时从 v 开始的搜索过程结束。
( 若 G是连通图 , 则遍历完成 ; 否则, 在图 C中另选一个尚未访问的顶点作为新源
点继续上述的搜索过程 , 直至 G中所有顶点均已被访问为止。 )
前缀编码
任何一个字符的编码都不是另一个字符编码的前缀 , 这种编码叫做前缀编码 .
广义表
是零个或多个原子表所构成的有序序列 .
线索二叉树
利用二叉树的一些空闲指针指向该结点的前驱或后继 , 这种指针叫线索 , 线索
后了的二叉树 , 称为线索二叉树 .
森林
M 棵互相不相交的树构成的集合 , 将一棵非空树的根结点删除 , 树就变成了森
林.
哈夫曼树
设有 N个权值的结点构造一棵有 N个叶子结点的二叉树 , 其中 WPL最小的那棵
树, 为哈夫曼树 .
哈夫曼编码
一般以 N 种字符出现的频率做权值 , 构造哈付曼树 , 左孩子边做 0, 右孩子边做
1, 那么从根到叶子结点经过的 0 和 1 序列, 构成了哈夫曼编码 .
子图
图 G=(V,E)与图 G1=(V1,E1), 若 V1包含于 V,且 E1包含于 E,则 G1是 G的子图。
网
图的弧或边有与它相关的有意义的数 , 称作权 , 带有权值的图称作网。
深度优先搜索 (DFS)
类似树的先序遍历 , 在图中任选一个顶点作为出发顶点 V0,访问 V0 后, 依次从
V0的没被访问过的邻接点出发进行深度优先搜索。直到与 V0所连通的所有顶
点均被访问。如果, 此时图中还有顶点尚未访问 , 则从剩余的顶点中再任选一个
顶点作为出发顶点 V0,重复上述过程 , 直到图中全部顶点均被访问为止。
查找
根据给定的关键字值 , 在特定的表中 , 确定一个其关键字与给定值相同的数据
元素, 并返回该数据元素在列表中的位置。这个过程叫查找。
平均查找长度 (ASL)
为确定数据元素在表中的位置 , 需和给定值进行比较的关键字个数的数学期望
值, 成为查找算法在查找成功的平均查找长度。
二叉排序树
它或是一棵空树 , 或是有下面性质的树：若左或右子树不空 , 左子树所有结点值
小于根结点 , 而右子树所有结点值大于根结点的值 , 其左右子树也是二叉排序
树。
顺序查找
对于给定的关键字 K,从线性表的第一个 ( 或最后一个 ) 元素开始 , 依次向后 ( 或
前) 与元素的关键字比较 , 若某个记录的关键字与 K 相等, 查找成功 , 否则失败。
平衡二叉树
或是一棵空树 , 或左右子树高度差的绝对值小于等于 1 而且, 左右子树也是平
衡二叉树。
插入排序
在一个已排好序的基础上 , 每一步将下一个待排序记录插到已排好记录的子集
上, 使之重新有序 , 直到所有待排记录插完为止。
分块查找 ( 索引查找 )
分块查找以前两个为基础 , 将待查记录分成若干块 , 每块的关键字无序 , 但每块
的关键字的最大值有序 , 查找时 , 先查找到待查记录所在的块 , 再在块内进行顺
序查找。找块时 , 即可以用折半查找 , 也可用顺序查找。
拓扑排序
由某个集合上的偏序集得到该集合上的一个全序 , 这个操作叫做拓扑排序。
归并排序
将两个或两个以上的有序表合并成一个新的有序表 , 开始将每个元素当成是一
个个单独的有序表 , 逐渐表个数以原来一半的速度递减 , 每个表的长度却是原
来长度的 2 倍增加 , 不断重复 , 直到最后是一个表 , 而表的长度是元素个数为
止。
排序
根据关键字的递减或递增的次序 , 把文件中的各个记录依次排列起来 , 可使一
个无序的数据元素序列变成一个有序的序列的操作。
79.shell 排序
它是插入排序的一种 , 又叫缩小增量排序 , 先按增量进行分组 , 组内插入排序 ,
然后每次缩短增量 , 再进行分组和组内插入排序 , 直到增量为 1 时, 进行最后
一次排序止。
内部排序
指的是待排序记录存放在计算机存储器中进行的排序过程；
外部排序
指的是待排序记录的数量很大 , 以致内存一次不能容纳全部记录 , 在排序过程
中对外存进行访问的排序过程。
不稳定排序
假设 Ki=Kj(1 ≤i ≤n,1 ≤j ≤n,i ≠j), 且在排序前的序列中 Ri 领先于 Rj( 即 i
＜j) 。若在排序后的序列中 Rj 领先于 Ri , 则称所用的排序方法是不稳定的。
稳定排序
假设 Ki=Kj(1 ≤i ≤n,1 ≤j ≤n,i ≠j), 且在排序前的序列中 Ri 领先于 Rj( 即 i
＜j) 。若在排序后的序列中 Ri 仍领先于 Rj, 则称所用的排序方法是稳定的
直接插入排序
第 1 遍, 将初始文件中的记录 R1看作有序子文件 , 将 R2插入这个子文件中。若
R2的关键字小于 R1的关键字 , 则 R2插在 R1的前面 , 否则 R2插在 R1的后面。
第 2 遍, 将 R3插入前面的两个记录的有序子文件中 , 得到 3 个记录的有序子文
件。依此类推 , 继续进行下去 , 直到将 Rn插入到前面的 n-1 个记录的有序子文
件中, 最后得到 n 个记录的有序文件。
气泡排序法
气泡排序的过程很简单。从第一记录开始 , 相邻的两个记录关键字进行比较 ,
若顺序不对 , 立即交换 , 直至 N-1 个与第 N个比较为止。得到一个最大 ( 或最小 )
的关键字记录的结果位置。
选择排序
选择排序是每一趟在 n-i+1(i= 1,2,3 …n-1) 个记录中选择关键字最小的记录
作为有序序列中第 i 个记录。其中最简单的是简单选择排序
快速排序
快速排序的基本思想是把当前待排序的记录 , 存放到整个表排好序后 , 它应当
在的最终位置上。将原来的待排序表分割成两部分 , 其中一部分表中的关键字
均比另一部分表中的关键字小。然后, 分别对两部分表用同样的方式进行排序 ,
直到整个表排好序。
堆排序
首先将根结点的记录与当前树中具有最大序号的记录交换 , 把交换后具有最大
序号的记录输出 , 得到一个排序的结果。这时的树不再是堆树 , 排序暂时停止。
然后, 必须把树重新调整成堆树 , 再重复上述过程 , 直到所有记录都排好序。
归并排序
归并排序是把两个或两个以上的有序表合并成一个新的有序表。把含有 N 个
记录的无序表当成 N 个有序的子表 , 每个子表的的长度为 1, 然后, 利用两两归
并, 得到 n/2 个长度为 2 或 1 的有序子表。再两两归并直到得到长度为 N 的一
个有序表。
基数排序
基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种
内排序方法。
含有n个顶点的带权连通图

他的最小生成树是指图中任意一个由n个顶点构成的边的权值之和最小的连通子图