Добавлен: 19.10.2018
Просмотров: 779
Скачиваний: 58
Домашнее задание № 1
структуры данных и их реализация
Цель работы – познакомиться с динамическими структурами данных, научиться создавать абстрактные типы данных, используя понятия списка, стека, очереди, дека, бинарного дерева, графа, понять взаимосвязь алгоритма обработки структур данных с их внутренним представлением.
Контрольные вопросы
-
Что такое абстрактный тип данных?
-
Объясните разницу между понятиями «структура данных» и «структура хранения».
-
Что такое полустатическая структура данных?
-
Что такое список как структура данных?
-
Что такое связанный список как структура хранения?
-
Какие виды списков Вы знаете?
-
Какие методы применимы к спискам?
-
Какие методы реализации списков Вы знаете?
-
Что такое дескриптор списка?
-
Что такое стек?
-
Какие операции применимы к стекам?
-
Каков механизм заполнения стека? Что такое «дно» стека?
-
Что такое очередь?
-
Какие операции применимы к очередям?
-
Каков механизм заполнения очереди?
-
Что такое дек?
-
Какие виды деков Вы знаете?
-
Как определить количество элементов в списке, стеке и очереди?
-
Что такое дек? Какие операции применимы к декам?
-
В чем различие между конкатенацией двух стеков и конкатенацией двух очередей?
-
Какая структура данных описывается аббревиатурой LIFO?
-
Какая структура данных описывается аббревиатурой FIFO?
-
От чего зависит выбор структуры хранения для реализации структуры данных?
-
Что такое дерево? Из каких элементов оно состоит?
-
Как измерить высоту дерева?
-
Что такое лес?
-
Какое дерево называют бинарным?
-
Какие бинарные деревья называются полными, почти полными и неполными?
-
Что понимают под идеально сбалансированным бинарным деревом?
-
Какие деревья называют бинарными деревьями поиска?
-
Какие существуют способы реализации бинарных деревьев?
-
Какие существуют способы организации общих деревьев?
-
Какие методы применимы для работы с деревьями?
-
Какие методы обхода бинарных деревьев Вы знаете?
-
Что такое бор?
-
Что такое граф? Какие виды графов Вы знаете?
-
Какие существуют способы реализации графов?
-
В чем заключается алгоритм Флойда?
-
В чем заключается метод Дейкстры?
-
Как найти центр ориентированного графа?
-
Для чего требуется транзитивное замыкание матрицы смежности?
-
Какие методы обхода графов Вы знаете?
-
Что такое остовное дерево графа? Сколько остовных деревьев может быть у графа?
-
Что такое минимальное остовное дерево графа?
Постановка задачи
Написать программы согласно номеру индивидуального варианта (номер варианта определяется по последней цифре номера зачетной книжки).
В первом задании требуется реализовать необходимую структуру данных с помощью двух структур хранения: векторной и списковой,– и использовать ее для решения поставленной задачи. Описание структуры данных должно быть в отдельном файле.
Во втором задании граф реализовать двумя способами (матрицей смежности или весов и списками смежности).
В третьем задании реализация дерева – по выбору студента (выбор обосновать!)
При оформлении отчета перед каждой программой поместить описание используемой структуры данных и применяемых способов ее реализации.
Вариант № 7
-
Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.
-
Из орграфа удалить все вершины, из которых недостижима заданная.
Построить дерево бинарного поиска. Определить, является ли это дерево сбалансированным. Обойти полученное дерево в симметричном, прямом и обратном порядках.