Структуры данных и алгоритмы. Вопросы к зачету
- “Качественность” программы – критерии оценки. Функции для оценки времени: точность: секунды, миллисекунды. Понятие об автоматизации тестирования.
- Функция “O”, назначение, свойства, здесь же будет задача: дается несложная программка вроде подсчета суммы элементов массива, необходимо будет определить значение функции ”O” для этого примера.
- Критерии сравнения и классификация алгоритмов сортировки. Ключевая функция. Оптимизация сортировки с помощью индексирования.
- Сортировка методом прямого обмена. Пример кода программы. Взять набор чисел X1, X2, …, Xn и на бумаге отобразить, как будет изменяться данный массив после каждого прохода внешнего цикла.
- Сортировка методом прямой вставки. Пример кода программы. Взять набор чисел X1, X2, …, Xn и на бумаге отобразить, как будет изменяться данный массив после каждого прохода внешнего цикла.
- Сортировка методом прямого выбора. Пример кода программы. Взять набор чисел X1, X2, …, Xn и на бумаге отобразить, как будет изменяться данный массив после каждого прохода внешнего цикла.
- Сортировка методом шейкера. Пример кода программы. Взять набор чисел X1, X2, …, Xn и на бумаге отобразить, как будет изменяться данный массив после каждого прохода внешнего цикла. В чем суть метода сортировки вставки с половинным делением.
- Сортировка методом слияния в случае, когда исходный массив не упорядочен и имеет размер кратный 2^n и в случае, когда размер не кратен этой величине. Также взять набор чисел X1, X2, …, Xn и на бумаге отобразить, как будет изменяться данный массив после каждого прохода внешнего цикла.
- Поиск элемента в массиве: простой перебор, метод половинного деления, эвристический метод поиска. Генерация случайных величин с равномерным и случайным законом распределения.
- Алгоритм поиска “k-ого” по величине элемента массива. Пример кода. На бумаге показать, как будут перемещаться элементы, в ходе “частичной сортировки”, набор чисел: X1,X2, ,Xn…
- Сортировка методом прямого выбора. Пример кода программы. Взять набор чисел X1, X2, …, Xn и на бумаге отобразить, как будет изменяться данный массив после каждого прохода первого внешнего цикла и второго внешнего. Способы расчета “расстояний” для данного алгоритма.
- “Быстрая сортировка”. Пример кода программы. Взять набор чисел X1, X2, …, Xn и на бумаге отобразить, как будет изменяться данный массив на каждом из уровней спуска рекурсии.
- “Пирамидальная сортировка” - Пример кода программы. Взять набор чисел X1, X2, …, Xn и на бумаге отобразить, как будет изменяться данный массив на каждом шаге постройки пирамиды на стадиях прямого и обратного хода.
- Рекурсия. Основные характеристики. Преимущества и недостатки + написать несложную задачку рекурсивным путем рассчитать, например сумму элементов массива или что-то похожее.
- Рекурсия и способ имитации рекурсии с помощью стека. Преимущества. Написать несложную задачку с помощью “имитации рекурсии – стека” рассчитать, например, сумму элементов массива или что-то похожее.
- Динамические структуры данных, определение. Модель представления оперативной памяти. Стек. Виды реализаций стеков (из практической работы), недостатки и плюсы каждой из трех моделей.
- Динамические структуры данных. Список однонаправленный. Очередь. Операции добавления, удаления элементов, поиск в очереди элемента - примеры кода.
- Динамические структуры данных. Список с двумя связями. Дек. Операции добавления, удаления элементов, поиск в очереди элемента - примеры кода.
- Деревья. Способы представления деревьев. Операция добавления в дерево нового узла. Операции прохода по дереву.
- Итераторы и курсоры.