Алгоритмы и структуры данных (контрольные + лабораторные работы)

Среда программирования: DEV C++

Название работы: Алгоритмы и структуры данных (контрольные + лабораторные работы)

Вид работы: Лабораторная работа

Описание: Алгоритмы и структуры данных

Задание на контрольную работу
Вариант выбирается по последним двум цифрам пароля.
Требования к содержанию отчета о выполнении контрольной работы:

Титульный лист.
Индивидуальное задание из табл. 1.
Тексты разработанных программ по каждой части задания (шрифт Courer New, размер 10-12 пт, интервалы до и после абзаца – 0, междустрочный интервал – 1,0).
Результаты работы программы по каждой части задания – ровно так, как они отражаются в консоли вывода.
Анализ полученных результатов по каждой части задания.
Выводы по работе в целом.

Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программированию статических структур данных (раздел 1 конспекта лекций) и области их эффективного использования, а также возможности языка С++ для создания и обработки статических структур.
2. Разработать программу с пользовательскими функциями для решения следующей задачи:
в соответствии с индивидуальным вариантом (табл. 1) составить структуру данных, описывающую заданную предметную область;
написать подпрограммы:
добавления записи;
вывода записей на экран;
удаления записи, указанной ее порядковым номером;
изменение данных записи, указанной ее порядковым номером;
вывода на экран записей, удовлетворяющих некоторому критерию;
в основной программе организовать простое текстовое меню, посредством которого реализовать обработку данных при помощи вызова подпрограмм.
3. Протестировать программу. Данные следует вводить псевдореальные (не бессмысленные).

Часть II – Дисциплина обслуживания
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программированию статических структур данных с заданной дисциплиной обслуживания (раздел 2 конспекта лекций) и области их эффективного использования, а также возможности языка С++ для создания и обработки структур с заданной дисциплиной обслуживания.
2. На базе структуры, разработанной при выполнении части I, реализовать обработку данных посредством заданной дисциплины обслуживания, выбранной согласно последней цифре пароля:
нечетная цифра – LIFO (стек);
четная цифра – FIFO (очередь);
3. Посредством пользовательских функций реализовать следующие операции:
добавление новой записи (с проверкой на переполнение);
извлечение записи (с исключением) и возвращение ее в основную программу для вывода на экран;
определение числа хранимых записей;
очистка структуры.
4. Провести тестирование реализованных функций.
5. Разработать пользовательскую функцию вывода на экран записей, удовлетворяющих заданному критерию, и протестировать ее выполнение. Функция должна вызывать функцию извлечения записи и осуществлять ее проверку на соответствие параметрам. При соответствии выводить запись на экран, иначе отбрасывать. В результате проведенного анализа структура должна оказаться пустой.

Часть III – Линейные односвязные списки
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить понятие линейного односвязного списка (раздел 3 конспекта лекций) и возможности языка программирования С++ для создания и обработки односвязных списков.
2. Разработать программу на языке С++ для решения следующей задачи:
В соответствии с индивидуальным вариантом задания (табл. 1) реализовать динамическую структуру данных, описывающую предметную область в виде линейного односвязного списка, и процедуры:
добавления элемента в начало списка;
добавления элемента в конец списка;
удаления элемента из начала списка;
удаления элемента из конца списка;
удаления из списка элемента, указанного его порядковым номером;
изменение данных элемента списка, указанного его порядковым номером;
вывода элементов списка на экран.
3. Протестировать программу.

