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

Что содержит указатель next последнего узла односвязного списка?

1. ANull (узла нет)
2. BАдрес первого узла
3. CАдрес предыдущего узла
4. DЧисло узлов в списке

Хеш-таблица (hash table) хранит данные в виде:

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

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

1. AO(log n), где n — число слов
2. BO(L × n)
3. CO(n), где n — число слов
4. DO(L), независимо от числа хранимых слов

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

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

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

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