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

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

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

Приложению нужен быстрый поиск, а также вывод ключей в отсортированном порядке и запросы по диапазону. Какая структура подходит лучше всего?

1. AХеш-таблица
2. BСбалансированное двоичное дерево поиска
3. CСтек
4. DНеотсортированный связный список

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

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

В чём главное преимущество списка с пропусками (skip list) перед отсортированным связным списком?

1. AОн не использует дополнительной памяти
2. BОн хранит ключи без упорядочения
3. CОжидаемый поиск за O(log n) благодаря нескольким уровням указателей вперёд
4. DГарантированный поиск за O(1), потому что каждый узел хранит указатель на каждый другой узел

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

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