Итак, друзья, пришло время сессии, потому я выкладываю вопросы к экзамену по методам программирования:
ВОПРОСЫ К ЭКЗАМЕНУ по курсу «Методы программирования» 1. Понятие структуры данных. Элементарные структуры данных. 2. Простые структуры данных: методы реализации, особенности в различных языках программирования. 3. Массив: спецификация, методы реализации, особенности в различных языках программирования. 4. Запись, объединение: спецификация, методы реализации, особенности в различных языках программирования. 5. Линейный список: спецификация, методы реализации, особенности в различных языках программирования. 6. Множество: методы реализации, особенности в различных языках программирования. 7. Стек: спецификация, методы реализации. Основные операции для стека. 8. Очередь: спецификация, методы реализации. Основные операции для очереди. 9. Дек: спецификация, методы реализации. Основные операции для дека. 10. Многосвязный список: спецификация, методы реализации. Циклические, двусвязные списки. 11. Бинарное дерево: определение, спецификация, методы реализации. 12. Двоичные деревья поиска, алгоритмы обхода. 13. Характеристики алгоритмов, способы их оценивания. 14. Основные понятия сортировки. Классификация алгоритмов сортировки. Понятие временной сложности алгоритма. 15. Нижняя оценка временной сложности класса алгоритмов сортировки сравнениями. 16. Сортировка простыми вставками: описание алгоритма, оценка временной сложности. 17. Сортировка Шелла: описание алгоритма, временная сложность при некоторых значениях шагов алгоритма. 18. Сортировка вставками в дерево: описание алгоритма, оценка временной сложности. 19. Сортировка простым выбором: описание алгоритма, оценка временной сложности. 20. Сортировка выбором из дерева (турнирная): описание алгоритма, оценка временной сложности. 21. Сортировка выбором из дерева (пирамидальная): описание алгоритма, оценка временной сложности. 22. Сортировка простыми обменами: описание алгоритма, оценка временной сложности. Пузырьковая сортировка и шейкерная сортировки. 23. Быстрая сортировка Хоара: описание алгоритма, оценка временной сложности. 24. Сортировка слиянием: описание алгоритма, оценка временной сложности, разновидности. 25. Лексикографическая сортировка: описание алгоритма, оценка временной сложности, разновидности. 26. Распределяющая сортировка: описание алгоритма, оценка временной сложности, разновидности. 27. Внешняя сортировка. Сбалансированное двухпутевое слияние. Генерация начальных цепочек. 28. Стандартная библиотека шаблонов STL. Состав и примеры использования.
Примечание: описание каждого алгоритма должно сопровождаться примером сортировки для конкретной последовательности данных.
Дополнительные вопросы:
1. Построить двоичное дерево поиска для данной последовательности. 2. В чем отличие односвязного линейного списка от двусвязного? 3. В каких изучаемых в курсе алгоритмах используются при реализации стеки и очереди? 4. Можно ли хранить двоичное дерево в массиве? 5. Новый элемент в двоичное дерево поиска вставляется в лист или внутренний узел? 6. Что происходит при удалении элемента из двоичного дерева поиска? 7. Можно ли придумать алгоритм сортировки сравнениями со средней трудоемкостью O(n)? (ответ обосновать) 8. Что такое пирамида? Является ли данное дерево пирамидой? 9. Какие структуры данных используются в алгоритме лексикографической сортировки? 10. Какой алгоритм как вспомогательный используется при формировании цепочек во внешней сортировке? 11. Как удобно хранить пирамиду в памяти компьютера? 12. Как удобно хранить дерево турнирной сортировки в памяти компьютера? 13. Какой объем памяти используется при реализации турнирной сортировки? 14. Какой алгоритм можно использовать для выбора первых K минимальных элементов? 15. Что такое шейкер–сортировка? 16. Что такое медиана в алгоритме быстрой сортировки? Как она выбирается? 17. Что такое m–путевое слияние?
