名词解释

1、 **数据结构 **

数据结构是相互之间存在一种或多种特定关系的数据元素的集合，数据结构包括三方面的内容：逻辑结构、存储结构、数据的运算

2、 **逻辑结构 **

数据元素之间的逻辑关系，与数据的存储无关，独立于计算机

3、 **存储结构 **

数据结构在计算机中的表示，也叫物理结构，包括数据元素的表示和关系的表示。是用计算机语言实现的

4、 **索引存储 **

在存储元素信息的同时还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。

5、 **散列存储 **

根据元素的关键字直接计算出该元素的存储地址，又称哈希存储。缺点是与散列函数的好坏有关。

6、 **数据的运算 **

施加在数据上的运算，包括运算的定义和实现。定义针对逻辑结构，实现针对存储结构。

7、 **数据 **

是描述客观事物属性的能输入到计算机中并被识别和处理符号的集合，数据是计算机程序加工的原料。

8、 **数据元素 **

数据的基本单元，通常做一个整体进行考虑和处理。一个数据元素由若干个数据项组成。例如学生数据就是一个数据元素，由学号，姓名等数据项组成。

9、 **数据项 **

数据不可分割的最小单位，一个元素由若干个数据项组成

10、 **数据对象 **

具有相同性质的数据元素的集合，是数据的一个子集。比如整形数据对象是集合N={0，±1，±2，…}

11、 **数据类型 **

是一个值的集合和定义在此集合上的一组操作数的总称，分为原子类型（不可再分），结构类型（可再分为若干数据类型），抽象数据结构（抽象数据组织与之相关的操作）。

12、 **算法 **

对特定问题求解步骤的一种描述。

13、 **时间复杂度 **

一个语句在算法中被重复执行的次数，它是规模为n的函数。

14、 **空间复杂度 **

该算法所耗费的存储空间，它是规模为n的函数。

15、 **线性表 **

是具有相同数据类型的n(n>=0)个元素的有限序列。

16、 **广义表 **

简称表，是零个或多个原子表所组成的有限序列。

17、 **顺序表 **

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，使逻辑上相邻的元素在物理位置上也相邻。

18、 **单链表 **

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。除首尾元素外，每一个元素有唯一前驱和唯一后继。

19、 **头结点 **

为了使链表在第一个元素的处理操作和其他位置相同而设置的结点，指针域指向第一个结点，数据域为空，也可以存放表长。

20、 **双链表 **

每一个结点有两个指针域，一个指向其前驱，一个指向其后继。

21、 **静态链表 **

借助数组来描述线性表的链式存储结构，这里的指针是结点的相对地址（数组下标），又称游标。

22、 **栈 **

只允许在一端进行插入删除操作的线性表，可插入删除的位置叫栈顶，另一端为栈底。

23、 **队列 **

只允许在一段入队，另一端出队的线性表，先进先出。

24、 **循环队列 **

在队列的顺序存储结构中，把存储空间的首位逻辑上相连，构成一个环。使得存储空间只要有空余地址就可以进行入队操作。用头部和尾部两个指示器表示队头和队尾。

25、 **双端队列 **

队列的两端分别称为前端和后端，两端都可以入队出队。输出受限的双端队列是允许一段插入删除，另一端只能插入。

26、 **递归 **

一个函数中又用了它自身。

27、 **矩阵的压缩存储 **

为多个值相同的元素只分配一个存储空间，对零元素不分配，从而节省存储空间。

28、 **稀疏矩阵 **

矩阵中非零元素的个数相对矩阵元素的个数来说非常少。

29、 **串 **

是由零个或多个字符组成的有限序列。一般记为S = ‘a1a2…an’。

30、 **串的存储结构 **
定长顺序存储：为每一个串分配固定长度的存储空间。

堆分配存储：仍然以一组地址连续的存储单元存放，只不过存储空间是由动态分配得到的。

块链存储：采用链表方式存储串。

31、 **串的匹配模式 **

子串的定位操作通常称为串的模式匹配，它求的是子串（常称模式串）在主串中的位置。

32、 **树 **

树是n（n>=0）个结点的有限集。在任意一棵非空树中

（1）有且仅有一个特殊的称为根的结点

（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集合，其中每一个集合本身又是一棵树，并称为根的子树。

33、 **二叉树 **

每个结点最多有两个孩子结点的一种树。两个孩子分别称左孩子和右孩子结点。

34、 **结点的度 **

结点的分支（子树）个数叫做该结点的度。

