Алгоритмы и структуры данных. 4 практических задания

Практическое задание № 1.

Тема 1.2. Динамические структуры данных: «линейные списки», «стек», «очередь», «дерево»

Цель работы: ознакомится с различными динамическими структурами данных и методами работы с ними; научиться решать задачи с

использованием динамических структур данных.

Формулировка задания № 1.

1. Сформировать динамическую структуру данных.

Описать структуру с именем STUDENT, содержащую следующие поля: фамилия и инициалы; номер группы; успеваемость (массив из пяти элементов). Написать программу, выполняющую следующие действия:

ввод с клавиатуры данных в массив, состоящий из десяти структур типа STUDENT;

записи должны быть упорядочены по возрастанию номера группы;

вывод на экран фамилий и номеров групп для всех студентов, включенных в массив, если средний балл студента выше 4.0;

если таких студентов нет, вывести соответствующее сообщение.

2. Информацию, составляющую содержание структуры и введенную с клавиатуры, организовать в виде стека, односвязного или двусвязного списка или в виде бинарного дерева.

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

Практическое задание № 2.

Тема 2.2. Решение задач с использованием рекурсивных алгоритмов

Цель работы: изучить основные понятия, связанные с рекурсией и рекурсивными алгоритмами; научится применять их при решении задач.

Формулировка задания № 2.

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

1) дано натуральное число n. Необходимо:

1. вывести на экран все его цифры;

2. найти сумму цифр данного числа;

3. записать его в обратном порядке;

2) дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0 Необходимо:

1. вывести все нечетные числа из этой последовательности, сохраняя их порядок.

Практическое задание № 3.

Тема 3.2. Алгоритмы сортировки

Цель работы: изучить основные алгоритмы поиска и сортировки; провести сравнительный анализ различных алгоритмов поиска и сортировки.

Формулировка задания № 3.

1. Изучить следующие методы сортировки:

включение;

выбор;

обмен;

сортировка Шелла;

сортировка Хоара;

пирамидальная сортировка.

2. Реализовать упомянутые выше методы. Проанализировать время, затрачиваемое на каждый из них при одинаковом количестве измерений (количестве элементов в массиве).

3. Изучить алгоритмы поиска:

в неупорядоченном массиве:

линейный;

быстрый линейный;

в упорядоченном массиве:

быстрый;

бинарный;

блочный.

4. Реализовать данные алгоритмы в одном файле в виде отдельных подпрограмм (функций).

5. Проанализировать, на какой итерации при разных алгоритмах поиска было найдено искомое число.

Практическое задание № 4.

Тема 4.4. Остовные деревья. Остовные деревья в графе.

Минимальное остовное дерево: алгоритмы Прима и

Крускала.

Формулировка задания № 4.

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

2. Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в ширину.

3. Используйте обход графа в ширину для определения всех вершин графа, находящихся на фиксированном расстоянии d от данной вершины.

4. Реализуйте программы, в которых выполняются алгоритм Дейкстры и алгоритм Флойда.

5. Реализуйте программу, в которой определяется минимальное остовное дерево графа.