HASH GAME - Online Skill Game GET 300

　　1、哈希表查找不成功怎么计算？解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空问个数！例如：散列函数为hash(x)=xMOD13,用线性探测，建立了哈希表之后，如何求查找不成功时的平均查找长度！？地址：2数据：-3638成功次数：1312211911不成功次数：110查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10=2.2查找不成功时的平均查找长度：ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54说明：第n个位置不成功时的比较次

　　2、数为，第n个位置到第1个没有数据位置的距离。至少要查询多少次才能确认没有这个值。(1)查询hash(x)=0,至少要查询9次遇到表值为空的时候，才能确认查询失败。(2)查询hash(x)=1,至少要查询8次遇到表值为空的时候，才能确认查询失败。(3)查询hash(x)=2,至少要查询7次遇到表值为空的时候，才能确认查询失败。(4)查询hash(x)=3,至少要查询6次遇到表值为空的时候，才能确认查询失败。(5)查询hash(x)=4,至少要查询5次遇到表值为空的时候，才能确认查询失败。(6)查询hash(x)=5,至少要查询4次遇到表值为空的时候，才能确认查询失败。(7)查询hash(x)=6

　　3、,至少要查询3次遇到表值为空的时候，才能确认查询失败。(8)查询hash(x)=7,至少要查询2次遇到表值为空的时候，才能确认查询失败。(9)查询hash(x)=8,至少要查询1次遇到表值为空的时候，才能确认查询失败。(10)查询hash(x)=9,至少要查询1次遇到表值为空的时候，才能确认查询失败。(11)查询hash(x)=10,至少要查询2次遇到表值为空的时候，才能确认查询失败。(12)查询hash(x)=11,至少要查询1次遇到表值为空的时候，才能确认查询失败。(13)查询hash(x)=12,至少要查询10次遇到表值为空(循环查询顺序表)的时候，才能确认查询失败。下面看下2010年2

　　4、010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。Question1:将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key)=(keyx3)MOD7,处理冲突采用线性探测再散列法，要求装填(载)因子为0.7。(1)请画出所构造的散列表。(2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。Ans：(1).首先明确一个概念装载因子，装载因子是指所有关键子填充哈希表后饱和的程度，它等于关键字总数/哈希表的长度。根据题意，我们可以确定哈希表的长度为L=7

　　5、/0.7=10;因此此题需要构建的哈希表是下标为09的一维数组。根据散列函数可以得到如下散列函数值表。H(Key)=(keyx3)MOD7,例如key=7时，H(7)=(7x3)%7=21%7=0其他关键字同理。KeyH(Key)0365560(表1)采用线性探测再散列法处理冲突，所构造的散列表为：地址0123456789关键字(表2)下面对散列表的构造方式加以说明，注意表1中的关键字7和14,30和9,11和18,这三组关键子的H(Key)值相同，这在构建散列表时就会产生冲突，因为他们的地址相同，所以要通过一定的冲突处理方法来解决这个问题。依题，采

　　6、用线性探测再散列法处理冲突。下面详细介绍如何构建散列表：第一个key7,它的地址是0,因此放到散列表的数组下表为0的位置，这个位置上没有关键字，因此没有冲突可以直接填入；第二个key8,它的地址是3,因此放到散列表的数组下表为3的位置，这个位置上没有关键字，因此没有冲突可以直接填入；第三个key30,它的地址是6,因此放到散列表的数组下表为6的位置,这个位置上没有关键字，因此没有冲突可以直接填入；第四个key11,它的地址是5,因此放到散列表的数组下表为5的位置,这个位置上没有关键字，因此没有冲突可以直接填入；第五个key18,它的地址是5,因此放到散列表的数组下表为5的位置,但这个位置上已经

　　7、有关键字11,遇到了冲突，此时我们根据线性探测再散列法来处理这个冲突，探测下一个位置6,6这个位置上已经存在关键字30则继续增加步长1,因此现在的新地址应为7,位置7上没有关键字，放入即可，到此冲突已经解决；第六个key9,它的地址是6,因此放到散列表的数组下表为6的位置，但这个位置上已经有关键字30,遇到了冲突，探测下一个位置7,7这个位置上已经存在关键字18则继续增加步长1,因此现在的新地址应为8,位置8上没有关键字，放入即可；第七个key14,它的地址是0,因此放到散列表的数组下表为0的位置,但这个位置上已经有关键字7,遇到了冲突，探测下一个位置1,位置1上没有关键字，放入即可；到这一步

　　8、所有关键字均已填入，散列表已经构造完成，如表2所示。（2）等概率情况下查找成功平均查找长度：这一问可以根据第一问的构造过程求解：key7一次就填入了表中，因此查找次数为1,同理8,30,11查找次数均为1;key18进行了3次放入操作，探测位置分别是5,6,7,因此查找次数为3;key9也是3次；key14进行了两次探测，因此查找次数为2。次数表如表3所小KeyCount1111332（表3）所以ASLsuccess=（1+1+1+1+3+3+2/7=12/7。等概率情况下查找不成功的平均查找长度：接下来讨论不成功的情况，看表2,计算查找不成功的次数就直接找关键字到第一个

　　9、地址上关键字为空的距离即可，但根据哈希函数地址为MOD7因此初始只可能在06的位置。等概率情况下，查找06位置查找失败的查找次数为：看地址0,到第一个关键字为空的地址2的距离为3,因此查找不成功的次数为3.地址1,到第一个关键为空的地址2的距离为2,因此查找不成功的次数为2.地址2,到第一个关键为空的地址2的距离为1,因此查找不成功的次数为1.地址3,到第一个关键为空的地址4的距离为2,因此查找不成功的次数为2.地址4,到第一个关键为空的地址4的距离为1,因此查找不成功的次数为1.地址5,到第一个关键为空的地址2（注意不是地址9,因为初始只可能在06之间，因此循环回去）的距离为5,因此查找不成

　　12、时：ASL=(1X4+2X3+3X1)/8=13/8其中红色标记为查找次数。也就是说，需查找1次找到的有4个，其它以此类推查找不成功时：ASL=(3+4+2+1+1+3+1+1+1+1+1)/11=19/11以第一个3为例，其对应于0地址位，确定查找不成功需比较3次，其它以此类推.链式处理冲突怎么求不成功的平均查找长度1 346723 584 2648815 9367 6889 75这个貌似不同的教材有不同的计算结果，不过运算方法是相同的。第一列的数据时需要比较一次的，包括34、58、26等以及2、6、8这三个位置。其中除了这三个位置外是查找成功比较一次，而这三个位置是查账不成功的。另外，3、

　　13、5、7、9这几个位置是需要比较两次才知道查找不成功的；同理，1位置查找不成功比较3次，4位置比较4次。所以有ASL=(1X3+2X4+3X1+4X1)/9=18/9下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。Question1:将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key)=(keyx3)MOD7处理冲突采用线性探测再散列法，要求装填(载)因子为0.7。(1)请画出所构造的散列表。(2)分别计算等概率情况下查找成功和查找不

