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

Что содержит каждый узел двусвязного списка?

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

В чём главное отличие статического массива от динамического?

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

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

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

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

1. AВ индексе ⌊i / 2⌋ + 1
2. BВ индексе 2i + 1
3. CВ индексе ⌊(i − 1) / 2⌋
4. DВ индексе i − 1

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

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

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

1. A2h + 1
2. B2^h+1 − 1
3. C2^h
4. Dh²

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

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

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

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