散列习题课公开课一等奖课件省赛课获奖课件

散列习题课第1页一、判断正误（）1.p是不大于或等于TableSize最大素数。（）2.取11位手机号码key后4位作为地址

散列函数为：h(key)=atoi(key+9)。（）3.选择合适h(key)，散列法查找效率盼望是常数O(1)，它几乎与关键字空间大小n无关！（）4.散列办法是一种以空间换时间。（）5.太小α也许造成空间挥霍，太大α又将付出更多时间代价。

第2页二、填空1.常用处理冲突办法有两种：开放地址法和链地址法。2.发生了第i次冲突，试探下一种地址将增加di，基本公式是：hi(key)=(h(key)+di)modTableSize,其中di取决于不一样处理冲突方案：线性探测时di＝i、平方探测时di＝±i2、双散列时di＝i*h2(key)。3.在开放地址散列表中，删除操作一般只能“懒惰删除”，即需要增加一种“删除标识(Deleted)”，而并不是真正删除它。4.当装填因子过大时，处理办法是加倍扩大散列表，这样α能够减小二分之一，这个过程叫做“再散列”。5.也许将不一样关键字映射到同一种散列地址上，即h(keyi)=h(keyj)（当keyi≠keyj），这种现象称为“冲突”，keyi和keyj称为“同义词”。第3页三、选择题1.散列法存放基本思想是根据A来决定B，碰撞（冲突）指是C，处理碰撞两类主要办法是D。供选择答案A，B：①存放地址②元素符号③元素个数 ④关键码值 ⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间C:①两个元素具有相同序号②两个元素关键码值不一样，而非码属性相同③不一样关键码值对应到相同存放地址④负载因子过大⑤数据元素过多D：①线性探查法和双散列函数法②建溢出区法和不建溢出区法 ③除余法和折叠法 ④拉链法和开地址法答案：A＝

B＝

C＝

D＝１.④

①

③

④

第4页四、简答题1.简述为手机号码建立一种散列表办法。2.简述影响产生冲突三个原因。第5页五、分析题1.设哈希（Hash）表地址范围为0～17，哈希函数为：H（K）＝KMOD16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题：画出哈希表示意图；若查找关键字63，需要依次与哪些关键字进行比较？若查找关键字60，需要依次与哪些关键字比较？假定每个关键字查找概率相等，求查找成功时平均查找长度。第6页（1）画表如下：（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但由于12号单元为空（应当有空标识），因此应当只比较这一次即可。（4）对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，ASL=1/11（6＋2＋3×3）＝17/11≈1.55第7页2.选用散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一种散列地址空间为0～10，表长为11散列表，{22，41，53，08，46，30，01，31，66}。则(22*3)%11=6……0(41*3)%11=11……2(53*3)%11=14……5(08*3)%11=2……2(46*3)%11=12……6(30*3)%11=8……2(01*3)%11=0……3(31*3)%11=8……5(66*3)%11=9……0第8页3.已知散列函数为H(K)=Kmod12,健值序列为25，37，52，43，84，99，120，15，26，11，70，82，采取分离链接法处理冲突，试构造散列表，并计算查找成功平均查找长度。查找成功平均查找长度为：（4*2+8）/12=4/3

第9页5.3设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74}，散列函数为H(key)=key%17,采取线性探测法处理冲突。试在0~18散列地址空间中对该关键字序列构造散列表，并计算成功查找平均查找长度。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。试在0~12散列地址空间中对该关键字序列构造散列表。第10页5.6已知线性表关键字集合{21,11,13,25,48,6,39,83,30,96,108}，散列函数为H(key)=K%11采取分离链接法处理冲突，试构造散列表，并计算查找成功平均查找长度。5.7将关键字序列{7,8,30,11,18,9,14}散列存放到散列表中散列表存放空间是一种下标从0开始一种一维数组散列函数维：H（key）=（key×3）%p，处理冲突采取线性探测再散列法，要求装填因子为0.7。（1）请画出所构造散列表；（2）分别计算等概率情况下，查找成功和查找不成功平均查找长度。第11页解：表长为10,p为7。H（key）=（key×3）%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。

第12页１.已知某哈希表装载因子不大于1，哈希函数H(key)为关键字（标识符）第一种字母在字母表中序号，处理冲突办法为线性探测开放定址法。试编写一种按第一种字母次序输出哈希表中所有关键字算法。解：注意此题给出条件：装载因子a〈1,则哈希表未填满。由此可写出下列形式简要算法：voidPrintWord(HashTableht){//按第一种字母次序输出哈希表ht中标识符。哈希函数为表达符第一种字母在字母表中序号，处理冲突办法是