Font size
WorksheetsСортировки + Преф. суммы
Total questions: 23
Worksheet time: 25mins
Ответьте своими словами на вопрос: "Что такое сортировка?"
(a) — определение сложности алгоритма?
Какова асимптотика сортировки пузырьком?
O(n2)
O(n)
O(ω)O
O(1)
Как называют сортировки с асимптотикой O(n²)?
Квадратные
Квадратичные
Квадра-сортировки
Квадратические
Какая из этих сортировок не квадратичная?
Поиск минимума
Подсчёт
Пузырёк
Вставки
Какая асимптотика у сортировки подсчётом, при n - длине вектора, а m - "разнообразие" элементов?
O(nm)
O(nm)
O(n + m)
O(n−m)
Какая это сортировка?
Поиском минимума
Поиском максимума
Вставками
Пузырьком
В какую строчку нужно что-то добавить, чтобы сортировка работала быстрее?
12
13
14
Нет верного ответа
За какую сложность работает этот код?
O(n2)
O(2n2)
O(n ⋅ a.size())
O(2n ⋅ a.size())
Код не работает
Расположите числа в том порядке, в каком выведет программа.
7
6
1
8
Что выведет программа?
1 2 5 6 7 8
6 7 1 8 2 5
6 1 7 8 2 5
6 7 1 8 2 5
Что выведет программа?
1 3 4 5 7 7
1 3 4 5 7
1 3 4 5 7 3
Ошибка
Переходим к префиксным суммам))
Сопоставьте элементы вектора префиксных сумм s , построенного на векторе a , с их значениями.
a[0]
s[2]
0
s[4]
a[0] + a[1]
s[1]
a[0] + a[1] + a[2] + a[3]
s[0]
Логический смысл переменной s[i] (если s - вектор префиксных сумм) — сумма первых (a) элементов исходного ветора.
Чему равно значение s[1]-a[0]+s[2]-a[1]+s[3]-a[2]-a[0]-a[1]-a[0]? (s - вектор префиксных сумм, a - изначальный вектор)
s[1]
s[0]
s[2]-s[1]
a[3] - a[2]
Что выведет программа при таких входных данных:
5
52 5 1 103 154
3
1 3
1 4
3 5
57 58 104
58 161 258
6 109 257
Ошибка
Что делает данная программа?
Находит количество чисел на отрезке, равных 3
Находит количество четных чисел на отрезке
Находит шестикратное количество чисел на отрезке, равных 3
Находит шестикратное количество чисел, равных 3
Что делает данная программа?
Находит двукратную сумму чисел на отрезке + длину отрезка
Находит индекс самого левого элемента на отрезке
Находит сумму индексов и сумму чисел на отрезке
Находит длину отрезка
Что делает эта программа?
Находит 2(r−l +1)−1
Находит 2(r−l)−1
Находит 2(r−l+1)
Находит 2(r−l)
Что выведет программа при таких входных данных:
10
4 4 1 1 3 2 4 3 3 3
4
1 7
1 8
2 10
5 9
3 3 5 1
3 4 5 2
3 4 4 1
3 3 4 1
НЕТ ВРЕМЕНИ ОБЪЯСНЯТЬ! РИСУЙ ЕМУ ШЛЯПУ!!!
Вопросы/просьбы/предложения писать сюда!!!
