admin 管理员组文章数量: 1086019
2023年12月20日发(作者：ps批量切片导出图片)
散列表：存放记录的数组
拓扑排序： 将一个 DAG 中所有顶点在不违反前置依赖
条件规定的基础上排成线性序列的过程称为拓扑排序(44)
最差情况：从一个 n 元一维数组中找出一个给定的 K，如
果数组的最后一个元素是 K，运行时间会相当长，因为要检查所有 n
个元素，这是算法的最差情况(15)
先进先出：队列元素只能从队尾插入，从队首删除(20) (P82)
增长率： 算法的增长率是指当输入的值增长时， 算法代价
的增长速率(14)
优先队列：一些按照重要性或者优先级来组织的对象成 为优先队列(26)
外排序： 考虑到有一组记录因数量太大而无法存放到
主存中的问题， 由于记录必须驻留在外存中， 因此这些排序方法称为
外排序(32)
量(40)
连通分量：无向图的最大连通子图称为连通分
栈：是限定仅在一端进行插入或者删除操作的线性表(19)
成
优先队列：一些按照重要性或者优先级来组织的对象
为优先队列(26)
广度优先搜索：在进一步深入访问其他顶点之前，检查起点的所
有相邻顶点(42)
冲突：对于一个散列函数 和两个关键码值 k1
和
k2
，如果 (k1) =
= (k2)，其中是表中的一个槽，那末就说
k1
和 k2
对于 在散列函数
下有冲(35)
1.
类型：是指一组值的集合
构件的实现
数据类型：一个类型和定义在这个类型上的一组操作
(ADT)抽象数据类型：指数据结构作为一个软件
2.
3.
4.
数据结构：是 ADT 的实现
问题：一个需要完成的任务，即对应一组输入，就有一 5.
组相应的输出
6.
函数：是输入和输出之间的一种映射关系
算法：是指解决问题的一种方法或者一个过程
解决问题的步骤， 它必须把每一次输入转化为正
7.
8.
确的输出；一个算法应该由一系列具体步骤组成，下一步应执行
的步骤必须明确；一个算法必须由有限步组成；算法必须可以终
止。
9.
计算机程序：被认为是使用某种程序设计语言
对一个算法的具体实现
10.
程序：是算法在计算机程序设计语言中的实现
或者元素 构成 11. 集合：是由互不相同的成员的一个整体
12. 递归：如果一个算法调用自己来完成它的部份工作，就
称这个算法是递归的
13. 渐进分析： 可以估算出当问题规模变大时， 一
种算法及实现它的程序的效率和开消
14. 增长率：算法的增长率是指当输入的值增长时，算法
代价的增长速率
15.
(p42)
(p43)
(P39)
上限：该算法可能有的最高增长率
下限：一种算法消耗某种资源的最大值
17. (p42) (p43) (p44)
18.
线性表： 是由称为元素的数据项组成的一种有限且有序的序列
栈：是限定仅在一端进行插入或者删除操作的线性表 19.
20. 队列：也是一种受限制的线性表，队列元素只能从队尾插
入，从队首删除
21. 二叉检索树：是满足下面所给出条件的二叉树，该条件即二
叉检索树性质：对于二叉检索树的任何一个结点，设其值为 K，
则该结点左子树中任意一个结点的值都小于 K；该结点右子树中
任意一个结点的值都大于或者等于 K
22.
深度：结点 M 的深度就是从根节点到 M 的路径长度
高度：树的高度等于最深结点的深度加 1
满二叉树：的每一个结点或者是一个分支结点，并
23.
24.
恰好有两个非空子结点；或者是叶结点
25. 彻底二叉树：有严格的形状要求：从根结点
起每一层从左到右填充
26. 优先队列：一些按照重要性或者优先级来组织的对象 成为优先队列
27. 堆：堆由两条性质来定义。首先，它是一棵彻底二叉树，所
有往往用数组来实现表示彻底二叉树。其次，堆中存储的数据是
局部有序的。也就是说，结点存储的值与其子结点存储的值之间
存在某种关系。
28.
:文件处理的黄金法则
使磁盘的访问次数至少！
29. 磁头在一个盘片的某个位置上可以访问的所有数据就构成
了一个磁道，即这个盘片上与主轴具有相同距离的所有数据
30.
扇区：每一个磁道(track)分为多个扇区
簇：多个扇区 31. Contiguous sectors are often grouped to form a通常集结成组，称为一个簇。簇是文件分配的最小单位，因此所
有文件都是一个或者几个簇的大小
32. 外排序：考虑到有一组记录因数量太大而无法存
放到主存中的问题，由于记录必须驻留在外存中，因此这些排序
方法称为外排序
33.
顺串：被排序的子序列成为顺串 (p294)
34. 散列： 可以通过一些计算， 把关键码值映射到数组中的位
置来访问记录，这个过程称为散列
35. 冲突：对于一个散列函数 和两个关键码值 k 和 k ，如
1 2
果 (k1) =
= (k2)，其中是表中的一个槽，那末就说k1
和 k2
对
于在散列函数
下有冲突
36. 索引：是把一个关键码与它对应的数据记录的位置相关
联的过程
37.
称为主码
主码：数据库中的每一条记录通常都有一个惟一标识，
38.
辅码：可能有多条记录相同的关键码值
39. 线性索引： 的索引文件中是一组关键码/指针对， 这个
文件按照关键码顺序排序，指针可以(1)指向磁盘中的完整记录
所在的位置，也可以(2)指向主索引中主码的位置，或者(3)
指向主码的实际值
40.
通分量
41.
连通分量：无向图的最大连通子图称为连
有向无环图：不带回路的有向图
广度优先搜索： 在进一步深入访问其他顶 42.
点之前，检查起点的所有相邻顶点
入栈中
44. 拓扑排序：将一个 DAG 中所有顶点在不违反前置
深度优先搜索： 把所有从顶点 V 出去的边存
依赖条件规定的基础上排成线性序列的过程称为拓扑排序
45. The 最小支撑树： 是一个包括图
G 中所有顶点及其一部份边的图，这些边是图 G 所有边集合的子
集。 (1)这个子集中所有边的权之和为所有子集中最小的
(2)子集中的边能保证图是连通的
版权声明：本文标题：数据结构名词解释整理 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/b/1703010140a439509.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论