早教吧作业答案频道 -->数学-->
请问一道,计算机中:数据结构与算法的问题,2、在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表:{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}(1)\x05用线性探测开放地址法处理冲
题目详情
请问一道,计算机中:数据结构与算法的问题,
2、在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表:
{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}
(1)\x05用线性探测开放地址法处理冲突;
(2)\x05用链地址法(开散列存储)处理冲突
并分别求这两个哈希表在等概率情况下查找成功的平均查找长度.设哈希函数为
H(key) = i/2,其中i为关键字中第一个字母在字母表中的序号,如下:
A B C D E F G H I J K L M N O P Q R S R U V W X Y Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
2、在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表:
{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}
(1)\x05用线性探测开放地址法处理冲突;
(2)\x05用链地址法(开散列存储)处理冲突
并分别求这两个哈希表在等概率情况下查找成功的平均查找长度.设哈希函数为
H(key) = i/2,其中i为关键字中第一个字母在字母表中的序号,如下:
A B C D E F G H I J K L M N O P Q R S R U V W X Y Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
▼优质解答
答案和解析
(1) 用线性探测开放地址法处理冲突;
H(Jan)=10/2=5;
H(Feb)=6/2=3;
H(Mar)=13/2=6;
H(Apr)=1/2=0;
H(May)=13/2=6;冲突;H1=6+1=7;
H(June)=10/2=5;冲突;H1=5+1=6;冲突;H2=7;H3=8;
H(July)=5;H1=6;H2=7;H3=8;H4=9
H(Aug)=0;H1=1;
H(Sep)=9;H1=10;
H(Oct)=7;H1=8;H2=9;H3=10;H4=11;
H(Nov)=7;H1=8;H2=9;H3=10;H4=11;H5=12
H(Dec)=2
ASL=(1+2+1+1+1+1+2+4+5+2+5+6)/12=31/12
(2) 用链地址法处理冲突
H(Jan)=5;
H(Feb)=3;
H(Mar)=6;
H(Apr)=0;
H(May)=6
H(June)=5;
H(July)=5;
H(Aug)=0;;
H(Sep)=9;
H(Oct)=7;
H(Nov)=7;
H(Dec)=2
0->Apr->Aug
1->
2->Dec
3->Feb
4->
5->Jan->June->July
6->Mar->May
7->Oct->Nov
8->
9->Sep
ASL=(1+2+1+1+1+2+3+1+2+1+2+1)/12=18/12
H(Jan)=10/2=5;
H(Feb)=6/2=3;
H(Mar)=13/2=6;
H(Apr)=1/2=0;
H(May)=13/2=6;冲突;H1=6+1=7;
H(June)=10/2=5;冲突;H1=5+1=6;冲突;H2=7;H3=8;
H(July)=5;H1=6;H2=7;H3=8;H4=9
H(Aug)=0;H1=1;
H(Sep)=9;H1=10;
H(Oct)=7;H1=8;H2=9;H3=10;H4=11;
H(Nov)=7;H1=8;H2=9;H3=10;H4=11;H5=12
H(Dec)=2
ASL=(1+2+1+1+1+1+2+4+5+2+5+6)/12=31/12
(2) 用链地址法处理冲突
H(Jan)=5;
H(Feb)=3;
H(Mar)=6;
H(Apr)=0;
H(May)=6
H(June)=5;
H(July)=5;
H(Aug)=0;;
H(Sep)=9;
H(Oct)=7;
H(Nov)=7;
H(Dec)=2
0->Apr->Aug
1->
2->Dec
3->Feb
4->
5->Jan->June->July
6->Mar->May
7->Oct->Nov
8->
9->Sep
ASL=(1+2+1+1+1+2+3+1+2+1+2+1)/12=18/12
看了 请问一道,计算机中:数据结构...的网友还看了以下:
伏安法 只给一个电压表,一个电池组,一个定值电阻R2(阻值已知),一个开关,导线若干,怎么测电阻R 2020-05-14 …
如图是用电磁继电器控制电灯的实验装置图,要想在控制电路的开关闭合时甲灯亮乙灯不亮,开关断开时乙灯亮 2020-05-14 …
断开总火线和总零线,关掉所有电器,拨掉所有插座上的电器,用万用表测火线和零线之间有电阻更奇怪的是, 2020-05-14 …
电表和线路的问题新装了三个电表.第一个是前2楼第二个是前3楼第四个是后2楼和后3楼.每个电表都有2 2020-06-10 …
高中物理一个160匝的小线圈,面积4cm2,电阻为50欧,把线圈与阻值为30欧的电流表连接起来,然 2020-07-18 …
已知直线l的函数表达式为y=-3/4+8,且l与x轴,y轴分别交于A,B两点,AB上有动点Q,AO 2020-07-20 …
(2006•贵港)如图,已知直线l的函数表达式为y=-x+8,且l与x轴,y轴分别交于A,B两点,动 2020-11-13 …
关于家庭线路墙壁开关和线路的问题,几个问题其实是一个问题,分不多了,有图片连接的,我家墙壁开关(外线 2020-12-03 …
用如图所示的电路来测量一个未知电阻Rx的值.电源电压保持不变,当把导线M的右端接到电流表“+”接线柱 2021-01-13 …
用如图所示的电路来测量一个未知电阻Rx的值.电源电压保持不变,当把导线M的右端接到电流表“+”接线柱 2021-01-13 …