当前位置:   article > 正文

20191220 数据结构名词解释_散列表中聚集和冲突的区别

散列表中聚集和冲突的区别

数据结构名词解释

 第三章 表、栈、队列
抽象数据类型ADT——操作的集合
诸如表、集合、图和它们的操作一起可以看作是ADT

 第四章 树

  1. 深度:根节点->当前节点的路径长
    高度:当前节点->一片树叶的最长路径
  2. 二叉树:每个节点的儿子树<=2 (表达式树)
    二叉查找树:对每个节点X,左子树<X<右子树
    AVL树:左右子树高度差<=1的二叉查找树
    伸展树
    B-树
  3. 先序遍历:先处理当前节点,再处理儿子节点
    后序遍历:先处理儿子节点,再处理当前节点
  4. 懒惰删除:对要删除的元素只做删除记号而不将其移除
  5. 内部路径长:一棵树内所有节点的深度和

 第五章 散列表

  1. 散列函数:从关键字到地址区间的一种映射
  2. 冲突:两个关键字散列到同一个值
  3. 装填因子λ:散列表中元素个数与散列表大小的比值,即散列表的平均长度
  4. 一次聚集:散列表中的元素占据的单元聚集形成一些区块,但同时表的其他部分相对较空
  5. 二次聚集:散列到同一位置上的元素将探测相同的备选单元

 第六章 优先队列(堆)

  1. 完全二叉树:除最底层外被全部填满的二叉树
    理想二叉树:完全填满的二叉树
  2. d-堆:每个节点都有d个儿子
  3. 零路径长Npl(X):从X到一个没有两个儿子节点的最短路径的长
    Npl(NULL)=-1;
    Npl(X)比其诸儿子零路径长的最小值多1;
  4. 左式堆:对任意节点,Npl(左儿子)>=Npl(右儿子)
    左式堆节点的三种可能性:
    (1) 有2个子节点
    (2) 没有子节点
    (3) 有1个左子节点
  5. 二项树:每个节点包含数据、第一个儿子及其右兄弟
  6. 二项队列(森林):堆序树(二项树)的集合

 第九章 图论

  1. 简单路径:所有顶点互异,但第一个顶点和最后一个顶点可能相同
  2. 连通:无向图中,任意两个顶点间都存在一条路径
    强连通:有向图中,任意两个顶点间都存在一条路径
    弱连通:有向图不是强连通的,但改为无向图后连通
  3. 完全图:任意两个顶点间都存在一条边
  4. 入度:进入该节点的边的数量
    出度:从该节点出发的边的数量
  5. 广度优先搜索BFS:按层处理顶点,据开始点最近的点先被赋值,最远的点最后被赋值
    深度优先搜索DFS:访问当前节点,并递归的遍历所有与当前节点相连的节点
  6. 关键路径:一条完全由零-松弛边组成的路径
  7. 流图Gf:表示在算法任意阶段已经达到的流,当算法终止时,Gf将包含最大流
    残余图Gr:表示对于每条边还能再添加上多少流
  8. 增长通路:从发点到收点的一条路径
  9. 最小生成树:连接图中所有顶点且总价值最低的树
  10. 双连通性:一个连通的无向图中任一顶点删除后,剩下的图仍然连通
  11. 割点:在一个连通但不是双连通的图中,删除后使图不再连通的顶点是割点
  12. 欧拉回路:对图的每条边恰好访问一次的路径
  13. 哈密尔顿圈:在无向图中,通过图的每一个顶点的圈

 第十章 算法设计

  1. 贪婪算法:不断选择局部最优,最终得到全局最优
    (例如:Dijkstra算法,Prim算法,Kruskal算法)
    应用:调度问题、文件压缩(Huffman编码)、近似装箱问题
  2. 非预占调度:一旦开始一个作业,就必须把该作业运行到完成
  3. 分治算法:递归解决较小的问题,再从子问题的解中构建原问题的解
    应用:最近点问题、选择问题、整数相乘、矩阵乘法
  4. 动态规划:利用非递归算法将子问题的答案系统的记录在一个表内
    应用:矩阵乘法的顺序安排(pqr次标量法)、最优二叉查找树、求所有点对最短路径
  5. 随机化算法
  6. 回溯算法
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/407271
推荐阅读
相关标签
  

闽ICP备14008679号