- •1)Стандартные операции языка Си.
- •2)Линейные списки, операции с линейными списками.
- •3)Модели жизненного цикла по
- •Итерационная модель
- •Спиральная модель жизненного цикла по
- •II билет)
- •1)Обработка нештатных ситуаций. Объекты исключения. Примеры.
- •Вопрос 1: какова дальнейшая судьба этих ресурсов, будут ли они освобождены?
- •Вопрос 2: как распознавать подобные ситуации и корректно их обрабатывать?
- •2) Основные понятия ооп: абстракция, инкапсуляция, наследование, полифморфизм
- •3)Диаграммы классов. Нотация, отношения.
- •III билет)
- •1)Язык Си: указатели и массивы. Определения, примеры.
- •2)Абстрактные классы. Их назначение, пример.
- •3)Диаграммы прецедентов. Нотация, семантика, примеры.
- •Основные обозначения на диаграммах прецедентов:
- •IV билет)
- •1)Язык Си: объявление функций, передача аргументов. Примеры.
- •2)Язык Си: Работа с файловой системой. Примеры.
- •3)Сценарий выполнения прецедентов(пример).
- •V билет)
- •1)Язык Си: строки и указатели. Определения, примеры.
- •2)Язык Си: Низкоуровневый ввод/вывод. Пример.
- •3) Атрибуты на диаграммах классов. Нотация и семантика. Примеры.
- •VI билет)
- •1)Язык Си: аргументы командной строки. Перегруженные функции. Примеры.
- •2)Альтернативное определение ооп.
- •3)Операции на диаграммах классов. Нотация и семантика. Примеры.
- •VII билет)
- •1)Язык Си: организация ввода/вывода. Пример: слияние файлов.
- •Открытие файла
- •Закрытие файла
- •Ввод из файла
- •Вывод в файл
- •Особые ситуации
- •Пример: слияние файлов
- •2)Объекты классов. Статические, автоматические, динамические. Примеры.
- •3)Полиморфный контейнер(пример).
- •VIII билет)
- •1)Язык Си: структуры. Пример.
- •2)Управление доступом к элементам классов. Пример.
- •3)Двоичные деревья. Алгоритмы обхода, поиска, вставки, сортировки.
- •IX билет)
- •1)Язык Си: Произвольный доступ к файлам. Пример.
- •2) Конструкторы и деструкторы. Их виды. Вызов конструктора при наследовании Примеры.
- •3)Проектирование по и uml. Основные понятия.
- •Uml (основные понятия)
- •Канонические диаграммы языка uml 2.X
- •X билет)
- •1)Язык Си: оператор определения типа. Примеры.
- •2)Наследование классов. Пример с Абстрактными фигурами.
- •XI билет)
- •1)Язык Си: Препроцессор. Директивы препоцессора. Примеры.
- •2)Множественное наследование. Виртуальная схема наследования. Пример.
- •П оскольку классы-потомки наследуют все данные и методы классов-предков, в итоге имеем следующую картину:
- •3)Шаблоны Функций и шаблоны классов. Примеры.
- •XII билет)
- •1)Язык Си: программный стек. Пример работы стека.
- •2)Виртуальные функции. Раннее и позднее связывание.
- •3)Hash-таблицы(Таблицы с перемешиванием).
3)Двоичные деревья. Алгоритмы обхода, поиска, вставки, сортировки.
1. Пустой граф и граф с одним узлом есть двоичное дерево.
2. Граф следующего вида есть двоичное дерево:
3. Двоичное дерево, левая и правая части которого есть двоичное дерево также есть двоичное дерево
Дерево - структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг) причем в каждый узел (кроме корневого) ведет ровно одна дуга
Корень – начальный узел дерева
Лист – узел, из которого не выходит ни одна дуга
Способы обходы дерева:
Head, left, right (hlr): 1 2 4 5 3 6 7
Left, head, right (lhr): 4 2 5 1 6 3 7
Left, right, head (lrh): 4 5 2 6 7 3 1
Код алгоритмов обхода:
Hlr:
Void hlr(Tp p){ //указатель на корень
If(p){
R(p->ptr); //обработка узла
hlr(p->left);
hlr(p->right);
}
}
Lhr
Void lhr(Tp p){ //указатель на корень
If(p){
lhr (p->left);
R(p->ptr); //обработка узла
lhr (p->right);
}
}
Lrh
Void lrh(Tp p){ //указатель на корень
If(p){
lrh (p->left);
lrh (p->right);
R(p->ptr); //обработка узла
}
}
Двоичные деревья полезны когда им присущ внутренний порядок
Пусть определена хэш функция h(<object>)
Рекурсивный поиск в сорт. Дерево с включением
Пусть задан некий <object> для поиска и/или вставки в дерево
Void locate(Tp p){ //з – указатель на корень дерева
If(!p){ p = new T; p->ptr=&<object>; p->left = p->right = NULL;}
else if(<object>!=*p->ptr)
if(h(<object>) < h(*p->ptr)) locate(p->left);
else locate(p->right);
}// в итоге р – указатель на найденный или созданный элемент
Е сли дерево построено при помощи алгоритма locate тогда сортировка есть просто lhr обход или rhl обход сортирующего дерева
Пример:
Пусть данные поступают в порядке: 4 5 2 7 3 6 1
Осуществим lhr обход и получим 1 2 3 4 5 6 7
Итеративный поиск
Пусть задан некий <object>
void search1 (Tp p){ // р – указатель на корень
while(p && (*p->ptr != <object>)
if(h(<object> < h(*p->ptr)) p = p->left;
else p = p->right;
} //в итоге р – указатель на найденный узел или NULL
Рекурсивный поиск в сортирующем дереве
Пусть задан некий <object>
void search2(Tp p){ // р – указатель на корень
if(p) if(<object> != *p -> ptr)
if(h(<object>) < h(*p->ptr) search2(p->left);
else search2(p->right);
} //в итоге р – указатель на найденный узел или NULL
IX билет)
1)Язык Си: Произвольный доступ к файлам. Пример.
Файл можно рассматривать как последовательность байтов:
|байт-1| |байт-2| |байт-3| ...... |байт-n| |ЕОF|
Когда файл открыт, с ним связан поток. В потоке всегда имеется внутренний указатель на текущий обрабатываемый байт. Фактически это смещение (в байтах) от начала файла. Это число типа long, оно всегда может быть получено:
long ftell ( FILE *stream );
Функция возвращает текущий внутренний указатель (т.е. номер текущего обрабатываемого байта) для потока stream или -1L при ошибке в/в.
Обычная обработка файлов — последовательная. Функция fseek() позволяет обращаться с дисковым файлом как с массивом байтов:
long fseek ( FILE *stream, long offset, int origin );
Функция позиционирует текущий внутренний указатель (т.е. задает номер текущего обрабатываемого байта) для потока stream. Возвращает 0 при успешном позиционировании или величину, отличную от нуля, при ошибке в/в. Аргумент offset задает смещение относительно некоторой позиции. Позиция задается аргументом origin.
Возможные значения origin описаны в <stdio.h>:
SEEK_SET - начало файла
SEEK_END - текущая позиция SEEK_END - конец файла