Контрольная работа по delphi: «учебная практика» заказ № 1941123

Вопрос 1 Вариант 3. Тема 1 Двоичные деревья Задание. Построение и обработка двоичных деревьев поиска. Реализовать программу, выполняющую следующий набор операций с деревьями поиска: поиск вершины с заданным значением ключа с выводом счетчика числа появлений данного ключа добавление новой вершины в соответствии со значением ее ключа или увеличение счетчика числа появлений построчный вывод дерева в наглядном виде на основе процедур обхода: - в прямом порядке; - с помощью обратно-симметричного обхода; Рекомендации: 1) Объявить и реализовать подпрограмму поиска. Поиск начинается с корня дерева и в цикле для каждой вершины сравнивается ее ключ с заданным значением. При совпадении ключей, поиск заканчивается с выводом значения счетчика числа появлений данного ключа. При несовпадении поиск продолжается в левом или правом поддереве текущей вершины. 2) Объявить и реализовать рекурсивную подпрограмму добавления новой вершины в дерево. Подпрограмма использует один параметр-переменную, определяющую адрес текущей вершины. Если при очередном вызове подпрограммы этот адрес равен nil, то производится добавление нового элемента с установкой всех необходимых полей. В противном случае продолжается поиск подходящего места для новой вершины за счет рекурсивного вызова подпрограммы с адресом левого или правого поддерева. При совпадении ключей надо просто увеличить значение счетчика появлений. 3) Объявить и реализовать рекурсивные подпрограммы для построчного вывода дерева в прямом и обратно-симметричном порядке: Все процедуры обхода должны выводить вершины с числом отступов, пропорциональным уровню вершины: корень дерева не имеет отступов, вершины первого уровня выводятся на 5 отступов правее, вершины 2-го уровня – еще на 5 отступов правее и т.д. Для этого в рекурсивные подпрограммы обхода надо ввести второй формальный параметр - уровень этой вершины. Все процедуры обхода имеют похожую структуру. Например, процедура обхода в прямом направлении должна: проверить пустоту очередного поддерева вывести в цикле необходимое число пробелов в соответствии с уровнем вершины вывести информационную часть текущей вершины вызвать рекурсивно саму себя для обработки своего левого поддерева с увеличением уровня на 1 вызвать рекурсивно саму себя для обработки своего правого поддерева с увеличением уровня на 1 Сравнение рассмотренных правил вывода двоичного дерева поиска приводится в следующей таблице Главная программа должна предоставлять следующие возможности: создание дерева с заданным числом вершин со случайными ключами добавление в дерево одной вершины с заданным пользователем значением ключа поиск в дереве вершины с заданным ключом построчный вывод дерева в наглядном виде Тема 2 Организация поиска в массиве данных при помощи специальных методов поиска. Задание. Реализовать программно метод хеш-поиска с разрешением конфликтов методом пустых ячеек. Исходные ключи – любые слова (например – фамилии). Размер хеш-таблицы должен задаваться в программе с помощью константы m. Хеш-функция – такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в таблице нового ключа, для него ищется первое свободное по порядку место по формуле j = (( h (ключ) + i ) mod m ) + 1, где i = 0, 1, 2, . . . , m-2 Программа должна выполнять следующие действия: добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений вывод текущего состояния таблицы на экран После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 10 ключей и разместить их поочередно в таблице размерности 11, 13 и 17. Для каждого случая найти суммарное число сравнений, необходимое для размещения ключей и их поиска. Сделать вывод о влиянии количества пустых мест в таблице на эффективность поиска. Тема 3 Сортировка данных Задание 1 Реализовать программу, реализующую простейший метод сортировки массивов: сортировку выбором сортировку вставками Каждый метод реализуется своей подпрограммой, добавляемой в основную программу по мере разработки. Кроме того, необходима вспомогательная подпрограмма генерации исходного массива случайных целых чисел с заданным числом элементов (не более 10 000) и выводом этого массива на экран Каждый исходный массив должен обрабатываться всеми подпрограммами сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. Поскольку каждый из универсальных методов выполняет сортировку “на месте”, т.е. изменяет исходный массив, то для наглядности работы можно передавать в подпрограмму сортировки копию исходного массива, объявив его как параметр-значение. После завершения разработки программы необходимо выполнить всеми методами сортировку нескольких массивов с разным числом элементов (10, 100, 1000, 10000) и провести сравнительный анализ эффективности рассматриваемых методов. Главная программа должна реализовать диалог с пользователем для выбора метода сортировки. Задание 2 Оформить программу, реализующую метод быстрой сортировки массивов. Метод реализуется в виде подпрограммы. Исходный массив должен обрабатываться подпрограммой сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. Выполнить сортировку нескольких массивов с разным числом элементов (10, 100, 1000, 10000). Требования к прохождению учебной практики: -небольшой теоретический обзор (анализ) по используемым структурам данных и методам – скриншоты результатов тестирования (запуска выполненных программ), отображающие набор выполненных по заданию основных действий – полный листинг программного кода по каждому заданию с комментариями;