⚙️ Алгоритмы  ·  20 вопросов  ·  ~35 мин  ·  ⏱ Таймер 35:00  ·  Лёгкий  · 

Стек, очередь и дек

Одна и та же коллекция элементов ведёт себя совершенно по-разному в зависимости от того, откуда мы добавляем и извлекаем данные. Тест включает разбор скобок, монотонные структуры, очередь BFS, кольцевой буфер и ситуации, где неверный выбор контейнера незаметно превращает линейное решение в квадратичное.

Отвечено: 0 из 20
⏱ --:--
0%
💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 35 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.
Вопрос 1 из 20
Что останется в стеке?
Python
stack = []
for x in [3, 1, 4, 1, 5]:
    if x % 2 == 0:
        stack.append(x)
    elif stack:
        stack[-1] += x
    else:
        stack.append(x)
print(stack)
Вопрос 2 из 20
Какой результат вернёт проверка?
Python
def valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    st = []
    for ch in s:
        if ch in '([{':
            st.append(ch)
        elif ch in pairs:
            if not st or st.pop() != pairs[ch]:
                return False
    return not st

print(valid('([{}])[]'))
Вопрос 3 из 20
Какой объект естественно хранить в стеке при вычислении арифметического выражения в постфиксной записи?
Вопрос 4 из 20
Какой список индексов будет напечатан?
Python
a = [2, 5, 3, 7, 4]
st = []
answer = [-1] * len(a)
for i, x in enumerate(a):
    while st and a[st[-1]] < x:
        answer[st.pop()] = i
    st.append(i)
print(answer)
Вопрос 5 из 20
Почему рекурсивные вызовы естественно обслуживаются стеком?
call_0\to call_1\to\dots\to call_k
Вопрос 6 из 20
Какой порядок элементов останется в очереди после переноса первого элемента в конец?
Python
from collections import deque
q = deque([2, 4, 6])
q.append(8)
x = q.popleft()
q.append(x + q[0])
print(list(q))
Вопрос 7 из 20
В каком порядке будут обработаны вершины?
Python
from collections import deque
g = {0: [1, 2], 1: [3], 2: [4], 3: [], 4: []}
q = deque([0])
seen = {0}
order = []
while q:
    v = q.popleft()
    order.append(v)
    for u in g[v]:
        if u not in seen:
            seen.add(u)
            q.append(u)
print(order)
Вопрос 8 из 20
Когда вершину графа безопаснее всего помечать посещённой в BFS, чтобы не помещать её в очередь много раз?
Вопрос 9 из 20
Какой элемент будет извлечён следующим из кольцевой очереди?
Python
buf = [None] * 5
head = 3
size = 0
for x in [10, 20, 30, 40]:
    tail = (head + size) % len(buf)
    buf[tail] = x
    size += 1
value = buf[head]
head = (head + 1) % len(buf)
size -= 1
print(value, head)
Вопрос 10 из 20
Система печати должна обслуживать обычные задания строго по времени поступления. Какая структура непосредственно выражает это правило?
Вопрос 11 из 20
Какой порядок элементов останется в деке после операций с обоих концов и поворота?
Python
from collections import deque
d = deque([2, 3])
d.appendleft(1)
d.append(4)
d.popleft()
d.rotate(1)
print(list(d))
Вопрос 12 из 20
Какой максимум будет записан для последнего окна?
Python
from collections import deque
a = [4, 2, 12, 3, 8, 7]
k = 3
d = deque()
ans = []
for i, x in enumerate(a):
    while d and d[0] <= i - k:
        d.popleft()
    while d and a[d[-1]] <= x:
        d.pop()
    d.append(i)
    if i >= k - 1:
        ans.append(a[d[0]])
print(ans[-1])
Вопрос 13 из 20
Зачем в монотонном деке для максимумов окна хранять индексы, а не только значения?
Вопрос 14 из 20
Какой список получится?
Python
from collections import deque
d = deque()
for x in [1, 2, 3, 4, 5]:
    if x % 2:
        d.appendleft(x)
    else:
        d.append(x)
print(list(d))
Вопрос 15 из 20
Какова амортизированная сложность алгоритма максимумов всех окон с монотонным деком?
T(n)\le c\cdot n
Вопрос 16 из 20
Какая структура лучше всего заменит список в этой функции, если n велико?
Python
def process(items):
    pending = list(items)
    result = []
    while pending:
        x = pending.pop(0)
        result.append(handle(x))
    return result
Вопрос 17 из 20
Какую структуру фактически реализует этот код?
Python
data = []

def put(x):
    data.append(x)

def take():
    return data.pop()
Вопрос 18 из 20
Редактор должен поддерживать отмену последних действий и отдельное возвращение отменённых действий. Какая схема естественнее?
Вопрос 19 из 20
Какой результат показывает, что структура выбрана неверно?
Python
requests = []
for req in ['A', 'B', 'C']:
    requests.append(req)
while requests:
    print(requests.pop(), end='')
Вопрос 20 из 20
Нужно всегда быстро извлекать задачу с наименьшим сроком, а при равных сроках — более раннюю по поступлению. Что выбрать?
(\text{срок},\ \text{номер поступления})

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

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

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

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