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

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

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

Сколько рёбер в дереве с n узлами?

1. An
2. B2n
3. Cn + 1
4. Dn − 1

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

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

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

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

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

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

Как работает extract-min в двоичной min-куче?

1. AИщут новый минимум среди всех листьев
2. BПоследний элемент перемещают в корень и опускают вниз (sift down)
3. CУдаляют корень и сдвигают все элементы на одну позицию влево
4. DУдаляют последний элемент массива

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

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

Узел АВЛ-дерева разбалансирован, потому что правое поддерево его левого потомка стало слишком высоким (случай левый–правый). Какое исправление применяется?

1. AОдиночный левый поворот в узле
2. BПравый поворот в левом потомке, затем левый поворот в узле
3. CЛевый поворот в левом потомке, затем правый поворот в узле
4. DОдиночный правый поворот в узле