ЭКЗАМЕНАЦИОННАЯ ПРОГРАММА весенний семестр 2008/09 уч. года (58 часов лекций)
1. Уровни описания структур данных.
2. Статические и динамические объекты программ.
3. Ссылочный тип данных.
4. Файл. Функциональная спецификация.
5. Файл. Логическое описание. Физическое представление.
6. Вектор. Функциональная спецификация. Логическое описание и физическое представление.
7. Очередь. Функциональная спецификация.
8. Очередь. Логическое описание и физическое представление (файл).
9. Очередь. Логическое описание и физическое представление (массив).
10. Очередь. Логическое описание и физическое представление (динамическиe объекты).
11. Стек. Функциональная спецификация.
12. Стек. Логическое описание.
13. Стек. Физическое представление (массив).
14. Стек. Физическое представление (динамические объекты).
15. Линейный список. Функциональная спецификация.
16. Линейный список. Логическое описание.
17. Линейный список. Физическое представление. Итераторы.
18. Линейный список. Физическое представление (массив).
19. Линейный список. Физическое представление (динамические объекты).
20. Списки общего вида. Представление и обработка графов.
21. Понятие рекурсии. Рекурсия и итерация. Примеры.
22. Деревья. Двоичные деревья.
23. Двоичное дерево. Функциональная спецификация.
24. Двоичное дерево. Логическое описание. Построение и визуализация.
25. Двоичное дерево. Физическое представление. Прошивка.
26. Алгоритмы обхода деревьев.
27. Особенности представления и обработки деревьев общего вида (преобразование к двоичному, ...).
28. Деревья выражений.
29. Рекурсивные структуры данных и их связь с алгоритмической рекурсией.
30. Деревья поиска.
31. Сбалансированные деревья поиска.
32. Простые методы поиска.
33. Поиск по образцу в последовательностях и таблицах.
34. Алгоритм Кнута-Морриса-Пратта.
35. Алгоритм Бойера-Мура.
36. Алгоритм Рабина-Карпа.
37. Таблицы с прямым доступом.
38. Алгоритмы сортировки.
39. Сортировка вставкой.
40. Сортировка выборкой.
41. Обменные сортировки.
42. Сортировка Шелла.
43. Турнирные сортировки.
44. Сортировка Хоора.
45. Сортировки слиянием.
46. Сравнение методов сортировки.
47. Модульное программирование. Реализация на языке Си.
48. Абстракции в языках программирования.
49. Абстрактные типы данных. Пример модуля АТД ОЧЕРЕДЬ.
50. Экспорт и импорт объектов. Инкапсулированные АТД.
51. Типизация языка программирования. Контроль типов.
52. Средства ослабления типового контроля. Преобразование и передача типов.
53. Полиморфизм операций, отношений и процедур. Родовые модули.
54. Адресный тип. Реализация полиморфизма с помощью адресного типа на языке Си.
55. Процедурный тип данных. Реализация полиморфизма с помощью процедурного типа на языке Си.
56. Понятие об объекте. Реализация полиморфизма в объектной форме на языке Си.
В качестве экзаменационных задач предлагаются задачи на написание программ на языке Си по всем концепциям, алгоритмам и структурам данных теоретического курса и практикума.