Практические задания

Задание 1.Разработать программу для имитации обработки простейшего Б-дерева второго порядка. Программа должна выполнять следующие действия:

· построение Б-дерева для заданного набора вершин, начиная с пустого дерева

· добавление отдельной вершины

· поиск заданной вершины

· удаление заданной вершины

· вывод Б-дерева в наглядном виде

Имитация обработки определяется тем, что файлы для хранения элементов дерева не используются.

Задание 2.Разработать программу сортировки файлов методом естественного слияния. Для простоты этап предварительной сортировки фрагментов для получения начальных серий не реализуется. Должны использоваться 5 файлов – входной и 4 вспомогательных. Исходный набор заполняется случайными числами в диапазоне от 1 до 1 миллиона.

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

1. В чем состоят особенности задач внешнего поиска и сортировки?

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

3. Для решения каких задач используется структура данных Б-дерево?

4. Что называется страницей Б-дерева?

5. Почему страничная организация Б-дерева является эффективной для решения задачи внешнего поиска?

6. Каким условиям должно удовлетворять Б-дерево?

7. Какими свойствами обладает Б-дерево как дерево поиска?

8. Как оценивается эффективность использования Б-деревьев для задач внешнего поиска?

9. Какие данные должна содержать страница Б-дерева?

10. Какие описания необходимы для определения Б-дерева как структуры данных?

11. Какие шаги включает алгоритм поиска в Б-дереве?

12. Какие основные шаги включает алгоритм добавления вершины в Б-дерево?

13. Что происходит при попытке добавления новой вершины на полностью заполненную страницу Б-дерева?

14. К чему может привести процесс расщепления полной страницы Б-дерева при добавлении новой вершины?

15. В каких случаях высота Б-дерева может увеличиться на единицу?

16. Приведите практический пример добавления вершины в простейшее Б-дерево.

17. Какие особенности возникают при программной реализации алгоритма добавления новой вершины в Б-дерево?

18. Почему при добавлении новой вершины в Б-дерево необходимо запоминать путь от корневой страницы к терминальной?

19. Какие параметры использует рекурсивная подпрограмма добавления новой вершины в Б-дерево?

20. Приведите схему рекурсивной подпрограммы добавления новой вершины в Б-дерево.

21. Что должна делать главная программа при добавлении новой вершины в Б-дерево?

22. Какие основные шаги включает алгоритм удаления вершины из Б-дерева?

23. Как обрабатывается удаление вершины из Б-дерева для терминальной и нетерминальной страницы?

24. Как находится элемент-заменитель для удаляемой из Б-дерева вершины?

25. Какая ситуация может возникнуть после удаления вершины с одной из страниц Б-дерева?

26. За счет чего сохраняется необходимая структура Б-дерева после удаления вершины?

27. Зачем и как выполняется перераспределение вершин между двумя соседними страницами при удалении вершины из Б-дерева?

28. Зачем и как выполняется объединение двух страниц при удалении вершины в Б-дереве?

29. К каким последствиям может привести процесс слияния соседних страниц при удалении вершин из Б-дерева?

30. Приведите практический пример удаления вершины из простейшего Б-дерева.

31. Какие особенности имеет программная реализация удаления вершины из Б-дерева?

32. Какие параметры должна иметь рекурсивная подпрограмма удаления вершины из Б-дерева?

33. Приведите схему рекурсивной подпрограммы удаления вершины из Б-дерева.

34. В чем состоит принцип слияния двух упорядоченных последовательностей?

35. Какие шаги выполняет алгоритм слияния двух упорядоченных последовательностей?

36. Как используется алгоритм слияния последовательностей для сортировки данных?

37. Что такое серия и как это понятие используется при сортировке данных?

38. Как можно улучшить сортировку файлов методом естественного слияния?

39. В чем состоит первый этап внешней сортировки?

40. В чем состоит второй этап внешней сортировки?

41. Какие необходимы вспомогательные файлы при внешней сортировке и как они используются?

42. Как можно уменьшить число вспомогательных файлов, используемых при внешней сортировке?

43. За счет чего можно ускорить сортировку файлов?

44. Как влияет число вспомогательных файлов на эффективность внешней сортировки?

Основные термины и понятия

АВЛ-сбалансированное дерево – разновидность дерева поиска, в котором для каждой вершины высота ее левого и правого поддерева отличаются не более чем на единицу

Балансировка дерева – перестановка вершин с целью сохранения “хорошей” структуры дерева

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

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

