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

1. Перечислите основные алгоритмы поиска в массивах.

2. Опишите принцип работы последовательного алгоритма поиска.

3. Опишите принцип работы двоичного алгоритма поиска.

4. Как реализован принцип хеширования.

5. Какая должна быть хеш-функция?

6. Когда возникает коллизия и как она разрешается?

7. Перечислите основные алгоритмы поиска подстроки в строке.

8. В чем суть линейного алгоритма поиска?

9. Опишите алгоритм БМ-поиска.

10. Опишите агоритм БМП-поиска.

11. Какой из алгоритмов поиска оптимальнее?

12. Какой алгоритм поиска быстродейственее?

Задания для практической работы

1. Реализовать алгоритмы последовательного и двоичного поиска. Провести сравнительный анализ при разных входных данных.

2. Хеширование:

1. Задан текст программы на языке Паскаль. Определить частоту использования:

а) идентификаторов;

б) ключевых слов:

в) символьных констант.

2. Задан текстовый файл. Сформировать список слов, употребляющихся в тексте более пяти раз.

3. Задан текстовый файл. Сформировать набор словосочетаний по два и более слова, встречающихся в тексте не менее двух раз.

4. Задан набор записей следующей структуры: табельный номер. ФИО. заработная плата. По табельном}* номеру найти остальные сведения.

5. Задан набор записей следующей структуры: номер телефона. ФИО адрес. По номеру телефона найти сведения о ФИО владельца и его адресе.

Задан набор записей следующей структуры: название кинофильма, режиссер, список актеров, краткое содержание. По заданному названию фильма найти остальные сведения.

6. Задан набор записей следующей структуры: номер автомобиля, его марка и ФИО владельца. По номеру автомобиля найти остальные сведения.

7. Задан список имен людей. Определить частоту использования каждого имени в некотором тексте.

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

9. Исследовать зависимость числа коллизий от коэффициента заполненности хеш-таблицы.

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

3. Реализовать и провести сравнительный анализ приведенных алгоритмов поиска подстроки в строке.

Литература

1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.:Вильямс, 2000. – 382 с.

2. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. — 2-е изд. испр. - СПб.: Невский Диалект, 2001. -352 с.

3. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: Пер. с англ. — М.: Мир, 1998, —703с.

4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001 — 960 с.

5. Кнут Д. Искусство программирования. Т.1. – М.: Вильямс, 2000 – 690с.

6. Кнут Д. Искусство программирования. Т.2. – М.: Вильямс, 2000 – 788с.

7. Кнут Д. Искусство программирования. Т.3. – М.: Вильямс, 2000 – 800с.

8. Кубенский А. А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на C++. - СПб.: БХВ-Петербург, 2004. - 464с.

9. Липский В. Комбинаторика для программистов: Пер. с польск. М.: Мир, 1988. —213 с.

10. Мозговой М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход. — СПб.: Наука и Техника, 2006.— 320 с.

11. Седжвик Р., Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - К.: Издагсльство «ДиаСофт», 2001.- 688 с.

12. Хэзфидд Ричард, Кирби Лоуренс и др. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. Энциклопедия программиста: Пер. с англ./Ричард Хэзфилд, Лоуренс Кирби и др. — К.: Издательство «ДиаСофт», 2001. — 736 с.

82