数据结构问答8-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构问答8。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

查找

关键字：能唯一标识该元素

查找：给定值k，在含n个元素的表中找出关键字==k的元素。找到返回其位置信息，否则返回-1。

动、静态查找表：查找同时对表进行修改（插入、删除等），相应的表为动态，否则为静态。

内、外查找：整个查找过程在内存中进行，称之为内查找；需要访问外存，则为外查找。

平均查找长度ASL：∑pici，pi：查找第i个元素的概率，一般为1/n，ci：找到第i个元素所需进行的关键字的比较次数。

答：通过平均查找长度ASL。其数量级反应了查找算法的时间复杂度。

答：

基本思想：从表的一端开始顺序扫描顺序表，依次扫描到的元素关键字与k比较，若找到，查找成功；若扫描结束也未找到，则失败。

时间复杂度：O（n）

优点：算法简单，且对表的结构无任何要求。

缺点：查找效率低。

答：要求线性表是有序表。不适合链式存储结构的数据查找。

基本思想：在[low, high]之间查找目标关键字，每次检查mid=(low+high)/2，根据mid所指元素与目标关键字的大小调整low和high，不断缩小low和high的范围，当low>high时则查找失败。

判定树（或判定表）构造及特性：

构造：由mid所指元素将原有元素分割到左右子树中。

特性：① 折半查找的判定树是是平衡的二叉排序树（左<中<右）

② 只有最下面一层试不满的

③ 若查找表有n个关键字，则失败结点有n+1个

④ 树高h=log2(n+1)上取整，不包含失败结点

时间复杂度：O（log2n）

优点：查找效率高

缺文章来源地址https://www.toymoban.com/news/detail-611085.html

到了这里，关于数据结构问答8的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！