- •Понятие алгоритма: рекурсивные функции, системы текстовых замен.
- •Системы счисления, переводы чисел из одной позиционной системы в другую.
- •Передача параметров в подпрограмму, параметры входные и выходные, параметры, передаваемые по значению и по адресу.
- •Использование подпрограмм, параметры формальные, локальные, глобальные, обращения к подпрограммам, фактические параметры.
- •Статические и динамические переменные, динамическая память, работа с динамическими переменными.
- •Понятие линейного связного списка, типы списков, представление стека с помощью массива, пример использования стека.
- •Использование динамических переменных для представления и работы со стеком.
- •Очередь, реализация очереди массивом.
- •Очередь, представление и реализация основных операций с помощью динамических переменных.
- •Реализация основных операций со списком: добавление, удаление, поиск.
- •Деревья, основные операции над деревьями, представление дерева массивом.
- •Двусвязные линейные списки, построение и обход бинарного дерева.
- •Операции поиска и удаления в бинарном дереве.
- •Понятие графа, представление графа на эвм.
- •Представление графа списком инцидентности, алгоритм обхода графа в глубину.
- •Представление графа списком списков, алгоритм обхода графа в ширину.
- •Технологии программирования, концепции, заложенные в ооп.
- •Основные понятия ооп: абстракция, инкапсуляция, полиморфизм.
- •Понятие объекта, его состояние и поведение, классы, определение класса и объявление класса.
- •Статические, дружественные и виртуальные поля и методы, особенности их использования.
- •Абстрактные классы, их назначение и использование.
- •Понятие области видимости: общие, личные, защищённые и опубликованные поля и методы объекта.
- •Указатель this и перегрузка методов.
- •Использование классов, различные способы инициализации.
- •Использование классов, работа с массивами и указателями на обьекты.
- •Наследование, пример использования наследования.
- •Конструкторы и деструкторы, их назначение и использование.
- •Архитектура пк, основные функциональные устройства и их назначение.
- •Мп с точки зрения программиста, регистры общего назначения.
- •Оперативная память, понятие исполняемого и физического адреса, сегментные регистры.
- •Регистр флажков, его назначение и использование.
- •Форматы данных и форматы команд, машинный формат двухадресной машины.
- •Адресация операндов, способы адресации, примеры команд с различными способами адресации.
- •Понятие команды и директивы в Ассемблере, формат команды и директивы.
- •Структура программы на Ассемблере с использованием стандартных директив сегментации.
- •Основные элементы языка Ассемблер: имена, константы, переменные, выражения.
- •Директивы определения данных и памяти, примеры.
- •Команда прерывания, команды работы со стеком.
- •Упрощённые директивы сегментирования, структура программы с использованием точечных директив, пример программы.
- •Этапы выполнения Ассемблерной программы на эвм, понятие com-файла.
- •Различие между exe - и com – файлами, требования, предъявляемые к исходному модулю, предназначенному для создания com – файла, примеры программ.
- •Понятие структурного программирования, этап проектирования – композиция и декомпозиция, понятие статической и динамической структуры программы, спецификация программы.
- •Понятие частичной и полной корректности программы, правила вывода – общий вид, правила консеквенции.
- •Правила вывода для операторов: пустого, присваивания, составного.
- •Правила вывода для операторов ветвления.
- •Правила вывода циклов с предусловием и посусловием.
Очередь, представление и реализация основных операций с помощью динамических переменных.
Графическое представление очереди: имеет две точки доступа. head – для удаления элементов, tail – для добавления элементов.
Описание типа: struct tqueue {int inf; tqueue *next};
Инициализация очереди : head = NULL, tail = NULL;
Добавление элемента в очередь:
r=new tqueue; r->inf=x; r->next=NULL;
if (head =NULL)
{head = r; tail = r;};
else {tail->next=r; tail = r};
Указатель r ссылается на новый элемент => для вставки надо изменить значения трёх указателей: Указатель на следующий узел в новом узле 1) (r->next=NULL); Указатель на следующий узел в текущем узле 2) (tail->next=r) и внешнего указателя 3) (tail=r). Так как добавляемый элемент всегда последний, то его указующей части r->next присваивается NULL.
Взятие элемента из очереди.
if (head!=NULL)
{r=NULL;
x=head-> inf; head=head->next;
delete r;} // удаление 1-го элемента.
r – указатель на 1-ый элемент (r=head).
Освобождение динамической памяти, занятой очередью.
void clear_queue (tqueue *&head)
{tqueue *r;
while (head!=NULL)
{r=head; head=head->next; delete r;}}
Реализация основных операций со списком: добавление, удаление, поиск.
Описание элемента списка в общем виде:
struct tnode {int inf; tnode *next;}
Добавить элемент с указателем p за элементом с указателем q.
p->next=q->next;
q->next=p;
Добавить элемент с указателем p перед элементом с указателем q, то есть добавить p после q, а затем поменять местами.
tnode *r =new tnode;
p->next=q->next; q->next=p;
r->inf=p->inf; p->inf=q->inf; q->inf = r->inf;
Удалить элемент расположенный за элементом с указателем q.
q->next=q->next->next;
или r=q->next; q->next=r->next; delete r;
Удалить элемент с указателем p.
r=first;
if (p==first) {first=first->next; delete r;}
else
{while (r->next!=p) r=r->next;
r1=r->next; r->next=r->next->next; delete r1;}
Найти элемент с заданным значением ключевого поля.
r=first; b=1;
while (r!=NULL&&b)
{if (r->inf!=x) r=r->next;
else b=0;};
if (!b) cout<<r->inf<<endl;
Деревья, основные операции над деревьями, представление дерева массивом.
Дерево – древовидная структура с базовым типом Т, либо пустая структура, либо узел типа Т, с которым связано конечное число древовидных структур с базовым типом Т поддерева.
Пусть базовый тип – множество букв.
(a (b (d (i) ) (e) (f) ) (c (g) (h (k) (l) ) ) )
Дерево – неориентированный связный граф без циклов с n вершинами и n-1 ребром.
Дерево – конечное множество элементов, называемых узлами: узел у находящийся под узлом х – потомок(сын) х, а узел х – предок(отец) у. Если х на уровне I, то y на уровне i+1.
Корень дерева – узел не имеющий отца. Max. уровень элемента – высота(глубина).
Если узел не имеет сыновей, то он терминальный – лист, а тот, который не является листом – внутренний. Количество потолков узла – степень. Количество ветвей или рёбер, которые надо пройти, чтобы продвинуться от корня к узлу х – длина пути Lx.
Упорядоченное дерево – такое, у которого ветви каждого узла (узлы) упорядочены, то есть следующие 2 дерева будут различны.
Бинарное дерево – множество узлов, каждый из которых либо пуст, либо состоит из узла, связанного с 2-мя различными бинарными деревьями (левое и правое поддеревья узла), то есть каждый узел имеет 0, 1 или 2 сына.
Операции над деревьями:
Построение дерева.
Добавление элемента в упорядоченное дерево.
Удаление элемента из упорядоченного дерева.
Обход бинарного дерева. (Прямой +ab, Симметричный a+b, Обратный ab+)/
Поиск в дереве величины с ключом равным данному.
Представление массивом: компоненты д.б. типа, 2 поля указывают на поддеревья узла(содержать их адреса), остальные поля – информационная часть – данные, хранящиеся в этом узле.
Tree |
Info |
Left |
Right |
1 |
* |
2 |
3 |
2 |
+ |
6 |
4 |
3 |
- |
9 |
5 |
4 |
/ |
7 |
8 |
5 |
* |
10 |
11 |
6 |
A |
0 |
0 |
7 |
B |
0 |
0 |
8 |
C |
0 |
0 |
9 |
D |
0 |
0 |
10 |
E |
0 |
0 |
11 |
F |
0 |
0 |
Struct T {char info;
Int left, right;} Tree[11];
Это позволяет находить путь от корня к узлу, если значением каждого элемента a[i], является указатель на родителя узла i. Корень ссылается либо на себя, либо на 0. Значением одного из полей может быть указатель на родителя:
a[1] |
a[2] |
a[3] |
a[4] |
a[5] |
a[6] |
a[7] |
a[8] |
a[9] |
a[10] |
0 |
1 |
1 |
2 |
2 |
5 |
5 |
5 |
3 |
3 |
Цикл: while(b) {cout<<b<<’\t’; b=a[b];} выведет на экран путь от вершины b к корню. Т.е для b=7 выведет 7521.