Системное программное обеспечение. Лабораторный практикум. Алексей Молчанов. Читать онлайн. Newlib. NEWLIB.NET

Автор: Алексей Молчанов
Издательство: Питер
Серия:
Жанр произведения: Программирование
Год издания: 2006
isbn: 978-5-469-00391-4
Скачать книгу
с 200 идентификаторами, допустимая длина идентификатора должна быть не менее 32 символов. Запрещается использовать в работе хэш-функции, взятые из примера выполнения работы.

      Лабораторная работа должна выполняться в следующем порядке:

      1. Получить вариант задания у преподавателя.

      2. Выбрать и описать хэш-функцию.

      3. Описать структуры данных, используемые для заданных методов организации таблиц идентификаторов.

      4. Подготовить и защитить отчет.

      5. Написать и отладить программу на ЭВМ.

      6. Сдать работающую программу преподавателю.

      Требования к оформлению отчета

      Отчет по лабораторной работе должен содержать следующие разделы:

      • задание по лабораторной работе;

      • описание выбранной хэш-функции;

      • схемы организации таблиц идентификаторов (в соответствии с вариантом задания);

      • описание алгоритмов поиска в таблицах идентификаторов (в соответствии с вариантом задания);

      • текст программы (оформляется после выполнения программы на ЭВМ);

      • результаты обработки заданного набора идентификаторов (входного файла) с помощью методов организации таблиц идентификаторов, указанных в варианте задания;

      • анализ эффективности используемых методов организации таблиц идентификаторов и выводы по проделанной работе.

      Основные контрольные вопросы

      • Что такое таблица символов и для чего она предназначена? Какая информация может храниться в таблице символов?

      • Какие цели преследуются при организации таблицы символов?

      • Какими характеристиками могут обладать лексические элементы исходной программы? Какие характеристики являются обязательными?

      • Какие существуют способы организации таблиц символов?

      • В чем заключается алгоритм логарифмического поиска? Какие преимущества он дает по сравнению с простым перебором и какие он имеет недостатки?

      • Расскажите о древовидной организации таблиц идентификаторов. В чем ее преимущества и недостатки?

      • Что такое хэш-функции и для чего они используются? В чем суть хэш-адресации?

      • Что такое коллизия? Почему она происходит? Можно ли полностью избежать коллизий?

      • Что такое рехэширование? Какие методы рехэширования существуют?

      • Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью хэш-адресации и рехэширования.

      • В чем заключается метод цепочек?

      • Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью хэш-адресации и метода цепочек.

      • Как могут быть скомбинированы различные методы организации хеш-таблиц?

      • Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью комбинированных методов.

      Варианты заданий

      В табл.