Практикум по теме

Составить и отладить программу для вычисления пятого множества по четырём заданным, представленным в форме хеш-таблиц. Элементы множеств — целые числа из интервала [0, MAXINT]. Формула для вычислений и средняя мощность множеств выбираются из следующей ниже таблицы в соответствии с номером индивидуального варианта. Подходящий размер хеш-таблиц определить по мощности обрабатываемых множеств.

Хеш-таблицу закодировать как класс, а операции с ней — как функции-члены этого класса. В качестве образца можно использовать программу для работы с множествами-объектами, составленную в предыдущем семестре.

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

1.2. Требования к отчёту

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

Контрольные вопросы

1. Какой объём памяти нужно выделять под хеш-таблицу для хранения множеств мощностью 50?

2. Хеш-таблица какого типа расходует больше памяти для хранения множества — с открытой адресацией или с цепочками переполнения?

3. Каким требованиям должна удовлетворять «хорошая» хеш-функция?

4. Можно ли построить хеш-таблицу, в которой не будет коллизий?

5. Каков оптимальный алгоритм выполнения двуместной операции над множествами в хеш-таблице? Какова его временная сложность?

6. Можно ли хранить в хеш-таблице множество с повторениями?

7. Какова временная сложность операций вставки и удаления элемента для хеш-таблицы?

8. Почему для операций с хеш-таблицей дают две оценки временной сложности — сложность в худшем случае и сложность в среднем?

9. Что такое вырождение хеш-таблицы и как его избежать?

10. Что нужно делать, если хеш-таблица переполнилась?

1.4. Варианты индивидуальных заданий
к темам «Хеш-таблицы» и «Деревья двоичного поиска»