哪种查找对应各自查找表如有序表可以为静态查找表也可以为动态查找表。依查找方式决定■■◆■◆◆。

　　假设查找成功与不成功的可能性相同对每个记录查找概率也相等则

　　看到上面静态查找的概念动态查找就很好理解了个人总觉得动态查找不像是“查找”更像是一个对表进行“创建、扩充、修改、删除”的过程。动态查找的过程中对表的操作会多两个动作1首先也有一个“判断性查找”的过程如果某特定的关键字在表中不存在则按照一定的规则将其插入表中2如果已经存在则可以对其执行删除操作。动态查找的过程虽然只是多了“插入★★■■★”和◆■◆“删除”的操作但是在对具体的表执行这两种操作时往往并不是那么简单。

　　分块查找的速度虽然不如折半查找算法但比顺序查找算法快得多同时又不需要对全部节点进行排序。当节点很多且块数很大时对索引表可以采用折半查找这样能够进一步提高查找的速度■■。

　　假设每个记录的查找概率相等顺序查找的平均查找长度

　　一般情况下为进行分块查找可以将长度为n的表均匀的分成b块每块含有s个记录假定表中每个记录的查找概率相等。用顺序查找确定所在块分块查找的平均查找长度为

　　分块查找由于只要求索引表是有序的对块内节点没有排序要求因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时只需将该节点调整到所在的块即可。在空间复杂性上分块查找的主要代价是增加了一个辅助数组■★■■。

　　含有n个节点的二叉排序树的平均查找长度和树的形态有关最好和成正比当先后插入的关键字有序构成的二叉排序树蜕变为单支树树的深度为n◆■★★,最坏情况平均查找长度为

　　以一个牛客网上的题目为例设顺序线个元素如果采用分块查找并且索引表和块内均采用顺序查找则其平均查找长度为(     )◆★■■◆。

　　分块查找是折半查找和顺序查找的一种改进方法折半查找虽然具有很好的性能但其前提条件时线性表顺序存储而且按照关键码排序这一前提条件在结点树很大且表元素动态变化时是难以满足的■■◆◆。而顺序查找可以解决表元素动态变化的要求但查找效率很低◆◆■◆◆■。如果既要保持对线性表的查找具有较快的速度又要能够满足表元素动态变化的要求则可采用分块查找的方法■◆。

　　所有叶子结点中包含了全部关键字信息及指向这些关键字记录的指针且叶子结点本身依关键字的大小自小而大顺序链接。

　　首先无论是静态查找还是动态查找都要有查找的对象也就是包含很多同类型数据的■■◆◆★“表”这个★★“表”可以理解为一个由同类型数据元素组成的一个“集合”该集合可以用各种容器来存储例如数组★★◆■■◆、链表、树等我们统称这些存储数据的数据结构为——查找表。可见查找表有时是我们传统意义的表有时候是很复杂的一种结构。

　　由于索引项按关键字有序则确定块的查找可以用顺序表查找也可以用折半查找块中记录是任意排列的在块中只能是顺序查找★◆◆。

　　对子表建立一个索引表包括两项内容关键字项值为该子表内最大关键字和指针项指向该子表的第一个记录在表中的位置。索引表按关键字有序表或者有序或者分块有序。

　　折半查找这个查找过程类似二叉树具有n个节点的判定树深度为

　　概念1、静态查找首先无论是静态查找还是动态查找，都要有查找的对象，也就是包含很多同类型数据的“表”★◆■■，这个“表”可以理解为一个由同类型数据元素组成的一个“集合”，该集合可以用各种容器来存储，例如数组、链表■★★■★■、树等，我们统称这些存储数据的数据结构为——查找表。可见◆★，查找表有时是我们传统意义的表◆★，有时候是很复杂的一种结构。静态查找就是我们平时概念中的查找，是◆★★■◆“真正的查找”。之所以说静态查找是真.★■■..

　　它或者是一棵空树或者是具有下列性质的二叉树它的左子树和右子树都是平衡二叉树且左右子树的深度之差绝对值不超过1。结点平衡因子定义为左子树深度减右子树深度-1,0★◆,1■■■。平均查找时间复杂度

　　分块查找会分两部分进行,第一步先进行索引表查找判断其在那个字表中,第二步然后进行在字表中的查找

　　所有非终端结点可以看成是索引部分结点中仅含有其子树根结点中最大或最小 关键字。

　　静态查找就是我们平时概念中的查找是“真正的查找★★◆■”■◆◆◆★。之所以说静态查找是线c;因为在静态查找过程中仅仅是执行“查找”的操作即1查看某特定的关键字是否在表中判断性查找2检索某特定关键字数据元素的各种属性检索性查找★◆。这两种操作都只是获取已经存在的一个表中的数据信息不对表的数据元素和结构进行任何改变这就是所谓的静态查找。