Free Printable Префиксные суммы и бинарный поиск

Worksheets

Префиксные суммы и бинарный поиск

Total questions: 12

Worksheet time: 6mins

Name

Class

Date

Как называется отрезок, содержащий несколько последних элементов последовательности?

(a)

Вставьте недостающую часть в код преподсчёта префиксных сумм

pref[i - 1] + a[i]

pref[i - 1] - a[i]

pref[i - 1] + a[i - 1]

pref[i - 1] + a[i + 1]

За сколько работает обработка одного запроса к отрезку с помощью префиксных сумм?

$O\left(1\right)$

$O\left(\log_{ }n\right)$

$O\left(n\right)$

$O\left(n^2\right)$

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

$O\left(1\right)$

$O\left(\log_{ }n\right)$

$O\left(n\right)$

$O\left(n^2\right)$

Что из этого можно считать на отрезке за $O\left(1\right)$ с помощью преподсчёта на префиксе?

Минимум

НОД

Среднее арифметическое

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

НОК

За сколько работает бинарный поиск в массиве?

$O\left(1\right)$

$O\left(\log_{ }n\right)$

$O\left(n\right)$

$O\left(n\cdot\log_{ }n\right)$

Для того, чтобы классический бинарный поиск был применим в массиве, элементы в нём должны быть расположены в порядке...

убывания

возрастания

неубывания

невозрастания

Сколько вопросов потребуется, чтобы гарантированно отгадать бинарным поиском натуральное число от 1 до 1000?

(a)

При использовании цикла for в вещественном бинарном поиске для вычисления $\sqrt[]{2}$ с точностью 6 знаков после запятой достаточно количество итераций около...

10.

Вставьте недостающий фрагмент кода

(L + R) / 2

R - L > 1

R > L

a[M] != 3

11.

Что выведет этот код?

Произойдёт ошибка

12.

Оцените викторину

Хорошо

Нормально

Ну такое

Плохо

Reset

Префиксные суммы и бинарный поиск

Total questions: 12

Worksheet time: 6mins

Similar Resources on Wayground