⚙️ Алгоритмы · 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] и [4,5,6,7] [1,2,3,4] и [5,6,7] [1,2,3] и [4,5,6,7] [1,2,3] и [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))

13 7 12 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))

7 9 24 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:])

Правая часть при длине 2 снова имеет длину 2 Сложение результатов запрещено База должна быть len(a)==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 2 3 4

Вопрос 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] [2,3,10,1,5,9] [1,2,3,5,9,10] [1,5,9,2,3,10]

Вопрос 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)

5 6 4 3

Вопрос 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

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

Вопрос 15 из 20

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

T_{merge}=O(p+q)

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

Вопрос 16 из 20

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

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

O(n log n) O(2ⁿ) 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) O(n²) O(log n) O(n log 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 log n) O(n²)

Вопрос 19 из 20

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

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

9 11 10 1024

Вопрос 20 из 20

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

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

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

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

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

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