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

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

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

Как элементы массива хранятся в памяти?

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

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

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

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

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

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

1. Ai + 1 и i + 2
2. B2i + 1 и 2i + 2
3. C2i и 2i + 1
4. Di/2 и i/2 + 1

Кольцевой буфер (ring buffer) обычно используют для реализации:

1. AХеш-функции
2. BДвоичного дерева поиска
3. CОбхода графа
4. DОчереди фиксированного размера

Что делает косое дерево (splay tree) после каждого обращения?

1. AПерестраивает всё дерево в сбалансированном виде
2. BПеремещает узел, к которому обращались, в лист
3. CПоворотами поднимает узел, к которому обращались, в корень
4. DПерекрашивает узлы на пути поиска

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

1. AВсегда очищать буфер, когда front равен rear, так что состояние — пустой
2. BДелать размер буфера степенью двойки
3. CХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
4. DХранить front и rear в одной переменной