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

Какая операция медленная в массиве, но быстрая в начале связного списка?

1. AОпределение длины массива фиксированного размера
2. BДоступ к 5-му элементу
3. CЧтение последнего элемента по индексу
4. DВставка в начало

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

1. AInsert
2. BDequeue
3. CPush
4. DEnqueue

Граф состоит из:

1. AСтрок и столбцов
2. BТолько корня и листьев
3. CТолько ключей и хешей
4. DВершин (узлов), соединённых рёбрами

Как вставляется новый элемент в двоичную кучу?

1. AЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
2. BЕго помещают в корень и опускают вниз
3. CЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
4. DВсю кучу перестраивают с нуля

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

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

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

1. A70
2. B50
3. C20
4. D40

Нужно хранить k наименьших значений из потока n чисел, используя O(k) памяти. Какой подход работает за время O(n log k)?

1. AMin-куча, хранящая все n значений, из которой в конце извлекаются k наименьших
2. BОтсортированный массив всех n значений
3. CОчередь FIFO последних k значений
4. DMax-куча размера k, корень которой заменяется, когда приходит меньшее значение

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

1. A40
2. B80
3. C60
4. D70