Вопросы к экзамену по дисциплине «Основы компьютерных наук»
направление 010200.62 – «Математика и компьютерные науки»
физико-математический факультет, очное отделение
III курс, 6 семестр
уч. год
1. Понятие алгоритма. Виды алгоритмов: механический, вероятностный, эвристический, вспомогательный (подчиненный).
2. Эффективные алгоритмы. Основные принципы создания эффективных алгоритмов.
3. Сложность алгоритмов. Оценка сложности алгоритмов. Функции сложности алгоритмов.
4. Итеративные и рекурсивные алгоритмы. Пример.
5. Методы разработки алгоритмов: декомпозиция, динамическое программирование, «жадные» методы, поиск с возвратом, локальный поиск.
6. Понятие структуры данных. Физическая и логическая структура данных. Классификация структур данных: простые и структурированные, по признаку изменчивости, несвязные и связанные, линейные и нелинейные.
7. Простые структуры данных: целые, вещественные, символьный, логический, диапазон, перечислимый, указатель.
8. Статические структуры данных: вектор, массивы, множества, записи, таблицы.
9. Файловые структуры данных. Физическая и логическая организация файла. Файлы последовательного, прямого, комбинированного доступа.
10. Полустатические структуры данных: стеки, очереди, деки, строки.
11. Динамические структуры данных: линейные связанные списки, разветвленные связанные списки, графы, деревья.
12. Абстрактные типы данных.
13. Основные принципы объектно-ориентированного программирования.
14. Понятие объекта. Построение объекта.
15. Понятие класса. Организация и структура класса. Конструктор и деструктор.
16. Понятие метода. Динамические, виртуальные и абстрактные методы.
Составитель: ст. преподаватель кафедры информатики, ТиМОИ
Зав. кафедрой информатики, ТиМОИ: к. п. н., доцент
