赞
踩
为了平时复习时方便,把每一章需要掌握的内容记录在此,这样浓缩的看,也好在脑子里面形成比较系统的思维导图。
本章多以选择题的形式考查,但也会涉及树遍历相关的算法题。树和二叉树的性质,遍历,转换,存储结构和操作特性等。满二叉树,完全二叉树,线索二叉树,哈夫曼树的定义和性质,二叉排序树和二叉平衡排序树的性质和操作等,都是选择题必然涉及的内容
应该掌握图的基本概念,图的存储结构及其特性,存储结构之间的转化,基于存储结构上的遍历操作和各种应用(拓扑排序,最小生成树,最短路径和关键路径)等
图的相关算法较多,易混,但通常只要掌握其基本思想和实现步骤(能动手模拟),而算法的具体实现不是重点
散列函数的:把一个查找表中的关键字映射成该关键字对应的地址的函数
散列表:根据散列表而直接进行访问的数据结构
同义词:发生冲突的不同的关键字叫做同义词
冲突:散列函数可能会把两个或两个以上的不同的关键字映射到同一个地址,这种情况叫做冲突
散列函数的构造方法:
常见的散列函数:
直接定址法:直接去关键字的某个线性数值为散列地址,散列函数为
H
(
k
e
y
)
=
a
∗
k
e
y
+
b
H(key)=a*key+b
H(key)=a∗key+b,其中a,b都是常数。这种计算方法比较简单,并且不会产生冲突。
有点:适合关键字分布基本连续的情况
缺点:当关键字不连续时,产生较多的空缺,浪费空间
除留余数法:这是一种,最简单,最常用的方法。假定散列表的长度为m,取一个不大于m,但最接近或等于m的质数,利用下面的公式把关键字转换成散列表地址,
H
(
k
e
y
)
=
k
e
y
H(key)=key%p
H(key)=key。
除留余数法的关键是选好p,使得每个关键字通过该函数转换后等概率的映射到散列表空间的任一地址,从而尽可能的减少冲突。
数字分析法
平方取中法
折叠法
开放地址法
概念:是指可存放新表项的空闲地址既向它的同义词开放,又向他的非同义词开放。
H
i
=
(
H
(
k
e
y
)
+
d
i
)
H_i=(H(key)+d_i)%m
Hi=(H(key)+di),i=0,1,2,3,……,k(k<=m-1);m为散列表表长,
d
i
d_i
di为增量序列
如何计算增量序列:
开放定址法的缺点:对于删除一个已经在散列表中的元素不友好,删除一个元素可能会导致某些元素失去索引
拉链法
概念:是指把所有的同义词都存放在一个线性的链表中,这个线性的链表由地址唯一标识,即散列表中每个单元存放该链表头指针。
拉链法适用于经常进行插入和删除的情况
填装因子
概念:一般记为
α
\alpha
α,表示表的装满程度
α = 表 中 记 录 数 n 散 列 表 长 度 m \alpha=\frac{表中记录数n}{散列表长度m} α=散列表长度m表中记录数n
散列表的平均查找长度依赖于散列表的填装因子
本章是考研的重点。对于散列查找,应该掌握散列表的构造,冲突处理方法(各种方法处理过程)、查找成功和查找失败的平均查找长度,散列表查找的特征和性能分析。对于折半查找,应该掌握这般查找的过程,构造判定树,分析平均查找长度。B树和B+树是本章的难点。对于B树,考研大纲要求掌握插入,删除和查找的操作过程。对于B+树,仅要求掌握基本概念和性质
以上内容参考王道数据结构
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。