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

Что такое узлы-братья (siblings) в дереве?

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

Глубина узла в дереве — это:

1. AЧисло потомков этого узла
2. BЧисло узлов в его поддереве
3. CЧисло рёбер от этого узла до самого глубокого листа
4. DЧисло рёбер от корня до этого узла

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

1. AЧтение первого элемента
2. BВставка в начало
3. CУдаление головного элемента
4. DДоступ к элементу с индексом i

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

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

Почему обход массива на практике часто гораздо быстрее обхода связного списка той же длины?

1. AСвязные списки всегда хранят элементы на диске
2. BОбход массива занимает в сумме O(1), а связного списка — O(n)
3. CМассивы требуют меньше инструкций для сравнения значений
4. DЭлементы массива расположены непрерывно, поэтому хорошо используют кэш процессора

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

1. Ai + 1
2. B2i + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

1. AХеш-таблица в сочетании с двусвязным списком
2. BТолько двоичное дерево поиска
3. CТолько стек
4. DОдин отсортированный массив

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

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