35、 **树的度 **

是树种所有结点的最大度数。

36、 **孩子结点与双亲结点 **

树中某结点的子树的根结点称为该结点的孩子结点。相反，该结点称为孩子结点的双亲结点。

37、 **兄弟结点 **

同一层上不同双亲的结点，互为兄弟

38、 **子孙 **

以某一结点为根的子树中任一结点称为该结点的子孙。

39、 **祖先 **

是指从根结点到该结点的路径上所有的结点。

40、 **叶子结点与分支结点 **

度为0的结点。度不为0的称为分支结点。

41、 **树的高度 **

树中所有结点的层次最大值。

42、 **平衡因子 **

结点的左子树深度与右子树深度的差。

43、 **满二叉树 **

深度为k，且有2k-1个结点的二叉树。

44、 **完全二叉树 **

高为h、有n个结点的二叉树，当且仅当每一个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。

45、 **二叉排序树 **

左子树上的所有结点的关键字都小于根结点的关键字，右子树上所有结点的关键字都大于根结点的关键字。并且左右子树也分别是二叉排序树。

46、 **平衡二叉树 **

树上任一结点的左子树和右子树的深度之差不超的1.

47、 **二叉树的遍历 **

指按某条搜索路径访问树中每一结点，使得每一结点被访问且仅被访问一次。

48、 **线索二叉树 **

对二叉树以某种次序遍历并加上线索的过程称为线索化。线索化的二叉树为线索二叉树。

49、 **线索 **

在二叉树中，必有n+1个空域，利用这些空域存放二叉树以某种次序遍历的结点的前驱后继。

50、 **树的遍历 **

先根和后根遍历。树的后根遍历与其对应的二叉树的中序遍历相同。

51、 **森林的遍历 **

先序遍历和中序遍历，森林的先序和中序遍历即为其对应二叉树的先序和中序遍历。

52、 **森林 **

M棵互不相交的树构成的集合。

53、 **哈夫曼树（最优二叉树） **

在含有N个带权结点的二叉树中，其带权路径长度最小的二叉树称为哈夫曼树，也称最优二叉树。

54、 **哈夫曼编码 **

一般以N种字符出现的频率做权值，构造哈夫曼树，左孩子边为0，右孩子边为1，那么从根到叶子结点经过的0和1序列，构成了哈夫曼编码。

55、 **树的路径长度 **

每个结点到根结点路径长度之和。

56、 **树的带权路径长度（WPL） **

每个结点的带权路径长度之和

57、 **前缀编码 **

任何一个字符的编码都不是另一个字符编码的前缀。

58、 **图 **

图G是由顶点集V和边集E组成，记G=(V,E)，各个顶点之间是多对多的关系。

59、 **有向图 **

E是有向边（也称弧）的有限集合，记为<v,w>，v,w是顶点，v是弧尾，w是弧头，<v,w>称为从顶点v到顶点w的弧。

60、 **无向图 **

E是无向边（简称边）的有限集合，记(v,w)或(w,v)。可以说w和v互为邻接点。

61、 **简单图 **

（1）不存在重复边（2）不存在顶点到自身的边

62、 **多重图 **

与简单图相对，允许存在重复边，允许顶点到自身的边。

63、 **完全图（简单完全图） **

有n(n-1)/2条边的无向图称为完全图

64、 **子图 **

图G=(V,E)与图G1=(V1,E1)，若V1包含于V，E1包含于E，则G1称为G的子图。

65、 **连通，连通图 **

若两点之间存在路径，则称v,w连通。若图中任意两个顶点都是连通的，则称其为连通图，否则为非连通图。若n个顶点边数小于n-1，则一定是非连通图。

66、 **连通分量 **

无向图中极大连通子图称为连通分量。

67、 **强连通图，强连通分量 **

在有向图中，若v到w和w到v之间都有路径，则称为这两个顶点是强连通的。有向图中的极大强连通子图称为有向图的强连通分量。

68、 **生成树，生成森林（对于无向图） **

连通图的生成树是包含图中全部顶点的一个极小连通子图。若顶点个数为n，则生成树含有n-1条边，对于生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会变成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

69、 **顶点的度，入度，出度 **

每一个顶点的度为以该顶点为一端的边的数目。

对于无向图，顶点的度为依附该顶点的边的数目。

对于有向图，顶点v的度分为入度出度，入度是以v为终点的有向边的个数，出度是以v为起点的有向边的个数。

