Файл: Экзаменационные вопросы по курсу Структуры и алгоритмы обработки данных.pdf

Экзаменационные вопросы по курсу
«Структуры и алгоритмы обработки данных»
(Весенний семестр, 2023 г., 1-й курс)
1. Понятие алгоритма. Свойства алгоритмов. Показатели эффективности алгоритмов.
Анализ времени выполнения алгоритмов.
2. Асимптотический анализ вычислительной сложности алгоритмов. Анализ вычисли- тельной сложности в худшем, среднем и лучшем случаях. Асимптотические обозначе- ния O, Θ, Ω. Основные классы сложности алгоритмов.
3. Анализ рекурсивных алгоритмов. Стек вызовов функций. Виды рекурсии. Решение ре- куррентных уравнений. Основная теорема (master method). Анализ эффективности ал- горитма сортировки слиянием.
4. Задача сортировки. Виды алгоритмов сортировки: устойчивые алгоритмы, сортировки сравнением, сортировки на месте (in-place). Сортировка вставками. Сортировка слия- нием. Быстрая сортировка. Пирамидальная сортировка. Поразрядная сортировка.
5. Поиск элемента по ключу. Линейный поиск. Бинарный поиск. Экспоненциальный по- иск (galloping search).
6. Абстрактный тип данных «список». Связный список. Односвязный список, двусвязный список. Основные операции и их вычислительная сложность.
7. Стек. Способы реализации стека. Основные операции и их вычислительная сложность.
8. Очередь. Способы реализации очереди. Основные операции и их вычислительная сложность. Реализация очереди на основе циклического массива. Двухсторонняя оче- редь (дек, deque).
9. Абстрактный тип данных «словарь». Основные операции словаря. Бинарные деревья поиска. Основные операции, их вычислительная сложность. Анализ эффективности бинарного дерева поиска в среднем и худшем случае.
10. Абстрактный тип данных «словарь». Хеш-таблицы. Основные операции хеш-таблицы.
Хеш-функции. Методы разрешения коллизий.
11. Очереди с приоритетом. Бинарные кучи. Реализация бинарной кучи на основе масси- ва. Построение бинарной кучи за время O(n).
12. Графы. Виды графов. Способы представления графов в памяти. Реализация графа на основе матрицы смежности.
13. Обход графа. Обход в глубину (DFS). Обход в ширину (BFS).
14. Задача поиска кратчайшего пути в графе. Постановки задачи о кратчайшем пути. Ал- горитмы поиска кратчайшего пути в графе. Алгоритм Дейкстры. Вычислительная сложность алгоритма Дейкстры.
15. Остовные деревья минимальной стоимости (minimum spanning tree, MST). Алгоритмы построения MST. Система непересекающихся множеств. Алгоритм Крускала. Алгоритм
Прима.
16. Основные методы разработки алгоритмов. Метод «грубой силы» (brute force). Метод декомпозиции. Алгоритмы, основанные на методе декомпозиции.
17. Методы разработки алгоритмов. Динамическое программирование. «Жадные» алго- ритмы (greedy algorithms). Код Хаффмана. Поиск с возвратом (backtracking). Задача о восьми ферзях. Задача о раскраске графа в k цветов. Локальный поиск.
18. Трудноразрешимые задачи. Классы сложности P. Класс сложности NP. Гамильтонов цикл. Задача коммивояжёра. Задача упаковки корзин. Сводимость задач. NP-полнота.