Часть IV – Двусвязные и кольцевые списки
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить понятие двусвязного и кольцевого списка (раздел 4 конспекта лекций) и возможности языка программирования С++ для создания и обработки таких списков.
2. Выполнить преобразование кода, разработанного при выполнении задания части III, сделав список:
нечетная цифра – однонаправленным кольцевым;
четная цифра – двунаправленным кольцевым;
3. Предусмотреть такие процедуры работы со списком:
добавления элемента в заданную позицию списка;
изменение данных элемента списка в заданной позиции;
удаления элемента из заданной позиции списка;
вывода элементов списка на экран.
Таблица 1. Варианты заданных предметных областей (ХХ –2 последние цифры пароля)
ХХ
Предметная область
Атрибуты информации
Критерий отбора
00
25
50
75
Отдел кадров предприятия
фамилия сотрудника, имя, отчество, должность, стаж работы, оклад
Сотрудники, работающие более 8 лет
01
26
51
76
Производство
обозначение изделия, группа к которой оно относится, год выпуска, объем выпуска, расход металла
Изделия заданной группы
02
27
52
77
Персональные ЭВМ
фирма-изготовитель, тип процессора, тактовая частота, емкость ОЗУ, емкость жесткого диска
ЭВМ с заданным типом процессора
03
28
53
78
Библиотека
автор книги, название, год издания, код УДК, цена, количество в библиотеке
Книги с нулевым количеством
04
29
54
79
Радиодетали
обозначение, тип, номинал, количество на схеме, обозначение возможного заменителя
Детали, не имеющие заменителей
05
30
55
80
Программы
наименование, фирма-разработчик, операционная система, стоимость
Программы с нулевой стоимостью
06
31
56
81
Телефонная станция
номер абонента, фамилия, адрес, наличие блокиратора, задолженность
Абоненты с ненулевой задолженностью
07
32
57
82
Студенты
фамилия студента, имя, отчество, факультет, число членов семьи
Студенты с заданного факультета
08
33
58
83
Спортивные соревнования
фамилия спортсмена, имя, команда, вид спорта, зачетный результат, штрафные очки
Спортсмены с числом штрафных очков более 10
09
34
59
84
Соревнование факультетов по успеваемости
факультет, количество студентов, средний балл по факультету, число отличников
Факультеты со средним баллом не менее 4,0
10
35
60
85
Сельхозработы
наименование с/х предприятия, вид собственности, число работающих, основной вид продукции, прибыль
3 предприятия с максимальной прибылью
11
36
61
86
Сведения о студентах
фамилия студента, имя, отчество, факультет, количество братьев и сестер
Студенты с ненулевым числом братьев и сестер
12
37
62
87
Микросхемы памяти
обозначение, разрядность, емкость, время доступа, количество на схеме, стоимость
Схемы памяти с заданной разрядностью
13
38
63
88
Описание изображения
тип фигуры (квадрат, окружность и т.п.), координаты на плоскости, числовые характеристики (длина стороны, радиус и т.п.).
Многоугольники
14
39
64
89
Парковое хозяйство
наименование зеленого массива, площадь, основная порода, средний возраст, плотность деревьев на кв.км
Массивы со средним возрастом деревьев менее 10 лет
15
40
65
90
Городской транспорт
вид транспорта, номер маршрута, начальная остановка, конечная остановка, время в пути
Маршруты заданнго вида транспорта
16
41
66
91
Оптовая база
название товара, количество на складе, стоимость единицы, название поставщика, срок поставки
Остатки товара
17
42
67
92
Сеть магазинов
номер, название, адрес, телефон магазина, ФИО, адрес, капитал владельцев магазина.
Магазины с капиталом, не более 1 млн. руб.
18
43
68
93
Авторемонтные мастерские
номер, марка, мощность и цвет автомобиля, ФИО и квалификация механика, тип работ
Автомобили заданной марки
19
44
69
94
Договорная деятельность организации
шифр договора, наименование организации, наименование контрагента сроки выполнения, сумма договора, вид договора.
Договоры заданного вида
20
45
70
95
Поликлиника
ФИО и дата рождения пациента, ФИО, должность и специализация лечащего врача, диагноз
Пациенты старше 40 лет
21
46
71
96
Домоуправление
номер квартиры, общая площадь, полезная площадь, количество комнат, фамилия квартиросъемщика, количество членов семьи
Квартиры общей площадью менее 40 кв.м.
22
47
72
97
Аэропорт
номер рейса, пункт назначения, день рейса, тип самолета, время вылета, время в пути
Рейсы выходного дня
23
48
73
98
Спорт
ФИО спортсмена, дата рождения, страна, спортивный разряд, рейтинг
Несовершеннолетние спорсмены
24
49
74
99
Автотранспортное предприятие
номерной знак автомобиля, марка, техническое состояние, грузоподъемность, расход топлива, табельный номер и ФИО водителя
Авто с расходом топлива более 15 л на 100 км


