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

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

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

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

1. AEnqueue
2. BPop
3. CPeek
4. DPush

В односвязном списке каждый узел содержит:

1. AТолько данные
2. BДанные и ссылку на следующий узел
3. CДанные и ссылки на все остальные узлы
4. DДанные и индекс

Что верно для матрицы смежности неориентированного графа?

1. AОна всегда верхнетреугольная
2. BВ каждой строке ровно одна 1
3. CОна симметрична относительно главной диагонали
4. DНа её главной диагонали всегда стоят единицы

Префиксное дерево (trie) особенно эффективно для:

1. AХранения матриц
2. BПоиска по префиксу, например автодополнения
3. CСортировки чисел
4. DПоиска кратчайших путей

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

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

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

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

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

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