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

Что такое лист дерева?

1. AУзел без родителя
2. BУзел с наибольшим значением
3. CУзел ровно с одним потомком
4. DУзел без потомков

Что определяет двоичное дерево?

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

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

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

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

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

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

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

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

1. Ai/2 и i/2 + 1
2. B2i и 2i + 1
3. Ci + 1 и i + 2
4. D2i + 1 и 2i + 2

Почему из стандартного фильтра Блума нельзя просто удалить элементы, обнулив их биты?

1. AБиты фильтра Блума нельзя менять после создания
2. BУдаление повысило бы долю ложноположительных результатов до 100%
3. CФильтры Блума хранят элементы целиком, и их невозможно снова найти после хеширования
4. DЭти биты могут принадлежать и другим элементам, что вызвало бы ложноотрицательные результаты

Какому правилу должны подчиняться хеш и равенство, чтобы хеш-таблица работала правильно?

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