"Продвинутые" алгоритмы для школьников

Упражнение 1:

Номер 1

Выпуклая оболочка для точек - это

Ответ:

(1) набор всех элементов множества точек

(2) наименьший многоугольник, содержащий все точки

(3) матрица смежности точек

Номер 2

Что представляет собой выпуклая оболочка?

Ответ:

(1) многоугольник

(2) окружность

(3) матрицу

Номер 3

Наименьший многоугольник, содержащий все данные точки, носит название

Ответ:

(1) матрица вариантности

(2) выпуклая оболочка

(3) поле точек

Упражнение 2:

Номер 2

Сортировка векторов по углу производится с помощью

Ответ:

(1) векторной суммы

(2) векторной разности

(3) векторного произведения

Номер 3

Каким образом можно произвести сортировку векторов по углу?

Ответ:

(1) с помощью матрицы смежности

(2) с помощью векторного произведения

(3) с помощью вектора инцидентности

Упражнение 3:

Номер 1

За какое минимальное время можно найти старший бит числа?

Ответ:

(1) O(1)

(2) O(n)

(3) O(logn)

Номер 2

Структура данных, позволяющая быстро изменять значения в массиве, носит название

Ответ:

(1) дерево отрезков

(2) матрица инцидентности

(3) граф определений

Номер 3

Дерево отрезков - это

Ответ:

(1) массив вершин графа

(2) структура данных, позволяющая быстро изменять значение в массиве

(3) взвешенный орграф динамических определений

Упражнение 4:

Номер 1

Что представляет собой дерево отрезков?

Ответ:

(1) структуру данных

(2) метод доступа к элементам

(3) тип связи

Номер 2

Что такое RSQ?

Ответ:

(1) дерево отрезков для суммы

(2) дерево отрезков для разности

(3) дерево отрезков для произведения

Номер 3

Дерево отрезков для суммы носит название

Ответ:

(1) SNQ

(2) RSQ

(3) QRS

Упражнение 5:

Номер 1

Увеличение в методе RSQ может быть

Ответ:

(1) только положительным

(2) только отрицательным

(3) как положительным, так и отрицательным

Номер 2

Какие определения используются при изменении в RSQ?

Ответ:

(1) отрезки, на которых производится изменение

(2) матрица инцидентности

(3) номера ячеек, в которых хранится информация

Номер 3

Сложность изменения в методе RSQ составляет

Ответ:

(1) O(n)

(2) O(nlogn)

(3) O(logn)

Упражнение 6:

Номер 1

Деревья отрезков, способные вычислять сумму и максимум, можно реализовать

Ответ:

(1) с хранением двух массивов одинаковой длины

(2) с матрицей вероятности

(3) с рекурсивной реализацией операции изменения

Номер 2

Какая реализация операции изменения используется при реализации дерева отрезков, способного вычислять сумму и максимум?

Ответ:

(1) рекурсивная

(2) матричная

(3) комплексная

Номер 3

Каким образом можно реализовать хранение деревьев отрезков, способных вычислять сумму и максимум?

Ответ:

(1) в двух массивах одинаковой длины

(2) в матрице инцидентности

(3) в стеке

Упражнение 7:

Номер 1

Что такое RMQ?

Ответ:

(1) дерево отрезков для максимума

(2) дерево отрезков для суммы

(3) дерево отрезков для произведения

Номер 2

Дерево отрезков для максимума носит название

Ответ:

(1) RSQ

(2) RMQ

(3) MRQ

Номер 3

Что представляет собой RMQ?

Ответ:

(1) матрицу

(2) дерево отрезков

(3) контейнер

Упражнение 8:

Номер 1

Препроцессинг для RMQ выполняется

Ответ:

(1) за O(n)

(2) за O(logn)

(3) за O(nlogn)

Номер 2

Нахождение максимума на отрезке выполняется

Ответ:

(1) за O(1)

(2) за O(n)

(3) за O(2n)

Номер 3

За какое время выполняется нахождение минимума на отрезке?

Ответ:

(1) O(logn)

(2) O(1)

(3) O(n)

Упражнение 9:

Номер 1

Найти все точки пересечений прямолинейных отрезков на плоскости позволяет алгоритм

Ответ:

(1) пересечения отрезков

(2) большинства покрытия

(3) матричной совместимости

Номер 2

Для чего применяется алгоритм пересечения отрезков?

Ответ:

(1) для нахождения всех точек пересечения отрезков

(2) для заполнения матрицы инцидентности

(3) для формирования остовного дерева

Номер 3

Какой метод применяется в алгоритме пересечения отрезков?

Ответ:

(1) метод выметающей прямой

(2) метод обобщающих прямых

(3) метод конструктивной матрицы

Упражнение 10:

Номер 1

Движущаяся прямая, сканирующая лини в алгоритме пересечения отрезков, носит название

Ответ:

(1) динамическая прямая

(2) выметающая прямая

(3) конструктивная прямая

Номер 2

К точкам событий алгоритма пересечения отрезков следует отнести

Ответ:

(1) концы отрезков

(2) точки пересечения отрезков

(3) точки статических максимумов

Номер 3

Самый верхний из пересекающихся отрезков в алгоритме пересечения отрезков после точки пересечения становится

Ответ:

(1) вторым верхним

(2) вторым нижним

(3) самым нижним

Упражнение 11:

Номер 1

Выметающая прямая может быть

Ответ:

(1) только горизонтальной

(2) только вертикальной

(3) как горизонтальной, так и вертикальной

Номер 2

Сколько будет точек пересечений, которые надо будет хранить, когда все отрезки, пересекаясь между собой, образуют прямоугольную сетку?

Ответ:

(1) O(n²)

(2) O(n)

(3) O(logn)

Номер 3

Удаление точки пересечения отрезков, которые временно перестают быть соседними при данном положении выметающей прямой, применяется для избегания использования

Ответ:

(1) квадрата памяти

(2) матрицы совместимости

(3) графа полярности

Упражнение 12:

Номер 1

В алгоритме пересечения отрезков используется динамические структура данных без повторений с логарифмическим временем

Ответ:

(1) поиска точек событий

(2) вставки точек событий

(3) удаления точек событий

Номер 2

Какие из приведенных ниже множеств используются в алгоритме пересечения отрезков?

Ответ:

(1) множество отрезков с точкой события в левом конце

(2) множество отрезков с точкой события в правом конце

(3) множество отрезков, пересекающихся в точке события

Номер 3

Если не удалять точки пересечения отрезков, которые перестали быть соседними, алгоритм пересечения отрезков занимает времени

Ответ:

(1) O(n)

(2) O(n+n²)

(3) O(nlogn)

"Продвинутые" алгоритмы для школьников - тест 10