考研DS名词解释

第一章 绪论

1、数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

2、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

3、数据项：是组成数据元素的最小单位。

4、数据对象：是性质相同的数据元素的集合，是数据的一个子集。

5、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储和数据组织的方式。

6、数据类型：是数据结构的一个子集，表示数据的取值范围和相应的操作。

7、抽象数据类型（Abstract Data Type，ADT）：是抽象数据组织及与之相关的操作。

8、算法：是解决特定问题的一种方法或一个过程，它通常用计算机语言描述。

9、算法的效率：算法的效率取决于算法的时间复杂度和空间复杂度。

10、时间复杂度：是算法执行所需时间的量度，通常用大O符号表示。

11、空间复杂度：是算法执行所需时间的量度，通常用大O符号表示。

第二章 线性表

1、线性表：是具有相同数据类型的n个数据元素的有限序列，其中n为表长，当n=0时为空表。

2、顺序表：是线性表的顺序存储结构，用一组地址连续的存储单元依次存储线性表中的数据元素。

3、链表：是线性表的链式存储结构，用一组任意的存储单元存储线性表中的数据元素。

4、循环链表：是链表的一种特殊形式，其最后一个结点的指针指向第一个结点，形成一个环。

5、双向链表：是链表的一种特殊形式，其每个结点都有两个指针，一个指向前一个结点，一个指向后一个结点。

6、静态链表：借助数组来描述线性表的链式存储结构，结点也有数据域和指针域，但指针是结点的相对地址，需要预先分配连续的内存空间。是链表的一种特殊形式，其每个结点都有一个指向下一个结点的指针和一个数据域。

7、动态链表：是链表的一种特殊形式，其每个结点都有一个指向下一个结点的指针和一个数据域，并且可以在运行时动态地增加或删除结点。

8、结点：是由数据元素和其后继结点地址的信息组成的存储映像，是链表的基本组成单位，包含数据域和指针域。

9、数据域：是结点中存储数据元素信息的部分。

10、指针域：是结点中存储其后继结点地址信息的部分。

11、头指针：是指向链表第一个结点的指针。

12、尾指针：是指向链表最后一个结点的指针。

13、头结点：是在链表第一个结点之前插入的一个结点，其数据域通常不存储任何信息。

14、首元结点：是链表的第一个结点，其数据域存储第一个数据元素的信息。

15、表长：是表中数据元素的个数。

第三章 栈和队列

1、栈：也叫后进先出表，是限定仅在表的一端进行插入和删除操作的线性表，表尾端称为栈顶，表头端称为栈底，不含元素的空表称为空栈。

2、顺序栈：是栈的顺序存储结构，用一组地址连续的存储单元依次存储栈中栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素位置。

3、链栈：是栈的链式存储结构，规定所有操作都在单链表的表头进行。

4、队列：也叫先进先出表，是限定仅在表的一端进行插入操作，在表的另一端进行删除操作的线性表，允许插入的一端称为队尾，允许删除的一端称为队头，不含元素的空表称为空队列。

5、链队：用链表表示的队列，需要两个指针分别指示队头和队尾。

6、循环队列：是队列的一种特殊形式，其队尾指针指向队列的最后一个元素的后一个位置，当队尾指针与队头指针重合时，表示队列为空。

7、双端队列：是限定在两端都可以进行插入和删除操作的线性表。

8、递归函数：是直接或间接地调用自身的函数。例如阶乘函数、斐波那契数列以及汉诺塔问题等。

9、共享栈：是两个栈共享同一片空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，即使其中一个栈为空时，另一个栈也可以继续使用这片空间。

第四章 串

1、串：是由零个或多个字符组成的有限序列。

2、子串：串中任意个连续的字符组成的子序列称为该串的子串。

3、空格串：只包含空格字符的串。

4、空串：不包含任何字符的串，即0个字符的串。

5、主串：包含子串的串。

