Лабораторные работы по предмету
«Структуры Данных и Алгоритмы в C++» на 2019-20
учебный год!
Последнее обновление: 01.10.2019
Примечание: для групп TI-21, IA-23, TIR-26 и IAR-27 обязательны первые 7
лабораторных работ, 8-я и 9-я – по желанью (лабораторную работу №8 можно
выполнить вместо одной из первых 7 лабораторных работ, а выполнение
лабораторной работы №9 освобождает от выполнения практической части на
экзамене, оценка будет совпадать с оценкой на этой лабораторной работе). Номер
варианта совпадает с номером студента в журнале. Если выполнен другой
вариант, лабораторная работа не принимается. Если указана фамилия или имя
другого студента или если есть прямые доказательства, что работа была взята у
кого-то из коллег, то она будет оценена максимум на пять (если студент объяснит
подробно процесс ее выполнения, то может быть поставлена, как исключение,
оценка шесть). На каждой паре можно сдать не более чем две лабораторные
работы, в качестве исключения (лабораторные № 7-9) можно сдать три.
Лабораторные работы № 8-9 могут быть представлены в день экзамена, остальные
должны быть представлены в течение семестра на лабораторных занятиях.
Лабораторные работы № 7-9 могут быть представлены и на последней паре по
теории.
Отчет лабораторной работы должен содержать объем около 6-10 страниц. На
первой странице должны быть титульный лист (названия министерства,
университета, факультета, название дисциплины, номер лабораторной, тема,
фамилия и имя студента и преподавателя, место для даты презентации, для
оценки, а также для подписи преподавателя). Вторая страница начинается с целью
и задачей лабораторной, потом должна быть короткая теоретическая информация
по теме (около одной страницы), остальные страницы должны содержать код
программы (полностью), а также скриншоты (минимум три) и электронный
вариант. Последняя страница должна содержать выводы (минимум три, с
различными начальными значениями, особенно те, которые могут привести к
ошибкам или к непредсказуемым ситуациям), основанных на выполнение
лабораторной работы. Чтобы получить максимальную оценку, студент должен
представить лабораторную работы в разумных сроках и должен быть в состоянии
продемонстрировать, что работа была выполнена им (ответить на
дополнительные вопросы, касающиеся работы). В конце проверьте орфографию
и грамматику. Работы с множеством ошибок не принимаются.
Лабораторная работа №1
Тема: Повторяющие инструкции (циклы)
Цель: использование циклов (for, while и do- while) для написания
программ в язык программирования C++.
Задачи
Напишите программу, которая выполняет то, что указанно в вашем
варианте, потом отображает на экран результат (рекомендуется, чтобы
варианты №1-7 были выполнены с помощью команд «for», варианты №8-13
– с «while», а №14-20 – с «do- while»):
1) Вычисляет сумму четных чисел от 2 до n.
2) Вычисляет n! (n факториал)
3) Вычисляет сумму последовательности: 1+1/2+1/3+1/4+...+1/n.
4) Вычисляет произведение нечетных чисел от 1 до n.
5) Вычисляет сумму последовательности: 1-1/2+1/4-1/8+...+(-1)n/2n.
6) Определяет, если число является совершенным (если оно равно сумме
своих делителей, кроме самого числа)
7) Определяет, если два числа являются дружественными (каждое из них
равно сумме делителей другого числа)
8) Вычисляет сумму цифр числа.
9) Вычисляет количество цифр в числе
10) Определяет, если число является простым (делится без остатка только
на 1 и на него самого).
11) Определяет, если два числа являются взаимно простыми (их
наибольший общий делитель является 1).
12) Определяет n-ое число Фибоначчи (Fibonacci).
13) Определяет наибольший общий делитель двух чисел
14) Читает с клавиатуры числа, пока не вводим отрицательное число, и
определяет сумму и произведение введенных чисел.
15) Читает с клавиатуры числа, пока не вводим 0, и определяет сумму
введенных чисел
16) Читает с клавиатуры числа, пока не вводим положительное число, и
определяет сколько чисел мы ввели (количество чисел)
17) Читает с клавиатуры числа, пока не вводим 0, и определяет среднее
арифметическое значение введенных чисел.
18) Читает с клавиатуры числа, пока не вводим положительное число и
определяет среднее геометрическое значение введенных чисел.
19) Читает с клавиатуры числа, пока не вводим 0, и определяет, сколько
положительных, и сколько отрицательных чисел было введено.
20) Читает с клавиатуры числа, пока не вводим отрицательное число, и
определяет среднее арифметическое значение введенных чисел.
Лабораторная работа №2
Тема: Массивы (одномерные- векторы и двумерныематрицы) и символьные строки
Цель: использование векторов, матриц и символьных строк для написания
программ в язык программирования C++.
Задачи
Напишите программу, которая обрабатывает массивы так, как указанно
в вашем варианте, потом выведите на экран результат (в вариантах, где идет
речь о главной или второстепенной диагонали, матрицы являются
квадратными, в других случаях – обычными):
1) Вычисляет среднее арифметическое значение элементов вектора.
2) Вычисляет среднее арифметическое значение элементов матрицы.
3) Вычисляет сумму четных элементов вектора.
4) Вычисляет сумму нечетных элементов матрицы.
5) Вычисляет произведение нечетных элементов вектора.
6) Вычисляет произведение четных элементов матрицы.
7) Вычисляет сумму элементов главной диагонали матрицы.
8) Вычисляет произведение элементов вторичной диагонали матрицы.
9) Вычисляет сумму элементов с четных позиций в векторе.
10) Вычисляет произведение элементов с нечетных позиций в векторе.
11) Определяет, если буква «а» содержится в строке.
12) Определяет, сколько раз буква «е» содержится в строку.
13) Переворачивает строку.
14) Заменяет букву «а» буквой «o» в строке.
15) Определяет, если слово «info» содержится в строку.
16) Заменяет слово «ori» со словом «sau» в строке.
17) Посчитывает, сколько слов в строке.
18) Определяет, если слово «programare» содержится в строке.
19) Заменяет слово «sa» со словом «s-a» в строке.
20) Определяет, сколько раз слово «ULIM» содержится в строке.
Лабораторная работа №3
Тема: Структуры и Массивы от Структур
Цель: создание комплексных программ, используя структуры, массивы из
структур, указатели на структуры и функции в языке программирования C++.
Задачи
Напишите программу, которая позволяет пользователю выбирать один из
пунктов меню (создание массива из структур; вывод на экран содержимого
массива; добавление данных; изменение данных; сортировка данных; поиск
данных по определенному критерию; удаление данных; выход и другие), и
записывает данные в виде структур в массив. Тема, по которой вы должны создать
структуру, а также необходимые поля, указана в вашем варианте.
1) Студенты (номер, фамилия, имя, телефон, специальность, год обучения,
средняя оценка)
2) Песни (название, жанр, исполнитель, длительность, автор слов, автор
музыки, год)
3) Сотрудники (номер, фамилия, имя, должность, адрес, телефон, зарплата)
4) Автомобильный салон (номер, марка, модель, цвет, страна, цена)
5) Салон мобильных телефонов (IMEI, марка, модель, цвет, страна, цена)
6) Продовольственные товары (номер, название, дата производства, срок
годности, цена)
7) Фильмы (номер, название, жанр, режиссер, длительность, страна)
8) Автостанция (номер маршрута, фирма, время прибытия, время
отправления, место назначения, тип транспорта (автобус, микроавтобус),
цена)
9) Пользователь (порядковый номер, адрес электронной почты, фамилия,
имя, пароль, тип учетной записи)
10) Ученики (номер, фамилия, имя, адрес, телефон, профиль, класс,
средняя оценка)
11) Интернет-магазин (номер, наименование товара, единица измерения,
цена, дата поступления)
12) Консервный завод (номер, название, тип, вес, цена, дата
изготовления)
13) Оргтехника (номер, наименование, модель, цена, год выпуска, страна)
14) Характер игры (номер, имя, ник, раса, класс, пол, возраст, количество
оружия, уровень)
15) Банки (имя, адрес, директор, веб-страница, курс евро, курс доллара)
16) Актеры (имя, фамилия, количество фильмов, известные фильмы,
любимый жанр, страна)
17) Операционные системы (название, подтипы, цена, производственная
компания, процент использования в мире, год выпуска)
18) Страны (аббревиатура из трех букв, численность населения (можно в
миллионах), столица, континент, форма правления, руководитель страны
(король, президент или премьер-министр))
19) Спортивные жанры (название, количество игроков в команду, очки за
победу, за ничью за и поражение, периодичность проведения чемпионата
мира)
20) Часы (компания, модель, тип (смарт, электронный, механический),
цена, страна, год)
Лабораторная работа №4
Тема: Файлы
Цель: создание комплексных программ, используя файлы, структуры и
функции в языке программирования C++.
Задачи
Напишите программу, которая позволяет пользователю выбирать один из
пунктов меню (создание файла из структур; вывод на экран содержимого файла;
добавление данных в файл; изменение данных из файла; сортировка данных
файла; поиск данных по определенному критерию в файле; удаление данных из
файла; выход и другие). Данные в виде структур записываются и читаются в файл.
Тема, по которой вы должны создать файл та же, что и лабораторной работе №3.
Рекомендуется использовать бинарный файл.
Лабораторная работа №5
Тема: Линейные Списки
Цель: создание комплексных программ, используя односвязные линейные
списки (созданные вручную), структуры и функции в языке программирования
C++.
Задачи
Напишите программу, которая позволяет пользователю выбирать один из
пунктов меню (создание линейного списка из структур; вывод на экран
содержимого списка; добавление данных в список; изменение данных списка;
сортировка данных списка; поиск данных по определенному критерию в список;
удаление данных из списка; выход и другие). Данные в виде структур
записываются в линейный список, а потом читаются из него. Тема, по которой вы
должны создать линейный список та же, что и лабораторной работе №3.
Лабораторная работа №6
Тема: Классы
Цель: создание классов в языке программирования C++.
Задачи
Напишите программу, которая позволяет создать простой класс по теме,
указанной ниже, имея в качестве функций (метод) чтение и отображение каждого
из полей, а также функцию, которая вычисляет значение какого-то поля
(например, для конвертирования цены из Евро в леях). Класс должен содержать,
по меньшей мере, три конструктора (один должен быть без параметров, другойсо всеми заданными параметрами, а третий- всего лишь с некоторыми
параметрами, в зависимости от темы. Тема, по которой вы должны создать класс
та же, что и лабораторной работе №3. Перегрузите как минимум два оператора
(например, «==» для проверки равенства и «+» для сложения двух объектов класса
или объекта класса с числом.
Лабораторная работа №7
Тема: Наследование
Цель: использование наследования при работе с классами в язык
программирования C++.
Задачи
Напишите программу, которая позволяет создавать класс, который
наследует поля и методы класса, созданного в предыдущей лабораторной
работе, но также добавляет некоторые собственные свойства, создавая и
соответствующие конструкторы (которые соответствуют конструкторам
основного класса), а затем создайте класс, который наследует
характеристики второго класса, имея необходимые конструкторы. Тема, на
основе которого необходимо создать производные классы, а также новые
обязательные поля, указаны в варианте, но разрешается создавать и другие
производные классы, которые логически связаны с основным классом, в
зависимости от фантазии студентов.
1) Mастеранды (имя специализации, тема магистерской диссертации) и
Докторанты (код специализации, руководитель докторской диссертации)
2) Песни для Шоу-Бизнеса (популярность исполнителя), Рэп (кол. скачивании)
3) Администрация (категория менеджера, кол. людей в руководстве) и
Владельцы (тип владельца, процент доступных акций)
4) Автомобили с Автоматической Коробки Передач (количество передач,
количество передач заднего хода) и Автомобили с GPS и Автоматической
Коробкой Передач (тип GPS)
5) Мобильные Телефоны с 4G (скорость интернета, присутствие Wi-Fi) и
Мобильные Телефоны с 4G с Максимальной Скоростью Интернета
(используемая технология)
6) Молочные Товары (производящая компания), соответственно Сыры
(процентное содержание жира, тип)
7) Документальные Фильмы (область, присутствие художественных элементов)
и Фильмы (шоу) в Реальном Времени (тема, актеры)
8) Международные Маршруты (страна назначения, валюта страны назначения) и
Маршруты с Международной Точки Отправления и Назначения (страна
отправления, валюта страны отправления)
9) Группы Пользователей (название группы, права), соответственно
Администратор (срок действия пароля)
10) Ученики
из
Профессионально-Технических
Учебных
Заведений
(специальности, стипендия) и Ученики Колледжей (код специальности,
название специальности)
11) Интернет Магазин Бытовой Техники (область, подобласть) и ИнтернетМагазин Компьютеров (частота процессора, объём оперативной памяти)
12) Завод Консервов для Вывоза за Границу (принимающей страны, валюта
страны-получателя) и Завод Консервов из Натуральных Продуктов,
Предназначенные для Вывоза за Границу (название натурального продукта,
срок хранения)
13) Ноутбуки (компания производитель, диагональ экрана) и Планшеты
(операционная система, разрешение веб-камеры)
14) Персонаж 1 и 2 (два класса по выбору студента)
15) Кредитные Банки (менеджер кредитного сектора), соответственно, Банки
Предоставляющие Кредиты для Сельского Хозяйства (процентная ставка по
кредиту, срок кредита)
16) Голливудские актеры (средняя плата за съемку) и Голливудские Комические
Актеры (любимый режиссер)
17) Microsoft Windows (самые популярные версии) и Windows NT соответственно
(периодичность новых выпусков или обновлений)
18) Страны Европы (площадь, валюта), соответственно Страны Европейского
Союза (год присоединения к ЕС)
19) Командные Виды Спорта (количество игроков в команде), Спорт с Мячом (тип
мяча, вес)
20) Умные Часы (используемая технология, совместимые операционные системы)
и Smartwatch от Samsung (гарантийный срок (в месяцах), наличие Allways on
Display)
Лабораторная работа №8
Тема: Абстрактные Классы
Цель: использование абстрактных классов в язык программирования C++.
Задачи
Напишите программу, которая создает абстрактный класс, а затем
использует этот класс в процессе наследования и полностью ее
реализовывает. Приведите также пример полиморфизма.
1) Площадь геометрических фигур (длина, ширина, абстрактный метод площадь()) и
производные классы Площадь Прямоугольника и Площадь Квадрата.
2) Коробка (длина, ширина, высота и абстрактный метод объем()) и производные
классы Коробка в Виде Прямоугольного Параллелепипеда и Коробка в Виде Куба.
3) Длина Геометрических Фигур (длина, ширина, абстрактный метод длина()) и
производные классы Длина Прямоугольника и Длина Равнобедренного
Треугольника.
4) Обмен Валют (сумма, валюта, абстрактный метод конверсия()) и производные
классы Обмен Леев в Евро и Обмен Евро в Леях (в первом случае сумма в леях, в во
втором- в Евро).
5) Преобразование Длины (длина, абстрактный метод преобразование()) и производные
классы Преобразование Сантиметров в Дюймы и Преобразование Дюймов в
Сантиметры (в первом случае длина в см, а во втором- в дюймах).
6) Кредит (начальная сумма, месячный платеж и абстрактный метод итоговаяСумма())
и производные классы 12-месячный Кредит и 24-месячный Кредит. В абстрактном
методе должна отображаться общая сумма продукта, зная первоначально
оплаченную сумму, ежемесячный платеж и предельный срок платежа.
7) Депозит (начальная сумма, ставка, абстрактный метод итоговаяСумма()) и
производные классы Депозит на 12 Месяцев и Депозит на 6 Месяцев. Абстрактный
метод должен рассчитать конечную сумму клиента за деньги, внесенные в указанный
период с указанным процентом. Процентная ставка считается фиксированной на
протяжении всего периода.
8) Типография (количество страниц, цена печати монохромной страницы, абстрактный
метод Стоимость()) и производные классы Цветная Газета и Монохромная Газета.
Стоимость печати цветной страницы в четыре раза выше черно-белой страницы.
9) Цена Квартиры (размер комнаты, цена m2, абстрактный метод стоимость()) и
производные классы Однокомнатные Квартиры и Двухкомнатные Квартиры.
Абстрактный метод должен рассчитать цену квартиры, если мы считаем, что она
имеет одну или две комнаты (считается, что кухня вместе с коридором и туалетом
имеют тот же размер, что и комнаты), зная цену за квадратный метр и площадь
помещения.
10) Объем Конических Геометрических Корпусов (радиус, высота, абстрактный метод
объем()) и производные классы Объем Конуса и Объем Цилиндра.
Лабораторная работа №9
Тема: Шаблоны
Цель: использование шаблонов в язык программирования C++.
Задачи
Напишите программу, которая создает шаблонную функцию и
параметризованный класс, а затем приведите примеры их использования.
1. а) Создать шаблонную функцию, меняющую порядок элементов следующим образом: первая
половина списка смещается в конец, а вторая в начало. Например: 1 2 3 4 5 6 - 4 5 6 1 2 3.
Функция должна работать с массивом любой длины. Если количество элементов нечетное, то
средний элемент обрабатывать не надо.
b) Создать параметризированный класс Stack. Класс должен содержать конструкторы,
деструктор, а также функции push, pop, empty, full и операторы ввода/вывода. Для выделения
памяти использовать оператор new.
2. а) Создать шаблонную функцию, меняющую порядок элементов попарно. Например: 1 2 3 4
5 6 - 2 1 4 3 6 5. Функция должна работать с массивом любой длины. Если количество элементов
нечетное, то последний элемент обрабатывать не надо.
b) Создать параметризированный класс Vector. Класс должен содержать конструкторы,
деструктор, функции getLength, операторы [], +, - и операторы ввода/вывода. Для выделения
памяти использовать оператор new.
3. а) Создать шаблонную функцию, подсчитывающую количество повторений заданного
параметра в списке. Например: список - 0 2 3 4 3 6, параметр - 3, результат - 2. Функция должна
работать с массивом любой длины.
b) Создать параметризированные классы List и ListItem. Классы должны содержать
конструкторы, деструкторы, функции add, in, remove, getLength, операторы [] и ввода/вывода.
4. а) Создать шаблонную функцию поиска по заданному ключу. Функция возвращает позицию
первого подходящего элемента. На пример: список - 0 2 3 4 3 6, параметр - 2, результат - 1. В
случае отсутствия подходящего элемента вернуть код ошибки. Функция должна работать с
массивом любой длины.
b) Создать параметризированный класс Queue - очередь. Класс должен содержать
конструкторы, деструктор, функции add, in, get, getLength, операторы [] и ввода/вывода.
5. а) Создать шаблонную функцию поиска второго по величине элемента списка. Например:
список - 0 2 3 4 3 6, результат - 4. Функция должна работать с массивом любой длины.
b) Создать параметризированный класс Set - множество. Класс должны содержать
конструкторы, деструктор, функции add, in, remove, getLength, операторы “+” - объединение,
“*” - пересечение, “-” - разность и операторы ввода/вывода.
6. а) Создать шаблонную функцию сортировки по возрастанию пузырьковым методом.
Функция должна работать с массивом любой длины.
b) Создать параметризированный класс Map – ассоциативный список, который содержит поля
ключ и значение. Одному ключу соответствует одно значение. Класс должен содержать
конструкторы, деструктор, функции add, removeByKey, getLength, getByKey, getByValue,
операторы [] и ввода/вывода.
7. а) Создать шаблонную функцию, изменяющую попарно элементы массива следующим
образом: первый элемент будет равняться сумме пары, а второй разности пары. Например:
список - 0 2 3 4 3 6, результат 2 –2 7 –1 9 –3.
b) Создать параметризированный класс Matrix – матрица. Класс должен содержать
конструкторы, деструктор, функции getRows, getCols, операторы [], +, -, * и ввода/вывода.
8. а) Создать шаблонную функцию, меняющую порядок элементов на обратный. Например: 1 2
3 4 5 6 - 6 5 4 3 2 1. Функция должна работать с массивом любой длины.
b) Создать параметризированный класс Tree – бинарное дерево. Класс должен содержать
конструкторы, деструктор, функции add, in, функции обхода дерева и операторы ввода/вывода.
9. а) Создать шаблонную функцию, подсчитывающую количество элементов, значение которых
больше заданного параметра. Например: список - 0 2 3 4 3 6, параметр - 5, результат - 1. Функция
должна работать с массивом любой длины.
b) Создать параметризированный класс Stack. Класс должен содержать конструкторы,
деструктор, а также функции push, pop, empty и операторы ввода/вывода. Для выделения памяти
использовать оператор new, по n элементов.
10. а) Создать шаблонную функцию сортировки элементов массива по убыванию методом
вставки. Функция должна работать с массивом любой длины.
b) Создать параметризированный класс MultiMap – мульти-ассоциативный список, который
содержит поля ключ и список значений. То есть, одному ключу может соответствовать
несколько значений. Класс должен содержать конструкторы, деструктор, функции add,
removeByKey, getLength, getByKey, getByValue, операторы [] и ввода/вывода.
11. а) Создать шаблонную функцию, подсчитывающую количество элементов, значение
которых меньше заданного параметра. На пример: список - 0 2 6 4 3 3, параметр - 3, результат 2. Функция должна работать с массивом любой длины.
b) Создать параметризированный класс PriorityQueue – приоритетная очередь. Каждый элемент
очереди имеет определенный приоритет и при извлечении выбирается элемент с наибольшим
приоритетом, а элементы с одинаковыми приоритетами - по времени добавления. Класс должен
содержать конструкторы, деструктор, функции add, in, get, getLength, операторы [] и
ввода/вывода.
12. а) Создать шаблонную функцию поиска второго минимального по величине элемента
списка. На пример: список - 0 2 3 4 3 6, результат - 2. Функция должна работать с массивом
любой длины.
b) Создать параметризированный класс Matrix – матрица. Класс должен содержать
конструкторы, деструктор, функции getRows, getCols, операторы [], +=, -=, *= и ввода/вывода.