　　14、成功的平均查找长度。Ans：(1),首先明确一个概念装载因子，装载因子是指所有关键子填充哈希表后饱和的程度，它等于关键字总数/哈希表的长度。根据题意，我们可以确定哈希表的长度为L=7/0,7=10;因此此题需要构建的哈希表是下标为09的一维数组。根据散列函数可以得到如下散列函数值表。H(Key)=(keyx3)MOD7,例如key=7时，H(7)=(7x3)%7=21%7=0,其他关键字同理。KeyH（Key）0365560（表1）采用线性探测再散列法处理冲突，所构造的散列表为:地址0123456789关键字（表2）下面对散列表的构造方式加以说明，注

　　15、意表1中的关键字7和14,30和9,11和18,这三组关键子的H(Key)值相同，这在构建散列表时就会产生冲突，因为他们的地址相同，所以要通过一定的冲突处理方法来解决这个问题。依题，采用线性探测再散列法处理冲突。下面详细介绍如何构建散列表：第一个key7,它的地址是0,因此放到散列表的数组下表为没有关键字，因此没有冲突可以直接填入；0的位置，这个位置第二个key8,它的地址是3,因此放到散列表的数组下表为没有关键字，因此没有冲突可以直接填入；3的位置，这个位置上第三个key30,它的地址是6,因此放到散列表的数组下表为上没有关键字，因此没有冲突可以直接填入；6的位置，这个位置第四个key11,

　　16、它的地址是5,因此放到散列表的数组下表为上没有关键字，因此没有冲突可以直接填入；5的位置，这个位置第五个key18,它的地址是5,因此放到散列表的数组下表为5的位置，但这个位置上已经有关键字11,遇到了冲突，此时我们根据线性探测再散列法来处理这个冲突，探测下一个位置6,6这个位置上已经存在关键字30则继续增加步长1,因此现在的新地址应为7,位置7上没有关键字，放入即可，到此冲突已经解决；第六个key9,它的地址是6,因此放到散列表的数组下表为6的位置，但这个位置上已经有关键字30,遇到了冲突，探测下一个位置7,7这个位置上已经存在关键字18则继续增加步长1,因此现在的新地址应为8,位置8上没有

　　17、关键字，放入即可；第七个key14,它的地址是0,因此放到散列表的数组下表为0的位置，但这个位置上已经有关键字7,遇到了冲突，探测下一个位置1,位置1上没有关键字，放入即可；到这一步所有关键字均已填入，散列表已经构造完成，如表2所示。(2)等概率情况下查找成功平均查找长度：这一问可以根据第一问的构造过程求解：key7一次就填入了表中，因此查找次数为1,同理8,30,11查找次数均为1;key18进行了3次放入操作，探测位置分别是5,6,7,因此查找次数为3;key9也是3次；key14进行了两次探测，因此查找次数为2。次数表如表3所示KeyCount1111332(表3)

　　18、所以ASLsuccess=(1+1+1+1+3+3+2)/7=12/7。等概率情况下查找不成功的平均查找长度：接下来讨论不成功的情况，看表2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可，但根据哈希函数地址为MOD7因此初始只可能在06的位置。等概率情况下，查找06位置查找失败的查找次数为：看地址0,到第一个关键字为空的地址2的距离为3,因此查找不成功的次数为3.地址1,到第一个关键为空的地址2的距离为2,因此查找不成功的次数为2.地址2,到第一个关键为空的地址2的距离为1,因此查找不成功的次数为1.地址3,到第一个关键为空的地址4的距离为2,因此查找不成功的次数为2.地址4,到第一个关键为空的地址4的距离为1,因此查找不成功的次数为1.地址5,到第一个关键为空的地址2（注意不是地址9,因为初始只可能在06之间,因此循环回去）的距离为5,因此查找不成功的次数为5.地址6,到第一个关键为空的地址2（注意不是地址9,因为初始只可能在06之间,因此循环回去）的距离为4,因此查找不成功的次数为4.因此查找不成功的次数表如下表所示KeyCount3212154（表4）所以ASLunsuccess=（3+2+1+2+1+5+4）/7=18/7。