Вопросы № 1-28 к экзамену по дисциплине "Структуры и алгоритмы обработки данных" (Оценка эффективности алгоритмов. Нотация Big-O. Б-дерево. Представление Б-дерева)

1. Оценка эффективности алгоритмов. Нотация Big-O. Техника вывода оценки Big-O на примере алгоритма сортировки вставками. Классификация алгоритмов по трудоёмкости.
2. Алгоритмы сортировки выбором и сортировки с помощью дерева выбора. Эффективность алгоритмов.
3. Алгоритмы сортировки выбором и пирамидальной сортировки. Эффективность алгоритмов.
4. Алгоритмы сортировки вставками и сортировки Шелла. Эффективность алгоритмов.
5. Алгоритмы обменной сортировки и Шейкер - сортировки. Эффективность алгоритмов.
6. Алгоритмы обменной сортировки и сортировки разделением. Эффективность алгоритмов.
7. Алгоритмы нисходящей и восходящей сортировки слиянием.  Эффективность алгоритмов.
8. Алгоритм поразрядной сортировки MSD и LSD. Эффективность алгоритмов.
9. Стек и очередь, общая характеристика, формы представления и операции.
10. Список, общая характеристика, формы представления и операции.
11. Деревья. Общая характеристика, формы представления и операции.
12. Бинарное дерево поиска. Схемы обхода бинарных деревьев. Итеративные и рекурсивные алгоритмы обхода дерева.
13. Бинарное дерево поиска. Алгоритмы поиска, вставки и  удаления элементов. Эффективность алгоритмов.
14. Бинарное дерево поиска. Алгоритм вставки в корень дерева нового элемента. Алгоритм объединения двух деревьев.
15. Бинарное дерево поиска. Алгоритмы поиска для заданного узла предыдущего и следующего по ключу узла дерева.
16. Бинарное дерево поиска. Алгоритм поиска К –го порядкового элемента. Алгоритм разбиения дерева на два дерева.
17. Сбалансированные деревья поиска. Алгоритм общей балансировки бинарного дерева поиска.
18. Рандомизированное дерево поиска. Алгоритмы вставки  и удаления элементов в рандомизированном дереве. Эффективность операций в рандомизированном дереве.
19. АВЛ – дерево поиска. Алгоритм вставки  и удаления элементов в АВЛ – дереве. Эффективность операций в АВЛ-дереве.
20. АВЛ – дерево поиска. Алгоритм удаления элементов, эффективность операций в АВЛ-дереве.
21. 2 – 3-дерево поиска. Алгоритм вставки и удаления элементов в 2 – 3-дереве. Эффективность операций в 2-3-дереве.
22. 2-3-4-дерео и красно-черное дерево. Моделирование операций 2-3-4-дерева в красно-чёрном дереве.
23. Рекурсивный и итеративный алгоритмы вставки в красно-чёрное дерево.
24. Итеративный алгоритм удаления из красно-чёрного дерева.
25. Хеш – таблицы. Типы и особенности функций хеширования.
26. Хеш – таблицы с цепочками коллизий и с открытой адресацией. Алгоритмы операций в хеш-таблицах. Методы повторного хеширования в хеш-таблицах с открытой адресацией. Эффективность операций  в хеш-таблицах.
27. Структуры внешнего поиска. Основные принципы организации структур внешнего поиска. Представление хешированного файла, плотного и разреженного индексного файла.
28. Б-дерево. Представление Б-дерева.  Алгоритмы вставки и удаления в Б-дереве. Эффективность операций в Б-дереве.

• назначение алгоритма,
• назначение вспомогательного алгоритма,
• нотация трудоемкости алгоритма

Insertion_Sort(A)      Shell_Sort (A)

Выполните графическую трассировку алгоритма Shell_Sort (по результатам повторений цикла 4 – 11 с отображением переменных A, h) для следующих данных:

5  23  2  6  8  2  78  1  9  12 