Вопрос 1. Понятие алгоритма. Свойства алгоритмов. Показатели эффективности
алгоритмов. Анализ времени выполнения алгоритмов.
Алгоритм — это последовательность шагов, выполняемых для решения определенной задачи.
Свойства алгоритма:
Дискретность – алгоритм состоит из чётких команд, которые выполняются в строгой последовательности.
Конечность (результативность, финитность) – алгоритм должен заканчиваться после выполнения конечного числа инструкций.
Детерминированность – каждый шаг алгоритма должен быть однозначно определен – записан на формальном языке исполнителя. Детерминированность обеспечивает совпадение результатов, получаемых при многократном выполнении алгоритма, на одном и том же наборе входных данных.
Массовость – алгоритм решения задачи должен быть применим для некоторого класса задач, различающихся лишь значениями входных данных.
Показатели эффективности алгоритмов зависят от:
1.
Количество выполняемых операций - сколько времени занимает выполнение алгоритма.
2. Потребление памяти - сколько памяти используется для выполнения алгоритма.
3. Сложность алгоритма - количественная оценка трудоемкости алгоритма.
Анализ времени выполнения алгоритмов — это процесс измерения времени, затрачиваемого на выполнение алгоритма. Он позволяет оценить эффективность алгоритма и выбрать наиболее подходящий для решения задачи.
Время выполнения зависит от размера входных данных, сложности алгоритма и скорости работы компьютера.
Эффективность алгоритма оценивается по количеству операций и используемой памяти. В большинстве случаев сложность алгоритма зависит от размера данных на вход

Вопрос 2. Асимптотический анализ вычислительной сложности алгоритмов. Анализ
вычислительной сложности в худшем, среднем и лучшем случаях. Асимптотические
обозначения O, Θ, Ω. Основные классы сложности алгоритмов.
Асимптотический анализ позволяет оценивать скорость роста функций T(n) при стремлении размера входных данных к бесконечности (при n → ∞).
Анализ вычислительной сложности:
Анализ в худшем случае оценивает максимальное время выполнения алгоритма для любых входных данных.
Анализ в среднем случае учитывает вероятностное распределение входных данных и позволяет получить среднее время выполнения алгоритма.
Анализ в лучшем случае оценивает минимальное время выполнения алгоритма при оптимальных входных данных.
Асимптотические обозначения O, Ω, и Θ используются для описания роста времени выполнения алгоритма в зависимости от размера входных данных.
O - указывает на верхнюю границу роста времени выполнения алгоритма
Ω - на нижнюю границу роста времени выполнения алгоритма
Θ - на точную оценку роста времени выполнения

Вопрос 3. Анализ рекурсивных алгоритмов. Стек вызовов функций. Виды рекурсии.
Решение рекуррентных уравнений. Основная теорема (master method). Анализ
эффективности алгоритма сортировки слиянием.
Рекурсивный алгоритм — это алгоритм, который вызывает сам себя для решения подзадач.
Стек вызовов — это структура данных, которая используется для хранения информации о вызовах функций в программе.
Принцип его работы "последним пришел - первым ушел" (LIFO).
Когда функция вызывается в программе, информация о ее выполнении сохраняется в стеке вызовов. Эта информация включает в себя адрес возврата (адрес, на который должно вернуться выполнение программы после завершения функции), значения параметров функции и локальные переменные функции.
Виды рекурсии:

Прямая — когда функция вызывает себя

Косвенная — когда функция вызывает внутри себя другую, которая когда-то вызовет первую

Линейная — когда при вычислении результата функции нужно вызвать себя один раз.

Каскадная — когда функция вызывает себя несколько раз
Решение рекуррентных уравнений - это метод нахождения времени выполнения рекурсивного алгоритма. Рекуррентное уравнение описывает время выполнения алгоритма в зависимости от размера входных данных и количества вызовов функции.
Основная теорема (master method) - это формула для решения рекуррентных уравнений вида T(n) = aT(n/b) + f(n), где a - количество вызовов функции, b - отношение размера входных данных при каждом вызове функции к общему размеру входных данных, f(n) - время выполнения операций, не связанных с вызовом функции. Основная теорема позволяет определить асимптотическую сложность рекурсивного алгоритма.
Анализ эффективности алгоритма сортировки слиянием. Сортировка слиянием - это алгоритм сортировки, который использует рекурсивный подход. Алгоритм разделяет массив на две половины, сортирует каждую половину рекурсивно и затем объединяет две отсортированные половины в один отсортированный массив. Время выполнения сортировки слиянием составляет O(n log n).

