Практикум по информатике (984128), страница 5
Текст из файла (страница 5)
Список свободньзх элементов. Линейный список на динамических структурах. Дерево и двоичное дерево. Иницшшизация, добавление узла, удаление узла, визуализация. Обход двоичного дерева (прямой, обратный, концевой). Обход дерева общего вида в глубину, в ширину. Прошитые деревья.
Обход дерева с исполъзованисм стека. Примеры: рекурсивное вычисление высоты дерева, вычисление высоты дерева без рекурсии с использованием стека или прошивки. Представление выражения в виде дерева. Польская инверсная запись. Обработка и вычисление выражений (рекурсия или стек). Поиск путей в графе (в глубину с рекурсией, в глубину без рекурсии, в ширину).
Хэш-табицы. Абстрактные типы данных. Противопоставление разреженным матрицам. АТД на Паскале. Реализация стека и дека на массиве. Пример рекурсивной обработки стека (вставка и удаление элемента с заданным номером). Визуализация Ханойских башен. Стек: модуль определений, модуль реализации и программный модуль с меню. Сортировка таблиц (внутренняя). Сортировка последовательностей (внешняя). !. 2. 4.
б. 7. 8. 9 10. 11. 12. 13. 14. 15. 16. Лабораторные работы (64 часа) 20. Обработка текстовых файлов в ОС ()МХ(8 часа). 2 !. Программирование на командном языке ОС ()МХ (12 часов). 22. Математическое издательство в среде ТеХ (8 часов) . 23. Динамические структуры данных. Обработка деревьев (8 часов).
24. Рекурсивные методы и структуры данных. Представление и обработка выражений. (8 часов). 25. Абстрактные типы данных. Сортировка последовательностей (12 часов). 26. Автоматизация процесса сборки программ модульной структуры с использованием утилиты ша1се (8 часов). Дополнтпельные работы (по со.ласованит с преподавателем): выполнение одного из задании пратпикииа в аяыпернативных средах програ кмирования.
Темы групповых и индпвидуальш гя консультаций по курсу (60-80 чае. и» группу 15-20 чел.) 1. Подготовка к лабораторной работе 20. Команды обработки текстовых файлов в ОС ()МХ. 2. Задание ЪЧ курсового проекга. Хранение и выборка данных в файлах Паскаля. 3. Входной контроль знаний по заданию ЪЧ. 4. Подготовка к лабораторной работе 21. Программирование на ИКЯ ОС ()МХ. 5. Подготовка к лабораторной работе 22.
Издательская система ТеХ. 6. Задание ЪЧ! курсового проекта. Разреженные матрицы. 7. Входной контроль знаний по заданию ЪЧ1. 8. Задание ЪЧ11 курсового проекта. Линейные списки. 9. Входной контроль знаний по заданию ЪЧ11. 1О. Подготовка к лабораторным работам 23. 11. Подготовка к лабораторным работам 24. 12. Подготовка к лабораторной работе 25. 27.* Объектно-ориентированное программирование в фон-Неймановских языках (Ех!епйед !ОЬ)ес! Рааса), С-н-. 1аза, Сй).
28.* Программирование в абсолютно объектных средах (С).ОБ, База)!Тайг). 29.* Программирование на Прологе, Лиепе или в системе АГР Дж. Бэкуса. 1. 2. 3. 7. 8. 9. 10. 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. 38. 39. 40. 41. 42. 43. 44. 45. 47. 48. 50. 5!. 52. 54. 55. 56. 13. Задание !Х курсового проекта. Методы сортировки. 14. Входной контроль знаний по заданию 1Х. 15. Подготовка к лабораторной работе 26. 16. Индивидуальные консультации (10 час.). 17. Проверка отчетов по КП (10-20 час.). 18. Тестирование и инспекция программ КП (10-20 час.). ЭКЗАМЕНА ИОННАЯПРОГРАММА 64часалек ий 2007/08 ч.го Уровни описания структур данных.
Статические и динамические объекты программ. Ссылочный тип данных. Файл. Функциональная спецификация. Файл. Логическое описание. Физическое представление. Вектор. Функциональная спецификация. Логическое описание и физическое представление. Очередь. Функциональная спецификации.
Очередь. Логическое описание и физическое прсдст шление (файл). Очередь. Логическое описание и физическое представление (массив). Очередь. Логическое описание и физическое представление (динамические объекты). Стек. Функциональная спецификация. Стек. Логическое описание. Стек.
Физическое представление (массив). Стек. Физическое представление (динамические объсктьз). Линейный список. Функциональная спецификация. Линейный список. Логическое описание. Линейный список. Физическое представление. Итераторы. Линейный список. Физическое представление (массив). Линейный список. Физическое представление (динамические объекты).
Списки общего вида. Графы. Понятие рекурсии. Рекурсзи и итерация. Примеры. Деревья. Двоичные деревья. Двоичное дерево. Функциональная спецификация. Двоичное дерево. Логическое описание. Построение и визуашзация. Двоичное дерево. Физическое представление. Прошивка. Алгоритмы обхода деревьев.
Особенности представления и обработки деревьев общего вида (преобразование к двоичному, ...). Деревья выражений. Рекурсивные структуры данных и их связь с алгоритмической рекурсией. Деревьв поиска. Сбалансированные деревья поиска. Простые методы поиска. Поиск по образцу в последовательностях и таблицах. Алгоритм Кнута-Морриса-Пратта. Алгоритм Бойера-Мура. Алгоритм Рабина-Карпа.
Таблицы с прямым доступом. Алгоритмы сортировки. Сортировка вставкой. Сортировка выборкой. Обменные сортировки. Сортировзш Шелла. Турнирные сортировки. Сортировзш Хоора. Сортировки слиянием. Сравнение методов сортировки. Модульное программирование. Модули в расширениях яззяка Паскаль. Абстракции в языках программирования. Абстрактные типы данных.
Пример модуля АТД О ЧН'(ЗДБ. Экспорт и импорт объектов. Инкапсулированные АТД. Типизация языка п!зограммнрования, Конт!золь типов. Средства ослабления типового контроля в языке Паскаль. Преобразование и передача типов. Полиморфизм операций, отношений и процедур. Родовые модули. Адресный тип. Реализация полиморфизма с помощью адресного типа. 57 58 59 бО б1 Процедурный тип данных. Реализация полиморфизма с помощью процедурного типа.
Наследование. Реализация полиморфизма с помощью наследования. Объектно-ориентированное программирование. В качестве зкзаменаииоиных задач предлагаютсн задачи на написание програми на расширенном Носкове или на Си (в зависимости от группьб по всем кониепйилм, алгоритмам и стриюпура и данных теоретического курса и праюникииа. Программа может быть уточнена ие позднее последней лекции.
.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