6、串相等：当且仅当两个串的长度相等且对应位置上的字符都相等。

7、串的长度：串中字符的个数。

8、模式匹配：在主串中查找子串的过程，串的定位操作。

9、定长顺序存储表示：用一组连续的存储单元依次存储串中的字符，每个字符占一个存储单元。

10、堆分配存储表示：用一组连续的存储单元存储串值，同时用一个指针指向串的基地址。

11、块链结构：用链表存储串值，每个结点存放若干个字符，除了头指针外还可以附设一个尾指针指示链表中的最后一个节点，最后一个结点存储字符个数。

第五章 树与二叉树（重点）

1、树：是n（n≥0）个结点的有限集合，当n=0时，称为空树。

2、树的结点：树中的每个元素称为结点。

3、结点的度：结点拥有的子树个数。

4、树的度：树中结点的度的最大值。

5、叶结点：度为0的结点。

6、分支结点：度不为0的结点。

7、结点的孩子：结点子树的根结点。相应的，该结点称为孩子的双亲结点。

8、结点的兄弟：具有相同双亲结点的结点。

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

10、树的高度：树中结点的最大层次数。

11、有序树：树中结点的各子树从左至右有次序，不能互换。

12、无序树：树中结点的各子树从左至右没有次序，可以互换。

13、森林：是m（m≥0）棵树的集合。

14、二叉树：是n（n≥0）个结点的有限集合，该集合或者为空集，或者由一个根结点及两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

15、满二叉树：一棵深度为k，且有（2^k）-1个结点的二叉树。

16、完全二叉树：深度为k，有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号为1至n的结点一一对应时，称之为完全二叉树。

17、线索链表：由每个结点中包含左指针，左标志位，数据域，右标志位，右指针五部分组成的二叉链表。

18、线索化：以二叉树某种遍历顺序给空指针加线索的过程。

19、线索二叉树：对二叉树以某种遍历次序进行线索化，使之变成线索二叉树。

20、哈夫曼树：最优二叉树，带权路径长度最短的二叉树。

21、二叉排序树：又称二叉查找树，左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值。

22、平衡二叉树：又称AVL树，树上任一结点的左子树与右子树的深度之差的绝对值不超过1。

23、平衡因子：结点的左子树深度与右子树深度的差。

第六章 图（重点）

1、图：是n（n≥0）个结点的有穷集合，记作G=(V，E)，其中V是结点集，E是边集。

2、顶点：图中的数据元素称为顶点。

3、边的权值：边上的数值。

4、完全图：即无向图中，任意两个顶点之间都有一条边相连。

5、有向完全图：有n*(n-1)条边的有向图称为有向完全图。

6、稀疏图：有很少条边或弧的图，相反为稠密图。

7、简单图：不存在重复边、不存在顶点到自身的边的图。

8、强连通图：有向图中，任意两个顶点之间都有来回路径想通。

9、连通图：无向图中，任意两个顶点之间都有路径相连。

10、连通分量：无向图中的极大连通子图。

11、强连通分量：有向图中的极大连通子图。

12、生成树：连通图的生成树是包含图中所有顶点的一个极小连通子图。

13、最小生成树：连通图的所有生成树中权值和最小的生成树。

14、AOV网：用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网。

15、AOE网：用顶点表示事件，用弧表示活动，用弧上的权值表示活动的持续时间的有向图称为边表示活动的网。

16、DAG：有向无环图。

17、数组表示法：用两个数组分别存储数据元素的信息和数据元素之间的关系的信息。

18、邻接矩阵：表示图中结点之间关系的矩阵称为邻接矩阵。

19、邻接表：用一个顶点数组和一个边链表来表示图。

20、十字链表：可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种存储形式。

21、邻接多重表：用一个顶点数组和一个边链表来表示图。

22、拓扑排序：由某个集合上的一个偏序得到该集合上一个全序的操作称为拓扑排序。

23、路径：两个顶点之间相连的边。

