1. Степенью вершины в неориентированном графе называют.

Ответ: Число инцидентных ей ребер.

2. Что такое исходящая степень вершины графа.

Ответ: Число исходящих из нее ребер.

3. В каком случае путь называется простым.

Ответ: Если все вершины в нем различны (Часть пути - подпуть).

4. Циклом в ориентированном графе называется.

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

5. Ориентированный граф называется простым, если.

Ответ: Он не содержит петель.

6. Полный граф – это.

Ответ: Неориентированный граф, содержащий всевозможные ребра.

7. Дерево без выделенного корня.

Ответ: Это связанный ациклический неориентированный граф.

8. Вершина корневого дерева называется листом если.

Ответ: Она не имеет детей (потомков).

9. Вершина корневого дерева называется внутренней если.

Ответ: Она имеет детей (потомков).

10. Дерево с порядком на детях.

Ответ: Это дерево, в котором для каждой его вершины множество детей упорядочено.

11. Высотой дерева называется.

Ответ: Максимальная длина пути от корня до листа.

12. Определение бинарного дерева.

Ответ: Это набор вершин, который либо пуст, либо делится на 3 непересекающиеся части :

1) корень; 2) левое двоичное поддерево корня; 3) правое двоичное поддерево корня;

13. Сколько листьев в полном k – ичном дереве.

Ответ: k^h , где h- высота дерева (высота - максимальная длина пути от корня до листа).

14. Определение f(n)=O(g(n)).

Ответ: Оценка сверху.

15. Определение f(n)=o(g(n)).

Ответ: Асимптотически точная оценка сверху.

16. Определение f(n)=(g(n)).

Ответ: Оценка снизу.

17. Определение f(n)=(g(n)).

Ответ: Асимптотически точная оценка снизу.

18. Определение абстрактного типа данных.

Ответ: Математическая модель данных в совокупности с операторами определенными на этих данных (в рамках этой модели).

19. АТД «Стек».

Ответ: Работает по принципу первый пришел, последний ушел. Элементы добавляются и извлекаются с одного конца. Реализуется на односвязных списках. Отдельно хранит указатель на голову (начало стека).

20. АТД «Очередь».

Ответ: Работает по принципу первый пришел, первый ушел. Элементы добавляются в один конец списка, а извлекаются с другого конца. Реализуется на односвязных списках. Хранит статический экземпляр, в котором хранятся указатели на голову ( начало очереди) и хвост (конец очереди).

21. АТД «Очередь по приоритетам».

Ответ: Работает по принципу первый пришел, наибольший или наименьший ушел. Используется для хранения элементов в порядке приоритета. Базируется на пирамидальной сортировке. Реализуется на массивах, списках и деревьях.

22. АТД «Двусторонняя очередь».

Ответ: Работает по принципу первый/последний пришел, первый/последний ушел. Элементы добавляются и извлекаются с обоих концов. Реализуется на двусвязных списках. Отдельно хранит экземпляр с указателями на голову/хвост и хвост/голову.

23. Время работы алгоритма сортировки линейными вставками.

Ответ: O(n) = N²

24. Время работы алгоритма сортировки двоичными вставками.

Ответ: O(n) = N²

25. Алгоритм сортировки методом Шелла.

Ответ: При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места.

(Если не понятно читай доп. Теорию ниже)

26. Время работы алгоритма сортировки методом Шелла.

Ответ: O(n) N^4/3

27. Алгоритм быстрой сортировки.

Ответ:

1) Элементы массива А[p..…r] переставляются таким образом, чтобы любой элемент из подмассива А[p..…q] не был больше любого из элементов подмассива А[q+1..…r] .

2) Процедура рекурсии вызывается для каждого из подмассивов.

Массив выгодно делить примерно пополам.

28. Время работы алгоритма быстрой сортировки.

Ответ: O(n) = Nlog2N

29. Алгоритм сортировки методом Синглтона.

Ответ: Алгоритм сортировки методом Синглтона (модифицированный метод быстрой сортировки):

1) Проверка на отсортированность.

2) Если массив короткий (до 4-х элементов) используются специальные методы:

Если 2 элемента то выбирается наибольший и наименьший элемент.

Если 3 элемента то выбирается тоже и наибольший и наименьший элемент средний вставляется посередине.

Если 4 элемента то используется сортировка двоичными вставками.

3) Если массив недлинный (до 100 элементов), то используют метод Шелла.

4) Длинные массивы делятся на 2 части по методу быстрой сортировки.

5) Для каждой его части рекурсивно вызывается метод Синглтона.

30. Время работы алгоритма сортировки методом Синглтона.

Ответ: O(n) = Nlog2N

31. Время работы алгоритма пирамидальной сортировки (бинарная куча).

Ответ: O(n) = Nlog2N

32. Алгоритм поразрядной сортировки.

Ответ:

1) При LSD сортировке, сначала сортируются младшие разряды, затем старшие с сохранением порядка следования одинаковых элементов. Используется метод подсчета внутри разряда. При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

2) При MSD сортировке, сначала сортируются старшие разряды, затем младшие с сохранением порядка следования одинаковых элементов. Используется метод Синглтона внутри разряда. MSD сортировке получается алфавитный порядок, который подходит для сортировки строк. Например "b, c, d, e, f, g, h, i, j, ba" отсортируется как "b, ba, c, d, e, f, g, h, i, j".

33. Время работы алгоритмов поразрядной сортировки.

Ответ: LSD = O(n) = N ; MSD = O(n) = Nlog2N

