将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为11的散列表中。散列函数为：h(key)=key%11，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？

将元素序列插入散列表的过程如下：

1. 18 % 11 = 7，散列表第7个位置为空，将18插入该位置。
2. 23 % 11 = 1，散列表第1个位置为空，将23插入该位置。
3. 11 % 11 = ，散列表第个位置为空，将11插入该位置。
4. 20 % 11 = 9，散列表第9个位置为空，将20插入该位置。
5. 2 % 11 = 2，散列表第2个位置为空，将2插入该位置。
6. 7 % 11 = 7，散列表第7个位置已被占用，采用线性探测法，从第8个位置开始查找，直到找到一个空位置，将7插入该位置。
7. 27 % 11 = 5，散列表第5个位置为空，将27插入该位置。
8. 33 % 11 = ，散列表第个位置已被占用，采用线性探测法，从第1个位置开始查找，直到找到一个空位置，将33插入该位置。
9. 42 % 11 = 10，散列表第10个位置为空，将42插入该位置。
10. 15 % 11 = 4，散列表第4个位置为空，将15插入该位置。

此时散列表已经被填满，装填因子为10/11≈.91，即装填因子大约为.91。

相关问题

将元素序列{18, 23, 4, 26, 31, 33, 17, 39}按顺序插入一个初始为空的、大小为13的散列表中。散列函数为：h(key)=key%13，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？

将元素序列插入散列表的过程如下：

1. 18 % 13 = 5，将18插入散列表的第5个位置。
2. 23 % 13 = 10，将23插入散列表的第10个位置。
3. 4 % 13 = 4，将4插入散列表的第4个位置。
4. 26 % 13 = ，将26插入散列表的第个位置。
5. 31 % 13 = 8，将31插入散列表的第8个位置。
6. 33 % 13 = 7，将33插入散列表的第7个位置。
7. 17 % 13 = 4，发现冲突，采用线性探测法，将17插入散列表的第5个位置。
8. 39 % 13 = ，发现冲突，采用线性探测法，将39插入散列表的第1个位置。

最终散列表的状态为：[26, 39, 4, 18, 17, 23, 33, 31, None, None, 10, None, None]

其中，装填因子为已插入元素个数/散列表大小，即8/13，约为.62。

对初始状态为递增序列的表按递增顺序排序，为什么快速排序最费时间

对初始状态为递增序列的表按递增顺序排序，快速排序的时间复杂度最费时间的原因如下：

快速排序的基本思想是通过选择一个基准元素，将待排序序列分成两部分，一部分小于基准元素，一部分大于基准元素，然后对这两部分分别进行递归排序。在最坏情况下，即每次选择的基准元素都是序列中的最大或最小元素时，快速排序的时间复杂度会达到O(n^2)。

在初始状态为递增序列的表中，如果每次选择的基准元素都是序列中的最大元素，那么每次分割操作都只能将一个元素放在正确的位置上，而其他位置上的元素会在后续的递归中再次进行比较和移动。这样就会导致每次分割操作只能减少序列长度1，需要进行n-1次分割操作才能完成排序。因此，在最坏情况下，快速排序的时间复杂度为O(n^2)。

相比之下，堆排序、直接插入排序和归并排序在初始状态为递增序列的表中都能够有较好的性能。堆排序的时间复杂度也为O(nlogn)，但它不受输入数据的初始状态影响；直接插入排序的时间复杂度为O(n^2)，但在初始状态为递增序列时，它的时间复杂度可以优化到O(n)；归并排序的时间复杂度为O(nlogn)，但它不会受到初始状态的影响。

因此，快速排序在初始状态为递增序列的表中最费时间，因为它需要进行大量的比较和移动操作来将元素放在正确的位置上。