70、 **权，网 **

图的弧或边有与它相关的有意义的数，称作权，带有权值的图称为网。

71、 **稠密图，稀疏图 **

边数很少称为稀疏图，反之称为稠密图。

72、 **路径，路径长度 **

顶点v1到vn之间的一条路径是指顶点序列v1vivj…vn。

路径上边的数目称为路径长度。

73、 **回路 **

第一个顶点和最后一个顶点相同的路径称为回路或环，若n个顶点有大于n-1条边，则此图一定有环。

74、 **简单路径，简单回路 **

在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路。

75、 **距离 **

从顶点u出发到v的最短路径长度称为u到v的距离。若从u到v路径不存在，记该距离为无穷(∞)。

76、 **有向树 **

一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树。

77、 **图的存储 **

分为邻接矩阵法，邻接表法，十字链表法，邻接多重表

78、 **邻接矩阵法 **

用一个一维数组存储图中顶点的信息，用二阶数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。

79、 **邻接表法 **

结合了顺序存储和链式存储，当一个图为稀疏图时，使用邻接表法可大大减少存储空间的浪费。

顶点vi的边表（对于有向图为出边表）：对vi建立单链表，表中的结点表示依附于顶点vi的边（有向图则为以vi为尾的弧）

顶点表：边表的头指针和顶点的数据信息采用顺序存储。

80、 **十字链表法 **

是有向图的一种链式存储结构，在十字链表中，对应于有向图的每条弧有一个结点，对应于每个顶点也有一个结点。

81、 **邻接多重表 **

是无向图的另一种链式存储，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。

82、 **广度优先搜索BFS **

是一种分层查找过程，类似于二叉树的层序遍历，以v为起点，由近至远依次访问和v优路径相通且路径长度为1，2，。。。的顶点。

广度优先生成树，由邻接矩阵得到的生成树是唯一的，由邻接表得到的不唯一。

83、 **深度优先搜索DFS **

类似于树的先序遍历，尽可能深的搜索一个图。深度优先生成树，由邻接矩阵得到的生成树是唯一的，由邻接表得到的不唯一。

84、 **最小生成树算法（无向带权图） **

在带权连通无向图图里搜索最小生成树。“P点K边”

**①Prim算法（普里姆） **

每次都从未选的顶点找到与已选的顶点之间权值最小的顶点并加进树中，如此重复，直到树包含所有顶点为止。适用于边稠密的图。

**②Kruskal算法（克鲁斯卡尔） **

每次都选未被选、权值最小且不构成回路的边，如此重复，直到树包含所有顶点为止。适用于点稠密的图。

85、 **最短路径算法（有向带权图） **

**①Dijkstra算法（迪杰斯特拉） **

求单源最短路径，从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接结点，直到扩展到终点为止。

**②Floyd算法（弗洛伊德） **

求每对顶点间的最短路径。利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。

86、 **有向无环图（DAG图） **

若一个有向图中不存在环，则称为有向无环图，简称DAG图。

87、 **拓扑排序 **

由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

①每个顶点出现且只出现一次

②若顶点A序列在顶点B的前面，则在图中不存在从B到A的路径。

88、 **AOV网 **

若用有向无环图表示一个工程，以顶点表示活动，用有向边表示活动先后关系，这样的图简称为AOV网。

89、 **AOE网 **

若用有向无环带权图表示一个工程，以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。

90、 **关键路径 **

从开始顶点（源点）到结束顶点（汇点）的所有路径中，具有最大路径长度的路径称为关键路径，把关键路径上的活动称为关键活动。

**①事件Vi: ** 早：early 迟：late

最早发生时间ve(i)

指从源点到vi的最长路径

最迟发生时间vl(i)

指不推迟整个工程时间下vi最迟发生的时间

**②活动ai： **

最早开始时间e(i)

指该活动弧的起点所表示的事件的最早发生时间

最迟开始时间l(i)

指该活动弧的终点所表示的事件的最迟发生时间与该活动所需时间之差。

91、 **时间余量 **d(i)=l(i)-e(l)

不增加完成整个工程所需总时间的情况下，活动可以拖延的时间，若d(i)=0，即l(i)=e(i)，则活动ai是关键活动。

92、 **查找表（查找结构） **

用于查找的数据集合称为查找表，由同一类型的数据元素组成，可以是一维数组或链表等数据类型。

93、 **静态查找表 **

只有查找操作，无须动态修改查找表。

94、 **关键字 **