Вопрос 4. Задача сортировки. Виды алгоритмов сортировки: устойчивые алгоритмы,
сортировки сравнением, сортировки на месте (in-place). Сортировка вставками.
Сортировка слиянием. Быстрая сортировка. Пирамидальная сортировка. Поразрядная
сортировка.
Задача сортировки заключается в упорядочивании элементов массива или списка по возрастанию или убыванию.
Виды алгоритмов сортировки:
-
Устойчивые алгоритмы - сохраняют относительный порядок элементов с одинаковыми значениями. Например, сортировка вставками и сортировка слиянием.
-
Сортировки сравнением - сравнивают элементы между собой и меняют их местами в соответствии с заданным порядком. Например, сортировка пузырьком, сортировка
вставками, сортировка выбором, быстрая сортировка, сортировка слиянием.
-
Сортировки на месте (in-place) - не используют дополнительную память для хранения данных. Например, быстрая сортировка, сортировка пузырьком.
Сортировка вставками - алгоритм, который проходит по массиву и вставляет каждый элемент в отсортированную последовательность слева направо. Время выполнения составляет O(n^2).
Сортировка слиянием - алгоритм, который разделяет массив на две половины, сортирует каждую половину рекурсивно и затем объединяет две отсортированные половины в один отсортированный массив. Время выполнения составляет O(n log n).
Быстрая сортировка - алгоритм, который выбирает опорный элемент, разделяет массив на две части: элементы меньше опорного и элементы больше опорного, и рекурсивно сортирует каждую часть. Время выполнения в среднем составляет O(n log n), в худшем случае - O(n^2).
Пирамидальная сортировка - алгоритм, который использует структуру данных "куча" (heap) для упорядочивания элементов. Время выполнения составляет O(n log n).
Поразрядная сортировка - алгоритм, который сортирует элементы по разрядам, начиная с младшего. Время выполнения зависит от количества разрядов и основания системы счисления. В худшем случае время выполнения составляет O(kn), где k - количество разрядов.

Вопрос 5. Поиск элемента по ключу. Линейный поиск. Бинарный поиск.
Экспоненциальный поиск (galloping search).
Поиск элемента по ключу — это операция, которая позволяет находить элемент в упорядоченном массиве или списке по его ключу (значению).
Алгоритмы поиска элемента по ключу:
Линейный поиск осуществляется путем последовательного перебора всех элементов массива или списка пока не будет найден элемент с заданным ключом.
Бинарный поиск основан на принципе деления массива или списка пополам на каждой итерации. Если элемент с заданным ключом находится в левой половине массива, то поиск продолжается в ней, в противном случае - в правой.
Экспоненциальный поиск (galloping search) — это модификация бинарного поиска, которая позволяет быстрее находить элементы в больших массивах или списках. Он основан на идее увеличения шага поиска при каждой итерации вместо фиксированного деления пополам.
Например, на первой итерации шаг может быть равен 1, на второй - 2, на третьей - 4 и т.д. Это позволяет быстрее находить элементы, находящиеся ближе к началу или концу массива или списка.
Линейный алгоритм является простым и универсальным, но его время выполнения может быть довольно большим при больших объемах данных.
Бинарный алгоритм является более эффективным, чем линейный поиск, но предполагает, что данные уже упорядочены.

Вопрос 6. Абстрактный тип данных «список». Связный список. Односвязный список,
двусвязный список. Основные операции и их вычислительная сложность.
Абстрактный тип данных «список» - структура данных, которая хранит набор элементов, расположенных в определенном порядке. Список может быть реализован как массив или как связный список.
Связный список — это структура данных, которая состоит из узлов, каждый из которых содержит элемент списка и ссылку на следующий узел. Первый узел называется головой списка, а последний - хвостом. Если ссылка на следующий узел отсутствует, то это означает, что текущий узел является последним в списке.
Односвязный список — это связный список, в котором каждый узел содержит только одну ссылку на следующий узел. Такой список можно обходить только в одном направлении - от головы к хвосту.
Двусвязный список — это связный список, в котором каждый узел содержит две ссылки: на следующий и на предыдущий узлы. Такой список можно обходить в обоих направлениях - как от головы к хвосту, так и наоборот.
Основные операции над списками и их вычислительная сложность:
1. Вставка элемента в начало списка (push) - O(1)
2. Вставка элемента в конец списка (append) - O(1) для двусвязного списка, O(n) для односвязного списка
3. Удаление элемента из начала списка (pop) - O(1)
4. Удаление элемента из конца списка (remove) - O(n) для односвязного списка, O(1) для двусвязного списка
5. Поиск элемента в списке (search) - O(n)
В целом, связный список является более гибкой структурой данных, чем массив, так как позволяет быстро вставлять и удалять элементы в середине списка. Однако, его преимущество может быть скомпенсировано более высокой вычислительной сложностью операций поиска и доступа к элементам по индексу.

