Font size
WorksheetsFinal test
Total questions: 10
Worksheet time: 6mins
Найти обратный элемент по модулю для сложения для 4 по модулю 15
4
11
15
7
Не существует
Найти обратный элемент по модулю для умножения для 4 по модулю 15
8
11
15
4
Не существует
Сложность алгоритма Евклида (по двум числам a и b)
O(a + b)
O(min(a, b))
O(log min(a, b))
O(log max(a, b))
Выберите верное утверждение про подсвеченную клетку (задача о рюкзаке)
Рюкзак состоит из одного слитка: 4 кг
Рюкзак состоит из слитков: 4 и 3 кг
Рюкзак либо пуст, либо состоит из слитков: 4 и/или 3 кг
Рюкзак либо пуст, либо состоит из слитков: 6, 4 и/или 3 кг
Двудольный ли это граф?
Да
Нет
Невозможно определить для данного графа
Выберите верные утверждения (DFS/BFS)
В DFS при посещении вершины мы рекурсивно/стеком уходим «вглубь» к потомкам, прежде чем возвращаться
В BFS сначала посещаются все соседи текущего уровня, затем следующий уровень
В BFS вершины посещаются строго по возрастанию их номеров
BFS корректно работает только в неориентированных графах
Какую задачу решает алгоритм Дейкстры?
Поиск кратчайших путей из стартовой вершины ко всем при неотрицательных весах рёбер
Поиск кратчайших путей из стартовой вершины ко всем при наличии отрицательных рёбер
Поиск кратчайших путей из стартовой вершины ко всем при наличии отрицательных рёбер и отрицательных циклов
Поиск кратчайших путей из каждой вершины в каждую при наличии отрицательных рёбер и отрицательных циклов
Какую задачу решает алгоритм Форда–Беллмана?
Поиск кратчайших путей из стартовой вершины ко всем только при неотрицательных весах рёбер
Поиск кратчайших путей из стартовой вершины ко всем при наличии отрицательных рёбер
Умеет детектировать отрицательные циклы
Поиск кратчайших путей из каждой вершины в каждую только при неотрицательных рёбрах, быстрее Дейкстры
За какую сложность можно найти сумму на подотрезке k, используя дерево отрезков?
O(1)
O(log n)
O(n)
O(k)
O(k log n)
В каких случаях используем дерево отрезков, а не префиксные суммы? (выберите все подходящие)
Нужны функции типа min/max/gcd на подотрезках
Когда массив статичен и нужны только суммы по отрезкам
Нужно быстро изменять один элемент и быстро брать функцию на подотрезке
