数据结构名词解释整理

Data Structure

2015

hash table散列表：存放记录的数组

topological sort拓扑排序：将一个DAG中所有顶点在不违反前置依赖条件规定的基础上排成线性序列的过程称为拓扑排序（44） worst case 最差情况：从一个n元一维数组中找出一个给定的K，如果数组的最后一个元素是K，运行时间会相当长，因为要检查所有n个元素，这是算法的最差情况（15）

FIFO先进先出：队列元素只能从队尾插入，从队首删除（20）（P82） 2014

growth rate增长率：算法的增长率是指当输入的值增长时，算法代价的增长速率（14）

priority queue 优先队列：一些按照重要性或优先级来组织的对象成为优先队列（26）

external sorting外排序：考虑到有一组记录因数量太大而无法存放到主存中的问题，由于记录必须驻留在外存中，因此这些排序方法称为外排序（32）

connected component连通分量：无向图的最大连通子图称为连通分量（40） 2013

stack栈：是限定仅在一端进行插入或删除操作的线性表（19） priority queue 优先队列：一些按照重要性或优先级来组织的对象成

为优先队列（26）

BFS广度优先搜索：在进一步深入访问其他顶点之前，检查起点的所有相邻顶点（42）

collision (in hashing)冲突：对于一个散列函数h和两个关键码值k1和k2，如果h(k1) =?= h(k2)，其中?是表中的一个槽，那么就说k1和k2对于?在散列函数h下有冲（35）

Chapter 1 Data Structures and Algorithms

1. type类型：是指一组值的集合

2. data type数据类型：一个类型和定义在这个类型上的一组操作 3. abstract data type (ADT)抽象数据类型：指数据结构作为一个软件构件的实现

4. data structure数据结构：是ADT的实现

5. problem问题：一个需要完成的任务，即对应一组输入，就有一组相应的输出

6. function函数：是输入和输出之间的一种映射关系 7. algorithm算法：是指解决问题的一种方法或者一个过程 8. algorithm算法是解决问题的步骤，它必须把每一次输入转化为正确的输出；一个算法应该由一系列具体步骤组成，下一步应执行的步骤必须明确；一个算法必须由有限步组成；算法必须可以终止。

9. computer program计算机程序：被认为是使用某种程序设计语言对一个算法的具体实现

10. program程序：是算法在计算机程序设计语言中的实现

Chapter 2Mathematical Preliminaries

11. set集合：是由互不相同的成员members或者元素elements构成的一个整体

12. recursive递归：如果一个算法调用自己来完成它的部分工作，就称这个算法是递归的

Chapter 3Algorithm Analysis

13. Asymptotic analysis渐进分析：可以估算出当问题规模变大时，一种算法及实现它的程序的效率和开销

14. growth rate增长率：算法的增长率是指当输入的值增长时，算法代价的增长速率

15. best / worst / average case最佳、最差、平均情况（P39） 16. upper bound (p42) / lower bound (p43) 上限：该算法可能有的最高增长率 下限：一种算法消耗某种资源的最大值

17. big-Oh (p42)/ big-Omega (p43) / Theta notation (p44)

Chapter 4List, Stacks, and Queues

18. list线性表：是由称为元素的数据项组成的一种有限且有序的序列 19. stack栈：是限定仅在一端进行插入或删除操作的线性表

20. queue队列：也是一种受限制的线性表，队列元素只能从队尾插入，从队首删除

Chapter 5Binary Trees

21. BST二叉检索树：是满足下面所给出条件的二叉树，该条件即二叉检索树性质：对于二叉检索树的任何一个结点，设其值为K，则该结点左子树中任意一个结点的值都小于K；该结点右子树中任意一个结点的值都大于或等于K

22. depth深度：结点M的深度就是从根节点到M的路径长度 23. height高度：树的高度等于最深结点的深度加1

24. full binary tree满二叉树：的每一个结点或者是一个分支结点，并恰好有两个非空子结点；或者是叶结点

25. complete binary tree完全二叉树：有严格的形状要求：从根结点起每一层从左到右填充

26. priority queue优先队列：一些按照重要性或优先级来组织的对象成为优先队列

27. heap堆：堆由两条性质来定义。首先，它是一棵完全二叉树，所有往往用数组来实现表示完全二叉树。其次，堆中存储的数据是局部有序的。也就是说，结点存储的值与其子结点存储的值之间存在某种关系。

Chapter 8File Processing and External Sorting

28. Golden Rule of File Processing:文件处理的黄金法则 使磁盘的访问次数最少！

29. track磁头在一个盘片的某个位置上可以访问的所有数据就构成了一个磁道，即这个盘片上与主轴具有相同距离的所有数据 30. sectors扇区：每个磁道（track）分为多个扇区

31. Contiguous sectors are often grouped to form a cluster簇：多个扇区通常集结成组，称为一个簇。簇是文件分配的最小单位，因此所有文件都是一个或几个簇的大小

32. external sorting外排序：考虑到有一组记录因数量太大而无法存放到主存中的问题，由于记录必须驻留在外存中，因此这些排序方法称为外排序

33. run顺串：被排序的子序列成为顺串 (p294)

Chapter 9Searching

34. hashing散列：可以通过一些计算，把关键码值映射到数组中的位置来访问记录，这个过程称为散列

35. collision冲突：对于一个散列函数h和两个关键码值k1和k2，如果h(k1) =?= h(k2)，其中?是表中的一个槽，那么就说k1和k2对于?在散列函数h下有冲突

Chapter 10Indexing

36. Indexing索引：是把一个关键码与它对应的数据记录的位置相关

本文来源：https://www.bwwdw.com/article/agxv.html