⚙️ Алгоритмы · 20 вопросов · ~45 мин · ⏱ Таймер 45:00 · Сложный ·

Разделяй и властвуй

Разделение задачи полезно лишь тогда, когда части действительно меньше, покрывают исходный вход и могут быть собраны без повторного решения всей задачи. Вопросы проверяют пропущенные границы, зацикленную рекурсию, слияние, подсчёт инверсий и оценки по дереву уровней.

Отвечено: 0 из 20

⏱ --:--

💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 45 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.

Вопрос 1 из 20

Какие части получатся для массива нечётной длины?

a = [1, 2, 3, 4, 5, 6, 7]
mid = len(a) // 2
left = a[:mid]
right = a[mid:]
print(left, right)

[1,2,3] и [4,5,6,7] [1,2,3] и [5,6,7] [1,2,3,4] и [4,5,6,7] [1,2,3,4] и [5,6,7]

Вопрос 2 из 20

Какой дефект в разбиении?

mid = len(a) // 2
left = a[:mid]
right = a[mid + 1:]

Средний элемент попадает в обе части Разбиение невозможно для чётной длины Средний элемент пропадает Обе части всегда пусты

Вопрос 3 из 20

Какая характеристика разбиения особенно важна для глубины быстрой сортировки?

Совпадают ли значения крайних элементов массива Насколько близки размеры частей после разбиения Сохраняется ли исходный порядок элементов с равными ключами Число сравнений внутри одного вызова процедуры разбиения

Вопрос 4 из 20

Сколько подмассивов длины 1 получится в листьях?

def split(n):
    if n <= 1:
        return 1
    left = n // 2
    right = n - left
    return split(left) + split(right)

print(split(13))

12 7 13 8

Вопрос 5 из 20

Когда подход «разделяй и властвуй» неприменим напрямую?

Когда каждая подзадача зависит от результата соседней так, что независимого решения нет Когда размер исходной задачи больше единицы и требуется хотя бы один рекурсивный вызов Когда для минимальных подзадач существуют простые базовые случаи без дальнейшего деления Когда части входа можно решать независимо, а ответы объединяются за предсказуемое время

Вопрос 6 из 20

Какой максимум вернёт функция?

def max_dc(a, left, right):
    if right - left == 1:
        return a[left]
    mid = (left + right) // 2
    return max(max_dc(a, left, mid),
               max_dc(a, mid, right))

print(max_dc([4, 9, 1, 7, 3], 0, 5))

9 24 7 4

Вопрос 7 из 20

Почему функция не завершится для массива длины 2?

def solve(a):
    if len(a) == 1:
        return a[0]
    mid = len(a) // 2
    return solve(a[:mid]) + solve(a[mid - 1:])

Сложение результатов запрещено Левая часть всегда пустая База должна быть len(a)==2 Правая часть при длине 2 снова имеет длину 2

Вопрос 8 из 20

Что должен обещать рекурсивный контракт merge_sort(a)?

Изменить только первый элемент массива, оставив остальные позиции без определённого порядка Вернуть любую перестановку элементов a, не гарантируя порядок или сохранение повторов Вернуть отсортированную последовательность с теми же элементами, что в a Вернуть число выполненных сравнений, не возвращая отсортированную последовательность

Вопрос 9 из 20

Сколько раз будет вычислен solve(2)?

calls = 0
def solve(n):
    global calls
    if n == 2:
        calls += 1
    if n <= 1:
        return 1
    return solve(n // 2) + solve(n - n // 2)

solve(8)
print(calls)

8 4 2 3

Вопрос 10 из 20

Почему вычислять одну и ту же подзадачу дважды внутри divide-and-conquer обычно нежелательно?

Это увеличивает дерево работы без добавления информации; результат лучше сохранить Чистая функция при повторном вызове с тем же аргументом может вернуть другое значение Разные рекурсивные ветви не могут содержать подзадачи с одинаковыми аргументами Стек вызовов автоматически кэширует первый результат, поэтому повторение лишь уменьшает глубину

Вопрос 11 из 20

Какой список получится после слияния?

a = [1, 5, 9]
b = [2, 3, 10]
i = j = 0
out = []
while i < len(a) and j < len(b):
    if a[i] < b[j]:
        out.append(a[i]); i += 1
    else:
        out.append(b[j]); j += 1
out += a[i:]
out += b[j:]
print(out)

[1,2,3,5,10,9] [1,5,9,2,3,10] [1,2,3,5,9,10] [2,3,10,1,5,9]

Вопрос 12 из 20

Сколько пересечений между половинами добавится?

left = [1, 4, 8]
right = [2, 3, 7]
i = j = 0
inversions = 0
while i < len(left) and j < len(right):
    if left[i] <= right[j]:
        i += 1
    else:
        inversions += len(left) - i
        j += 1
print(inversions)

3 6 4 5

Вопрос 13 из 20

Почему при слиянии двух отсортированных массивов достаточно сравнивать их первые ещё не взятые элементы?

Каждый первый элемент — минимум своей оставшейся части, поэтому глобальный минимум находится среди двух кандидатов Потому что элементы после первых ещё не упорядочены и могут быть просмотрены только в конце Потому что сравнение первых элементов уменьшает память, но само по себе не сохраняет порядок Потому что рассуждение работает лишь для частей одинаковой длины и без повторяющихся значений

Вопрос 14 из 20

Какой дефект даст потерю элементов?

def merge(left, right):
    i = j = 0
    out = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out

Нельзя сравнивать через <= Цикл должен использовать or без дополнительных проверок out нужно сортировать после каждого append Не добавляются хвосты части, которая не закончилась

Вопрос 15 из 20

Какова стоимость слияния массивов длины p и q?

T_{merge}=O(p+q)

O(1) O(p+q) O(log(p+q)) O(pq)

Вопрос 16 из 20

Какова сложность функции?

def solve(n):
    if n <= 1:
        return
    solve(n // 2)
    solve(n // 2)
    for _ in range(n):
        pass

O(2ⁿ) O(n log n) O(n) O(n²)

Вопрос 17 из 20

Какова сложность при перекошенном разбиении?

T(n)=T(n-1)+O(n)

def bad_sort(a):
    if len(a) <= 1:
        return a
    pivot = a[0]
    rest = bad_sort(a[1:])
    # вставка pivot в подходящее место за O(len(a))
    return insert_sorted(rest, pivot)

O(n log n) O(log n) O(n) O(n²)

Вопрос 18 из 20

Какова сложность T(n)=T(n/2)+O(n)?

T(n)=T(n/2)+O(n)=O(n)

O(n²) O(log n) O(n) O(n log n)

Вопрос 19 из 20

Что произойдёт с общей сложностью сортировки слиянием, если слияние каждой пары частей реализовать за O(n²) на уровне корня?

n = 1024
levels = 0
while n > 1:
    n //= 2
    levels += 1
print(levels)

11 1024 10 9

Вопрос 20 из 20

Что произойдёт с общей сложностью сортировка слиянием, если слияние каждой пары частей реализовать за O(n²) на уровне корня?

Останется O(n log n), поскольку глубина деления не изменилась Станет O(n²): уже корневое объединение требует квадратичной работы Станет O(n² log n), потому что квадратичная работа полностью повторится на каждом уровне Станет O(n log² n), потому что к каждому уровню добавится ещё один логарифм

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу