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

Что делает операция peek (или top) стека?

1. AУдаляет все элементы из стека
2. BУдаляет верхний элемент и возвращает его
3. CВозвращает верхний элемент, не удаляя его
4. DВозвращает нижний элемент стека

Что такое взвешенный граф?

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

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

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

Какова стоимость вставки элемента в середину массива из n элементов?

1. AO(1), потому что индекс известен
2. BO(n), потому что последующие элементы нужно сдвинуть
3. CO(log n) из-за двоичного поиска
4. DO(n²), потому что каждый элемент сдвигается n раз

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

1. Alog₂ n
2. B√n
3. C1
4. Dn (дерево превращается в связный список)

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ динамическом массиве
2. BВ двусвязном списке
3. CВ отсортированном массиве
4. DВ односвязном списке

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

1. AПервичную кластеризацию, при которой образуются длинные серии занятых ячеек
2. BСтоимость O(n) чтения значения по ключу
3. CНеобходимость в хеш-функции
4. DНеобходимость хранить ключи в таблице

Сколько времени занимает поиск произвольного ключа в двоичной min-куче из n элементов?

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