- •Дані як основа, з якою працює програмне забезпечення. Модифікація даних. Вимоги до даних в частині швидкості пошуку та модифікації. Навести приклади із баз даних різного призначення.
- •Структура даних мови Object Pascal, коротка характеристика складених типів даних, приклади використання.
- •Масиви статичні та динамічні, переваги та недоліки. Використання масивів для організації роботи з даними. Заповнення масивів з файлу.
- •Формування типізованого файлу на базі таблиці Excel. Приклад програми.
- •Масиви статичні та динамічні. Додавання, видалення та модифікація даних (робота із даними). Приклад програмного коду.
- •Стек: призначення, приклади, застосування. Організація та робота стеку на базі масиву. Приклад програмного коду.
- •Черга: призначення, приклади , застосування. Організація та робота черги на базі масиву. Приклад програмного коду.
- •Пошук даних в масиві. Послідовний та бінарний методи пошуку. Переваги та недоліки. Приклад програмного коду.
- •Сортування масивів на місці, метод вставок.
- •Сортування масивів на місці, метод простого вибору.
- •Сортування масивів на місці, прості та складні алгоритми сортування. Приклад програмного коду (але не бульбашкою).
- •Сортування масивів на місці, метод Shaker (одночасний пошук мінімального та максимального елементів.
- •Динамічний список: призначення, організація, формування, ініціалізація, наприклад з файлу. Переваги та недоліки порівняно з масивами. Приклад програмного коду.
- •Лінійний динамічний список: додавання, видалення та модифікація даних (робота з даними, порівняти із масивами). Приклад програмного коду.
- •Кільцевий динамічний список: переваги та недоліки порівняно з лінійним. Додавання, видалення та модифікація даних (робота із даними). Порівняти з лінійним. Приклад програмного коду.
- •Сортування даних у динамічних списках по одному та декільком полях. Приклад програмного коду.
- •Стек: призначення, приклади , застосування. Організація стеку за допомогою лінійного динамічного списку. Приклад програмного коду.
- •Включення/забирання елемента до/з стеку. Приклад програмного коду.
- •Включення/забирання елемента до/з черги. Приклад програмного коду.
- •Черга: призначення, приклади застосування. Організація черги за допомогою лінійного динамічного списку. Приклад програмного коду.
- •Формування черги: принципи вставки заявок у чергу, використання приоритетів при формування черги. Позачерговий пріоритет (0).
- •Визначення характеристик черги: середня довжина черги, середній час виконання заявки.
- •Наведіть алгоритми додавання (insert) заявки у чергу.
- •Наведіть алгоритми обслуговування (service) заявки у черзі.
- •Робота із плоским файлом. Додавання, видалення та модифікація даних (робота із даними). Файли переповнення. Порівняти з масивами та списками. Приклад програмного коду.
- •Пошук даних у плоских файлах (послідовний та бінарний). Сортування файлів по одному та декільком полям. Приклад програмного коду.
- •Пошук даних у плоских декількох логічно зв’язаних файлах. Приклад програмного коду.
- •Індексні файли: призначення, створення та використання. Переваги та недоліки. Приклад програмного коду.
- •Сторінкова організація файлу: переваги та недоліки порівняно з плоским файлом. Файли переповнення.
- •Індексна організація файлу. Одно- та багаторівнева індексація. Переваги та недоліки порівняно з плоским файлом. Ознаки необхідності реорганізації файлу. Навести схему з поясненнями.
- •Динамічна організація при сторінковій організації файлу, організація файлів переповнення. Навести схему з поясненнями.
- •Файли прямого доступу. Визначення адрес в залежності від значення даних. Функції хешування. Файл переповнення. Загальні алгоритми.
- •Функції хешування: алгоритми ділення, складання.
- •Функції хешування: алгоритми зсуву розрядів, .
- •Функції хешування: алгоритми ділення, .
- •Колізії при хешуванні, шляхи (декілько) розв’язання цих проблем.
- •Дерева: загальна характеристика, структура вузла, приклади використання.
- •Бінарні дерева пошуку: приклади призначення, структура вузла, алгоритм формування.
- •Бінарні ідеально сбалансовані дерева: приклади призначення, структура вузла, алгоритм формування.
Бінарні ідеально сбалансовані дерева: приклади призначення, структура вузла, алгоритм формування.
Дерево является СБАЛАНСИРОВАННЫМ тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1.
Поэтому деревья, удовлетворяющие этому условию, часто называют "АВЛ-деревьями" (по фамилиям их изобретателей).
Операции выполняемые над сбалансированным деревом: поиск, вставка, удаление элемента.
Алгоритм построения идеально сбалансированного дерева при известном числе вершин n лучше всего формулируется с помощью рекурсии .
При этом необходимо лишь учесть, что для достижения минимальной высоты при заданном числе вершин, нужно располагать максимально возможное число вершин на всех уровнях, кроме самого нижнего.
Это можно сделать очень просто, если распределять все поступающие в дерево вершины поровну слева и справа от каждой вершины.
взять одну вершину в качестве корня.
построить левое поддерево с nl = n DIV 2 вершинами тем же способом.
построить правое поддерево с nr = n-nl-1 вершинами тем же способом.
В сбалансированном дереве каждый узел должен находится в одном из этих трех состояний. Если в дереве существует узел, для которого это условие несправедливо, такое дерево называется несбалансированным.
function B_Tree(N:integer):Tree;
var
NewNode :Tree; Nl,Nr :integer; X :char;
begin
if N = 0 then B_Tree:=nil
else begin
Nl:=N div 2;
Nr:=N-Nl-1;
Inc(I);
X:= Mas[I];
New(NewNode);
with NewNode^ do begin
Key:=X;
Left:=B_Tree(Nl);
Right:=B_Tree(Nr);
end;
B_Tree:=NewNode;
end;end;
