Вопросы для обсуждения

  1. Используя формулы для производительности хэш-таблиц, данные в этой главе, посчитайте среднее количество сравнений, необходимых при заполненности таблицы на

Как вы думаете, в какой момент хэш-таблица становится чересчур мала?

  1. Измените хэш-функцию для строк таким образом, чтобы использовались веса позиций.
  2. Для строк мы использовали хэш-функцию, которая взвешивает символ с учётом его позиции. Придумайте альтернативную схему весов. Какие у неё существуют недостатки?
  3. Исследуйте идеальные хэш-функции. Используя список имён (одноклассников, членов семьи и т.п.), сгенерируйте хэш-значения с помощью алгоритма идеальной хэш-функции.
  4. Сгенерируйте список случайных чисел. Покажите, как его можно отсортировать с помощью алгоритмов
  1. Рассмотрите следующий список чисел: [1,2,3,4,5,6,7,8,9,10]. Покажите, как он будет сортироваться с помощью алгоритмов
  1. Рассмотрите следующий список чисел: [10,9,8,7,6,5,4,3,2,1]. Покажите, как он будет сортироваться с помощью алгоритмов
  1. Рассмотрите список символов: [‘P’,’Y’,’T’,’H’,’O’,’N’]. Покажите, как он будет сортироваться с помощью алгоритмов
  1. Придумайте альтернативную стратегию выбора опорного элемента в быстрой сортировке. Например, используйте значение из середины списка. Переделайте алгоритм и примените его к набору случайных данных. По каким критериям ваша новая стратегия превосходит или уступает стратегиям из этой главы?
Next Section - Упражнения для программирования