数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果因该是唯一的。

95、 **平均查找长度 **

一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值ASL=PiCi，Pi是查找第i个元素的概率，Ci是找到第i个数据元素所需要进行的比较次数。

96、 **顺序查找 **

又称线性查找，主要用于线性表中查找，从一端开始，逐个查找。分为一般线性表的顺序查找和对按关键字有序的顺序表的顺序查找。一般线性表需要从一端开始，逐个检查关键字是否满足给定条件。在有序的顺序表中，若a[i]小于key，a[i+1]大于key，则直接得出查找失败。

97、 **哨兵 **

将表的一个元素设置为哨兵，然后查找的时候当达到哨兵时不用再判断数组越界，引入哨兵可以避免很多不必要的判断语句，从而提高效率

98、 **失败结点 **

有序顺序表上的顺序查找判定树中的矩形结点称为失败结点

99、 **折半查找 **

又称二分查找，仅适用于有序的顺序表，将key与表中中间值比较，若相等则返回，若大于key则在表左半查找，若小于key则在表右半查找，重复上述操作直至查到或失败。折半查找的判定树是一个平衡二叉树。

100、 **判定树 **

是将查找过程通过二叉树进行描述。树中每个圆形结点表示一个记录,结点中的值为该记录的关键字值，树中最下面的叶结点都是方形的,它表示查找不成功的情况

101、 **分块查找 **

又称索引顺序查找，吸取了顺序查找和折半查找各自的优点。将查找表分为若干子块，块内的元素可以无序，块之间是有序的。先用折半查找在索引表中确定待查记录所在块，再用顺序查找块内元素。

102、 **B树 **

B树又称多路平衡查找树，是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：

（1）每个结点最多只有m个子结点。

（2）每个非叶子结点（除了根）具有至少⌈m/2⌉子数，至少有⌈m/2⌉-1个关键字。

（3）如果根不是叶结点，则根至少有两个子结点。

（4）具有k个子结点的非叶结点包含k-1个键。

（5）所有叶子都出现在同一水平，没有任何信息（高度一致）。

103、 **B+树 **

B+树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反。

104、 **散列表 **

是根据关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

105、 **散列函数 **

一个把查找表中的关键字映射成该关键字对应的地址的函数

106、 **直接定址法 **

取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。

107、 **除留余数法 **

取关键字被某个不大于哈希表表长m的质数p除后所得余数为哈希地址。

108、 **数字分析法 **

设关键字是r进制的树，用r个数码在各个位置上不同的频率进行分配哈希地址。

109、 **平方取中法 **

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。

110、 **冲突 **

列函数可能会把两个或以上的不同关键字映射到同一地址，这种情况为冲突，这些发生冲突的不同关键字称为同义词。

111、 **开放定址法 **

指的是可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。

112、 **拉链法 **

把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。

113、 **二次聚集 **

指在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象。

114、 **装填因子 **

a=表中记录数n/散列表长m，散列表的平均查找长度依赖于装填因子，a越大表示装填的记录越满，越容易冲突。

115、 **排序算法的稳定 **

若相同的两个值a1,a2在排序后前后位置不变，则表示稳定。

116、 **排序法分类 **

根据数据是否在内存中进行分类

**①内部排序 **

指的是待排序记录存放在计算机存储器中进行的排序过程。

**②外部排序 **

指的是待排序记录的数量很大, 以致内存一次不能容纳全部记录, 在排序过程中对外存进行访问的排序过程。

117、 **插入排序 **

**①直接插入排序 **

每次将一个待排序的记录，按关键字大小插入到前面已经排好序的子序列中，直至全部记录插入完成。

②**折半插入排序 **

对插入排序算法的一种改进。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。

**③希尔排序 **

又称**缩小增量排序 **，把记录按下标的一定增量分组，对每组用直接插入排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

118、 **交换排序 **

**①冒泡排序 **

从后往前（或从前往后）两两比较相邻元素的值，若为逆序则交换它们，直到序列比较完毕，得到一个本次排序最大（最小）的值，之后重复上述操作，直至排序结束。

**②快速排序 **

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。

119、 **选择排序 **

**①简单选择排序 **

每趟在后面待排序元素中选取关键字最小的元素放到有序子序列，。

**②堆排序 **

指利用的一种排序。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父结点。

120、 **归并排序 **

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

121、 **基数排序 **

采用多关键字排序思想，借助“分配 /收集”两种操作对但逻辑关键字进行排序。