2015-10-13
386
1 Дайте понятие термину «структура данных». Классификация структур данных.
2 Статические и динамические структуры данных.
3 Указатель. Базовые операции с указателями в языке Паскаль.
4 Структура данных «стек»: определение, основные операции – создание, добавление элемента, удаление элемента. Алгоритм преобразования выражения в обратную польскую запись.
5 Структура данных «односвязный список»: определение, основные операции – создание, добавление элемента, удаление элемента.
6 Структура данных «двусвязные список»: определение, основные операции – создание, добавление элемента, удаление элемента.
7 Структура данных «очередь»: определение, основные операции – создание, добавление элемента, удаление элемента.
8 Структура данных «кольцо»: определение, основные операции – создание, добавление элемента, удаление элемента.
9 Структура данных «бинарное дерево»: определение, основные операции над бинарным деревом – создание, добавление элемента, удаление элемента.
|
|
|
10 Опишите алгоритмы поиска по ключу и полного обхода в бинарном дереве.
11 Структура данных «прошитое бинарное дерево»: определение, основные операции – создание, добавление элемента, удаление элемента.
12 Опишите алгоритм поиска по ключу в прошитом бинарном дереве
13 Структура данных «красно-черное бинарное дерево»: определение, основные свойства, создание, размещение очередного элемента.
14 Комбинаторика. Размещения. Алгоритмы генерации размещений.
15 Комбинаторика. Сочетания. Алгоритмы генерации сочетаний.
16 Комбинаторика. Перестановки. Алгоритмы генерации перестановок.
17 Опишите алгоритмы генерирования множества всех подмножеств множества.
18 Опишите алгоритмы генерирования множества всех к-элементных подмножеств множества.
19 Понятие графа. Основные свойства графов.
20 Способы представления графов в памяти компьютера.
21 Опишите вычислительную схему алгоритма поиска в глубину на графе.
22 Опишите вычислительную схему алгоритма поиска в ширину на графе.
23 Опишите вычислительную схему алгоритма поиска кратчайшего пути между двумя вершинами на графе.
24 Опишите понятие «сеть». Дайте определение понятию максимального потока на сети.
25 Опишите алгоритм нахождения максимального потока методом Форда-Фанкерсона.
26 Опишите алгоритм нахождения потока минимальной стоимости.
27 Опишите общую схему полного перебора.
28 Опишите вычислительную схему алгоритма решения задачи о коммивояжере методом полного перебора.
29 Опишите вычислительную схему алгоритма решения задачи о шахматном коне методом полного перебора.
30 Опишите вычислительную схему алгоритма решения задачи о лабиринте методом полного перебора.
|
|
|
31 Опишите общие схемы сокращения полного перебора.
32 Понятие рекурсии. Вычислительная схема алгоритмов перебора с возвращением.
33 Опишите алгоритмы решения задачи о расстановке ферзей на шахматной доске.
34 Опишите технологии динамического программирования: восходящее динамическое программирование, нисходящее динамическое программирование.
35 Опишите способ реализации метода динамического программирования на примере задачи о ранце.
36 Опишите способ реализации метода динамического программирования на примере задачи генерирования чисел Фибоначчи.
37 Опишите способ реализации метода динамического программирования на примере задачи поиска наибольшей общей последовательности.
38 Опишите вычислительную схему метода ветвей и границ.
39 Опишите принципы работы алгоритма жадного выбора.
40 Опишите применение жадного алгоритма в задаче о поиске кратчайшего пути между двумя вершинами графа.
41 Опишите применение жадного алгоритма в задаче о ранце.
42 Опишите применение жадного алгоритма в задаче о сумме элементов подмножества.
43 Опишите вычислительную схему алгоритма Хоффмана.
44 Вычислительная геометрия. Опишите алгоритмы определения взаимного расположения отрезков, прямых и плоскостей.
45 Вычислительная геометрия. Опишите алгоритмы построения выпуклой оболочки.
46 Вычислительная геометрия. Опишите алгоритмы отыскания пары ближайших точек.
47 Вычислительная геометрия. Опишите алгоритмы нахождения площадей фигур.
48 Опишите методы генерирования равномерно распределенных случайных чисел.
49 Опишите методы генерирования нормально распределенных случайных чисел.
50 Опишите методы генерирования случайных чисел, распределенных по показательному закону.
51 Опишите классы задач, решаемых с помощью генераторов случайных чисел.
52 Понятия хеш-функции и хеш-таблицы.
53 Опишите методы хеширования: метод деления, метод середины квадратов, метод свертывания.
54 Коллизии при хешировании. Методы разрешения коллизий.
55 Опишите классы задач, решаемых с помощью построения хеш-таблиц.
