- •Вопрос 1) Основные структуры данных.
- •Вопрос 2) Массивы и их свойства.
- •Вопрос 3) Записи
- •Вопрос 4) Множества
- •Операции над множествами
- •Операции отношения.
- •Вопрос 5) Динамические структуры данных;
- •Вопрос 6) Линейные списки.
- •Вопрос 7) Циклические списки
- •Вопрос 8) Стек и его организация
- •Вопрос 9) Очереди и их организация
- •Вопрос 10) Задачи поиска в структурах данных.
- •Вопрос 11) Алгоритм линейного поиска.
- •Вопрос 12) Алгоритм бинарного поиска.
- •Вопрос 13) Алгоритм Кнута, Мориса- Пратта
- •Вопрос 14) Хэширование данных
- •Вопрос 15) сортировка данных
- •15. Сортировка данных
- •1) Сортировка включением
- •2) Сортировка Шелла
- •3) Обменная сортировка
- •4) Сортировка перемешиванием (Шейкерная сортировка)
- •5) Сортировка со слиянием
- •1) Прямое слияние
- •2) Естественное слияние
- •Вопрос 16) Пузырьковая сортировка.
- •17 Вопрос
- •Вопрос 18) Представление графов и деревьев
- •Вопрос 19) Представление бинарных деревьев.
- •Вопрос 20) Представление графов Способы представления графа в информатике Матрица смежности
- •Матрица инцидентности
- •Список рёбер
- •Вопрос 21) Алгоритмы на графах
- •Алгоритм Дейкстры нахождения кратчайшего пути
Вопрос 1) Основные структуры данных.
Данные – это материальные объекты произвольной формы, выступающие в качестве средства представления информации. Преобразование и обработка данных позволяют извлечь информацию, т.е. знание о том или ином предмете, процессе, явлении. Другими словами данные – диалектическая составная часть информации. Они представляют собой зарегистрированные сигналы. В соответствии с методом регистрации данные могут храниться и транспортироваться на носителях различных видов.
Любые данные могут быть отнесены к одному из двух типов: основному (простому), форма представления которого определяется архитектурой ЭВМ, или сложному, конструируемому пользователем для решения конкретных задач.
Данные простого типа это - символы, числа и т.п. элементы, дальнейшее дробление которых не имеет смысла. Из элементарных данных формируются структуры (сложные типы) данных.
Основные структуры:
Массив (функция с конечной областью определения). именованный набор однотипных переменных, расположенных в памяти непосредственно друг за другом (в отличие от списка), доступ к которым осуществляется по индексу. Отдельный элемент массива задается индексом. Массив может быть одномерным, двумерным и т.д. Разновидностями одномерных массивов переменной длины являются структуры типа кольцо, стек, очередь и двухсторонняя очередь.
(IntArray : array[1..100] of Integer; )
Стек - структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришел — первым вышел»).
Очередь — структура данных доступа к элементам которой осуществляется по принципу «первый пришёл — первый вышел» (FIFO, First In — First Out).
Кольцо - циклически связанный список (кольцо или циклический список) обладает той особенностью, что связь его последнего узла не равна пустоте, а идет назад к первому узлу списка.
Запись (декартово произведение) - совокупность элементов данных разного типа. В простейшем случае запись содержит постоянное количество элементов, которые называют полями. Совокупность записей одинаковой структуры называется файлом. (Файлом называют также набор данных во внешней памяти, например, на магнитном диске).
(<имя>=record fam:string[10]; grup:string[4]; end;)
Файлы Файл – динамическая структура данных, размер которой может меняться в процессе выполнения над ним каких-либо действий (он может быть равен нулю, что соответствует пустому файлу). Большие совокупности данных удобно иметь записанными во внешней памяти в виде последовательности сигналов. В Паскале для этих целей предусмотрены специальные объекты – файлы (file). Файлом называется совокупность данных, записанная во внешней памяти под определенным именем.
Такие структуры данных как массив или запись занимают в памяти ЭВМ постоянный объем, поэтому их называют статическими структурами. К статическим структурам относится также множество.
Множество — это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект в множестве называется элементом множества.
(colors = (red,green,blue);
smallnumbers = 0..10;
colorset = set of colors;
numberset = set of smallnumbers;
anothernumberset = set of 0..20;)
Строка — это последовательность символов. Каждый символ занимает 1 байт памяти (код ASCII). Количество символов в строке называется ее длиной. Длина строки может находиться в диапазоне от 0 до 255.
(Var Name : string[20];)
Имеется ряд структур, которые могут изменять свою длину - так называемые динамические структуры. К ним относятся дерево, список, ссылка.
Список - это последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться.
(type Link = ^zveno;
zveno = record
inf: integer;
sled: Link;
end;)
Дерево — одна из наиболее широко распространённых структур данных, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы.