Лабораторная работа должна выполняться в следующем порядке:
1. Получить вариант задания у преподавателя.
2. Выбрать и описать хэш-функцию.
3. Описать структуры данных, используемые для заданных методов организации таблиц идентификаторов.
4. Подготовить и защитить отчет.
5. Написать и отладить программу на ЭВМ.
6. Сдать работающую программу преподавателю.
Требования к оформлению отчета
Отчет по лабораторной работе должен содержать следующие разделы:
• задание по лабораторной работе;
• описание выбранной хэш-функции;
• схемы организации таблиц идентификаторов (в соответствии с вариантом задания);
• описание алгоритмов поиска в таблицах идентификаторов (в соответствии с вариантом задания);
• текст программы (оформляется после выполнения программы на ЭВМ);
• результаты обработки заданного набора идентификаторов (входного файла) с помощью методов организации таблиц идентификаторов, указанных в варианте задания;
• анализ эффективности используемых методов организации таблиц идентификаторов и выводы по проделанной работе.
Основные контрольные вопросы
• Что такое таблица символов и для чего она предназначена? Какая информация может храниться в таблице символов?
• Какие цели преследуются при организации таблицы символов?
• Какими характеристиками могут обладать лексические элементы исходной программы? Какие характеристики являются обязательными?
• Какие существуют способы организации таблиц символов?
• В чем заключается алгоритм логарифмического поиска? Какие преимущества он дает по сравнению с простым перебором и какие он имеет недостатки?
• Расскажите о древовидной организации таблиц идентификаторов. В чем ее преимущества и недостатки?
• Что такое хэш-функции и для чего они используются? В чем суть хэш-адресации?
• Что такое коллизия? Почему она происходит? Можно ли полностью избежать коллизий?
• Что такое рехэширование? Какие методы рехэширования существуют?
• Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью хэш-адресации и рехэширования.
• В чем заключается метод цепочек?
• Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью хэш-адресации и метода цепочек.
• Как могут быть скомбинированы различные методы организации хеш-таблиц?
• Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью комбинированных методов.
Варианты заданий
В табл.