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

Что делает операция peek (или top) стека?

1. AВозвращает нижний элемент стека
2. BУдаляет все элементы из стека
3. CУдаляет верхний элемент и возвращает его
4. DВозвращает верхний элемент, не удаляя его

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

1. AГраф
2. BСтек
3. CОчередь
4. DХеш-множество

Что такое дек (deque, двусторонняя очередь)?

1. AОчередь, допускающая удаление только с конца
2. BОчередь, отсортированная по приоритету
3. CСтруктура, допускающая вставку и удаление с обоих концов
4. DДве отдельные очереди в одном массиве

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

1. Ai + 1
2. B(i + 1) mod n
3. C2i + 1
4. D(i − 1) mod n

Префиксное дерево (trie) особенно эффективно для:

1. AПоиска кратчайших путей
2. BПоиска по префиксу, например автодополнения
3. CСортировки чисел
4. DХранения матриц

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

1. AВ индексе i − 1
2. BВ индексе ⌊(i − 1) / 2⌋
3. CВ индексе 2i + 1
4. DВ индексе ⌊i / 2⌋ + 1

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

1. AС возможными ложноположительными, но без ложноотрицательных результатов
2. BТолько для чисел
3. CВсегда точно
4. DС возможными ложноотрицательными, но без ложноположительных результатов

Зачем серверу выбирать хеш-функцию случайно из универсального семейства?

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