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

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

1. AКуча
2. BОчередь
3. CСтек
4. DБинарное дерево

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

1. AДанные, указатель на следующий узел и указатель на предыдущий узел
2. BДанные и два указателя: один на следующий узел и один на узел после него
3. CДве копии данных и один указатель
4. DДанные и только указатель на следующий узел

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

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

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

1. A2i + 1
2. Bi + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

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

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

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

1. A1
2. B2
3. C0,5
4. DМаксимума нет

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

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

Какому свойству должно удовлетворять красно-чёрное дерево?

1. AКаждый узел должен быть красным
2. BКорень должен быть красным
3. CУ каждого красного узла должны быть красные потомки, поэтому красные узлы всегда образуют непрерывные цепочки до листьев
4. DКаждый путь от узла до его листьев-потомков содержит одинаковое число чёрных узлов