Вопрос 7. Стек. Способы реализации стека. Основные операции и их вычислительная
сложность.
Стек - это абстрактный тип данных, который представляет собой упорядоченные элементы, который работает по принципу "последним пришел - первым вышел" (LIFO - last in, first out).
Т.е. последний добавленный элемент будет первым удаленным.
Способы реализации стека:
Реализация стека с помощью массива:
- push - добавление элемента в конец массива, вычислительная сложность O(1)
- pop - удаление последнего элемента из массива, вычислительная сложность O(1)
- top - получение значения последнего элемента без его удаления, вычислительная сложность O(1)
Реализация стека с помощью связного списка:
- push - добавление нового узла в начало списка, вычислительная сложность O(1)
- pop - удаление первого узла из списка, вычислительная сложность O(1)
- top - получение значения первого узла без его удаления, вычислительная сложность O(1)
Реализация на массиве обычно более эффективна по памяти и быстрее при доступе к элементам по индексу, но может быть неэффективной при частых операциях вставки и удаления элементов. Реализация на связном списке более эффективна при операциях вставки и удаления элементов, но менее эффективна при доступе к элементам по индексу.
Основные операции над стеком и их вычислительная сложность:
1. push - добавление элемента в стек, O(1)
2. pop - удаление последнего элемента из стека, O(1)
3. top - получение значения последнего элемента без его удаления, O(1)
4. isEmpty - проверка, пуст ли стек, O(1)

Вопрос 8. Очередь. Способы реализации очереди. Основные операции и их
вычислительная
сложность. Реализация очереди на основе циклического массива. Двухсторонняя
очередь (дек, deque).
Очередь — это структура данных, которая представляет собой последовательность элементов, где добавление новых элементов происходит в конец очереди, а удаление - в ее начале. Очередь работает по принципу "первым пришел - первым ушел" (FIFO - First In First
Out).
Способы реализации очереди:
1. На основе массива - элементы хранятся в массиве, а индекс начала и конца очереди указывают на соответствующие элементы массива.
2. На основе связного списка - каждый элемент очереди ссылается на следующий элемент, а последний элемент ссылается на null.
Основные операции над очередью и их вычислительная сложность:
1. Enqueue - добавление элемента в конец очереди. O(1)
2. Dequeue - удаление элемента из начала очереди. O(1)
3. Peek - получение элемента из начала очереди без его удаления. O(1)
4. Count - количество элементов в очереди. O(1)
5. Size
– возвращает количество элементов в очереди
6. Clear
– очищает очередь
Реализация очереди на основе циклического массива:
Циклический массив позволяет использовать всю доступную память, не переписывая элементы в начало массива. Для этого используются два индекса: начало и конец очереди.
Если конец очереди достигает конца массива, то он переносится на начало массива.
Двухсторонняя очередь (дек, deque):
Дек - это структура данных, которая позволяет добавлять и удалять элементы как в начале, так и в конце очереди. Она работает по принципу "первым пришел - последним ушел" (FIFO) и "последним пришел - последним ушел" (LIFO - Last In First Out). Дек может быть реализован как на основе массива, так и на основе связного списка.
Основные операции над деком и их вычислительная сложность:
1. AddFirst - добавление элемента в начало очереди. O(1)
2. AddLast - добавление элемента в конец очереди. O(1)
3. RemoveFirst - удаление элемента из начала очереди. O(1)
4. RemoveLast - удаление элемента из конца очереди. O(1)
5. PeekFirst - получение элемента из начала очереди без его удаления. O(1)
6. PeekLast - получение элемента из конца очереди без его удаления. O(1)