Финальная викторина, 8 класс

Какая структура данных позволяет добавлять элемент с одной стороны, а удалять - с другой?

• Вектор

• Стек

• Очередь

• Дек

• Сет

Какие операции можно считать на отрезке с помощью идеи префиксных сумм?

• Количество нечётных чисел

• НОД

• Количество минимумов

• Произведение

• Количество чисел, меньших предыдущего

Как узнать номер буквы x в алфавите? Нумерация с 0

(x - строчная латинская буква)

• x + 'a'

• x + "a"

• x - 'a'

• x - "a"

За какую асимптотику работает преподсчёт в префиксных суммах?

Какие структуры данных итерируемы (можно перебирать с помощью auto)?

• Вектор

• Стек

• Очередь

• Дек

• Сет

За какую асимптотику будет работать ответ на запрос о сумме чисел на отрезке, если использовать разреженные таблицы?

Жадный алгоритм - это метод решения задач, при котором...

• Задача сводится к задача с меньшей размерности

• Каждую итерацию мы добавляем или удаляем элемент

• Перебираются все возможные варианты

• Каждую итерацию мы выбираем самое выгодное на данный момент

• Миша съедает всю кашу

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

• Жадный алгоритм

• Два указателя

• Динамическое программирование

• Перебор с возвратом

• Ничто из вышеперечисленного

За кукую асимптотику работает перебор с возвратом в задаче о рюкзаке в предыдущем вопросе? (Выбрать лучшую)

Как решается эта задача?

Найти в массиве самый короткий отрезок, в котором каждое число из массива встречается хотя бы 1 раз

• Жадный алгоритм

• Два указателя

• Динамическое программирование

• Ничто из вышеперечисленного