Государственный экзамен по информатике. Горбенко О.Д - 4 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

и удаления динамического объекта. Действия над ссылками:
присваивание, сравнение.
Динамические структуры , линейные цепочки (списки). Создание
списка, просмотр списка, включение в список и удаление из списка
элементов .
3. Понятие об абстрактных структурах данных. Абстракция ,
представление, способы преобразования , аксиоматика -
характеристики информации. Три уровня описания структур данных:
функциональная спецификация , логическое описание, физическое
представление. Два способа представления совокупности данных:
сплошное и цепочное.
Стек. Реализация стека с п
омощью массива. Пакет процедур для
реализации функциональных требований к стеку. Цепочное
представление стека. Адекватность структуры данных и структуры
алгоритма.
Очередь . Параллельное выполнение двух процессов , посредник .
Сплошное представление очер
еди , кольцевой буфер. Пакет процедур
для реализации функциональных требований к очереди. Цепочное
представление очереди.
Линейный упорядоченный список. Двухсвязные списки. Поиск с
включением в список.
Древовидные структуры . Определение типа для к
омпонент дерева.
Способы обхода узлов дерева. Преимущества постфиксной записи
выражений . Способы представления деревьев с помощью массивов .
Цепочное представление бинарных деревьев . Задача поиска в дереве
по ключу . Сортировка элементов массива: быстрые сортировки,
пирамидальная сортировка.
4. Нисходящая технология программирования . Метод пошаговой
детализации. Операционный маршрут нисходящей технологии.
Нисходящее кодирование и тестирование. Восходящая технология
программирования . Операционный маршрут восходящей технологии.
Литература
1. Вирт Н . Алгоритмы + структуры данных = программы . -
М .:"Мир",1989 - 212 с.
2. Йенсен К .,Вирт Н . Паскаль . Руководство для пользователей и
end
;
Сортировки обменами
Сортировка методом “пузырька”
Этот метод основан на том что , на первом проходе соседние
элементы сравниваются , в результате чего самый большой элемент
переставляется на последнее место , за второй проход самый большой
из оставшихся (сравнение идет между N-1 элементами) перемещается
на предпоследнее место и т. д., до тех пор пока массив не окажется
отсортированным.
В данном примере рассматривается усовершенствованный метод:
на каждом проходе алгоритма запоминается место последнего обмена
между элементами, для того чтобы на следующем проходе выполнять
сравнение только до этого места.
procedure Bubble (var A : tArray);
var i,Bound,t:integer;
Elem:PtrElem;
begin
{выбираем границу справа для сравниваемых элементов }
Bound:=N;
repeat
{предполагаем , что на данном проходе алгоритма обменов не
будет, т.е. все элементы упорядочены }
t:=0;
{сравниваем все соседние элементы : 1 и 2, 2 и 3, … , Bound-1 и
Bound}
for i:=1 to Bound-1 do
{если элемент слева больше, чем элемент справа, то }
if A[i]^.Key>A[i+1]^.Key then
begin
{меняем их местами}
Elem:=A[i+1]; A[i+1]:=A[i]; A[i]:=Elem;
{запоминаем место последнего обмена}
t:=i
end;
{запоминаем место последнего обмена как правую границу}
Bound:=t
until t=0
4 45 
и удаления динамического объекта. Действия над ссылками:           end;
присваивание, сравнение.
  Динамические структуры, линейные цепочки (списки). Создание                            Сортировки обменами
списка, просмотр списка, включение в список и удаление из списка
элементов.                                                           Сортировка методом “пузырька”
3. Понятие об абстрактных структурах данных. Абстракция,
                                                                      Этот метод основан на том что, на первом проходе соседние
представление,    способы    преобразования,    аксиоматика    -   элементы сравниваются, в результате чего самый большой элемент
характеристики информации. Три уровня описания структур данных:    переставляется на последнее место, за второй проход самый большой
функциональная спецификация, логическое описание, физическое       из оставшихся (сравнение идет между N-1 элементами) перемещается
представление. Два способа представления совокупности данных:      на предпоследнее место и т.д., до тех пор пока массив не окажется
сплошное и цепочное.                                               отсортированным.
  Стек. Реализация стека с помощью массива. Пакет процедур для        В данном примере рассматривается усовершенствованный метод:
реализации функциональных требований к стеку. Цепочное             на каждом проходе алгоритма запоминается место последнего обмена
представление стека. Адекватность структуры данных и структуры     между элементами, для того чтобы на следующем проходе выполнять
алгоритма.                                                         сравнение только до этого места.
  Очередь. Параллельное выполнение двух процессов, посредник.
                                                                   procedure Bubble (var A : tArray);
Сплошное представление очереди, кольцевой буфер. Пакет процедур
                                                                    var i,Bound,t:integer;
для реализации функциональных требований к очереди. Цепочное               Elem:PtrElem;
представление очереди.                                             begin
  Линейный упорядоченный список. Двухсвязные списки. Поиск с          {выбираем границу справа для сравниваемых элементов}
включением в список.                                                  Bound:=N;
  Древовидные структуры. Определение типа для компонент дерева.       repeat
Способы обхода узлов дерева. Преимущества постфиксной записи             {предполагаем, что на данном проходе алгоритма обменов не
выражений. Способы представления деревьев с помощью массивов.      будет, т.е. все элементы упорядочены}
Цепочное представление бинарных деревьев. Задача поиска в дереве         t:=0;
                                                                         {сравниваем все соседние элементы: 1 и 2, 2 и 3, …, Bound-1 и
по ключу. Сортировка элементов массива: быстрые сортировки,
                                                                   Bound}
пирамидальная сортировка.
                                                                         for i:=1 to Bound-1 do
4. Нисходящая технология программирования. Метод пошаговой            {если элемент слева больше, чем элемент справа, то }
детализации. Операционный маршрут нисходящей технологии.                 if A[i]^.Key>A[i+1]^.Key then
Нисходящее кодирование и тестирование. Восходящая технология                 begin
программирования. Операционный маршрут восходящей технологии.                {меняем их местами}
                                                                              Elem:=A[i+1]; A[i+1]:=A[i]; A[i]:=Elem;
                                                                             {запоминаем место последнего обмена}
                          Литература                                         t:=i
                                                                           end;
1. Вирт Н. Алгоритмы + структуры данных = программы. -                   {запоминаем место последнего обмена как правую границу}
                                                                         Bound:=t
М.:"Мир",1989 - 212 с.
                                                                      until t=0
2. Йенсен К.,Вирт Н. Паскаль. Руководство для пользователей и

                             4                                                                       45

Страницы