Selection_Sort (A)    Heap_Sort (A) Shift (A, l, r)

Выполните графическую трассировку алгоритма Heap_Sort (по результатам повторений циклов 4 – 6 и 7 – 12 с отображением переменных A, L, R) для следующих данных:       5 23  2  6  8  2  78  1  9  12 

Bubble_Sort (A)        Sheker_Sort (A)

Выполните графическую трассировку алгоритма Sheker_Sort (по результатам повторений циклов 4 -9 и строки 11 – 16, с отображением переменных A, l, r) для следующих данных: 5  23  2  6  8  2  78  1  9  12 

QSort (A, l, r)            Partition (A, l, r)

Выполните графическую трассировку алгоритма QSort с отображением переменных A, l, r для следующих данных: 5  23  2  6  8  2  78  1  9  12 

Itrative_QSort (A, n)

Выполните графическую трассировку алгоритма Itarative_QSort (по результатам повторений цикла 4 – 34 с отображением переменных A, L, R) для следующих данных:

5  23  2  6  8  2  78  1  9  12 

Merge_Sort (A, L, R, C)                  Merge (A, L, m, R, C)

Выполните графическую трассировку алгоритма Merge_Sort (с отображением переменных A, L, R, m) для следующих данных: 5  23  2  6  8  2  78  1  9  12   

Iterative_Merge_Sort (A, n, C)      Merge (A, L, m, R, C)

Выполните графическую трассировку алгоритма Iterative_Merge_Sort (по результатам повторений цикла 1 – 7 с отображением переменных A, h) для следующих данных:  5  23  2  6  8  2  78  1  9  12   

MSD_Sort (A, l, r, d, C)

Выполните графическую трассировку алгоритма MSD_Sort для следующих данных:

123, 2154, 222, 4, 283, 1560, 1061,2150

LSD _Sort (A, n, C)

Выполните графическую трассировку алгоритма LSD _Sort для следующих данных:

123, 2154, 222, 4, 283, 1560, 1061,2150

BST_Search(t, k)                  BST_Insert(t, k)

BST_Iterative_Search(t, k) BST_ Iterative_Insert(t, k)

BST_Delete(t, k)      Del(t, t0)

Приведите изображение приведенной ниже структуры дерева после последовательного выполнения алгоритма BST_Delete(t, k) для k = 2, 5, 12, 6, 15.

t_L_R (t, Op)                         L_R_t (t, Op)

L_t_R (t, Op)                         Traverse (t, Op)

Для алгоритмов t_L_R (t, Op), L_R_t (t, Op), L_t_R (t, Op) и Traverse (t, Op) приведите последовательности элементов структуры дерева, над которыми выполняется операция Op(T).

BST_Root_Insert(t, x)         L(t)     R(t)

Приведите изображение изначально пустой структуры дерева после вызовов алгоритма BST_Root_Insert(t, x) для k = 15, 18, 7, 9, 4, 5, 14.

BST_Predecessor(t, x)         Maximum (t) BST_Right_Parent(t, x)

Приведите результат работы функции BST_Predecessor(t, x) для x = 9, 13, 5, 12.

BST_Part(t,k)           Selectk(t, k)              BST_Partition(t,x)                Ln(t)               Rn(t)

Приведите изображение заданной структуры после вызова BST_Part(t,9).

BST_Join(a,b) BST_Root_Insert(t, x) L(t) R(t)

Приведите изображение структуры, полученной в результате вызова алгоритма BST_Join для исходных структур:

BST_Balance(t)        BST_Partition (t,x)

BST_Part(t,k)           Selectk(t, k)              Ln(t)               Rn(t)

Приведите изображение структуры, полученной в результате вызова алгоритма BST_Balance для исходной структуры:

Rand_BST_Insert(t, k, data, inserted)       BST_Root_Insert(t, x)

Rand_L(t)                                                     Calc_n(t)

Приведите изображение структуры, полученной в результате вызова