ВУЗ:
Составители:
1. ОБЩИЕ ПОЛОЖЕНИЯ
1.1. Программа государственного экзамена
для студентов факультета ПММ
(раздел информатики)
1. Классы и структурные особенности современных ЭВМ .
Центральный процессор, память, внешние устройства.
Обрабатываемые данные. Программное обеспечение ЭВМ : системное
и прикладное. Современные операционные системы .
Программирование. Управляющие структуры . Проектирование
алгоритма сверху вниз . Подпрограммы . Основные идеи структурного
программирования . Простейшие алгоритмы сортировки: обменом ,
выбором, подсчетом , включениями.
2. Языки программирования . Словарь , синтаксис, семантика языка.
Язык программирования Паскаль. Понятие типа. Стандартные типы.
Общая структура программы . Типы , определяемые пользователем .
Операторы Паскаля . Оператор присваивания , приоритеты операций
при вычислении выражения . Составной оператор. Условный оператор.
Операторы цикла: а) с пред- условием , б ) с пост- условием , в ) с
параметром . Оператор выбора. Оператор перехода. Метка.
Допустимые случаи использования оператора перехода.
Структурированные статические типы данных. Регулярный тип .
Поиск в массиве. Методы барьера и булевского признака.
Комбинированный тип . Множественный тип . Множества, операции
над множествами.
Процедуры , описание и вызов . Классификация объектов тела
процедуры . Способы обмена данными с процедурой. Параметры -
значения , параметры - переменные.
Функции, описание и вызов . Передача в качестве параметра имени
функции или процедуры . Побочные эффекты при вызове функции.
Процедуры и функции без параметров . Рекурсивные функции и
процедуры . Прямая и косвенная рекурсии.
Файловый тип . Действия над файлами: создание файла, просмотр
файла. Копирование файлов . Стандартные процедуры . Текстовые
файлы , процедуры чтения и записи. Стандартные файлы .
Ссылочный тип . Указатель, базовый тип . Ссылка на составной
объект, взаимно рекурсивное определение типа. Процедуры создания
end
;
Быстрая сортировка или метод Хоара
Сортируемый массив просматривается сразу с двух сторон (слева и
справа). Если слева находится элемент больший , чем элемент справа,
то эти элементы меняются местами. Так продолжается до тех пор,
пока указатели на левый и правый элементы не пересекутся . В
результате такого прохода алгоритма получим , что весь массив разбит
на две части . В левой части находятся элементы с меньшими
значениями ключей , а в правой – с большими значениями. Теперь
осталось отсортировать тем же самым методом каждую часть
отдельно .
procedure Quick_Rec (var A : tArray);
procedure QuickSort (left,right : integer);
var i,j:integer;
Elem:PtrElem;
begin
{если есть что сортировать }
if left<right then
begin
{запоминаем указатели на левый и правый сравниваемые элементы }
i:=left; j:=right;
{до тех пор, пока указатели не пересекутся }
while (i<j) do
begin
{ищем элемент справа, который был бы меньше, чем
элемент слева}
while (i<j) and (A[j]^.Key>=A[i]^.Key) do j:=j-1;
{меняем элементы местами}
Elem:=A[i]; A[i]:=A[j]; A[j]:=elem;
{ищем элемент слева, который был бы больше, чем
элемент справа}
while (i<j) and (A[j]^.Key>=A[i]^.Key) do i:=i+1;
Elem:=A[i]; A[i]:=A[j]; A[j]:=elem;
end;
{сортируем левую часть массива}
QuickSort(left,i-1);
{сортируем правую часть массива}
3 46
end; 1. ОБЩИЕ ПОЛОЖЕНИЯ
1.1. Программа государственного экзамена
Быстрая сортировка или метод Хоара для студентов факультета ПММ
(раздел информатики)
Сортируемый массив просматривается сразу с двух сторон (слева и
справа). Если слева находится элемент больший, чем элемент справа,
то эти элементы меняются местами. Так продолжается до тех пор, 1. Классы и структурные особенности современных ЭВМ.
пока указатели на левый и правый элементы не пересекутся. В Центральный процессор, память, внешние устройства.
результате такого прохода алгоритма получим, что весь массив разбит Обрабатываемые данные. Программное обеспечение ЭВМ: системное
на две части. В левой части находятся элементы с меньшими и прикладное. Современные операционные системы.
значениями ключей, а в правой – с большими значениями. Теперь Программирование. Управляющие структуры. Проектирование
осталось отсортировать тем же самым методом каждую часть алгоритма сверху вниз. Подпрограммы. Основные идеи структурного
отдельно. программирования. Простейшие алгоритмы сортировки: обменом,
выбором, подсчетом, включениями.
procedure Quick_Rec (var A : tArray); 2. Языки программирования. Словарь, синтаксис, семантика языка.
procedure QuickSort (left,right : integer);
Язык программирования Паскаль. Понятие типа. Стандартные типы.
var i,j:integer;
Общая структура программы. Типы, определяемые пользователем.
Elem:PtrElem;
begin Операторы Паскаля. Оператор присваивания, приоритеты операций
{если есть что сортировать} при вычислении выражения. Составной оператор. Условный оператор.
if left=A[i]^.Key) do j:=j-1; процедуры. Способы обмена данными с процедурой. Параметры-
{меняем элементы местами} значения, параметры-переменные.
Elem:=A[i]; A[i]:=A[j]; A[j]:=elem; Функции, описание и вызов. Передача в качестве параметра имени
{ищем элемент слева, который был бы больше, чем функции или процедуры. Побочные эффекты при вызове функции.
элемент справа} Процедуры и функции без параметров. Рекурсивные функции и
while (i=A[i]^.Key) do i:=i+1; процедуры. Прямая и косвенная рекурсии.
Elem:=A[i]; A[i]:=A[j]; A[j]:=elem; Файловый тип. Действия над файлами: создание файла, просмотр
end; файла. Копирование файлов. Стандартные процедуры. Текстовые
{сортируем левую часть массива}
файлы, процедуры чтения и записи. Стандартные файлы.
QuickSort(left,i-1);
{сортируем правую часть массива} Ссылочный тип. Указатель, базовый тип. Ссылка на составной
объект, взаимно рекурсивное определение типа. Процедуры создания
46 3
