- •Понятие алгоритма: рекурсивные функции, системы текстовых замен.
- •Системы счисления, переводы чисел из одной позиционной системы в другую.
- •Передача параметров в подпрограмму, параметры входные и выходные, параметры, передаваемые по значению и по адресу.
- •Использование подпрограмм, параметры формальные, локальные, глобальные, обращения к подпрограммам, фактические параметры.
- •Статические и динамические переменные, динамическая память, работа с динамическими переменными.
- •Понятие линейного связного списка, типы списков, представление стека с помощью массива, пример использования стека.
- •Использование динамических переменных для представления и работы со стеком.
- •Очередь, реализация очереди массивом.
- •Очередь, представление и реализация основных операций с помощью динамических переменных.
- •Реализация основных операций со списком: добавление, удаление, поиск.
- •Деревья, основные операции над деревьями, представление дерева массивом.
- •Двусвязные линейные списки, построение и обход бинарного дерева.
- •Операции поиска и удаления в бинарном дереве.
- •Понятие графа, представление графа на эвм.
- •Представление графа списком инцидентности, алгоритм обхода графа в глубину.
- •Представление графа списком списков, алгоритм обхода графа в ширину.
- •Технологии программирования, концепции, заложенные в ооп.
- •Основные понятия ооп: абстракция, инкапсуляция, полиморфизм.
- •Понятие объекта, его состояние и поведение, классы, определение класса и объявление класса.
- •Статические, дружественные и виртуальные поля и методы, особенности их использования.
- •Абстрактные классы, их назначение и использование.
- •Понятие области видимости: общие, личные, защищённые и опубликованные поля и методы объекта.
- •Указатель this и перегрузка методов.
- •Использование классов, различные способы инициализации.
- •Использование классов, работа с массивами и указателями на обьекты.
- •Наследование, пример использования наследования.
- •Конструкторы и деструкторы, их назначение и использование.
- •Архитектура пк, основные функциональные устройства и их назначение.
- •Мп с точки зрения программиста, регистры общего назначения.
- •Оперативная память, понятие исполняемого и физического адреса, сегментные регистры.
- •Регистр флажков, его назначение и использование.
- •Форматы данных и форматы команд, машинный формат двухадресной машины.
- •Адресация операндов, способы адресации, примеры команд с различными способами адресации.
- •Понятие команды и директивы в Ассемблере, формат команды и директивы.
- •Структура программы на Ассемблере с использованием стандартных директив сегментации.
- •Основные элементы языка Ассемблер: имена, константы, переменные, выражения.
- •Директивы определения данных и памяти, примеры.
- •Команда прерывания, команды работы со стеком.
- •Упрощённые директивы сегментирования, структура программы с использованием точечных директив, пример программы.
- •Этапы выполнения Ассемблерной программы на эвм, понятие com-файла.
- •Различие между exe - и com – файлами, требования, предъявляемые к исходному модулю, предназначенному для создания com – файла, примеры программ.
- •Понятие структурного программирования, этап проектирования – композиция и декомпозиция, понятие статической и динамической структуры программы, спецификация программы.
- •Понятие частичной и полной корректности программы, правила вывода – общий вид, правила консеквенции.
- •Правила вывода для операторов: пустого, присваивания, составного.
- •Правила вывода для операторов ветвления.
- •Правила вывода циклов с предусловием и посусловием.
Использование динамических переменных для представления и работы со стеком.
struct tstack { int inf; tstack*next}; //описание типа стек
tstack*init_stack() // инициализация стека
{ return NULL; }
void push (tstack*&s, init item) // добавление элемента в стек
{tstack *r=new tstack;
r->inf=item; r->next=s; s=r;}
int pop (tstack*&s) // удаление элемента из стека
{ tstack*r=s;
int i=r->inf; s=r->next;
delete r; return i;}
int peek (tstack*s) // просмотр элемента, расположенного на вершине стека
{return s->inf; }
int empty_stack(tstack*s) // определение стека на пустоту
{ return(s)?0:1; }; // 0, если пуст и 1 если не пуст
Объединив все функции в файл stackint.h и сохранив его в папке INCLUDE, можно подключить его к любой программе с помощью # include <stackint.h>
Пример: Переписать из h в g в обратной последовательности.
# include <stdio.h>
# include <stackint.h>
#include <iostream>
using namespace std;
FILE*h=fopen(“input_stack.txt”, “r”); // для чтения
FILE*g=fopen(“output.txt”, “w”); // для записи
int i;
tstack*sp=init_stack(); // инициализация sp=NULL
while (!feof(h))
{ fscanf (h, “%d”, &i);
push (sp, i);
printf(“%d\t”, i); };
cout<<”\n”;
while (!empty_stack(sp)) // пока стек не пуст
{ i=pop (sp);
printf (“%d\t”, i);
fprintf (g, “%d\t”, i); } ;
fcloseall ();}
Очередь, реализация очереди массивом.
Очередь – линейный список, где все включения (ввод, добавление компонент) производится с другой стороны, а исключения и всякий доступ – с другой; абстрактная структура данных, работающая по принципу FIFO. Так как доступ возможен с двух концов, существуют 2 переменные: head и tail. Можно описать и реализовать с помощью массива:
Const int n=100;
float Queue[n],x;
int head, tail;
Основные операции:
Инициализация очереди (присваивание начальных значений head и tail).
Пусть head = l, tail = 1. Head указывает на 1-ый элемент в очереди, tail – на последний или на l-ю свободную ячейку. Сначала tail head чтобы не переполнить массив, присвоить tail значение 1 и заполнять очередь с начала массива, т.о. закольцованная структура. Чтобы отличить пустую ячейку от непустой, оставляем 1 ячейку свободной. Если пуста, то head=tail, если полна, то head = tail+1.
Взятие элементов.
If (head = tail)
cout<<”Очередь пуста”;
else {x=Queue[head];
head=head+1;
if (head = n) head = 1;}
Добавление элемента.
r=tail +1;
if (r=n) r=1;
if (r=head) cout<<”Очередь полна”;
else {Queue[tail] = x;
tail = r;}
2-й вариант реализации: массив из n+1 элементов, описанного от 0 до n. tail указывает на последний элемент, head – на ячейку, предшествующую 1 элементу в очереди. Отличие: индекс tail увеличивается на 1, а затем проверка (tail=head).
Основные операции:
Инициализация. tail = 0, head =0.
Взятие элемента:
If (head = tail)
cout<<”очередь пуста”;
else {head=((head+1)%n);
x=Queue[head];}
Добавление элемента:
tail=((tail+1)%n);
if (tail=head) cout<<”Очередь полна”;
else Queue[tail]=x;
Изменение индекса массива head(tail), движение по кольцу осуществляется за счёт операции %. Если tail < n-1, то tail увеличивается на 1. (1%100)=1, (2%100)=2, но когда tail станет равным n-1, то tail присвоится 0. ((99+1)%100)=0.