Федеральное государственное бюджетное образовательное учреждение высшего образования
(ВоГУ)
Кафедра АВТ Дисциплина: Построение и анализ алгоритмов
Билет №10
- Классификация методов сортировки. Простые методы сортировки (пузырьком, простым выбором, простыми вставками)
- Задача. В круге стоят N человек. Условно пронумеруем их по порядку от 1 до N. Первый начинает произносить считалку из K слов (каждый следующий человек произносит следующее слово). Тот, кто произнёс последнее слово, выбывает. Затем считалку начинает произносить следующий за выбывшим и т.д. Процесс продолжается до тех пор, пока не останется один человек. Определите его номер.
Преподаватель Зав. кафедрой
Министерство образования и науки
Федеральное государственное бюджетное образовательное учреждение высшего образования
(ВоГУ)
Кафедра АВТ Дисциплина: Построение и анализ алгоритмов
Билет №11
- Быстрая сортировка Хоара
- На столе лежит стопка из N книг, условно пронумерованных сверху вниз от 1 до N. Некто решил перепутать все книги в стопке и действует следующим образом: берёт стопку из K верхних книг, переворачивает и помещает её в низ стопки, затем снова делает то же самое, и так M раз. Например, если N=5, K=3, M=2, то у нас получается такая последовательность: 1 2 3 4 5 -> 4 5 3 2 1 -> 2 1 3 5 4. Определите результирующую перестановку.
Преподаватель Зав. кафедрой
Министерство образования и науки
Федеральное государственное бюджетное образовательное учреждение высшего образования
(ВоГУ)
Кафедра АВТ Дисциплина: Построение и анализ алгоритмов
Билет №12
- Сортировка слиянием
- Имеется N камней разного веса (N<21, веса до 108). Требуется разложить их на две кучки так, чтобы разница весов этих кучек была как можно меньше.
Преподаватель Зав. кафедрой
Министерство образования и науки
Федеральное государственное бюджетное образовательное учреждение высшего образования
(ВоГУ)
Кафедра АВТ Дисциплина: Построение и анализ алгоритмов
Билет №13
- Троичный поиск
- Задача. Дан набор слов. Над ними строится структура данных «бор» («луч»). Требуется определить количество вершин в этой структуре.
Преподаватель Зав. кафедрой
Министерство образования и науки
Федеральное государственное бюджетное образовательное учреждение высшего образования
(ВоГУ)
Кафедра АВТ Дисциплина: Построение и анализ алгоритмов
Билет №14
- Хеширование с цепочками переполнения
- Задача. Дано бинарное дерево, все его вершины уникально пронумерованы целыми числами. КЛП-скобочное представление дерева строится следующим образом: пустое дерево представляется словом NIL, дерево из одной вершины представляется одним числом - её номером, непустое дерево представляется как (n,A,B), где n - номер корня дерева, A и B - КЛП-скобочные представления левого и правого поддеревьев. Аналогично строится и ЛКП-представление, только непустое дерево записывается как (A,n,B). Дано КЛП-представление дерева. Требуется получить его ЛКП-представление.
Преподаватель Зав. кафедрой
Министерство образования и науки
Федеральное государственное бюджетное образовательное учреждение высшего образования
(ВоГУ)
Кафедра АВТ Дисциплина: Построение и анализ алгоритмов
Билет №15
- Хеширование без цепочек переполнения
- Дана постфиксная (польская) запись арифметического выражения, содержащая целые числа типа int и знаки действий +,-,*,/ (знак / означает целочисленное деление). Элементы выражения разделены пробелами. Длина выражения не превышает 255 символов. Гарантируется, что выполнение операций в заданном порядке не приводит к переполнению или делению на 0. Требуется вычислить значение данного выражения.
Преподаватель Зав. кафедрой
Министерство образования и науки
Федеральное государственное бюджетное образовательное учреждение высшего образования
(ВоГУ)
Кафедра АВТ Дисциплина: Построение и анализ алгоритмов
Билет №16
- Распределяющая сортировка
- Задача. Даны два текстовых файла. Найти количество различных слов, которые есть во втором файле, но нет в первом. Примечание: словом в данной задаче называется последовательность английских букв, слева и справа от которой нет буквы.
Преподаватель Зав. кафедрой
Министерство образования и науки
федеральное государственное бюджетное образовательное учреждение высшего образования
(ВоГУ)
Кафедра АВТ Дисциплина: Построение и анализ алгоритмов
Билет №17
- Сортировка пирамидой
- Задача. Дан текстовый файл. Найти все словосочетания из двух слов, которые встречаются не менее K раз (значение K вводится). Примечание: словом в данной задаче называется последовательность английских букв, слева и справа от которой нет буквы.
Преподаватель Зав. кафедрой