федеральное государственное бюджетное образовательное учреждение высшего образования

Федеральное государственное бюджетное образовательное учреждение высшего образования

(ВоГУ)

Кафедра АВТ Дисциплина: Построение и анализ алгоритмов

 

Билет №10

 

1. Классификация методов сортировки. Простые методы сортировки (пузырьком, простым выбором, простыми вставками)
2. Задача. В круге стоят N человек. Условно пронумеруем их по порядку от 1 до N. Первый начинает произносить считалку из K слов (каждый следующий человек произносит следующее слово). Тот, кто произнёс последнее слово, выбывает. Затем считалку начинает произносить следующий за выбывшим и т.д. Процесс продолжается до тех пор, пока не останется один человек. Определите его номер.

 

Преподаватель Зав. кафедрой

 

 

Министерство образования и науки

Федеральное государственное бюджетное образовательное учреждение высшего образования

(ВоГУ)

Кафедра АВТ Дисциплина: Построение и анализ алгоритмов

 

Билет №11

 

1. Быстрая сортировка Хоара
2. На столе лежит стопка из 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

 

1. Сортировка слиянием
2. Имеется N камней разного веса (N<21, веса до 10⁸). Требуется разложить их на две кучки так, чтобы разница весов этих кучек была как можно меньше.

 

Преподаватель Зав. кафедрой

 

 

Министерство образования и науки

Федеральное государственное бюджетное образовательное учреждение высшего образования

(ВоГУ)

Кафедра АВТ Дисциплина: Построение и анализ алгоритмов

 

Билет №13

 

1. Троичный поиск
2. Задача. Дан набор слов. Над ними строится структура данных «бор» («луч»). Требуется определить количество вершин в этой структуре.

 

Преподаватель Зав. кафедрой

 

 

Министерство образования и науки

Федеральное государственное бюджетное образовательное учреждение высшего образования

(ВоГУ)

Кафедра АВТ Дисциплина: Построение и анализ алгоритмов

 

Билет №14

 

1. Хеширование с цепочками переполнения
2. Задача. Дано бинарное дерево, все его вершины уникально пронумерованы целыми числами. КЛП-скобочное представление дерева строится следующим образом: пустое дерево представляется словом NIL, дерево из одной вершины представляется одним числом - её номером, непустое дерево представляется как (n,A,B), где n - номер корня дерева, A и B - КЛП-скобочные представления левого и правого поддеревьев. Аналогично строится и ЛКП-представление, только непустое дерево записывается как (A,n,B). Дано КЛП-представление дерева. Требуется получить его ЛКП-представление.

 

Преподаватель Зав. кафедрой

 

 

Министерство образования и науки

Федеральное государственное бюджетное образовательное учреждение высшего образования

(ВоГУ)

Кафедра АВТ Дисциплина: Построение и анализ алгоритмов

 

Билет №15

 

1. Хеширование без цепочек переполнения
2. Дана постфиксная (польская) запись арифметического выражения, содержащая целые числа типа int и знаки действий +,-,*,/ (знак / означает целочисленное деление). Элементы выражения разделены пробелами. Длина выражения не превышает 255 символов. Гарантируется, что выполнение операций в заданном порядке не приводит к переполнению или делению на 0. Требуется вычислить значение данного выражения.

 

Преподаватель Зав. кафедрой

 

 

Министерство образования и науки

Федеральное государственное бюджетное образовательное учреждение высшего образования

(ВоГУ)

Кафедра АВТ Дисциплина: Построение и анализ алгоритмов

 

Билет №16

 

1. Распределяющая сортировка
2. Задача. Даны два текстовых файла. Найти количество различных слов, которые есть во втором файле, но нет в первом. Примечание: словом в данной задаче называется последовательность английских букв, слева и справа от которой нет буквы.

Преподаватель Зав. кафедрой

 

 

Министерство образования и науки

федеральное государственное бюджетное образовательное учреждение высшего образования

(ВоГУ)

Кафедра АВТ Дисциплина: Построение и анализ алгоритмов

 

Билет №17

 

1. Сортировка пирамидой
2. Задача. Дан текстовый файл. Найти все словосочетания из двух слов, которые встречаются не менее K раз (значение K вводится). Примечание: словом в данной задаче называется последовательность английских букв, слева и справа от которой нет буквы.

 

Преподаватель Зав. кафедрой