34. Алгоритм сортировки подсчетом.

Ответ:

Если каждый из n элементов последовательности – целое положительное число, не превосходящее заранее известного k , то можно использовать сортировку подсчётом.

1) Находим самый большой элемент по значению k в сортируемом массиве и создаем промежуточный массив на k элементов, предварительно обнулив его.

2) Проходим через сортируемый массив и для каждого его элемента находим соответствующий индекс в промежуточном массиве и увеличиваем значение элемента промежуточного массива с этим индексом на 1.

3) Затем в соответствии со значениями элементов промежуточного массива записываем отсортированный массив.

35. Время работы алгоритма сортировки подсчетом.

Ответ: T = n+k, где n - размерность входного массива, а k – наибольший по значению элемент в этом массиве.

36. Алгоритм сортировки двоичным слиянием.

Ответ:

1) Массив делится на два подмассива примерно одинакового размера.

2)Для каждого из подмассивов вызываем рекурсию до тех пор пока не получим единичные элементы.

3) Берем 2 смежные ячейки в двойки и сортируем их

4)Затем берем эти 2 смежные отсортированные двойки в четверки и сортируем их.

5)И так далее в таком порядке пока не получим отсортированный массив.

37. Время работы алгоритма сортировки двоичным слиянием.

Ответ: T = Nlog2N

38. Назовите «устойчивые» алгоритмы сортировок.

Ответ: «Устойчивые» алгоритмы сортировок - это алгоритмы, сохраняющие относительный порядок следования элементов в массиве. Сортировка двоичным слиянием, сортировка подсчётом, сортировка вставками и сортировка пузырьком.

39. Определение АТД первого класса.

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

(На С++ реализуется через шаблоны и перегрузку операций).

40. Алгоритм прямого обхода дерева.

Ответ: (сверху вниз) – узел -> левое поддерево -> правое поддерево.

41. Алгоритм поперечного обхода дерева.

Ответ: (слева направо) – левое поддерево -> узел -> правое поддерево.

42. Алгоритм обратного обхода дерева.

Ответ: (снизу вверх) – левое поддерево -> правое поддерево -> узел.

43. Определение АТД «Таблица символов».

Ответ: Структура данных элементов с ключами, которая поддерживает две базовые операции: вставка нового элемента и возврат элемента с заданным ключом.

44. Важнейшие операции АТД «Таблица символов».

Ответ:

1. вставка нового элемента 2. поиск элемента(ов) с заданным ключом 3. удаление эл-та

4. выбор K-го по величине 5. сортировка по ключам 6. объединение двух таблиц

45. Определение BST – дерева бинарного поиска.

Ответ: Это бинарное дерево, с каждым из внутренних узлов которого связан ключ, причем ключ в любом узле больше или равен ключам во всех узлах левого поддерева, и меньше или равен ключам во всех узлах правого поддерева этого узла.

46. Определение 2-3-4-дерева поиска.

Ответ: Это либо пустое дерево, либо дерево, содержащее 3 типа узлов:

1) 2-узлы с одним ключом, левой связью к дереву с меньшими ключами, правой связью к дереву с большими ключами;

2) 3-узлы с двумя ключами, левой связью к дереву с меньшими ключами, правой связью к дереву с большими ключами, средней связью к дереву, значения ключей которых лежат между значениями ключей данного узла;

3) 4-узлы с тремя ключами и четырьмя связями к деревьям, значения ключей которых определены диапазонами, образованными ключами узла.

47. Определение сбалансированного 2-3-4-дерева поиска.

Ответ: Это 2-3-4 дерево, все пустые деревья которого расположены на одинаковом расстоянии от корня.

48. Определение RB-дерева поиска.

Ответ: Это бинарное дерево, с каждым из узлов которого связан признак (красный, черный), с доп. условием: никакие 2 красные связи не могут идти подряд.

49. Определение сбалансированного RB-дерева поиска.

Ответ: Это дерево, в котором все пути от внешних связей к корню содержат одинаковое количество черных узлов.

50. Нарисуйте 4-узел и соответствующее ему RB-дерево.

Ответ:

51. Нарисуйте 3-узел и соответствующее ему RB-дерево.

Ответ:

52. Нарисуйте результат разделения 2-узел родитель и 4-узел потомок.

Ответ:

53. Нарисуйте результат разделения 3-узел родитель и 4-узел потомок.

Ответ:

54. Время построения и поиска на BST–дереве.

Ответ:

1) Построение в среднем O(n) = Nlog₂N, в худшем O(n) = N²

2) Поиска в среднем O(n) = log₂N, в худшем O(n) = N.

55. Время работы бинарного поиска.

Ответ: O(n) = log₂N.

56. Время поиска на BST–дереве, в среднем.

Ответ: O(n) = log₂N.

57. Время построения и время поиска на BST–дереве, в худшем случае.

Ответ: Построение O(n) = N² , поиск O(n) = N

58. Определение списка пропусков.

Ответ: Это связанный список, в котором каждый узел содержит разное количество связей, причем i-е связи в узлах реализуют односвязные списки, пропускающие узлы, содержащие менее чем i связей.

Количество уровней: j+1.

Количеств пропускающих узлов t^j.

59. Зондирование – это?

Ответ: Первое обращение к странице (на винчестере, не загружена в ОП), где страница – это непрерывный блок данных.

60. Определение В-дерева.

Ответ: Это дерево, каждый узел которого содержит M записей и некоторый минимум записей, за исключением корня (он может содержать только одну запись).