设有12个数据{25,40,33,47,12,66,72,87,94,22,5,58},它们存储在散列表中,利用双散列解决冲突,要求插入新数据的平均查找次数不超过3次。
① 该散列表的大小m应该设计多大?
② 试为该散列表设计相应的散列函数(用除留余数法)并计算寻找下一个“空位”时向前跨步步长的再散列函数。
③ 顺次将各个数据散列到表中。
④ 计算查找成功的平均查找次数。
设有12个数据{25,40,33,47,12,66,72,87,94,22,5,58},它们存储在散列表中,利用双散列解决冲突,要求插入新数据的平均查找次数不超过3次。
① 该散列表的大小m应该设计多大?
② 试为该散列表设计相应的散列函数(用除留余数法)并计算寻找下一个“空位”时向前跨步步长的再散列函数。
③ 顺次将各个数据散列到表中。
④ 计算查找成功的平均查找次数。
① 线性探测再散列的哈希表查找成功的平均查找长度为:Sn=(1+1/(1-α))/2≤3∴ α≤4/5 (α为填充因子)即 12/m≤4/5,m≥15不妨取m=16.② 散列函数 H(key)=ke...
查看完整答案若杂凑表(Hash)的地址范围为[0,9],杂凑函数为H(key)=(key2+2) MOD 9,并采用链地址法处理冲突,请画出元素7、4、5、3、6、2、8、9依次插入杂凑表的状态。
假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行【 】次探测。
负载因子(装填因子)是散列表的一个重要参数,它反映散列表的装满程度。
一棵满二叉排序树深度为k,节点数为2k-1;节点值为1至(2k - 1),给出k和任意三个节点的值,输出包含该三个节点的最小子树的根节点。样例输入:4 10 15 13样例输出:12
已知序列17,31,13,11,20,35,25,8,4,11,24,40,27,请画出该序列的二叉排序树,并分别给出下列操作后的二叉排序树:① 插入数据9;② 删除结点17;③ 再删除结点13。
在任意一棵非空二叉排序树中,删除某结点后又将其插入,则所得二叉排序树与删除前原二叉排序树相同。
在关键字随机分布的情况下,用二叉排序树的方法进行查找,其查找长度与【 】量级相当。
用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。
在n个记录的有序顺序表中进行折半查找,最大的比较次数是__________。
用二分法查找一个线性表时,该线性表必须具有的特点是____________。
分块查找要求将待查找的表均匀地分成若干块,块中诸记录的顺序可以是任意的,但块与块之间____________。
在分块检索中,若索引表和各块内均用顺序查找,则有900个元素的线性表分成__________块最好;若分成25块,其平均查找长度为__________。
利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后,查找元素35要进行【 】次元素间的比较。