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

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

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

Глубина узла в дереве — это:

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(n)
3. CO(log n)
4. DO(1)

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

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

Как вставляется новый элемент в двоичную кучу?

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

Какое утверждение о пирамидальной сортировке (heapsort) верно?

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

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

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