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

Что такое ориентированный граф?

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

Какая операция медленная в массиве, но быстрая в начале связного списка?

1. AВставка в начало
2. BОпределение длины массива фиксированного размера
3. CДоступ к 5-му элементу
4. DЧтение последнего элемента по индексу

Граф состоит из:

1. AВершин (узлов), соединённых рёбрами
2. BСтрок и столбцов
3. CТолько корня и листьев
4. DТолько ключей и хешей

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

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

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. A2^h
2. B2^h+1 − 1
3. Ch²
4. D2h + 1

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

1. AВ индексе 0
2. BВ индексе 4
3. CВ индексе 3
4. DВ индексе 6

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

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

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

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