- •1. Понятие алгоритма: рекурсивные функции, системы текстовых замен.
- •2.Системы счисления, переводы чисел из одной позиционной системы в другую.
- •3/4.Понятие подпрограммы, функции, возвращающей/не возвращающей значение в
- •5.Передача параметров в подпрограмму,параметры входные и выходные,параметры,передаваемые по значению и по адресу.
- •6.Использование подпрограмм, параметры формальные, локальные, глобальные, обращения к подпрограммам, фактические параметры.
- •8.Статические и динамические переменные,динамическая память,работа с динамическими переменными.
- •9.Понятие линейного связного списка, типы списков, представление стека с помощью массива, пример использования стека.
- •10.Использование динамич. Переменных для представл. И работы со стеком.
- •11.Очередь,реализация очереди массивом.
- •12.Очередь, представление и реализация основных операций с помощью динамических переменных.
- •13.Реализация основных операций со списком:добавление, удаление, поиск.
- •14.Деревья,основные операции над деревьями, представление дерева массивом.
- •15.Двусвязные линейные списки, построение и обход бинарного дерева.
- •16.Операции поиска и удаления в бинарном дереве.
- •17.Понятие графа, представление графа в эвм.
- •18.Представление графа списком инцидентности,алгоритм обхода графа в глубину.
- •19.Представление графа списком списков,алгоритм обхода графа в ширину.
- •20.Технологии программирования,концепции,заложенные в ооп.
- •21.Основные понятия ооп:абстракция, инкапсуляция,полиморфизм.
- •22.Понятие объекта,его состояние и поведение,классы,определение класса и объявление класса.
- •23.Статистические,дружественные и виртуальные поля и методы,особенности их использования.
- •24.Абстрактные классы,их назначение и использование.
- •25.Понятие области видимости:общие,личные,защищенные и опубликованные поля и методы объекта.
- •26.Указатель This и перегрузка методов.
- •27.Использование классов,различные способы инициализации.
- •28.Использование классов,работа с массивами и указателями на объекты.
- •29.Наследование,пример использования наследования.
- •30.Конструкторы и деструкторы, их значение и использование.
- •31.Архитектура пк, основные функциональные устройства и их значения.
- •32.Мп с точки зрения программиста,регистры общего назначения.
- •33.Оперативная память,понятие исполняемого и физического адреса,сегментные регистры.
- •34.Регистр флажков, его назначение и использование.
- •35.Форматы данных и форматы команд.
- •36.Адресация операндов,способы адресации,примеры команд с различными способами адресации.
- •37.Структура программы на Ассемблере.Стандартные директивы сегментации.
- •38.Формат команды и директивы на Ассемблере.Примеры команд и директив.
- •39.Алфавит,слова,константы,переменные и выражения в Ассемблере.
- •40.Директивы определения данных и памяти.
- •41.Команды прерывания, команды работы со стеком.
16.Операции поиска и удаления в бинарном дереве.
1)Пусть ключевое поле — поле mf и мы рассмотрим дерево поиска:
Функция осуществляет поиск заданного элемента в дереве и если его не находит, то добавляет его в качестве листа.
Void Search (int x,tnode*&t){if(!t)/*такого эл-та нет, включаем его*/ {t=new tnode;
t->inf=x; t->left=NULL; t->right=NULL;}; else if(x<t->inf)search(x,t->left);
else if(x>t->inf) search(x,t->right); else(cout<<t->inf;}};
Эту функцию можно использовать для построения бинарного упорядоченного дерева,
вводя номер вершины с клавиатуры:
r=NULL; cin>>x; while(x!=0){Search(x,r); cout<<”vvedite№vershiny”<<endl;
cin>>x; cout<<endl;};
2)Удаление из упорядоченного дерева:
tnode*q;void Del_node(inf x;tnode*&t){if(t==NULL) {cout<<”такого узла нет”<<endl;};
else if(x<t->inf) Del_node(x,t->left); else if(x>t->inf) Del_node(x,t->right); else{ q=t;
if(q->left==NULL)t=q->right; else if(q->right==NULL)t=q->left; else Del_vs(q->left);
delete q;};};
17.Понятие графа, представление графа в эвм.
Граф G=(V,E) состоит из конечного множества вершин V и множества ребер E. Если ребра соединяют неупорядоченные пары вершин,т.е. E э {(x,y)|x,y э V&x!=y} то граф- неориентированный. Ребро(x,y).
Если ребра — направленные отрезки,то граф — ориентированный,ребра дуги,т.е множество ребер Е э VxV – множество упорядоченных пар вершин(<x,y,x-начало,
y-конец)
Если в графе G(V,E) ребро (u,v) или дуга <u,v> э E , то вершины u и v - смежные, а ребро(дуга) (u,v) - инцидентное вершинам u и v .
Для любой вершины оператора определяется кол-во дуг , исходящих из данной вершины(полустепень исхода) и входящих в неё(полустепень захода). Сумма полустепеней определяет степень вершин в орграфе. Вершина нулевой степени - изолированная.
Путь - последовательность рёбер вида (V0 , V1) ( V1 , V2)...(Vk-1, Vk) или последовательность вершин V0....Vk : V0 - начало , Vk - конец и k - длина пути.
Длина пути - сумма длин дуг , входящих в путь или их кол-во.
Путь простой, если все входящие в него вершины, кроме 1 и последней различны и путь 3амкнутый, если V0=Vk. Граф связный, если для любой пары вершин существует соединяющий их путь. Представление графа:
1) матрица инцидентности - размерности( n x m ,n- кол-во вершин, m - рёбер)
если U - откуда исходит, то в строку (-1) и (1) куда входит стрелка.
const int n= , m= ; int Matr_in [n][m]; матрица смежности где n- кол-во вершин, и aij = 1 , если существует ребро ( i,j) , иначе 0. Вершина : struct tgraf {int k; tgraf*left; Tnode*right;}; left - ука3атель на след. вершину right - на список вершин , смежной с k - oй . Struct tnode { int k; nexy*tnode;};
18.Представление графа списком инцидентности,алгоритм обхода графа в глубину.
Список смежности содержит для каждой вершины список вершин,смежных с ней.
Т.о. Для n-вершинного графа список смежности состоит из линейных связных списков,адрес и начало каждого списка хранятся в спец.массиве a[i] его элемент содержащий указатель на начало связного списка, содержащего смежные с i-ой вершины. Nach [1]->|2| |->|3| |; Nach [2]=NULL; Nach[3]=|2| |->|4|
| Представление списком смежности снимает ограничение на количество рёбер.
Обход в глубины: алгоритм: начинаем обход с произвольной вершины V0. 3атем выбираем любую вершину U , смежную с V0 и повторяем рекурсивно процесс от вершины U. В общем случае, находясь в некоторой вершине V , просматриваем, есть ли у неё не пройденные смежные вершины . Если есть , просматриваем её, полагая не новой, и продолжаем обход в глубину, если нет, полагаем её использованной и возвращаемся на шаг к вершине, из которой мы попали в V. Так до тех пор , пока не вернёмся в V0 и у нас уже не будет непройденных вершин.