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

Как называется операция стека, добавляющая элемент на вершину?

1. APush
2. BEnqueue
3. CPeek
4. DPop

Что такое цикл в графе?

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

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

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

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

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

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

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

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

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

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

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

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

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