Структуры данных: лист заданий с ответами

Что такое коллизия в хеш-таблице?

1. AДва разных ключа отображаются в один и тот же индекс
2. BДва одинаковых ключа хранятся дважды
3. CКлюч вообще невозможно хешировать
4. DВ таблице заканчивается память

В двоичном дереве поиска значения в левом поддереве узла:

1. AМеньше значения узла
2. BБольше значения узла
3. CРасположены в случайном порядке
4. DРавны значению узла

Где находится наименьший элемент двоичной min-кучи?

1. AВ последней позиции массива
2. BВ корне
3. CВ каком-то листе, который придётся искать
4. DВ самом левом листе

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ динамическом массиве
2. BВ двусвязном списке
3. CВ отсортированном массиве
4. DВ односвязном списке

Как работает extract-min в двоичной min-куче?

1. AУдаляют корень и сдвигают все элементы на одну позицию влево
2. BПоследний элемент перемещают в корень и опускают вниз (sift down)
3. CИщут новый минимум среди всех листьев
4. DУдаляют последний элемент массива

Очередь реализована двумя стеками: push в стек «in», pop из стека «out», который при опустошении заполняется из «in». Какова амортизированная стоимость одной операции?

1. AO(n)
2. BO(log n)
3. CO(n²)
4. DO(1)

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

1. AХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
2. BХранить front и rear в одной переменной
3. CВсегда очищать буфер, когда front равен rear, так что состояние — пустой
4. DДелать размер буфера степенью двойки

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

1. AМеняют его местами с корнем
2. BУдаляют всё поддерево
3. CЗаменяют его in-order преемником (или предшественником) и удаляют тот узел
4. DПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