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

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

1. APush
2. BDequeue
3. CInsert
4. DEnqueue

Как элементы массива хранятся в памяти?

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

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

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

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

1. AОдин отсортированный массив вершин
2. BМатрица смежности
3. CСписки смежности
4. DДвоичная куча рёбер

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

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

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

1. A2i + 1 и 2i + 2
2. Bi + 1 и i + 2
3. Ci/2 и i/2 + 1
4. D2i и 2i + 1

Почему базы данных часто используют для индексов B+ деревья, а не обычные B-деревья?

1. AB+ деревья не нужно балансировать
2. BВсе записи находятся в связанных листьях, что делает сканирование диапазонов эффективным
3. CB+ деревья используют двоичные внутренние узлы, что сокращает число чтений с диска
4. DB+ деревья хранят данные только в корне

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

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