Экзаменационные билеты САОД

                    ЭКЗАМЕНАЦИОННЫЕ БИЛЕТЫ  Саод

БИЛЕТ 1

1.  Задача Гаусса о ферзях.

2.  Генерация упорядоченных деревьев

3.  Написать подпрограмму сложения чисел, заданных в виде списков цифр.

БИЛЕТ 2

1.  Представление итерации рекурсией. Методы исключения рекурсии (показать на примере генерации перестановок).

2.  Очередь с приоритетами и методы ее организации.

3.  Написать программу, находящую по заданным числам x₁, ..., x_n  коэффициенты многочлена степени n, корнями которого являются эти числа.

БИЛЕТ 3

1.  Методы генерации перестановок.

2.  Оптимальное дерево поиска.

3.  Написать программу для решения задачи Джозефуса с помощью циклического списка

БИЛЕТ 4

1.  Косвенная рекурсия: Вывод кривой Пеано.

2.  Код Прюфера.

3.  (Код Грея.) Задано множество  {a₁ , a₂, …, a_n}.  Организовать перебор его подмножеств таким образом, чтобы каждое получалось из предыдущего добавлением или удалением одного элемента.

БИЛЕТ 5

1.  Линейные списки: организация стека.

2.  АВЛ—деревья.

3.  Написать подпрограмму двоичного поиска элемента в отсортированном массиве.

БИЛЕТ 6

1.  Очередь и ее организация.

2.  Черно—красные деревья.

3.  Написать программу генерации m-элементных подмножеств n-элементного множества.

БИЛЕТ 7

1.  Задача о размене денег.

2.  Б-деревья. Поиск и добавление элементов.

3.  Из шахматной доски вырезали несколько клеток. Написать программу, находящую маршрут шахматного коня обходящего все оставшиеся поля, побывав на каждом ровно один раз.

БИЛЕТ 8

1.  Организация циклического однонаправленного списка

2.  Сжатие файла методами Фано и Хаффмена.

3.  Написать рекурсивную подпрограмму float fix(f, a, b, eps); для нахождения корня уравнения x = f (x)  на отрезке [a, b], с точностью до eps. Функция f (x) непрерывна и отображает отрезок [a,b] в себя.

БИЛЕТ 9

1.  Обход вершин графа в ширину и глубину

2.  Сортировочные сети и параллельна сортировка Бетчера.

3.  Вывести все расположения 8 слонов на шахматной доске, не бьющих друг друга и стоящих на различных вертикалях.

БИЛЕТ 10

1.  Синтаксический анализ и вычисление значений арифметических выражений методом рекурсивного спуска.

2.  Турнир с выбыванием.

3.  (Лабиринт) Похожая на шахматную доску квадратная таблица состоит из нечетного числа клеток, раскрашенных в два цвета – белый и черный. Требуется найти все пути из центра к краю таблицы из белых клеток. Пути состоят из горизонтальных и вертикальных перемещений.

БИЛЕТ 11

1.  Динамическое программирование: Алгоритм Дейкстры поиска кратчайшего пути.

2.  Быстрая сортировка Хоара.

3.  Число задается в виде стека составляющих его цифр. Написать подпрограмму сложения и вычитания двух чисел.

БИЛЕТ 12

1.  Рекурсивный обход вершин графа.

2.  Пирамидальная сортировка.

3.  Граф задан с помощью трех массивов, содержащих для каждого ребра информацию о начальной и конечной вершинах и длину ребра. Написать программу, находящую с помощью алгоритма Краскала номера  ребер его кратчайшего остова.

БИЛЕТ 13

1.  Организация циклического двухсвязного списка.

2.  Четырехленточная сортировка.

3.  Из шахматной доски удалили p клеток 

(x[0],y[0]), (x[1],y[1]), ... , (x[p-1],y[p-1]).

Определить, может ли шахматный конь попасть с поля (1,1)  на поле (a,b)?

БИЛЕТ 14

1.  Бинарные деревья и организация их перебора.

2.  Простое двухпутевое слияние.

3.  Даны монеты достоинством p₁ < p₂ < … < p_s, достаточное число каждого достоинства. Найти наименьшее количество монет, в сумме дающих заданное число m.

БИЛЕТ 15

1.  Организация бинарного дерева поиска. Алгоритм удаления элемента.

2.  Естественное двухпутевое слияние.

3.  Задан текст, состоящий из букв A и B и операций * и +. Проверить, является ли префиксной формой записи арифметического выражения.

БИЛЕТ 16

1.  Генерация подмножеств, состоящих из заданного числа элементов

2.  Простая (трехленточная) сортировка слиянием.

3.  Заданно множество чисел . При заданном k перебрать все его подмножества  , в сумме дающих заданное число M.

БИЛЕТ 17

1.  Методы перебора подмножеств. Код Грея.

2.  Двухленточная сортировка на основе поразрядной

3.  Организовать стек. Применить его для поиска элемента двоичного дерева в глубину.

БИЛЕТ 18

1.  Задача Эйлера.

2.  Обменная поразрядная сортировка.

3.  Имеется внешний массив чисел x[0], x[1], ..., x[N-1]. Написать подпрограмму, аргументом которой является элемент этого массива, возвращающую номер этого элемента в отсортированном массиве.

БИЛЕТ 19

1.  Представление деревьев с помощью бинарных деревьев и методы обхода.

2.  Сортировка подсчетом. Распределяющий подсчет.

3.  Написать программу перебора монотонно неубывающих отображений между множествами {0,1,2, ..., m} и {0,1,2, ..., n}.

БИЛЕТ 20

1.  Список смежности для графа

2.  Сортировка Шелла.

3.  Написать программу перебора решений уравнения z₁ + z₂ + ... + z_s = n  (z_i > 0).      Решения, полученные друг из друга перестановкой, считаются различными.

БИЛЕТ 21.

1.  Методы вставок: бинарные, двухпутевые и вставки в список.

2.  Нахождение гамильтонова цикла в графе

3.  Написать программу построения остова минимального веса