Лабораторная работа №1
Тема: Линейные односвязные списки.
Цель: изучение и освоение использование структур и линейных списков.
Задание:
На основе материалов конспекта лекций (раздел 3) и рекомендуемой литературы изучить теоретический материал по программированию односвязного списка.
Сформировать однонаправленный список целых чисел заданной (см. табл. 1) длины и вывести его на экран.
Рассчитать заданный (см. табл. 1) показатель на основе значений элементов списка и вывести значение показателя на экран.
Выполнить заданную (см. табл. 1) обработку списка и вывести обработанный список на экран.
Таблица 1 - Индивидуальные задания к лабораторной работе №1
№
вар.
Число элементов
Критерий для анализа
Обработка
1
10
Количество четных положительных элементов P
Отрицательные элементы сделать положительными и уменьшить на P
2
10
Минимальный положительный элемент V
Отрицательные элементы увеличить на V
3
20
Сумма чётных чисел, расположенных до минимального элемента массива
Нечетные элементы уменьшить на найденную сумму
4
20
Среднее арифметическое значение элементов
Удвоить элементы, меньшие найденного среднего
5
10
Сумма чисел, расположенных между минимальным и максимальными элементами
У элементов, расположенных до максимального элемента, изменить знак
6
10
Минимальный по модулю не нулевой элемент M
Нулевые элементы заменить на M
7
10
Количество отрицательных элементов N
Элементы, значение которых меньше N, увеличить вдвое
8
10
Разность значений максимального и минимального элементов массива
Четные элементы, меньшие найденной разности, обнулить
9
20
Минимальный четный элемент E
Нечетные элементы уменьшить на E
10
20
Разность количества положительных и отрицательных элементов
Все элементы увеличить на найденную разность
11
10
Количество одноразрядных неотрицательных элементов
Положительные элементы сделать отрицательными
12
10
Минимальный положительный элемент K
Отрицательные элементы увеличить на K
13
10
Среднее арифметическое значение четных элементов
Удвоить нечетные элементы, больше найденного среднего
14
20
Минимальный по модулю элемент B
Отрицательные элементы сделать положительными и уменьшить на B
15
20
Максимальный по модулю не нулевой элемент W
Нулевые элементы заменить на W

Лабораторная работа №2
Тема: Двусвязные списки
Цель работы: изучить понятие и способы описания двусвязных списков и освоить их программную реализацию средствами языка С++.
Задание
На основе материалов конспекта лекций (раздел 3) и рекомендуемой литературы изучить теоретический материал по программированию двусвязного и кольцевого списка.
Составить программу на языке С++, в которой реализовать двусвязный список целых чисел. Предусмотреть операции добавления, изменения и удаления элемента в указанной позиции.
Сформировать список произвольных целых чисел (не менее 10 элементов) и вывести его на экран.
В соответствии с индивидуальным вариантом (табл. 2) обработать данные списка. При этом не использовать дополнительные списки или массивы. Обработанные данные вывести на экран.
Модифицировать программу для работы с кольцевым двусвязным списком и протестировать ее работу.
Сравнить реализации обоих списков и сделать выводы.
Таблица 2 - Индивидуальные задания к лабораторной работе №2
№
варианта
Обработка
1
Расположить отрицательные элементы вначале списка с сохранением исходного порядка
2
Упорядочить элементы списка по возрастанию
3
Проходя список слева направо после каждого второго элемента добавить элемент, значение которого есть разность двух предыдущих элементов
4
Удалить из списка все элементы с нечетными значениями
5
Проходя список справа налево после каждого элемента добавить элемент, значение которого произведение предшествующего элемента и минимального элемента в списке
6
Удалить из списка все элементы, содержащие цифру 0
7
Отрицательные элементы сделать положительными и разместить вначале списка с сохранением исходного порядка
8
Элементы меньше среднего арифметического значений элементов списка расположить в конце списка с сохранением исходного порядка
9
Упорядочить элементы списка по убыванию
10
Проходя список справа налево после каждого третьего элемента добавить элемент, значение которого есть сумма трех предыдущих элементов
11
Удалить из списка все элементы больше среднего арифметического значений элементов списка
12
Проходя список слева направо из списка повторяющиеся элементы
13
Упорядочить элементы списка по убыванию их младших разрядов
14
Упорядочить элементы списка по возрастанию их абсолютных значений
15
Проходя список справа налево удалить из списка повторяющиеся элементы

