Домашнее задание № 1

структуры данных и их реализация

Цель работы – познакомиться с динамическими структурами данных, научиться создавать абстрактные типы данных, используя понятия списка, стека, очереди, дека, бинарного дерева, графа, понять взаимосвязь алгоритма обработки структур данных с их внутренним представлением.

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

1. Что такое абстрактный тип данных?

2. Объясните разницу между понятиями «структура данных» и «структура хранения».

3. Что такое полустатическая структура данных?

4. Что такое список как структура данных?

5. Что такое связанный список как структура хранения?

6. Какие виды списков Вы знаете?

7. Какие методы применимы к спискам?

8. Какие методы реализации списков Вы знаете?

9. Что такое дескриптор списка?

10. Что такое стек?

11. Какие операции применимы к стекам?

12. Каков механизм заполнения стека? Что такое «дно» стека?

13. Что такое очередь?

14. Какие операции применимы к очередям?

15. Каков механизм заполнения очереди?

16. Что такое дек?

17. Какие виды деков Вы знаете?

18. Как определить количество элементов в списке, стеке и очереди?

19. Что такое дек? Какие операции применимы к декам?

20. В чем различие между конкатенацией двух стеков и конкатенацией двух очередей?

21. Какая структура данных описывается аббревиатурой LIFO?

22. Какая структура данных описывается аббревиатурой FIFO?

23. От чего зависит выбор структуры хранения для реализации структуры данных?

24. Что такое дерево? Из каких элементов оно состоит?

25. Как измерить высоту дерева?

26. Что такое лес?

27. Какое дерево называют бинарным?

28. Какие бинарные деревья называются полными, почти полными и неполными?

29. Что понимают под идеально сбалансированным бинарным деревом?

30. Какие деревья называют бинарными деревьями поиска?

31. Какие существуют способы реализации бинарных деревьев?

32. Какие существуют способы организации общих деревьев?

33. Какие методы применимы для работы с деревьями?

34. Какие методы обхода бинарных деревьев Вы знаете?

35. Что такое бор?

36. Что такое граф? Какие виды графов Вы знаете?

37. Какие существуют способы реализации графов?

38. В чем заключается алгоритм Флойда?

39. В чем заключается метод Дейкстры?

40. Как найти центр ориентированного графа?

41. Для чего требуется транзитивное замыкание матрицы смежности?

42. Какие методы обхода графов Вы знаете?

43. Что такое остовное дерево графа? Сколько остовных деревьев может быть у графа?

44. Что такое минимальное остовное дерево графа?

Постановка задачи

Написать программы согласно номеру индивидуального варианта (номер варианта определяется по последней цифре номера зачетной книжки).

В первом задании требуется реализовать необходимую структуру данных с помощью двух структур хранения: векторной и списковой,– и использовать ее для решения поставленной задачи. Описание структуры данных должно быть в отдельном файле.

---

Во втором задании граф реализовать двумя способами (матрицей смежности или весов и списками смежности).

В третьем задании реализация дерева – по выбору студента (выбор обосновать!)

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

Вариант № 7

1. Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.

2. Из орграфа удалить все вершины, из которых недостижима заданная.

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

---

Смотрите также файлы

• 2. Лекции Паскаль (Часть 2).doc

• 1. Лекции Паскаль (Часть 1).doc

• Информатика КР2.pdf

• проектирование информационных систем радчук.docx

• СЕТИ СВЯЗИ.doc