Внешняя сортировка – упорядочивание больших наборов данных с преимущественным хранением на дисковой памяти

Внутреннее хеширование – метод разрешения конфликта ключей при хеш-поиске, основанный на размещении конфликтующих ключей в свободных ячейках таблицы

Внутренняя сортировка – упорядочивание элементов массива, полностью располагающихся в оперативной памяти

Высота дерева – наиболее длинный путь от корневой вершины к терминальной

Граф – нелинейная структура данных, состоящая из элементов-вершин, между некоторыми из которых установлены определенные связи

Двоичное дерево – разновидность дерева, в котором каждая вершина может иметь не более двух связанных с нею поддеревьев

Двунаправленный линейный список – разновидность списковой структуры, в которой каждый элемент имеет два указателя на каждого из своих соседей

Дерево – нелинейная структура данных, рекурсивно представимая в виде отдельных поддеревьев

Дерево поиска – разновидность двоичного дерева, в котором для каждой вершины ключи в левом поддереве меньше, а в правом поддереве больше ключа этой вершины

Динамическое распределение памяти – механизм, с помощью которого при выполнении программы можно получать и освобождать области памяти для хранения каких-либо данных

Естественное слияние – один из методов внешней сортировки, основанный на попарном сравнении и объединении двух упорядоченных последовательностей в одну последовательность

Заголовок списка – дополнительный необязательный элемент в начале списка, который никогда не удаляется из списка

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

Карманная сортировка – один из специальных методов сортировки, применяемый для ключей с различными значениями в пределах от 1 до n

Конфликт ключей – ситуация, когда при использовании хеш-поиска два различных ключа претендуют на одно и то же место в массиве

Матрица смежности – способ описания графа с помощью двухмерного массива N*N, ненулевые элементы которого соответствуют связанным вершинам

Метод Шелла – улучшенный метод сортировки массивов, основанный на многократном группировании элементов массива с уменьшающимся шагом и последующей сортировкой методом вставок

О-нотация – способ оценивания трудоемкости алгоритма в зависимости от объема обрабатываемых данных

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

Очередь – линейная структура данных, в которую добавление производится с одного конца, а удаление – с другого

Переменные-указатели – специальные переменные, значениями которых являются адреса областей памяти

Пирамида – разновидность двоичного дерева, в котором ключ каждой вершины не больше ключей всех ее потомков

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

Поразрядная сортировка - один из специальных методов сортировки, применяемый для целочисленных ключей с известным числом разрядов и требующий использования дополнительных списков

Простейшие методы сортировки – алгоритмически простые методы сортировки массивов с трудоемкостью порядка n²

Сортировка вставками – простейший метод сортировки массивов, основанный на поиске для каждого очередного элемента подходящего места в уже обработанной последовательности

Сортировка выбором - простейший метод сортировки массивов, основанный на поиске в необработанном подмножестве наименьшего элемента

Сортировка обменом – простейший метод сортировки массивов, основанный на попарном сравнении и перестановке соседних элементов

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

Список – линейная структура данных с возможностью добавления и удаления элементов в любом месте

Список смежности – способ описания графа в виде массива или главного списка вершин, с каждым элементом которого связан список смежных с нею вершин

Стек – линейная структура данных с односторонним добавлением и удалением элементов

Улучшенные методы сортировки – алгоритмически достаточно сложные методы сортировки массивов с трудоемкостью порядка n*logn

Универсальные методы сортировки – группа методов сортировки массивов, не требующих никакой дополнительной информации о сортируемых наборах и никакой дополнительной памяти

Хеш-поиск – метод поиска, позволяющий по значению входного ключа сразу определять его положение в массиве, организованном в виде специальной таблицы (хеш-таблицы)

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

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

Литература

1. Кнут Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд. – М.: Изд. дом “Вильямс”, 2000 г.

2. Кнут Д. Искусство программирования, том 3. Сортировка и поиск, 2-е изд. – М.: Изд. дом “Вильямс”, 2000 г.

3. Вирт Н. Алгоритмы и структуры данных

4. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Изд. дом “Вильямс”, 2001 г.

5. Кормен Т. и др. Алгоритмы: построение и анализ. – МЦНМО, 2000 г.

6. Топп У., Форд У. Структуры данных в С++. – М.: ЗАО “Издательство БИНОМ”, 2000 г.

7. Хэзфилд Р., Кирби Л. и др. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. – К.: Издательство “ДиаСофт”, 2001 г.