22. Определение атд, связной структуры данных, структурированного типа данных, массива.

Абстра́ктный тип да́нных (АТД) - это математическая модель для типов данных, где тип данных определяется поведением (семантикой) с точки зрения пользователя данных, а именно в терминах возможных значений, возможных операций над данными этого типа и поведения этих операций.

Связные структуры характеризуются наличием связи. Примерами несвязных структур есть векторы, массивы, строки, стеки, очереди; примеры связных структур - связные списки.

Структурированные типы данных определяют наборы однотипных или разнотипных компонент.

Типы компонент образуются из других типов (простых, структурированных, указателей и т. д.)

данных.

23. Очереди, физическая структура, понятие кольцевой очереди.

Кольцевая очередь - это разновидность обычной очереди. Она также представляет концепцию FIFO (First In First Out), то есть элемент, который добавили в очередь первым, первым ее и покинет.

24. Стратегии сортировки массивов

Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке.

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

количество шагов алгоритма, необходимых для упорядочения;

количество сравнений элементов;

количество перестановок, выполняемых при сортировке.

25. Определение данных, структуры данных, списка данных, указателей.

Данные - поддающееся многократной интерпретации представление информации в формализованном виде, пригодном для передачи, связи или обработки

Структурированные типы данных определяют наборы однотипных или разнотипных компонент.

Типы компонент образуются из других типов (простых, структурированных, указателей и т. д.)

данных. В языке Паскаль существуют следующие структурированные типы:

- тип-массив;

- тип-запись;

- тип-множество;

- тип-файл.

В Turbo Pascal имеется еще два структурированных типа:

- тип-строка string и

- тип-строка PChar, являющиеся разновидностями массива.

В дальнейшем объекты структурированных типов для краткости будут называться теми же

именами, что и их типы, без указания слова "тип": массив, запись, множество, файл, строка.

В стандарте языка существуют упакованные (packed) и неупакованные структурированные

типы. В Turbo Pascal слово packed, характеризующее упакованный тип, не оказывает никакого

влияния; в случае, когда это возможно, упаковка данных осуществляется автоматически.

26. Операции над очередям

Очередь – линейный список, элементы в который добавляются только в конец, а исключаются из начала.

Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.

27. Понятие дека, операции над деком

Дека — очередь с двумя концами. Дека является последовательным списком, в котором включение и исключение элементов может осуществляться с любого из двух концов списка. Логическая и физическая структуры деки аналогичны обычной очереди, но относительно деки следует говорить не о хвосте и голове, а о правом и левом конце очереди. Реализацию операций включения и исключения в деку следует также дополнить признаками левого или правого конца. В литературе можно встретить понятие дека с ограниченным вводом. Это дека, в которой элементы могут вставляться в одном конце, а удаляться с обоих.