数据结构-资源试题库及解析《数据结构》期末考试试卷D卷-简答题6-配套说课稿.docx

大数据技术与应用专业教学资源库 《数据结构》课程说课稿 《数据结构》期末考试试卷D卷-简答题6 主讲： 章万静  序号 PPT 说课稿 幻灯片 1 大家好。我是《数据结构》课程的主讲教师——章老师。 下面我们开始重点分析试卷D中的题目。 幻灯片 2 我们来看一下简答题。 幻灯片 3 简答题的第6题。 选取除留余数法设计散列函数H(K)= K%11，关键字集合为{10，20，15，17，21，6，8，25，40，35}，采用拉链法处理冲突，请画出拉链法示意图。 这道题5分。 我们知道，散列表也叫哈希表，它是将关键字数据存放在通过散列函数转换的地址空间里，这里使用的散列函数为H(K)= K%11，余数相同的关键字会产生冲突，产生冲突时可以采用线性探查法或者拉链法进行处理。本题要求采用拉链法解决冲突，拉链法就是先将地址相同的关键字链接形成一个单链表，然后再将单链表的首地址存储在散列表相应的存储单元中。 幻灯片 4 下面，我们来分析这些关键字如何采用拉链法存储在散列表或哈希表中？ 关键字集合为{10，20，15，17，21，6，8，25，40，35}，选取的散列函数H(K)= K%11。 第一个关键字10，对11求余数，余数为10，所以在数组下标为10的空间里指向一个新的链表结点，结点的数据域中存储关键字10。 第二个关键字20，对11求余数，余数为9，所以在数组下标为9的空间里指向一个新的链表结点，结点的数据域中存储关键字20。 第三个关键字15，对11求余数，余数为4，所以在数组下标为4的空间里指向一个新的链表结点，结点的数据域中存储关键字15。 第四个关键字17，对11求余数，余数为6，所以在数组下标为6的空间里指向一个新的链表结点，结点的数据域中存储关键字17。 第五个关键字21，对11求余数，余数为10，关键字21和10产生冲突， 所以在关键字10这个链结点后面指针域里指向一个新的链表结点，结点的数据域中存储关键字21。 第六个关键字6，对11求余数，余数为6，关键字6和17产生冲突， 所以在关键字17这个链结点后面指针域里指向一个新的链表结点，结点的数据域中存储关键字6。 第七个关键字8，对11求余数，余数为8，所以在数组下标为8的空间里指向一个新的链表结点，结点的数据域中存储关键字8。 第八个关键字25，对11求余数，余数为3，所以在数组下标为3的空间里指向一个新的链表结点，结点的数据域中存储关键字25。 第九个关键字40，对11求余数，余数为7，所以在数组下标为7的空间里指向一个新的链表结点，结点的数据域中存储关键字40。 第十个关键字35，对11求余数，余数为2，所以在数组下标为2的空间里指向一个新的链表结点，结点的数据域中存储关键字35。 最后，在每个单链表最后一个结点的指针域中分别填上一个空指针，表示后面没有其他结点。这样这10个关键字采用拉链法解决冲突并且存储完毕。 幻灯片 5 本次微课就介绍到这里，希望大家好好理解与掌握。谢谢观看。