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

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

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

В двоичном дереве поиска значения в левом поддереве узла:

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

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

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

Какой абстрактный тип данных использует алгоритм Дейкстры для выбора следующей обрабатываемой вершины?

1. AМножество без упорядочения
2. BОчередь FIFO
3. CОчередь с приоритетом по минимуму
4. DСтек

Очередь реализована двумя стеками: push в стек «in», pop из стека «out», который при опустошении заполняется из «in». Какова амортизированная стоимость одной операции?

1. AO(1)
2. BO(log n)
3. CO(n²)
4. DO(n)

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

1. AВ порядке вставки
2. BВ порядке возрастания (отсортированно)
3. CПо уровням
4. DВсегда в порядке убывания

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

1. AO(1)
2. BO(log n)
3. CO(n log n)
4. DO(n)

Какую гарантию дают правила красно-чёрного дерева относительно высоты дерева с n ключами?

1. AВысота равна ровно log₂ n
2. BВысота не превышает 2 log₂(n + 1)
3. CВысота не превышает log₂ n + 1
4. DВысота не превышает n / 2