Вопросы для теоретической части зачета 28 декабря 2016 г.

  1. Цели и задачи программирования. Парадигмы программирования.
  2. Языки программирования низкого и высокого уровня. Трансляторы.
  3. Данные. Машинное представление целых чисел.
  4. Машинное представления нецелых чисел. Числа с плавающей точкой, их устройство и особенности.
  5. Машинное представление символов. Кодировки. Строки, их машинное представление и операции над ними.
  6. Быстродействие алгоритмов.
  7. Метод «пузырька», сортировка выбором и вставками. Сортировка Шелла.
  8. Рекурсивные и нерекурсивные алгоритмы. Принцип «разделяй и властвуй». Алгоритмы поиска элементов в массиве.
  9. Быстрая сортировка Хоара (Quicksort). Пирамидальная сортировка (Heapsort).
  10. Сортировка слиянием. Сортировка подсчетом. Поразрядная сортировка. Карманная сортировка.
  11. Алгоритмы поиска подстроки в строке: метод грубой силы, алгоритм Боуэра-Мура, алгоритм Рабина-Карпа.
  12. Модули. Реализация модулей в C.
  13. Составные типы данных. Адресация в многомерных массивах.
  14. Понятие об абстрактном типе данных. Стеки и очереди. Связанные списки.
  15. Дерево как структура данных. N-арные и двоичные деревья.
  16. Деревья поиска. Реализация операций над ними.
  17. Балансировка деревьев поиска. АВЛ-деревья. 2-3-4 деревья. Красно-черные деревья.
  18. Очередь с приоритетом, двоичная куча.
  19. Хеш-таблицы: идея и интерфейс. Хеш-функции и требования к ним. Решение проблемы конфликтов с помощью динамического массива списков.
  20. Открытая адресация в хеш-таблице. Кукушиное хеширование. Сходства и отличия между хеш-таблицей и деревом поиска. Криптографические хеш-функции.
  21. Алгоритмы сжатия данных. Алгоритм RLE. Метод Хаффмана.
  22. Алгоритмы LZ77 и LZW.