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

Что хранится для каждой вершины в представлении графа списками смежности?

1. AСтрока из V булевых значений
2. BСписок соседних вершин
3. CОбщее число рёбер графа
4. DКратчайший путь до каждой другой вершины

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

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

Высота дерева обычно определяется как:

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

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

1. AO(log n), где n — число слов
2. BO(n), где n — число слов
3. CO(L), независимо от числа хранимых слов
4. DO(L × n)

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

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

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

1. AВсегда его родитель
2. BСамый правый узел его левого поддерева
3. CВсегда его правый потомок
4. DСамый левый узел его правого поддерева

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

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

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

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