WorksheetsЛогарифмы и бинарный поиск
Total questions: 21
Worksheet time: 11mins
Что означает $\log_{10}100 = 2$?
10^2 = 100
2^10 = 100
100^2 = 10
2*10 = 100
Какой логарифм показывает, сколько раз нужно умножить основание на себя?
Линейный
Обратный
Показательный
Противоположный возведению в степень
Что такое $\log_{2}8$?
2
3
4
8
Для списка из 1024 элементов бинарный поиск требует не более _ шагов.
8
10
1024
512
Что нужно сделать перед применением бинарного поиска?
Отсортировать список
Увеличить список
Разбить на подсписки
Перемешать элементы
Как вычисляется средний индекс mid?
(low - high) / 2
(low + high) / 2
low * high / 2
low + high
Что происходит, если guessed значение меньше искомого элемента?
high = mid - 1
low = mid + 1
low = mid - 1
high = mid + 1
Что показывает переменная "high"?
Нижнюю границу поиска
Верхнюю границу поиска
Количество шагов
Размер массива
В случае нечетного (low+high) Python округляет mid в сторону _ .
вверх
к нулю
вниз
до ближайшего четного
Сколько проверок требуется в худшем случае для бинарного поиска по n элементам?
n
log₂ n
n/2
2n
Что представляет собой переменная "low"?
Число совпадений
Нижний индекс диапазона
Средний элемент
Количество шагов
Если list[mid] == item, алгоритм _ .
увеличивает low
уменьшает high
возвращает mid
продолжает цикл
Если list[mid] == item, алгоритм _ .
увеличивает low
уменьшает high
возвращает mid
продолжает цикл
Что будет, если список не отсортирован, а применяется бинарный поиск?
Всегда находит элемент
Работает медленнее
Может вернуть неверный результат
Приводит к ошибке
После проверки mid, если guess > item, что обновляется?
low = mid + 1
high = mid - 1
low = mid - 1
high = mid + 1
Для массива из 8 элементов log₂8 = _ .
2
3
4
8
Почему логарифм называют обратной операцией к возведению в степень?
Потому что log undoes exponentiation
Потому что он умножает
Потому что он складывает
Потому что он делит
Что происходит с областью поиска на каждом шаге бинарного поиска?
Увеличивается вдвое
Сужается вдвое
Остаётся прежней
Дублируется
Каким свойством обладает логарифмическая сложность O(log n)?
Линейный рост
Экспоненциальный рост
Медленный рост
Квадратичный рост
Как меняется mid, если меняются low и high?
Всегда растёт
Всегда уменьшается
Вычисляется заново как (low+high)/2
Не меняется
В каком случае бинарный поиск завершит цикл досрочно?
При истечении времени
Когда low > high
Когда число нечетное
Когда high == -1