24、路径长度：路径上边的数目。

25、回路：路径的起点和终点相同的路径。

26、简单路径：路径上各顶点均不互相重复的路径。

27、简单回路：除了起点和终点相同外，其余顶点均不相同的路径。

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

29、关键活动：关键路径上的活动称为关键活动。

30、连通图：图中任意两个顶点之间都有路径相连。

31、最短路径：两个顶点之间相连的边中，权值和最小的路径。

32、弧头：有向边箭头所指的顶点。

33、弧尾：有向边箭头开始的点。

34、深度优先搜索：从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。类似于树的先根遍历，是树的先根遍历的推广。

35、广度优先搜索：类似于树的按层次遍历的过程。

36、关节点：在无向连通图中，删除一个顶点以及和它相关联的边后，图的连通分量数增加，则称此顶点为关节点。

37、重连通图：一个没有关节点的连通图。

第七章 查找

1、关键字：是数据元素中某个数据项的值，用它可以识别一个或一组数据元素。

2、主关键字：若此关键字可以唯一地标识一个记录，则称此关键字为主关键字。

3、次关键字：反之，用以识别若干记录的关键字称为次关键字。

4、查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。

5、查找表：由同一类型的数据元素构成的集合。

6、静态查找表：只作查找操作的查找表。

7、动态查找表：在查找过程中同时作插入和删除操作的查找表。

8、平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。

9、顺序查找：从表的一端开始，依次比较表中各记录的关键字，若找到与给定值相等的关键字，则查找成功，返回该记录的存储位置；反之，若直到表的另一端，仍未找到与给定值相等的关键字，则查找失败，返回查找失败的信息。

10、B树：又称多路平衡查找树，是一种特殊的二叉树，每个结点最多有m个子树，且每个结点包含n个关键字，其中m/2向上取整≤n≤m。

11、B+树：是B树的一种变形，也是一种多路平衡查找树，与B树的不同之处在于，B+树的非叶结点不存储数据，只存储关键字信息，所有的叶结点中包含了全部关键字的信息，且叶结点之间按关键字的大小顺序链接。

12、散列表：又称哈希表，是根据关键字直接访问的数据结构。

13、散列函数：将关键字映射到散列表中的一个位置的函数。

14、散列地址：散列函数计算得到的值。

15、冲突：两个不同的关键字映射到同一个散列地址。

16、同义词：具有相同散列地址的两个不同关键字。

17、装填因子：散列表中元素个数与散列表长度的比值。

18、二分查找：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。

19、分块查找：将查找表分成若干块，块内无序，块间有序，先确定待查记录所在的块，再在块内进行顺序查找。

第八章 排序

1、排序：将一组杂乱无章的数据按一定的规律顺次排列起来。

2、稳定性：若排序后，关键字相同的元素相对位置不变，则称这种排序算法是稳定的。

3、内部排序：在排序过程中，所有数据元素均保存在内存中。

4、外部排序：在排序过程中，需要访问外存。

5、插入排序：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部被插入为止。

6、直接插入排序：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

7、希尔排序：又称“缩小增量排序”，先将整个待排序记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

8、冒泡排序：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

9、快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

10、简单选择排序：每一趟在n-i+1（i=1，2，…，n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。

11、堆排序：利用堆这种数据结构所设计的一种排序算法。

12、归并排序：将两个或两个以上的有序表组合成一个新的有序表。

13、基数排序：又称“桶子法”，是一种基于分配的排序方法，将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行排序。

14、二路归并排序：将两个有序表合并成一个新的有序表。

15、多路归并排序：将多个有序表合并成一个新的有序表。

16、交换排序：通过交换数据元素的次序进行排序的方法。

17、大根堆：每个结点的值都大于或等于其子结点的值，根结点最大。

18、小根堆：每个结点的值都小于或等于其子结点的值，根结点最小。

Tips

排序算法的实现这一块可以翻阅我写的其他博客，在此不做详细的展开。