数据结构名词解释

1、1. 数据数据是描述客观事物的符号, 是能够被计算机输入, 识别 , 处理的各种符号, 是计算机化的信息。2.数据项数据不可分割的最小单位, 一个元素由若干个数据项构成。3.数据元素它是组成数据的基本单位 , 是数据集合中的个体 , 在计算机程序中 , 通常作为一个整体进行考虑和处理。4. 数据对象是性质相同的数据元素的集合, 是数据的一个子集。5. 数据处理是指对数据进行查找, 插入 , 删除 , 合并 , 排序 , 统计以及简单计算等的操作过程。6.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示( 即数据的逻辑结构和物理结构), 并对这种结构定义相适应的运算, 设

2、计出相应的算法 , 且确保经过这些运算后所得到的新结构仍然是原来的结构类型。7.数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称。8. 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。 抽象数据类型的定义取决于它的一组逻辑特性 , 而与其在计算机内部如何表示和实现无关。.算法解决一个问题的方法和步骤。10. 时间复杂度T(N) O(F(N), 它表示随问题规模增大 , 算法执行时间增长率与 F(N) 的增长率相同 ,F(N) 算法的时间复杂性。11. 原地工作算法执行时作。12. 线性表, 若额外空间相对于输入数据量来说是常数, 则称此算法为原地工一种数据结构, 是N

3、(N>=0)唯一的前驱和唯一的后继。13. 队列个同质元素的有限序列, 除首尾元素外, 每个元素有是一种受限线性表14. 循环队列, 是先进先出的线性表在队列的顺序存储结构中, 把存储空间的首尾逻辑上相连, 构成一个环, 使得存储空间上只要有空余的地址, 就可以继续进行入队列操作, 极大利用了物理空间。用头部和尾部两个指示器表示队列头和队列尾, 插入在尾部进行, 删除在头部进行。15. 单链表每一个数据元素, 都需用两部分来存储：一部分用于存放数据元素值, 称为数据域；另一部分用于存放直接后继结点的地址 ( 指针 ), 称为指针域 , 元素的存储空间可以连续 , 也可以是不连续的。 而数

4、据元素之间的逻辑关系由指针域来确定。16. 双向链表线性表采用链式存储时 , 每个结点除一个数据域外 , 包含两个指针域 , 一个指向该结点的直接后继 , 一个指向该结点的直接前驱 , 这种方式构成的链表 , 即为双向链表。17. 希尔排序是插入排序的一种后每次缩短增量, 又叫缩小增量排序, 先按增量进行分组, 再进行分组和组内插入排序,直到增量为, 组内插入排序, 然1 时 , 进行最后一次排序止。18. 完全图任何一个有图N 个结点的无向图, 若其边数为N(N-1)/2,则这个无向图就是完全19. 有向完全图任何一个有向完全图。20. 广度遍历N 个结点的有向图, 若其弧个数为N(N-1)

5、个 ,则这个有向图就是有按层次编历方式, 从某一点V0 开始遍历它的所有邻接点V1,V2, 再依次访问 V1,V2. 的所有未被访问过的邻接点, 直到所有的点均遍历完成21. 关键字数据元素的某个数据项的值, 用它可以标识列表的一个或一组元素。22. 串串是字符线性的有限集合。23. 子串串中任意个连续的字符组成的子序列称作该串的子串。24. 栈是一种受限线性表, 是插入和删除操作在同一端进行的, 是后进先出的线性表。25. 树树是 n(n>=0) 个结点的有限集。在任意一棵非空树中：(1) 有且仅有一个特殊的称为根的结点;(2) 当 n>1 时 , 其余结点可分成m(m>0

6、)个互不相交的有限集T1,T2,.,Tm,其中每一个集合本身又是一棵树26. 二叉树, 并且称为根的子树。二叉树是每个结点至多有两个孩子结点的一种树。为左孩子结点和右孩子结点。其中两个孩子结点分别被称27. 子孙子孙结点以某结点为根的子树中的任一结点都称为该结点的子孙。28. 孩子结点与双亲结点树中某个结点的子树的根结点称为该结点的孩子结点。相反结点的双亲结点。29. 结点的度, 称该结点为孩子树的某个结点的分支(子树)个数叫做该结点的度。30. 树的度树的度是树中所有结点的最大度数。31. 平衡因子结点的左子树深度与右子树深度之差。32. 生成树一个连通图的生成树是指一个极小连通子图边。33

7、. 满二叉树, 它含有图中的全部顶点,N-1条深度为K, 且有 2K -1个结点的二叉树34. 物理结构 ( 存储结构 )物理结构又称为数据的存储结构, 是指数据的逻辑结构在计算机中的映像( 表示 ), 即数据结构在计算机中的存储方法。35. 线索在二叉树中 , 利用空余的指针指向二叉树某种遍历方式的结点的前驱和后继这种指向前驱和后继的指针 , 叫线索。,36. 线索二叉树对二叉树以某种次序进行遍历并加上线索的过程叫做线索化。树称为线索二叉树。37. 广义表线索化了的二叉广义表简称表, 是零个或多个原子表所组成的有限序列。38. 强连通分量有向图的极大强连通子图, 称为有向图的强连通分量。39

8、. 结点的带权路径长度该结点到树根之间的路径长度与结点上权的乘积。40. 插入排序在一个已排好序的记录子集的基础上 , 每一步将下一个待排序的记录有序地插入到已排好序记录的子集上 , 直到将所有待排记录全部插入为止。41. 祖先一个结点的祖先是指从根结点到该结点的路径上的所有结点。42. 数据结构数据结构是数据元素的集合以及定义在该集合上的关系。43. 模式匹配子串的定位操作称作串的模式匹配。44. 单循环链表是单链表的另一种形式 , 它是一个首尾相接的链表域由 null 改为指向头结点或线性表的第一个结点, 表中最后一个结点的指针, 整个链表形成了一个环45. 线索在二叉树的存储结构中 ,

9、必有个空域 , 利用这些空域存放某种遍历的前驱和后继 , 其中指向前驱和后继的指针叫线索46. 图图是顶点与边的集合。一般表示为一个二元组是多对多的关系。47. 折半查找, 即 ,图G=(V,E),各个顶点之间对于顺序存储的有序表, 先取中间位置的记录关键字与所给的关键字进行比较若相等 , 则查找成功, 否则 , 若给定的关键字比中间的关键字大, 在原表的后半部分比较 , 反之 , 在原表的前半部分比较, 如此反复 , 逐步缩小范围, 直到找到为,止 , 或找不到 , 最后查找范围为空48. 最小生成树在图 G的所有生成树中49. 广度优先搜索(BFS), 树权值最小的那棵生成树, 称作最小生

10、成树首先访问出发点v, 接着依次访问v 的所有邻接点w1,w2,wt,然后再依次访问与wl,w2,wt邻接的所有未曾访问过的顶点。依此类推, 直至图中所有和源点 v 有路径相通的顶点都已访问到为止。此时从v 开始的搜索过程结束。( 若 G是连通图 , 则遍历完成; 否则 , 在图 C 中另选一个尚未访问的顶点作为新源点继续上述的搜索过程, 直至 G中所有顶点均已被访问为止。)50. 完全二叉树对满二叉树的结点从上到下, 从左到右进行依次进行编号每一个结点都与深度为K 的满二叉树中编号都一一对应时称做完全二叉树.51. 前缀编码, 若有一棵二叉树的 , 只是最后一层不满,任何一个字符的编码都不是

11、另一个字符编码的前缀, 这种编码叫做前缀编码.52. 广义表是零个或多个原子表所构成的有序序列.53. 线索二叉树利用二叉树的一些空闲指针指向该结点的前驱或后继后了的二叉树, 称为线索二叉树.54. 树的高度, 这种指针叫线索, 线索树中所有结点的层次的最大值55. 堂兄弟.同一层上不同双亲的结点, 互称堂兄弟.56. 叶子结点度为 0的结点 , 即没有后继的结点.57. 森林M 棵互相不相交的树构成的集合, 将一棵非空树的根结点删除, 树就变成了森林 .58. 树的路径长度树中每个结点到根结点的路径长度之和.59. 树的带权路径长度 (WPL)树中所有叶子结点的带权路径长度之和.60. 哈夫

12、曼树设有 N 个权值的结点构造一棵有N 个叶子结点的二叉树, 其中树 , 为哈夫曼树.61. 哈夫曼编码一般以N 种字符出现的频率做权值, 构造哈付曼树, 左孩子边做1, 那么从根到叶子结点经过的0 和 1 序列 , 构成了哈夫曼编码.WPL最小的那棵0, 右孩子边做62. 图中顶点的度顶点 V 的度是图中和顶点V 相关联的边的数目。包括入度和出度两种。63. 子图图 G=(V,E) 与图 G1=(V1,E1), 若 V1 包含于 V, 且 E1 包含于 E, 则 G1是 G的子图。64. 连通图对于无向图 , 若 V1 到 V2 有路径 , 称 V1V2 是连通的 , 若图中任意两点都是连通

13、的 , 则称该无向图是连通图。65. 网图的弧或边有与它相关的有意义的数, 称作权 , 带有权值的图称作网。66. 深度优先搜索 (DFS)类似树的先序遍历, 在图中任选一个顶点作为出发顶点V0, 访问 V0 后 , 依次从V0 的没被访问过的邻接点出发进行深度优先搜索。直到与V0 所连通的所有顶点均被访问。 如果 , 此时图中还有顶点尚未访问, 则从剩余的顶点中再任选一个顶点作为出发顶点V0, 重复上述过程, 直到图中全部顶点均被访问为止。67. 简单回路除了第一个顶点和最后一个顶点之外路。68. 简单路径, 其余顶点均不相同的回路称为简单回在用一个顶点序列表示一条路径时其为简单路径。69.

14、 查找, 若序列中没有相同的顶点重复出现, 则称根据给定的关键字值 , 在特定的表中 , 确定一个其关键字与给定值相同的数据元素 , 并返回该数据元素在列表中的位置。这个过程叫查找。70. 平均查找长度 (ASL)为确定数据元素在表中的位置, 需和给定值进行比较的关键字个数的数学期望值 , 成为查找算法在查找成功的平均查找长度。71. 二叉排序树它或是一棵空树, 或是有下面性质的树：若左或右子树不空, 左子树所有结点值小于根结点 , 而右子树所有结点值大于根结点的值 , 其左右子树也是二叉排序树。72. 顺序查找对于给定的关键字K, 从线性表的第一个( 或最后一个) 元素开始 , 依次向后 (

15、 或前 ) 与元素的关键字比较 , 若某个记录的关键字与K 相等 , 查找成功 , 否则失败。73. 平衡二叉树或是一棵空树衡二叉树。74. 插入排序, 或左右子树高度差的绝对值小于等于1 而且, 左右子树也是平在一个已排好序的基础上, 每一步将下一个待排序记录插到已排好记录的子集上 , 使之重新有序 , 直到所有待排记录插完为止。75. 分块查找 ( 索引查找 )分块查找以前两个为基础 , 将待查记录分成若干块 , 每块的关键字无序 , 但每块的关键字的最大值有序 , 查找时 , 先查找到待查记录所在的块 , 再在块内进行顺序查找。找块时 , 即可以用折半查找 , 也可用顺序查找。76. 拓

16、扑排序由某个集合上的偏序集得到该集合上的一个全序, 这个操作叫做拓扑排序。77. 归并排序将两个或两个以上的有序表合并成一个新的有序表个个单独的有序表, 逐渐表个数以原来一半的速度递减来长度的2 倍增加 , 不断重复 , 直到最后是一个表止。78. 排序, 开始将每个元素当成是一, 每个表的长度却是原, 而表的长度是元素个数为根据关键字的递减或递增的次序, 把文件中的各个记录依次排列起来, 可使一个无序的数据元素序列变成一个有序的序列的操作。79.shell排序它是插入排序的一种, 又叫缩小增量排序, 先按增量进行分组, 组内插入排序,然后每次缩短增量, 再进行分组和组内插入排序,直到增量为1

17、 时 , 进行最后一次排序止。80. 内部排序指的是待排序记录存放在计算机存储器中进行的排序过程；81. 外部排序指的是待排序记录的数量很大, 以致内存一次不能容纳全部记录, 在排序过程中对外存进行访问的排序过程。82. 不稳定排序假设Ki=Kj(1 i n,1 j n,i j),且在排序前的序列中Ri 领先于Rj( 即 i j) 。若在排序后的序列中Rj 领先于 Ri , 则称所用的排序方法是不稳定的。83. 稳定排序假设 Ki=Kj(1 i n,1 j j) 。若在排序后的序列中 n,i j), 且在排序前的序列中 Ri 领先于 Rj( 即 i Ri 仍领先于 Rj, 则称所用的排序方法是

18、稳定的84. 直接插入排序第 1 遍 , 将初始文件中的记录 R1 看作有序子文件 , 将 R2 插入这个子文件中。 若 R2 的关键字小于 R1 的关键字 , 则 R2 插在 R1 的前面 , 否则 R2 插在 R1 的后面。第 2 遍 , 将 R3 插入前面的两个记录的有序子文件中, 得到 3 个记录的有序子文件。依此类推, 继续进行下去, 直到将Rn 插入到前面的n-1 个记录的有序子文件中 , 最后得到n 个记录的有序文件。85. 气泡排序法气泡排序的过程很简单。从第一记录开始, 相邻的两个记录关键字进行比较,若顺序不对, 立即交换 , 直至 N-1 个与第 N 个比较为止。 得到一个最大( 或最小 )的关键字记录的结果位置。86. 选择排序选择排序是每一趟在n-i+1(i= 1,2,3n-1) 个记录中选择关键字最小的记录作为有序序列中第i 个记录。其中最简单的是简单选择排序87. 快速排序快速排序的基本思想是把当前待排序的记录, 存放到整个表排好序后, 它应当在的最终位置上。将原来的待排序表分割成两部分, 其中一部分表中的关键字均比另一部分表中的关键字小。然后 , 分别对两部分表用同样的方式进行排序,直到整个表排好序。88. 堆排序首先将根结点的记录与当前树中具有最大序号的记录交换, 把交换后具有最大序号的记录输出, 得到一个排序的结果。这时的树不再是堆树