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

В односвязном списке каждый узел содержит:

1. AДанные и ссылки на все остальные узлы
2. BТолько данные
3. CДанные и индекс
4. DДанные и ссылку на следующий узел

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

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

Что такое цикл в графе?

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

Какова временная сложность поиска ключа в сбалансированном двоичном дереве поиска?

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

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

1. AЧто ни у одного узла нет двух потомков
2. BПоиск за константное время в любом случае
3. CХранение ключей в порядке вставки
4. DВысоту O(log n) благодаря перебалансировке

Какова высота двоичного дерева поиска с n узлами в худшем случае, если ключи вставляются в отсортированном порядке?

1. An (дерево превращается в связный список)
2. B√n
3. C1
4. Dlog₂ n

Структура union-find (система непересекающихся множеств) с объединением по рангу и сжатием путей имеет амортизированную стоимость операции:

1. AO(n)
2. BO(α(n)), обратная функция Аккермана, практически константа
3. CРовно O(log n)
4. DO(n²)

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

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