Лабораторная работа №3
Тема: Бинарные деревья
Цель работы: изучить понятие и способы описания бинарных деревьев и освоить их приемы программирования алгоритмов их обработки.
Задание
На основе материалов конспекта лекций (раздел 5) и рекомендуемой литературы изучить теоретический материал по программированию бинарных деревьев.
Сформировать дерево (деревья) двоичного поиска и вывести его (их) на экран.
Выполнить обработку данных на этом бинарном дереве (табл. 3, задание 1) и вывести обработанное дерево на экран.
На полученном бинарном дереве найти заданную характеристику (табл. 3, задание 2) и вывести ее на экран.
Таблица 3 - Индивидуальные задания к лабораторной работе №3
№
варианта
Задание 1
(преобразование)
Задание 2
(определение характеристики)
1
Обнулить все совершенные листья дерева, больших разности максимального и минимального значения элементов дерева.
Найти сумму элементов, расположенных на максимальном уровне от корня.
2
Поменять знак элементов дерева меньших среднего арифметического листьев дерева.
Найти разность суммы элементов, расположенных на четных уровнях, и суммы элементов – на нечетных уровнях бинарного дерева.
3
Все отрицательные элементы дерева заменить их квадратами. Проверить, осталось ли дерево деревом двоичного поиска.
Найти сумму элементов на каждом уровне дерева.
4
Обнулить листья дерева с нечетным количеством цифр.
Найти уровень с максимальной суммой элементов.
5
Если в дереве встречаются числа Фибоначчи, то все отрицательные элементы заменить их модулем. Проверить, осталось ли дерево деревом двоичного поиска.
Найти уровень с максимальным количеством листьев.
6
Даны два дерева двоичного поиска. Все простые элементы второго дерева добавить в первое.
Найти уровень, элементы которого наименее отличаются от среднего арифметического значения этого уровня.
7
Обнулить узлы, имеющие ровно два потомка со значениями разного знака.
Найти уровень с максимальным количеством простых элементов.
8
Обнулить узлы, имеющие потомка с простым значением.
Найти среднее значение элементов для каждого уровня бинарного дерева.
9
Заменить значения простых элементов дерева максимальным значением всех простых листьев дерева.
Найти уровень с максимальным количеством нулевых элементов.
10
Даны два дерева двоичного поиска. Все совершенные элементы второго дерева добавить в первое.
Найти уровень, на котором больше всего узлов с двумя потомками.
11
Даны два дерева двоичного поиска. Построить дерево двоичного поиска, содержащее все простые элементы двух деревьев.
Найти количество уровней дерева, на которых встречаются отрицательные элементы.
12
Дано бинарное дерево. Поменять местами корень дерева и элемент, наиболее близкий к среднему арифметическому элементов дерева.
Укажите номера двух уровней бинарного дерева, сумма элементов которых максимальна.
13
Дано бинарное дерево. Поменять местами элементы с максимальным и минимальным значением.
Найти номер срединного уровня бинарного дерева.
14
Обнулить элементы, являющиеся совершенным числом и среди потомков которых также есть совершенные числа.
Определить для узла и двух его потомков, можно ли их значения принять за стороны треугольника. Найти количество возможных решений для данного бинарного дерева.
15
Обнулить элементы дерева, потомки которых являются числами Фибоначчи.
Найти уровень бинарного дерева, на котором одинаковое количество положительных и отрицательных элементов.

Год: 2020

Данный заказ (лабораторная работа) выполнялся нашим сайтом в 2020-м году, в рамках этого заказа была разработана программа в среде программирования DEV C++. Если у Вас похожее задание на программу, которую нужно написать на DEV C++, либо на другом языке программирования, пожалуйста заполните форму, приведённую ниже, после чего Ваше задание в первую очередь рассмотрит наш программист, выполнявший в 2020-м году этот заказ, если он откажется, то Ваше задание оценят другие наши программисты в течение 48-и часов, если оценка нужна срочно, просим Вас оставить пометку об этом - напишите в тексте задания фразу "СРОЧНЫЙ ЗАКАЗ".

Тел.: +79374242235 Viber: +79374242235 Telegram: kursovikcom ВКонтакте: kursovikcom WhatsApp +79374242235 E-mail: info@kursovik.com Skype: kursovik.com