![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Практикум по теме
Составить и отладить программу для вычисления пятого множества по четырём заданным, представленным в форме хеш-таблиц. Элементы множеств — целые числа из интервала [0, MAXINT]. Формула для вычислений и средняя мощность множеств выбираются из следующей ниже таблицы в соответствии с номером индивидуального варианта. Подходящий размер хеш-таблиц определить по мощности обрабатываемых множеств. Хеш-таблицу закодировать как класс, а операции с ней — как функции-члены этого класса. В качестве образца можно использовать программу для работы с множествами-объектами, составленную в предыдущем семестре. Программа должна генерировать исходные данные и выводить на экран структуру всех хеш-таблиц таким образом, чтобы было видно распределение элементов множества по ячейкам. 1.2. Требования к отчёту Отчёт по теме составляется по стандартной форме. В него следует поместить обоснование по выбору размера хеш-таблицы и коэффициентов хеш-функции, а также оценку временной сложности алгоритма обработки множеств — в худшем случае и в среднем. В выводах постарайтесь дать ответ на контрольные вопросы. Контрольные вопросы 1. Какой объём памяти нужно выделять под хеш-таблицу для хранения множеств мощностью 50? 2. Хеш-таблица какого типа расходует больше памяти для хранения множества — с открытой адресацией или с цепочками переполнения? 3. Каким требованиям должна удовлетворять «хорошая» хеш-функция? 4. Можно ли построить хеш-таблицу, в которой не будет коллизий? 5. Каков оптимальный алгоритм выполнения двуместной операции над множествами в хеш-таблице? Какова его временная сложность? 6. Можно ли хранить в хеш-таблице множество с повторениями? 7. Какова временная сложность операций вставки и удаления элемента для хеш-таблицы? 8. Почему для операций с хеш-таблицей дают две оценки временной сложности — сложность в худшем случае и сложность в среднем? 9. Что такое вырождение хеш-таблицы и как его избежать? 10. Что нужно делать, если хеш-таблица переполнилась? 1.4. Варианты индивидуальных заданий
|