«Алгоритмы и структуры данных»

Лабораторная работа №1 Тема: "Поиск ключа в массиве. Анализ эффективности алгорит-мов поиска" I. Разработать программу, обеспечивающую выполнение следующих функций:

1. Формирование и вывод на экран массива случайных чисел, со-стоящего из n целочисленных элементов (n – заданное число).
2. Поиск заданного ключа в исходном неотсортированном массиве.

Значение ключа вводиться в режиме диалога или формируется дат-чиком случайных чисел. Используется следующий метод поиска ключа:

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

Лабораторная работа №2 Тема: "Сортировка массивов. Анализ эффективности алгорит-мов сортировки" I. Разработать программу, обеспечивающую выполнение следующих функций:

1. Формирование и вывод на экран массива случайных чисел, со-стоящего из n целочисленных элементов (n – заданное число).
2. Сортировка исходных массивов двумя методами, заданными в табл. П.1.

Примечание: сортировка элементов в массиве каждым из методов должна сопровождаться определением времени сортировки или подсче-том количества операций сравнения, выполненных программой (данная характеристика выбирается разработчиком). II. Выполнить разработанную программу для различных значений n в диапазоне от 100 до 1000. III. Оценить эффективность работы алгоритмов сортировки и произ-вести их сравнение. Построить графики характеризующие зависимость времени (или количества операций сравнения) от n для заданных методов сортировки. Методы сортировок, выбираемые по вариантам:

1. Быстрая сортировка выбором (турнир с выбыванием или пира-мидальная – по выбору).
2. Сортировка подсчетом

Лабораторная работа №3 Тема: "Работа с линейными списками"

1. Выбрать из табл. П.2 вид списка, способ его реализации и функ-ции, которые надо выполнить. Написать программу, которая создает список из десяти элементов и выполняет заданную в табл. П.2 последо-вательность функций.
2. Список функций, номера которых содержатся в последней ко-лонке таблицы:

1) обход списка; 2) сортировка элементов списка; 3) поиск элемента списка, совпадающего с заданным ключом x, причем данный элемент может отсутствовать в списке; 4) удаление шестого по порядку элемента списка; 5) добавление в список нового элемента после элемента, совпада-ющего с ключом x; если такого элемента нет, добавить новый элемент в начало списка; 6) добавление в список после второго элемента трех новых элемен-тов; 7) удаление из списка всех элементов, которые меньше среднего значения элементов списка; 8) обход списка с вычислением среднего значения элементов списка.

Варианты индивидуального задания. Номер послед. цифры ст. кода Вид списка Способ реализации списка Выполняемые функции 0, 8 Линейный однонаправленный Двумя массивами 1, 2, 5, 6, 1

Лабораторная работа №4 Тема: "Методы обхода графов"

1. Нарисовать на бумаге граф, состоящий из 10 вершин. В вершины графа записать буквы, которые образуют вашу фамилию и часть имени.
2. В соответствии с табл. П.3 реализовать граф в ЭВМ. Обойти граф, используя заданный в табл. П.3 алгоритм, и прочитать текст в вершинах графа.
3. Проанализировать прочитанный текст и переставить буквы в вершинах так, чтобы фамилия и имя читались правильно. Снова обойти граф, прочитав новый текст. Примечание: Способ построения графа и его обход реализовать в про-грамме. Анализ прочитанного текста и перестановка букв в вершинах графа может выполняться как программным путем, так и вручную.

Варианты индивидуального задания. Способ реализации графа

Список инцидентности

Метод обхода графа

Обход в глубину

Лабораторная работа №5 Тема: " Бинарные деревья" Вариант I

1. Построить упорядоченное сбалансированное бинарное дерево.
2. Найти узел, содержащий элемент, который совпадает с заданным ключом.
3. Удалить найденный узел.
4. Проверить условие сбалансированности дерева, если оно наруше- но, перес