Итоговая контрольная работа



Список вопрос к весеннему зачёту

Первая часть вопросов (алгоритмы — с реализацией)

  1. Представление вещественных чисел в памяти ПК. Cтандарт IEEE 754-2008. Типы чисел в С++. Арифметические операции. Обработка последовательностей: подсчёт, сумма, произведение, поиск максимального.
  2. Логический тип и логические операции. Проверка последовательности чисел на наличие элемента с заданными свойствами и на соответствие всех элементов заданному свойству.
  3. Операторы присваивания. Инициализация переменной при поиске максимума и минимума. Поиск местоположения максимума в последовательности за один проход.
  4. Отказ от инициализации переменной для максимума. Поиск максимума и подсчёт количества элементов, равных максимальному.
  5. Вложенные и каскадные условные конструкции. Нахождение трёх максимальных элементов в последовательности за один проход.
  6. Цикл for. Оператор break. Проверка простоты числа. Метод грубой силы.
  7. Цикл while. Оператор continue. Разложение числа на множители. Метод грубой силы.
  8. Операторы new и delete для массива. Решето Эратосфена.
  9. Обычные двумерные массивы в С++. Транспонирование матрицы. Умножение матриц.
  10. Типы целых чисел с явно заданной разрядностью в С++. Проверка упорядоченности массива. Сортировка подсчётом.
  11. Типы строки в С++. Сортировка дурака и сортировка методом пузырька.
  12. Локальные и глобальные переменные. Динамическая память. Указатель в никуда. Разыменование и взятие адреса. Ошибки при работе с памятью. Сортировка выбором.
  13. Адреса и указатели. Двойные указатели. Бестиповые указатели. Размер указателя в байтах. Динамические двухмерные массивы.
  14. Адресная арифметика и доступ к элементам одномерного массива. Сортировка вставками.
  15. Функции в С++. Стек локальных переменных. Передача аргумента по значению и по указателю. Поиск корня уравнения методом двоичного поиска.
  16. Передача массива в функцию и проблема возврата массива из функции. Передача в функцию двумерного массива. Линеаризация двумерного массива ручным расчётом индекса.
  17. Структуры struct (пользовательские типы данных). Размер структуры в байтах. Массив, структура и указатель как поля структуры. Указатель на структуру. Оператор "стрелка". Массив структур. Устойчивость сортировок.
  18. Стек и очередь.
  19. Расширяемый массив (std::vector). Асимптотика доступа к произвольному элементу, добавления элемента в конец, добавления элемента в начало. Реализации стека и очереди на std::vector.
  20. Контейнер std::list. Доступ к элементам через итератор. Цикл for C++11. Асимптотика доступа к произвольному элементу, добавления элемента в конец, добавления элемента в начало. Реализации стека и очереди на std::list.

Вторая часть вопросов (алгоритмы "на пальцах", без реализации)

  1. Односвязный список. Асимптотика доступа к произвольному элементу, добавления элемента в конец, добавления элемента в начало.
  2. Двухсвязный список. Асимптотика доступа к произвольному элементу, добавления элемента в конец, добавления элемента в начало.
  3. Бинарный поиск в упорядоченном массиве.
  4. Поразрядная сортировка.
  5. Рекурсия. Крайний и рекуррентный случаи. Рекуррентный алгоритм Евклида.
  6. Рекурсия. Быстрое возвдение в степень.
  7. Рекурсия. Дерево вызовов. Ханойские башни.
  8. Рекурсия. Рекурсивная генерация всех чисел длины M.
  9. Генерация всех перестановок в массиве.
  10. Принцип "Разделяй и властвуй". Умножение Карацубы.
  11. Быстрая сортировка Тони Хоара. Выбор опорного элемента.
  12. Сортировка слиянием. Асимптотика по памяти.
  13. Динамическое программирование.
  14. Кузнечик: количество траекторий.
  15. Кузнечик: траектория минимальной стоимости.
  16. Алгоритм укладки рюкзака (дискретный).
  17. Наибольшая возрастающая подпоследовательность.
  18. Вычисление расстояния Левенштейна.
  19. Наибольшая общая подпоследовательность.
  20. Префикс-функция. Алгоритм Кнута-Морриса-Пратта.
  21. Асимптотики. Привести примеры алгоритмов О(1), О(N), O(logN), O(NlogN), O(N^2) и т.д.