- •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.Команды прерывания, команды работы со стеком.
13.Реализация основных операций со списком:добавление, удаление, поиск.
Описание элемента списка в общем виде: struct tnode {int inf; tnode *next;}
1)Добавить элемент с указателем p за элементом с указателем q.
p->next=q->next; q->next=p;
2)Добавить элемент с указателем 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; delete r;
3)Удалить элемент расположенный за элементом указателя q.
q->next=q->next->next;/*стирает память*/ или r=q->next; q->next=r->next; delete r;
4)Удалить элемент с указателем 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;}
5)Найти элемент с заданным значением ключевого поля.
r=first;b=1; while (r!=NULL&&b) {if(r->inf!=x)r=r->next; else b=0;}; if(!b) cout<<r->inf<<endl;
14.Деревья,основные операции над деревьями, представление дерева массивом.
Дерево — древовидная структура с базовым типом Т, либо пустая структура, либо узел типа Т, с которым связано конечное число древовидных структур с базовым типом Т поддерева.
Пусть базовый тип множество букв. (a(b(d(i))(e)(f))(c(g)(h(k)(l))))
Дерево — неориентированный связный граф без циклов с n вершинами и n-1 ребром.
Дерево — конечное множество элементов, называемых узлами: узел y под x — потомок, узел x – предок y .
Корень дерева - узел, не имеющий отца. Мах. уровень— высота, глубина.
Узел не имеет сыновей — терминальный — лист. Внутренний — не является листом.
Упорядоченное дерево — такое, у которого ветви каждого узла упорядочены, то есть следующие 2 дерева будут различны.
Бинарное дерево — множество узлов, каждый из которых либо пуст, либо состоит из узла, связанного с 2-мя различными бинарными деревьями, т.е каждый узел имеет 0,1 или 2 сына.
Операции над деревьями:
1)Построение дерева
2)Добавление элемента в упорядоченное дерево
3)Удаление элемента из упорядоченного дерева.
4)Обход бинарного дерева.
5)Поиск в дереве величины с ключом равным данному.
Представление массивом: компоненты д.б. типа,2 поля указывают на поддеревья узла, остальные поля — информационная часть — данные, хранящиеся в этом узле.
(a+b/c)*(d-e*f)
Struct T {char info;
Int left, right;} Tree[11];
15.Двусвязные линейные списки, построение и обход бинарного дерева.
Дерево — структура данных, которая может быть рекурсивно определена и поэтому для работы с деревьями предпочтительнее использовать рекурсивные алгоритмы.
Идеально сбалансированное — такое, что для любого узла верно, что количество узлов в левом поддереве отличается от количества узлов в правом поддереве не больше чем на единицу.
Построение: Пусть информационной частью будут номера вершин, вводимых с клавиатуры. Рекурсивный алгоритм. 1) Взять 1 узел в качестве корня. 2) построить левое поддерево состоящее из nl = n/2 узлов тем же способом. 3) Построить правое поддерево состоящее из nr=n-nl-1 узлов
1) Не возвращающая.
Void Tree(tnode *&t, int n) {tnode *r; int nr, nl, x; If (n==0) t=NULL; Else {nl=n/2; nr=n-nl-1;
Cout<<”Введите номер вершины”<<endl; cin>>x; r=new tnode; r->inf=x; Tree(n->left, nl); Tree(n->right, nr);};};
2) Возвращающая.
Tnode *Tree(int n) {tnode *r; int nl, nr, x; If (n==0) return 0; Else {nl=n/2; nr=n-nl-1; cout<<nl<<nr; Cout<<”введите номер вершины”;cin>>x; r=new tnode; r->inf=x;
r->left=Tree(nl); r->right=Tree(nr); return r;};};
Обходы бинарного дерева: 1) Прямой 2) Симметричный. 3) Обратный
1) Void Preorder(tnode *t) {If (t!=NULL) {cout<<t->inf<<’t’; Preorder(t->left);
Rteorder(t->right);};};
2) Void Inorder(tnode *t) {if (t!=NULL) {Inorder(t->left); Cout<<t->inf<<’\t’;
Inorder(t->right);};};
3) Void Postorder(tnode *t) {if(t!=NULL) {Postorder(t->left); Postorder(t->right);
Cout<<t->inf<<’\t’;};};