散列习题课ppt课件.ppt

1、散列习题课,一、判断正误,（ ）1. p 是小于或等于 TableSize的最大素数 。 （ ）2.取11位手机号码key的后4位作为地址的 散列函数为：h(key) = atoi(key+9) 。 （ ）3.选择合适的 h(key) ，散列法的查找效率期望是常数O(1)，它几乎与关键字的空间的大小n无关！ （ ）4.散列方法是一个以空间换时间。 （ ）5.太小的可能导致空间浪费，太大的又将付出更多的时间代价。,二、填空,1 .常用的处理冲突的方法有两种：开放地址法和链地址法。 2 . 发生了第 i 次冲突，试探的下一个地址将增加di，基本公式是：hi(key) = (h(key)+di) m

2、od TableSize ,其中di 取决于不同的解决冲突方案：线性探测时di i 、平方探测时di i2 、双散列时di i*h2(key)。 3 .在开放地址散列表中，删除操作通常只能“懒惰删除”，即需要增加一个 “删除标记(Deleted)”，而并不是真正删除它。 4.当装填因子过大时，解决的方法是加倍扩大散列表，这样可以减小一半，这个过程叫做“再散列”。 5.可能将不同的关键字映射到同一个散列地址上，即h(keyi) = h(keyj)（当keyi keyj），这种现象称为“冲突”， keyi 和keyj称为“同义词”。,三、选择题,1.散列法存储的基本思想是根据 A 来决定 B ，碰

3、撞（冲突）指的是 C ，处理碰撞的两类主要方法是 D 。 供选择的答案 A，B： 存储地址 元素的符号 元素个数 关键码值 非码属性 平均检索长度 负载因子 散列表空间 C: 两个元素具有相同序号 两个元素的关键码值不同，而非码属性相同 不同关键码值对应到相同的存储地址 负载因子过大 数据元素过多 D： 线性探查法和双散列函数法 建溢出区法和不建溢出区法 除余法和折叠法 拉链法和开地址法 答案：A B C D . ,四、简答题,1.简述为手机号码建立一个散列表的方法。 2.简述影响产生冲突的三个因素。,五、分析题,1. 设哈希（Hash）表的地址范围为017，哈希函数为：H（K）K MOD 1

4、6。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： 画出哈希表的示意图； 若查找关键字63，需要依次与哪些关键字进行比较？ 若查找关键字60，需要依次与哪些关键字比较？ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。,（1）画表如下： （2） 查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！ （3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因

5、为12号单元为空（应当有空标记），所以应当只比较这一次即可。 （4） 对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， ASL=1/11（6233）17/111.55,2. 选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为010，表长为11的散列表，22，41，53，08，46，30，01，31，66。,则(22*3)%11=60 (41*3)%11=112 (53*3)%11=145 (08*3)%11=22 (

6、46*3)%11=126 (30*3)%11=82 (01*3)%11=03 (31*3)%11=85 (66*3)%11=90,3.已知散列函数为H(K)=K mod 12,健值序列为25，37，52，43，84，99，120，15，26，11，70，82，采用分离链接法处理冲突，试构造散列表，并计算查找成功的平均查找长度。 查找成功的平均查找长度为：（4*2+8）/ 12 = 4/3,5.3设有一组关键字29,01,13,15,56,20,87,27,69,9,10,74，散列函数为H(key)=key%17,采用线性探测法解决冲突。试在018的散列地址空间中对该关键字序列构造散列表，并计

7、算成功查找的平均查找长度。 5.4题目同上，采用平方探测法解决冲突。 5.5设有一组关键字92,81,58,21,57,45,161,38,117，散列函数为H(key)=key%13,采用双散列探测法解决第i次冲突：H(key)=(H(key)+i* H2(key)%13,其中， H2(key)=(key%11)+1 。试在012的散列地址空间中对该关键字序列构造散列表。,5.6已知线性表关键字集合21,11,13,25,48,6,39,83,30,96,108，散列函数为H(key)=K % 11采用分离链接法处理冲突，试构造散列表，并计算查找成功的平均查找长度。 5.7将关键字序列7,8

8、,30,11,18,9,14散列存储到散列表中散列表的存储空间是一个下标从0开始的一个一维数组散列函数维：H（key）=（key3）% p，处理冲突采用线性探测再散列法，要求装填因子为0.7。 （1）请画出所构造的散列表；（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。,解：表长为10,p为7。 H（key）=（key3）% 7 （1） (2) 查找成功： ASL = (1+2+1+1+1+3+3) / 7 = 12 / 7 所以ASLu= （3+2+1+2+1+8+7+6+5+4）/ 10 = 39/10。,.已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。 解：注意此题给出的条件：装载因子a1, 则哈希表未填满。由此可写出下列形式简明的算法： void PrintWord(Hash Table ht) /按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法。 for(i=1; i=26;