Вопросы для подготовки к экзамену по курсу «Программирование на языке высокого уровня (структурное программирование)»

(для групп В4-121, 122, 123, 124; К4-12в)

1. Методологии программирования. Понятие алгоритма. Способы записи алгоритмов.

Методологии программирования:

- Хаотическое программирование

- Структурное программирование

- Объектно-ориентированное программирование

Алгоритм - точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных.

Способы записи алгоритмов:

- вербальный, когда алгоритм описывается на человеческом языке;

- символьный, когда алгоритм описывается с помощью набора символов;

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

Общепринятыми способами записи являются графическая запись с помощью блок-схем и символьная запись с помощью какого-либо алгоритмического языка.

2. Уровни представления информации. Понятие абстрактных (логических) структур данных. Основные операции.

Выделяют три уровня абстракции в представлении информации:

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

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

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

2. Абстрактные структуры информации – это тот или иной формальный способ интерпретации интуитивной структуры. Без такой формализации невозможно представить в программных продуктах требуемую информацию. Для представления одной и той же интуитивной структуры могут быть использованы различные абстрактные структуры – естественно, с разной степенью точности.

3. Конкретные структуры информации – это способы представления соответствующих абстрактных структур в памяти ЭВМ.

Абстрактные структуры называют также логическими структурами или просто структурами данных; конкретные структуры называют еще внутренними структурами.

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

Абстрактные структуры данных.

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

Элемент данных (или узел) – это некоторая часть абстрактной структуры; элементы определяют хранимую информацию и представляют собой модель некоторой части интуитивной структуры данных.

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

Структура данных определяется как совокупность правил и ограничений, которые отражают связи, существующие между отдельными частями данных

Элемент обозначает часть абстрактной структуры данных. Элемент, в свою очередь, может представлять какую-то логическую структуру данных – таким образом, строится иерархическая последовательность структур данных.

Наиболее часто используются следующие абстрактные структуры данных, которые можно определить как базовые: строка, очередь, стек, таблица, дерево.

Строка – это упорядоченное множество элементов. В качестве примеров операций, определенных над строками, укажем следующие:

- сцепление двух строк,

- поэлементное сравнение двух строк,

- разбиение строки на несколько частей,

- нахождение подстроки.

Очереди и стеки – это динамически изменяющиеся структуры данных.

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

С очередью можно выполнять следующие операции:

- Добавление нового элемента; в этом случае элемент ставится в конец упорядоченного множества.

- Исключение элемента из очереди; исключение элемента можно производить только с начала упорядоченного множества, определяющего очередь.

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

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

Таблица состоит из множества элементов, в котором с каждым элементом однозначно связано некоторое имя, или ключ.

Можно указать много операций, определенных над таблицами; ниже приведены некоторые из них:

- добавление элемента,

- доступ к элементу,

- удаление элемента.

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

3. Конкретные структуры данных. Отображение структуры данных в памяти вектором.

Конкретные структуры информации – это способы представления соответствующих абстрактных структур в памяти ЭВМ.

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

• базовый адрес,

• размер вектора (количество элементов),

• размер одного элемента вектора.

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

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

Адрес_i = базовый_адрес + (i-1)* размер_элемента

В языке С/С++ вектор определяется как массив элементов определенного типа, при этом язык не накладывает ограничения на тип элемента массива:

тип_элемента имя_массива [ количество_элементов ];

Тогда имя_массива определяет базовый адрес вектора, количество_элементов – размер вектора и тип_элемента – размер элемента вектора.

Примеры:

int a[12], b[3];

char s[80];

struct S{ ... };

S x[100];

Доступ к элементу массива в языке С/С++ можно осуществить двумя способами:

• с помощью индекса, при этом в языке С/С++ первый элемент массива имеет значение индекса 0, а последний – (количество_элементов – 1),

• с помощью указателя.

4. Конкретные структуры данных. Отображение структуры данных в памяти списком. Типы списков.

Конкретные структуры информации – это способы представления соответствующих абстрактных структур в памяти ЭВМ.

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

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

Доступ к списку как к единому целому обеспечивается определением начала списка (т.е. первого элемента списка). Обычно список определяется специальным указателем на начало списка. Последний элемент списка в поле указателя на следующий элемент может иметь специальную запись – так называемый "пустой" указатель (NULL или 0). Список, определенный таким образом, получил название линейного односвязного списка.

Можно определить список, задав вместо указателя специальный – головной элемент, в котором поле указателя на информацию не используется, а поле указателя на следующий элемент определяет начало списка. Такой список получил название списка с головным элементом.

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

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

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

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

Элемент односвязного списка определяется с помощью структуры следующим образом:

struct Item{

тип info;

Item *next;

};

5. Элементарная структура данных – стек: определение, основные операции. Реализация стека вектором и списком.

Стек представляет собой также упорядоченное по времени поступления множество элементов, но в отличие от очереди стек характеризуется только одним концом – вершиной стека (рис. II–3).

Рис. II–1

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

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

Вектор см. билет 3.

Список см. билет 4.