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

Связные списки

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

Отвечено: 0 из 20
⏱ --:--
0%
💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 40 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.
Вопрос 1 из 20
Какие значения будут напечатаны?
Python
class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

c = Node(3)
b = Node(2, c)
a = Node(1, b)
p = a.next
p.value = 8
print(a.next.value, b.value, p.next.value)
Вопрос 2 из 20
Какую последовательность обойдёт цикл?
Python
class Node:
    def __init__(self, v, nxt=None):
        self.v, self.next = v, nxt

tail = Node(4)
shared = Node(3, tail)
first = Node(1, shared)
second = Node(2, shared)
p = second
out = []
while p:
    out.append(p.v)
    p = p.next
print(out)
Вопрос 3 из 20
Какая операция над односвязным списком выполняется за O(1), если известна только голова?
T_{push\_front}(n)=O(1)
Вопрос 4 из 20
Какие значения и ссылка будут выведены после отделения первого узла?
Python
class Node:
    def __init__(self, v, nxt=None):
        self.v, self.next = v, nxt

head = Node(1, Node(2, Node(3)))
q = head
head = head.next
q.next = None
print(head.v, q.v, q.next)
Вопрос 5 из 20
Почему получить длину обычного односвязного списка нельзя за O(1), если структура не хранит отдельный счётчик?
O(n)
Вопрос 6 из 20
Какой список получится после вставки?
Python
class Node:
    def __init__(self, v, nxt=None):
        self.v, self.next = v, nxt

head = Node(2, Node(4, Node(7)))
new = Node(5)
p = head
while p.next and p.next.v < new.v:
    p = p.next
new.next = p.next
p.next = new

out = []
while head:
    out.append(head.v)
    head = head.next
print(out)
Вопрос 7 из 20
Какой порядок двух присваиваний корректно вставляет new после узла p, не теряя хвост?
Вопрос 8 из 20
Что особенно упрощает фиктивный головной узел dummy при вставке в отсортированный список?
Вопрос 9 из 20
В каком порядке цикл прочитает цепочку, построенную вставками в голову?
Python
class Node:
    def __init__(self, v, nxt=None):
        self.v, self.next = v, nxt

head = None
for x in [1, 2, 3, 4]:
    head = Node(x, head)
out = []
while head:
    out.append(head.v)
    head = head.next
print(out)
Вопрос 10 из 20
В двусвязный список вставляют узел x между a и b. Какие связи нужно согласованно обновить?
Вопрос 11 из 20
Какой список останется?
Python
class Node:
    def __init__(self, v, nxt=None):
        self.v, self.next = v, nxt

head = Node(1, Node(2, Node(3, Node(4))))
p = head
while p.next:
    if p.next.v % 2 == 0:
        p.next = p.next.next
    else:
        p = p.next
out = []
while head:
    out.append(head.v)
    head = head.next
print(out)
Вопрос 12 из 20
Что вернёт функция?
Python
def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev
Вопрос 13 из 20
Зачем при развороте сначала сохранять nxt = cur.next?
Вопрос 14 из 20
Какой дефект есть в функции удаления первого совпадения?
Python
def remove(head, target):
    p = head
    while p.next:
        if p.next.v == target:
            p.next = p.next.next
            return head
        p = p.next
    return head
Вопрос 15 из 20
В односвязном списке дан указатель на внутренний узел x, но нет головы. Как иногда удаляют x за O(1), если x не последний?
Вопрос 16 из 20
Обнаружит ли функция цикл в списке 1→2→3→4→2?
Python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
Вопрос 17 из 20
Сколько итераций до первой встречи slow и fast?
Python
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

nodes = [Node(i) for i in range(5)]
for i in range(4):
    nodes[i].next = nodes[i + 1]
nodes[4].next = nodes[2]

slow = fast = nodes[0]
steps = 0
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    steps += 1
    if slow is fast:
        break
print(steps)
Вопрос 18 из 20
Почему множество посещённых узлов тоже обнаруживает цикл, но требует больше памяти, чем алгоритм Флойда?
M_{set}(n)=O(n),\quad M_{Floyd}(n)=O(1)
Вопрос 19 из 20
Что нужно сделать после встречи указателей, чтобы найти начало цикла?
Python
# slow и fast встретились внутри цикла
# head указывает на начало списка
Вопрос 20 из 20
Какой вход особенно важен для проверки функции has_cycle помимо списка с обычным циклом?

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

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

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

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