数据结构名词解释整理.doc

《数据结构名词解释整理.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、（42）collision(inhashing)冲突：对于一个散列函数h和两个关键码值k1和k2，如果h(k1)==h(k2)，其中是表中的一个槽，那么就说k1和k2对于在散列函数h下有冲（35）Chapter1DataStructuresandAlgorithms1.type类型：是指一组值的集合2.datatype数据类型：一个类型和定义在这个类型上的一组操作3.abstractdatatype(ADT)抽象数据类型：指数据结构作为一个软件构件的实现4.datastructure数据结构：是ADT的实现5.problem问题：一个需要完

4、成的任务，即对应一组输入，就有一组相应的输出6.function函数：是输入和输出之间的一种映射关系7.algorithm算法：是指解决问题的一种方法或者一个过程8.algorithm算法是解决问题的步骤，它必须把每一次输入转化为正确的输出；一个算法应该由一系列具体步骤组成，下一步应执行的步骤必须明确；一个算法必须由有限步组成；算法必须可以终止。9.computerprogram计算机程序：被认为是使用某种程序设计语言对一个算法的具体实现1.program程序：是算法在计算机程序设计语言中的实现Chapter2MathematicalPre

5、liminaries2.set集合：是由互不相同的成员members或者元素elements构成的一个整体3.recursive递归：如果一个算法调用自己来完成它的部分工作，就称这个算法是递归的Chapter3AlgorithmAnalysis4.Asymptoticanalysis渐进分析：可以估算出当问题规模变大时，一种算法及实现它的程序的效率和开销5.growthrate增长率：算法的增长率是指当输入的值增长时，算法代价的增长速率6.best/worst/averagecase最佳、最差、平均情况（P39）7.upperbound(p

6、42)/lowerbound(p43)上限：该算法可能有的最高增长率下限：一种算法消耗某种资源的最大值8.big-Oh(p42)/big-Omega(p43)/Thetanotation(p44)Chapter4List,Stacks,andQueues9.list线性表：是由称为元素的数据项组成的一种有限且有序的序列1.stack栈：是限定仅在一端进行插入或删除操作的线性表2.queue队列：也是一种受限制的线性表，队列元素只能从队尾插入，从队首删除Chapter5BinaryTrees3.BST二叉检索树：是满足下面所给出条件的二叉树，

7、该条件即二叉检索树性质：对于二叉检索树的任何一个结点，设其值为K，则该结点左子树中任意一个结点的值都小于K；该结点右子树中任意一个结点的值都大于或等于K4.depth深度：结点M的深度就是从根节点到M的路径长度5.height高度：树的高度等于最深结点的深度加16.fullbinarytree满二叉树：的每一个结点或者是一个分支结点，并恰好有两个非空子结点；或者是叶结点7.completebinarytree完全二叉树：有严格的形状要求：从根结点起每一层从左到右填充8.priorityqueue优先队列：一些按照重要性或优先级来组织的对象成

8、为优先队列9.heap堆：堆由两条性质来定义。首先，它是一棵完全二叉树，所有往往用数组来实现表示完全二叉树。其次，堆中存储的数据是局部有序的。也就是说，结点存储的值与其子结点存储