chapter09
复制本地路径 | 在线编辑
1. SkipList
1.1 证明: 跳表的空间复杂度为O(n)
1.2 证明: 跳表的高度复杂度为O(logn)
1.3 证明: 跳表的查找复杂度为O(logn)
1.4 证明: 跳表的插入复杂度为O(logn)
2. HashTable--Hash Function
2.1 为什么M不推荐取为2的次方
2.2 为什么M不推荐取为合数
(Hint: 插入间隔为T的M个关键码，求每个关键码和gcd(T,M)个关键码冲突)
3. HashTable--Collision_1
3.1 简化平方试探法的复杂度(Hint: Multiply->Addition)
3.2 如果M为素数，证明装填因子不超过0.5时，插入操作必然成功
3.3 如果M为素数，证明装填因子超过0.5时，插入操作必然会失败
3.4 如果M为合数，举例证明装填因子不超过0.5时，仍有可能失败
3.5 双向平方试探法，证明若M=4k+3时，插入操作保证成功
4. HashTable--Collision_2
4.1 说明公共溢出区法的应用场景
4.2 举例说明闭散列的插入删除操作
4.3 给出闭散列中插入删除操作的源码
5. 桶排序扩展
5.1 给定[0,n^d)范围内的n个整数，利用基数排序进行O(n)排序
5.2 给定[0,M)范围内的n个整数，进行计数排序,要求空间O(M),时间O(n),保持稳定性
5.3 给定n个不同的点，可知有n-1个间隙，求出其中的最大间隙