《2022年数据结构名词解释.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构名词解释.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构名词解释1. 数据数据是描述客观事物的符号， 是能够被计算机输入、 识别、处理的各种符号，是计算机化的信息。2线性表一种数据结构，是 N（N=0 ）个同质元素的有限序列，除首尾元素外，每个元素有唯一的前驱和唯一的后继。3. 队列是一种受限线性表，是先进先出的线性表4. 循环队列在队列的顺序存储结构中，把存储空间的首尾逻辑上相连，构成一个环，使得存储空间上只要有空余的地址，就可以继续进行入队列操作， 极大利用了物理空间。用头部和尾部两个指示器表示队列头和队列尾，插入在尾部进行， 删除在头部进行。5. 双向链表线性表采用链式存储时，每个结点除一个数据域外，包含两个指针域，一个指向该结点的直
2、接后继， 一个指向该结点的直接前驱， 这种方式构成的链表， 即为双向链表。6. 希尔排序是插入排序的一种， 又叫缩小增量排序， 先按增量进行分组， 组内插入排序，然后每次缩短增量，再进行分组和组内插入排序，直到增量为 1 时，进行最后一次排序止。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 8 页 - - - - - - - - - - 7. 完全图任何一个有 N 个结点的无向图，若其边数为N（N-1 ）/2 ，则这个无向图就是完全图8. 有向完全图任何一个有 N 个结点的有向图，若其狐个数
3、为N（N-1 ）个，则这个有向图就是有向完全图。9. 广度遍历按层次编历方式， 从某一点 V0 开始遍历它的所有邻接点V1,V2 ,再依次访问 V1,V2. 的所有未被访问过的邻接点，直到所有的点均遍历完成10. 二叉树每个结点的度读都不大于2 的树11. 关键字数据元素的某个数据项的值，用它可以标识列表的一个或一组元素。12. 数据元素数据元素是数据的基本单位，是数据集合的个体。13. 串串是字符线性的有限集合。14. 子串串中任意个连续的字符组成的子序列称作该串的子串。15. 栈是一种受限线性表，是插入和删除操作在同一端进行的，是后进先出的线性表。16. 平衡因子精品资料 - - - 欢迎
4、下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 8 页 - - - - - - - - - - 结点的左子树深度与右子树深度之差。17. 生成树一个连通图的生成树是指一个极小连通子图，它含有图中的全部顶点，N-1条边。18. 满二叉树深度为 K，且有 2K -1 个结点的二叉树19. 物理结构物理结构又称为数据的存储结构，是指数据的逻辑结构在计算机中的映像（表示） ，即数据结构在计算机中的存储方法。20. 线索在二叉树中，利用空余的指针指向二叉树某种遍历方式的结点的前驱和后继，这种指向前驱和后继的指针，叫线索。21.
5、线索二叉树对二叉树以某种次序进行遍历并加上线索的过程叫做线索化。线索化了的二叉树称为线索二叉树。22.广义表广义表简称表，是零个或多个原子表所组成的有限序列。23. 强连通分量有向图的极大强连通子图，称为有向图的强连通分量。24. 结点的带权路径长度该结点到树根之间的路径长度与结点上权的乘积。25. 插入排序精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 8 页 - - - - - - - - - - 在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序记录的子集上
6、，直到将所有待排记录全部插入为止。26. 祖先一个结点的祖先是指从根结点到该结点的路径上的所有结点27. 数据结构数据结构是数据元素的集合以及定义在该集合上的关系。28. 模式匹配子串的定位操作称作串的模式匹配。29. 单循环链表是单链表的另一种形式，它是一个首尾相接的链表，表中最后一个结点的指针域由改为指向头结点或线性表的第一个结点，整个链表形成了一个环30. 线索在二叉树的存储结构中，必有个空域，利用这些空域存放某种遍历的前驱和后继，其中指向前驱和后继的指针叫线索31. 折半查找对于顺序存储的有序表， 先取中间位置的记录关键字与所给的关键字进行比较，若相等，则查找成功，否则，若给定的关键字
7、比中间的关键字大，在原表的后半部分比较，反之，在原表的前半部分比较，如此反复，逐步缩小范围，直到找到为止，或找不到，最后查找范围为空32. 最小代价生成树在图 G 的所有生成树中 ,树权最小的那棵生成树 ,称作最小生成树精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 8 页 - - - - - - - - - - 33. 首先访问出发点 v，接着依次访问 v 的所有邻接点 w1，w2， wt，然后再依次访问与 wl，w2，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点 v 有路径
8、相通的顶点都已访问到为止。 此时从 v 开始的搜索过程结束。(若 G 是连通图，则遍历完成；否则，在图C 中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G 中所有顶点均已被访问为止。). 34. 完全二叉树对满二叉树的结点从上到下,从左到右进行依次进行编号,若有一棵二叉树的每一个结点都与深度为K 的满二叉树中编号都一一对应时,只是最后一层不满 ,称做完全二叉树 .35. 前缀编码任何一个字符的编码都不是另一个字符编码的前缀,这种编码叫做前缀编码. 36. 广义表是零个或多个原子表所构成的有序序列. 37. 线索二叉树利用二叉树的一些空闲指针指向该结点的前驱或后继,这种指针叫线索 ,
9、线索后了的二叉树 ,称为线索二叉树 . 38. 树的高度树中所有结点的层次的最大值. 39. 堂兄弟同一层上不同双亲的结点 ,互称堂兄弟 .精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 8 页 - - - - - - - - - - 40. 叶子结点度为 0 的结点 ,即没有后继的结点. 41. 森林M 棵互相不相交的树构成的集合,将一棵非空树的根结点删除,树就变成了森林. 42. 树的路径长度树中每个结点到根结点的路径长度之和.43. 树的带权路径长度(WPL): 树中所有叶子结点的带权路
10、径长度之和.44. 哈夫曼树设有 N 个权值的结点构造一棵有N 个叶子结点的二叉树 ,其中 WPL 最小的那棵树 ,为哈夫曼树 . 45. 哈夫曼编码一般以 N 种字符出现的频率做权值,构造哈付曼树 ,左孩子边做 0,右孩子边做1,那么从根到叶子结点经过的0 和 1 序列,构成了哈夫曼编码 . 46. 图中顶点的度顶点 V 的度是图中和顶点V 相关联的边的数目。包括入度和出度两种。47. 子图图 G = （V，E）与图 G1（V1，E1） ，若 V1 包含于 V，且 E1 包含于 E，则 G1 是 G 的子图。48. 连通图对于无向图，若 V1 到 V2 有路径，称 V1V2 是连通的，若图中
11、任意两点都精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 8 页 - - - - - - - - - - 是连通的，则称该无向图是连通图。49. 网图的弧或边有与它相关的有意义的数，称作权，带有权值的图称作网。50. 查找根据给定的关键字值，在特定的表中，确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。这个过程叫查找。51 平均查找长度（ASL ）为确定数据元素在表中的位置， 需和给定值进行比较的关键字个数的数学期望值，成为查找算法在查找成功的平均查找长度。52. 二叉
12、排序树它或是一棵空树，或是有下面性质的树：若左或右子树不空，左子树所有结点值小于根结点， 而右子树所有结点值大于根结点的值，其左右子树也是二叉排序树。53. 顺序查找对于给定的关键字K，从线性表的第一个（或最后一个）元素开始，依次向后（或前）与元素的关键字比较，若某个记录的关键字与K 相等，查找成功，否则失败。54. 平衡二叉树或是一棵空树， 或左右子树高度差的绝对值小于等于1 而且，左右子树也是平衡二叉树。55. 插入排序在一个已排好序的基础上， 每一步将下一个待排序记录插到已排好记录的子精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - -
13、- - - - - - - -第 7 页，共 8 页 - - - - - - - - - - 集上，使之重新有序，直到所有待排记录插完为止。56. 分块查找分块查找以前两个为基础，将待查记录分成若干块，每块的关键字无序，但每块的关键字的最大值有序， 查找时，先查找到待查记录所在的块，再在块内进行顺序查找。找块时，即可以用折半查找，也可用顺序查找/。57.序由某个集合上的偏序集得到该集合上的一个全序，这个操作叫做拓扑排序。57归并排序两个或两个以上的有序表合并成一个新的有序表，开始将每个元素当成是一个个单独的有序表， 逐渐表个数以原来一半的速度递减，每个表的长度却是原来长度的 2 倍增加，不断重复，直到最后是一个表，而表的长度是元素个数为止。58. 排序关键字的递减或递增的次序，把文件中的各个记录依次排列起来，可使一个无序的数据元素序列变成一个有序的序列的操作。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 8 页 - - - - - - - - - -