Тема 5. Структуры данных и работа с ними (4 часа)

Структуры данных, способы их хранения, передачи и обработки. Линейные, табличные, древовидные структуры данных. Задачи обхода и сортировки структурированных данных. Статические и динамические структуры данных. Массивы одномерные и многомерные. Односвязные и двусвязные списки. Стеки. Очереди. Кольца. Отображения. Графы. Деревья. Двоичные деревья. Словари. Хеш-таблицы. Декомпозиция до стандартных типов данных.

Контрольные вопросы

1. Как соотносятся структурированные и неструктурированные данные?

2. Какую роль в выборе структуры данных играют вопросы интерпретации этих данных?

3. Чем отличаются физическая, логическая и концептуальная структуризация данных?

4. Какие задачи решаются при концептуальном структурировании?

5. Какие задачи решаются при логическом структурировании?

6. Какие задачи решаются при физическом структурировании?

7. Что такое «стандартные типы данных»?

8. Перечислите стандартные типы данных и связанные с ними операции.

9. Приведите примеры задач, в которых удобно использовать линейные структуры данных.

10. Приведите примеры задач, в которых удобно использовать табличные структуры данных.

11. Приведите примеры задач, в которых удобно использовать древовидные структуры данных.

12. Дайте определение задачи обхода структурированных данных.

13. Дайте определение сортировки данных.

14. Дайте определение понятий «первичный ключ сортировки» и «вторичный ключ сортировки».

15. Перечислите основные алгоритмы сортировки линейного массива.

16. Дайте определение динамической структуры данных.

17. Поясните устройство многомерного массива данных.

18. Перечислите основные операции над массивами данных на примере двухмерного массива – матрицы.

19. Дайте определение списка и назовите задачи, в алгоритмизации которых удобны такие типы данных.

20. Чем двухсвязный список отличается от односвязного?

21. Дайте определения графа и бинарного графа.

22. Что представляет собой операция хеширования и в каких случаях она применяется?

23. Что представляет собой процедура декомпозиции структуры данных?

Основная литература

1. Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона. — М.: ДМК-Пресс, 2010 г. — 272 с. — Электронное издание. — ISBN 978-5-94074-584-6

2. Макарова, Н. В. (д-р пед. наук; канд. техн. наук). Информатика: учебник для студентов высших учебных заведений, обучающихся по направлениям подготовки бакалавров "Системный анализ и управление" и "Экономика и управление" / Н.В. Макарова, В.Б. Волков. - Санкт-Петербург [и др.] : Питер, 2011. - 573 с. : ил. ; 24 см. - (Учебник для вузов) (Стандарт третьего поколения) (Для бакалавров).

Дополнительная литература

1. Венделева, Мария Александровна. Информационные технологии управления : учеб. пособие для бакалавров / М. А. Венделева, Ю. В. Вертакова. - М. : Юрайт, 2011. - 462 c.

2. Кубенский А. Структуры и алгоритмы обработки данных: обьектно ориентированный подход и реализация на С++. — СПб.: БХВ-Петербург, 2010 г. — 464 с. — Электронное издание. — Гриф УМО. — ISBN 5-94157-506-8

Тема 6. Информационное моделирование

Эта тема прорабатывается самостоятельно по литературе. Предусмотрена подготовка докладов студентами. Список рекомендуемой литературы представлен в разделе практических занятий.