有以下关键字序列2140524529120266H K=K11试在0~10的裂空地址空间中用线性探测再散列方法处理冲突则等概率下查找成功的平均查找长度为多少?
线性探测再散列方法是一种处理冲突的方法,当发生冲突时,通过逐个探测下一个位置,直到找到一个空的位置为止。
根据题目给出的关键字序列,使用H(K)=K%11作为哈希函数,然后使用线性探测再散列方法进行处理冲突。
首先,创建一个大小为11的数组作为哈希表,初始化所有位置为空。
然后,依次插入关键字序列中的每个关键字。
关键字序列为(21,40,52,45,29,12,02,66)。
插入关键字21时,计算哈希值为21%11=10,该位置为空,插入成功。
插入关键字40时,计算哈希值为40%11=7,该位置为空,插入成功。
插入关键字52时,计算哈希值为52%11=8,该位置为空,插入成功。
插入关键字45时,计算哈希值为45%11=1,该位置为空,插入成功。
插入关键字29时,计算哈希值为29%11=7,该位置已经被关键字40占用,发生冲突。
由于发生冲突,使用线性探测再散列方法,逐个探测下一个位置。
下一个位置为29%11+1=8,该位置为空,插入成功。
插入关键字12时,计算哈希值为12%11=1,该位置已经被关键字45占用,发生冲突。
逐个探测下一个位置,下一个位置为12%11+1=2,该位置为空,插入成功。
插入关键字02时,计算哈希值为2%11=2,该位置已经被关键字12占用,发生冲突。
逐个探测下一个位置,下一个位置为2%11+1=3,该位置为空,插入成功。
插入关键字66时,计算哈希值为66%11=0,该位置为空,插入成功。
最终得到的哈希表为[66, 21, 12, 02, 45, 29, 52, 40, , , ]。
等概率下查找成功的平均查找长度为(1+2+3+4+5+6+7+8)/8=36/8=4.5
原文地址: https://www.cveoy.top/t/topic/iySF 著作权归作者所有。请勿转载和采集!