Задания по информатике

Вопрос

Вопрос 1 Вариант 6

Тема 1 Двоичные деревья

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

деревьями поиска:

поиск вершины с заданным значением ключа с выводом счетчика числа появлений данного ключа

добавление новой вершины в соответствии со значением ее ключа или увеличение счетчика числа появлений

построчный вывод дерева в наглядном виде на основе процедур обхода:

- в прямом порядке;

- с помощью обратно-симметричного обхода;

Рекомендации:

1) Объявить и реализовать подпрограмму поиска. Поиск начинается с корня дерева и в цикле для каждой вершины сравнивается ее ключ с

заданным значением. При совпадении ключей, поиск заканчивается с выводом значения счетчика числа появлений данного ключа. При

несовпадении поиск продолжается в левом или правом поддереве текущей вершины.

2) Объявить и реализовать рекурсивную подпрограмму добавления новой вершины в дерево. Подпрограмма использует один параметр-

переменную, определяющую адрес текущей вершины. Если при очередном вызове подпрограммы этот адрес равен nil, то производится

добавление нового элемента с установкой всех необходимых полей. В противном случае продолжается поиск подходящего места для новой

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

увеличить значение счетчика появлений.

3) Объявить и реализовать рекурсивные подпрограммы для построчного вывода дерева в прямом и обратно-симметричном порядке:

Все процедуры обхода должны выводить вершины с числом отступов, пропорциональным уровню вершины: корень дерева не имеет

отступов, вершины первого уровня выводятся на 5 отступов правее, вершины 2-го уровня – еще на 5 отступов правее и т.д. Для этого в

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

Все процедуры обхода имеют похожую структуру. Например, процедура обхода в прямом направлении должна:

проверить пустоту очередного поддерева

вывести в цикле необходимое число пробелов в соответствии с уровнем вершины

вывести информационную часть текущей вершины

вызвать рекурсивно саму себя для обработки своего левого поддерева с увеличением уровня на 1

вызвать рекурсивно саму себя для обработки своего правого поддерева с увеличением уровня на 1

Сравнение рассмотренных правил вывода двоичного дерева поиска приводится в следующей таблице

Главная программа должна предоставлять следующие возможности:

создание дерева с заданным числом вершин со случайными ключами

добавление в дерево одной вершины с заданным пользователем значением ключа

поиск в дереве вершины с заданным ключом

построчный вывод дерева в наглядном виде

Тема 2 Организация поиска в массиве данных при помощи специальных методов поиска.

Задание. Реализовать программно метод хеш-поиска с разрешением конфликтов методом цепочек.

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

функция – такая же, что и в задании 1, но делить надо на константу m. В случае возникновения конфликта при попытке размещения в

таблице нового ключа этот ключ добавляется в конец вспомогательного списка. Это требует включения в каждую ячейку хеш-таблицы двух

указателей на начало и конец вспомогательного списка.

Программа должна выполнять следующие действия:

добавление нового ключа в таблицу с подсчетом сделанных при этом сравнений

поиск заданного ключа в таблице с подсчетом сделанных при этом сравнений

вывод текущего состояния таблицы на экран

удаление заданного ключа из таблицы

Алгоритм удаления:

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

если удаляемый элемент найден в ячейке таблицы, то эта ячейка либо становится пустой (если связанный с ней список пуст), либо в нее

записывается значение из первого элемента списка с соответствующим изменением указателей

Учебная практика

/

ISU v2.121

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

После отладки программы необходимо выполнить ее для разных соотношений числа исходных ключей и размерности таблицы: взять 20

ключей и разместить их поочередно в таблице размерности 9, 17 и 23. Для каждого случая найти суммарное число сравнений, необходимое

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

Тема 3 Сортировка данных

Задание 1 Реализовать программу, реализующую простейший метод сортировки массивов:

сортировку вставками

сортировку обменом (метод пузырька)

Каждый метод реализуется своей подпрограммой, добавляемой в основную программу по мере разработки. Кроме того, необходима

вспомогательная подпрограмма генерации исходного массива случайных целых чисел с заданным числом элементов (не более 10 000) и

выводом этого массива на экран

Каждый исходный массив должен обрабатываться всеми подпрограммами сортировки с подсчетом и выводом фактического числа

выполненных сравнений и пересылок. Поскольку каждый из универсальных методов выполняет сортировку “на месте”, т.е. изменяет

исходный массив, то для наглядности работы можно передавать в подпрограмму сортировки копию исходного массива, объявив его как

параметр-значение.

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

элементов (10, 100, 1000, 10000) и провести сравнительный анализ эффективности рассматриваемых методов.

Главная программа должна реализовать диалог с пользователем для выбора метода сортировки.

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

Метод реализуется в виде подпрограммы. Исходный массив должен обрабатываться подпрограммой сортировки с подсчетом и выводом

фактического числа выполненных сравнений и пересылок. Выполнить сортировку нескольких массивов с разным числом элементов (10, 100,

1000, 10000)