37. Определение стека, массива, множества, структуры данных

Стек – это линейный список, в котором добавление новых элементов и удаление существующих производится только с одного конца, называемого вершиной стека.

Массивом называется ряд (последовательность, набор) величин одного типа (например, real, integer или char), имеющих одно имя (один идентификатор).

Множество — это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект в множестве называется элементом множества.

Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

38. Понятие методов сортировки массивов, привести методы нескольких сортировок

По-видимому, самым простым методом сортировки является так называемый метод "пузырька". Чтобы уяснить его идею, представьте , что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:

* если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;

* при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .

В результате наибольший элемент оказывается в самом верху массива.

begin for j:=1 to N-1 do for i:=1 to N-j do if M[i] > M[i+1] then swap(M[i],M[i+1]) end;

Второй метод называется метод вставок., т.к. на j-ом этапе мы "вставляем" j-ый элемент M[j] в нужную позицию среди элементов M[1], M[2],. . ., M[j-1], которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены. Сказанное можно записать следующим образом:

нц для j от 2 до N переместить M[j] на позицию i <= j такую, что M[j] < M[k] для i<= k < j и либо M[j] >= M[i-1], либо i=1 кц

begin M[0] := -oo; for j:=2 to N do begin i := j; while M[i] < M[i-1] do begin

swap(M[i],M[i-1]); i := i-1 end end end;

Идея сортировки с помощью выбора не сложнее двух предыдущих. На j-ом этапе выбирается элемент наименьший среди M[j],M[j+1],. . ., M[N](см. процедуру FindMin) и меняется местами с элементом M[j]. В результате после j-го этапа все элементы M[j], M[j+1],. . ., M[N]будут упорядочены.

Сказанное можно описать следующим образом:

нц для j от 1 до N-1 выбрать среди M[j],. . ., M[N] наименьший элемент и поменять его местами с M[j] кц

Более точно:

begin for j:=1 to N-1 do begin FindMin(j, i); swap(M[j],M[i]) end end;

39. Области применения массивов

1. Для хранения данных. Тот же текстовый файл - разновидность массива данных. 2. Самое простое применение для вычислительной техники - вычисления. Она и создавалась для этого в первую очередь. 3. Напрямую. Программирование это раздел математики.

40. Определение дескриптора

, данных, типа данных, записи Дескри́птор (от лат. descriptor — описывающий) — лексическая единица (слово, словосочетание) информационно-поискового языка, служащая для описания основного смыслового содержания документа или формулировки запроса при поиске документа (информации) в информационно-поисковой системе. Дескриптор однозначно ставится в соответствие группе ключевых слов естественного языка, отобранных из текста, относящегося к определённой области знаний.

Данные — поддающееся многократной интерпретации представление информации в формализованном виде, пригодном для передачи, связи или обработки (ISO/IEC 2382:2015). Данные — формы представления информации, с которыми имеют дело информационные системы и их пользователи (ISO/IEC 10746-2:1996).

Тип - это свойство переменой, по которому переменная может принимать множество значений, допустимых этим типом, и участвовать во множестве операций, допустимых над данным типом.

Запись Паскаля – структурированный комбинированный тип данных, состоящий из фиксированного числа компонент (полей) разного типа.