数据结构名词解释整理

1、v1.0可编辑可修改Data Structure2015hash table 散列表：存放记录的数组topological sort拓扑排序：将一个DAG中所有顶点在不违反前置依赖条件规定的基础上排成线性序列的过程称为拓扑排序（44） worst case 最差情况：从一个n元一维数组中找出一个给定的 K, 如果数组的最后一个元素是 K,运行时间会相当长，因为要检查所有 n个元素，这是算法的最差情况（15）FIFO先进先出：队列元素只能从队尾插入，从队首删除（20）（ P82）2014growth rate增长率：算法的增长率是指当输入的值增长时，算法代价的增长速率（14）priority q

2、ueue优先队列：一些按照重要性或优先级来组织的对象成为优先队列（26）exter nal sorti ng外排序：考虑到有一组记录因数量太大而无法存放到主存中的问题，由于记录必须驻留在外存中，因此这些排序方法 称为外排序（32）connected component 连通分量：无向图的最大连通子图称为连通分量（40）2013stack栈：是限定仅在一端进行插入或删除操作的线性表（19） priority queue优先队列：一些按照重要性或优先级来组织的对象成为优先队列(26)BFS广度优先搜索：在进一步深入访问其他顶点之前，检查起点的所有相邻顶点(42)collision (in hash

3、ing)冲突：对于一个散列函数 h和两个关键码值也和k2，如果h(k1) = = h(k2)，其中 是表中的一个槽，那 么就说k1和k2对于 在散列函数h下有冲(35)Chapter 1 Data Structures and Algorithms1. type类型：是指一组值的集合2. data type数据类型：一个类型和定义在这个类型上的一组操作3. abstract data type (ADT)抽象数据类型：指数据结构作为一个软件构件的实现4. data structure数据结构：是 ADT的实现5. problem问题：一个需要完成的任务，即对应一组输入，就有一组相应的输出6.

4、function 函数：是输入和输出之间的一种映射关系7. algorithm 算法：是指解决问题的一种方法或者一个过程8. algorithm 算法是解决问题的步骤，它必须把每一次输入转化为 正确的输出；一个算法应该由一系列具体步骤组成，下一步应执 行的步骤必须明确；一个算法必须由有限步组成；算法必须可以 终止。9. computer program计算机程序：被认为是使用某种程序设计语言 对一个算法的具体实现10. program程序：是算法在计算机程序设计语言中的实现Chapter 2 Mathematical Prelim in aries11. set集合：是由互不相同的成员 mem

5、bers或者元素 elements构成的一个整体12. recursive递归：如果一个算法调用自己来完成它的部分工作， 就称这个算法是递归的Chapter 3 Algorithm An alysis13. Asymptotic analysis 渐进分析：可以估算出当问题规模变大 时，一种算法及实现它的程序的效率和开销14. growth rate 增长率：算法的增长率是指当输入的值增长时， 算法代价的增长速率15. best / worst / average case 最佳、最差、平均情况(P39)16. upper bound (p42) / lower bound (p43)上限：该

6、算法可能有的最高增长率下限：一种算法消耗某种资源的最大值17. big-Oh (p42) / big-Omega (p43) / Theta notation (p44)Chapter 4 List, Stacks, and Queues18. list线性表：是由称为元素的数据项组成的一种有限且有序的序列19. stack栈：是限定仅在一端进行插入或删除操作的线性表20. queue队列：也是一种受限制的线性表，队列元素只能从队尾 插入，从队首删除Chapter 5 Binary Trees21. BST二叉检索树：是满足下面所给出条件的二叉树， 该条件即二叉检索树性质：对于二叉检索树的任何

7、一个结点，设其值为K,则该结点左子树中任意一个结点的值都小于K;该结点右子树中任意一个结点的值都大于或等于 K22. depth深度：结点M的深度就是从根节点到M的路径长度23. height高度：树的高度等于最深结点的深度加 124. full b in ary tree满二叉树：的每一个结点或者是一个分支结点，并恰好有两个非空子结点；或者是叶结点25. complete bi nary tree完全二叉树：有严格的形状要求：从根结点起每一层从左到右填充26. priority queue优先队列：一些按照重要性或优先级来组织的对象成为优先队列27. heap堆：堆由两条性质来定义。首先，它

8、是一棵完全二叉树， 所有往往用数组来实现表示完全二叉树。其次，堆中存储的数据 是局部有序的。也就是说，结点存储的值与其子结点存储的值之 间存在某种关系。Chapter 8 File Processing and External Sorting28. Golden Rule of File Processing:文件处理的黄金法则使磁盘的访问次数最少！29. track磁头在一个盘片的某个位置上可以访问的所有数据就构 成了一个磁道，即这个盘片上与主轴具有相同距离的所有数据30. sectors扇区：每个磁道（track ）分为多个扇区31. Con tiguous sectors are of

9、te n grouped to form acluster簇：多个扇区通常集结成组，称为一个簇。簇是文件分配的最小 单位，因此所有文件都是一个或几个簇的大小32. external sorti ng外排序：考虑到有一组记录因数量太大而无法存放到主存中的问题，由于记录必须驻留在外存中，因此这 些排序方法称为外排序33. run顺串：被排序的子序列成为顺串（p294）Chapter 9 Search ing34. hashing散列：可以通过一些计算，把关键码值映射到数组中 的位置来访问记录，这个过程称为散列35. collision冲突：对于一个散列函数 h和两个关键码值也和k2，如果h（k1）

10、= = h（k2），其中 是表中的一个槽，那么就说 k1和k2对于在散列函数h下有冲突Chapter 10 In dex ing36. In dex ing索引：是把一个关键码与它对应的数据记录的位置 相关联的过程37. primary key主码：数据库中的每一条记录通常都有一个唯一 标识，称为主码38. secondary key辅码：可能有多条记录相同的关键码值39. lin ear in dex线性索引：的索引文件中是一组关键码/指针对，这个文件按照关键码顺序排序，指针可以(1)指向磁盘中的 完整记录所在的位置，也可以(2)指向主索引中主码的位置，或 者(3)指向主码的实际值Chapter 11 Graphs40. connected components连通分量：无向图的最大连通子图 称为连通分量41. directed acyclic graph(DAG)有向无环图：不带回路的有向图42. BFS (breadth-first search) 广度优先搜索：在进一步深入访问其他顶点之前，检查起点的所有相邻顶点43. DFS (deep-first search)深度优先搜索：把所有从顶点 V出去的边存入栈中44. topological sort拓扑排序：将