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

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

1. AДоступ к элементу с индексом i
2. BУдаление головного элемента
3. CЧтение первого элемента
4. DВставка в начало

Что такое коэффициент заполнения (load factor) хеш-таблицы?

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

В чём главное отличие статического массива от динамического?

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

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

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

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

1. AХранение ключей в порядке вставки
2. BЧто ни у одного узла нет двух потомков
3. CПоиск за константное время в любом случае
4. DВысоту O(log n) благодаря перебалансировке

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

1. AОчередь FIFO
2. BСтек
3. CМножество без упорядочения
4. DОчередь с приоритетом по минимуму

Каково при простом равномерном хешировании ожидаемое время поиска в хеш-таблице с цепочками, n ключами и m корзинами?

1. AO(log n)
2. BO(1 + α), где α = n / m
3. CO(n)
4. DO(m)

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

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