5.15. 练习¶

5.15. Exercises

中文

翻译¶

1. 使用章节中给出的哈希表性能公式，计算当哈希表的装载因子分别为：

    - 10% 时
    - 25% 时
    - 50% 时
    - 75% 时
    - 90% 时
    - 99% 时

    需要的平均比较次数是多少？你认为哈希表何时太小？请解释。

2. 修改字符串的哈希函数以使用位置加权。

3. 我们使用了对字符按位置加权的哈希函数。设计一个替代的加权方案。这些函数存在哪些偏差？

4. 研究完美哈希函数。使用一个名字列表（同学、家人等），使用完美哈希算法生成哈希值。

5. 生成一个随机整数列表。展示该列表如何通过以下算法进行排序：

    - 冒泡排序
    - 选择排序
    - 插入排序
    - 希尔排序（你决定增量）
    - 归并排序
    - 快速排序（你决定基准值）

6. 考虑以下整数列表：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]。展示该列表如何通过以下算法进行排序：

    - 冒泡排序
    - 选择排序
    - 插入排序
    - 希尔排序（你决定增量）
    - 归并排序
    - 快速排序（你决定基准值）

7. 考虑以下整数列表：[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]。展示该列表如何通过以下算法进行排序：

    - 冒泡排序
    - 选择排序
    - 插入排序
    - 希尔排序（你决定增量）
    - 归并排序
    - 快速排序（你决定基准值）

8. 考虑字符列表：[``"P", "Y", "T", "H", "O", "N"``]。展示该列表如何通过以下算法进行排序：

    - 冒泡排序
    - 选择排序
    - 插入排序
    - 希尔排序（你决定增量）
    - 归并排序
    - 快速排序（你决定基准值）

9. 为快速排序设计替代策略来选择基准值。例如，选择中间项。重新实现该算法，然后在随机数据集上执行它。根据什么标准，你的新策略比章节中的策略表现得更好或更差？

10. 设置一个随机实验来测试顺序搜索和二分搜索在整数列表上的差异。

11. 使用文本中给出的二分搜索函数（递归和迭代）。生成一个随机有序整数列表，并对每个函数进行基准测试。你的结果是什么？你能解释一下吗？

12. 使用递归实现二分搜索，不使用切片操作符。记住你需要传递列表以及子列表的起始和结束索引值。生成一个随机有序整数列表并进行基准测试。

13. 为哈希表 Map ADT 实现实现 ``len`` 方法（``__len__``）。

14. 为哈希表 Map ADT 实现实现 ``in`` 方法（``__contains__``）。

15. 如何从使用链表解决冲突的哈希表中删除项目？如果使用开放地址法呢？需要处理哪些特殊情况？为 ``HashTable`` 类实现 ``del`` 方法。

16. 在哈希表映射实现中，哈希表的大小选择为 101。如果表变满了，需要增加大小。重新实现 ``put`` 方法，使得当装载因子达到预定值时，表会自动调整大小（你可以根据对负载与性能的评估决定该值）。

17. 实现二次探测作为重哈希技术。

18. 使用随机数生成器，创建一个包含 500 个整数的列表。使用本章中的一些排序算法进行基准测试。执行速度的差异是什么？

19. 冒泡排序可以修改为双向“冒泡”。第一次遍历向“上”移动，第二次遍历向“下”移动。这种交替模式继续，直到不再需要遍历。实现这种变体并描述在什么情况下它可能是合适的。

20. 对同一列表进行希尔排序的基准测试，使用不同的增量集合。

21. 实现不使用切片操作符的 ``merge_sort`` 函数。

22. 一种改进快速排序的方法是在长度较短的列表上使用插入排序（称为“分区限制”）。为什么这样做是合理的？重新实现快速排序，并使用不同的列表大小进行分析，以确定分区限制。

23. 实现三数中值法选择基准值作为对 ``quick_sort`` 的修改。运行实验以比较这两种技术。

英文

Using the hash table performance formulas given in the chapter, compute the average number of comparisons necessary when the table is
- 10% full
- 25% full
- 50% full
- 75% full
- 90% full
- 99% full
At what point do you think the hash table is too small? Explain.
Modify the hash function for strings to use positional weightings.
We used a hash function for strings that weighted the characters by position. Devise an alternative weighting scheme. What are the biases that exist with these functions?
Research perfect hash functions. Using a list of names (classmates, family members, etc.), generate the hash values using the perfect hash algorithm.
Generate a random list of integers. Show how this list is sorted by the following algorithms:
- bubble sort
- selection sort
- insertion sort
- Shell sort (you decide on the increments)
- merge sort
- quicksort (you decide on the pivot value)
Consider the following list of integers: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Show how this list is sorted by the following algorithms:
- bubble sort
- selection sort
- insertion sort
- Shell sort (you decide on the increments)
- merge sort
- quicksort (you decide on the pivot value)
Consider the following list of integers: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Show how this list is sorted by the following algorithms:
- bubble sort
- selection sort
- insertion sort
- Shell sort (you decide on the increments)
- merge sort
- quicksort (you decide on the pivot value)
Consider the list of characters: ["P", "Y", "T", "H", "O", "N"]. Show how this list is sorted using the following algorithms:
- bubble sort
- selection sort
- insertion sort
- Shell sort (you decide on the increments)
- merge sort
- quicksort (you decide on the pivot value)
Devise alternative strategies for choosing the pivot value in a quicksort. For example, pick the middle item. Reimplement the algorithm and then execute it on random data sets. Under what criteria does your new strategy perform better or worse than the strategy from this chapter?
Set up a random experiment to test the difference between a sequential search and a binary search on a list of integers.
Use the binary search functions given in the text (recursive and iterative). Generate a random, ordered list of integers and do a benchmark analysis for each one. What are your results? Can you explain them?
Implement the binary search using recursion without the slice operator. Recall that you will need to pass the list along with the starting and ending index values for the sublist. Generate a random, ordered list of integers and do a benchmark analysis.
Implement the len method (__len__) for the hash table Map ADT implementation.
Implement the in method (__contains__) for the hash table Map ADT implementation.
How can you delete items from a hash table that uses chaining for collision resolution? How about if open addressing is used? What are the special circumstances that must be handled? Implement the del method for the HashTable class.
In the hash table map implementation, the hash table size was chosen to be 101. If the table gets full, this needs to be increased. Re-implement the put method so that the table will automatically resize itself when the loading factor reaches a predetermined value (you can decide the value based on your assessment of load versus performance).
Implement quadratic probing as a rehash technique.
Using a random number generator, create a list of 500 integers. Perform a benchmark analysis using some of the sorting algorithms from this chapter. What is the difference in execution speed?
A bubble sort can be modified to “bubble” in both directions. The first pass moves “up” the list, and the second pass moves “down.” This alternating pattern continues until no more passes are necessary. Implement this variation and describe under what circumstances it might be appropriate.
Perform a benchmark analysis for a shell sort, using different increment sets on the same list.
Implement the merge_sort function without using the slice operator.
One way to improve the quicksort is to use an insertion sort on lists that have a short length (call it the “partition limit”). Why does this make sense? Reimplement the quicksort and use it to sort a random list of integers. Perform an analysis using different list sizes for the partition limit.
Implement the median of three method for selecting a pivot value as a modification to quick_sort. Run an experiment to compare the two techniques.

最后更新: 2024年9月13日
创建日期: 2024年9月9日