WorksheetsФинальная викторина, 8 класс
Total questions: 26
Worksheet time: 31mins
Какая структура данных позволяет добавлять элемент с одной стороны, а удалять - с другой?
Вектор
Стек
Очередь
Дек
Сет
Какие операции можно считать на отрезке с помощью идеи префиксных сумм?
Количество нечётных чисел
НОД
Количество минимумов
Произведение
Количество чисел, меньших предыдущего
Как узнать номер буквы x в алфавите? Нумерация с 0
(x - строчная латинская буква)
x + 'a'
x + "a"
x - 'a'
x - "a"
За какую асимптотику работает преподсчёт в префиксных суммах?
O(1)
O(logn)
O(n)
O(nlogn)
O(n2)
Какие структуры данных итерируемы (можно перебирать с помощью auto)?
Вектор
Стек
Очередь
Дек
Сет
За какую асимптотику будет работать ответ на запрос о сумме чисел на отрезке, если использовать разреженные таблицы?
O(1)
O(logn)
O(n)
O(n+logn)
O(nlogn)
Жадный алгоритм - это метод решения задач, при котором...
Задача сводится к задача с меньшей размерности
Каждую итерацию мы добавляем или удаляем элемент
Перебираются все возможные варианты
Каждую итерацию мы выбираем самое выгодное на данный момент
Миша съедает всю кашу
Как можно решить задачу о рюкзаке, в которой мы хотим максимизировать стоимость набранных предметов? Веса предметов различны. Восстановление ответа не требуется
Жадный алгоритм
Два указателя
Динамическое программирование
Перебор с возвратом
Ничто из вышеперечисленного
За кукую асимптотику работает перебор с возвратом в задаче о рюкзаке в предыдущем вопросе? (Выбрать лучшую)
O(n)
O(nlogn)
O(n2)
O(2n)
O(n⋅2n)
Как решается эта задача?
Найти в массиве самый короткий отрезок, в котором каждое число из массива встречается хотя бы 1 раз
Жадный алгоритм
Два указателя
Динамическое программирование
Ничто из вышеперечисленного
Как решается эта задача?
Найти в массиве целых чисел отрезок с суммой, равной k
Жадный алгоритм
Два указателя
Динамическое программирование
Ничто из вышеперечисленного
Выберете все верные утверждения
Cn0 = 1
0∑nCnk = 2n
Cnk = Cnn−k
Cnk = Cnk−1 + Cn−1k−1
Ank = (n−k)!n!
За сколько вопросов можно бинарным поиском отгадать натуральное число от 1 до 500?
(a)
Для того, чтобы максимум функции можно было найти тернарным поиском, необходимо, чтобы...
функция сначала возрастала, а затем убывала
функция сначала убывала, а затем возрастала
функция всё время возрастала
функция всё время убывала
Во сколько раз сокращается область поиска за одну итерацию в тернарном поиске?
32
3
1,5
2
0,3
Есть 6 игроков. Сколькими способами можно выбрать из них одну мафию и одного доктора?
(a)
Сколько подмножеств у множества из 7 человек?
(a)
Сколькими способами можно из 10 детей выбрать 8, которые поедут на Байконур?
(a)
Что выведет данная программа?
1 2 -2 4 -1 -3 -5
1 2 5 4 6 4 2
1 2 2 4 1 3 5
1 2 -5 4 -6 -4 -2
Что выведет данная программа?
10
01
11
00
Что делает данная программа?
Набирает как можно больше чисел, чтобы сумма их остатков по модулю 3 не превышала k и при этом сумма остатков этих чисел была максимальной при данном количестве, выводит их сумму
Набирает как можно больше чисел, чтобы сумма их остатков по модулю 3 не превышала k и при этом сумма этих чисел была максимальной при данном количестве, выводит их сумму
Набирает как можно больше чисел, чтобы сумма их остатков по модулю 3 не превышала k, выводит их сумму
Набирает как можно больше чисел, чтобы сумма их остатков по модулю 3 не превышала k, выводит их сумму
Что выведет данная программа?
1 2
4 7
5 3
2 3
4 7
5 3
1 2
3 6
4 7
3 6
4 7
5 3
Что делает данная программа?
Находит сумму на подотрезках
Находит сумму на подотрезках такую, что в ней первое число на подотрезке повторяется один раз, второе два и так далее
Находит сумму на подотрезке, умноженную на идекс левой границы
Находит сумму на подотрезке такую, что каждое число в ней умножено на его индекс + 1
В какой строке ошибка? (задача - классические префсуммы)
13
12
20
ошибок нет
В какой строке ошибка? (задача - классический бинпоиск)
6
19
ошибок нет
21
Что выведет данный код при таких входных данных:
7 7
1 2 1 2 3 1 7
1 7
3 6
7 7
2 5
