Введение в алгоритмы

Упражнение 1:

Номер 1

Какова вычислительная сложность алгоритма цифровой сортировки?

Ответ:

(1) линейная

(2) квадратичная

(3) кубическая

Номер 2

Эффективность алгоритма цифровой сортировки зависит

Ответ:

(1) от типизации данных

(2) от плотности элементов в массиве ячеек

(3) от метода формирования идентификаторов

Номер 3

Алгоритм сортировки, в котором сортируемые элементы делятся на конечное число отдельных блоков так, что все элементы в одном блоке всегда больше (или меньше), чем в другом, носит название

Ответ:

(1) структурная сортировка

(2) блочная сортировка

(3) массивная сортировка

Упражнение 2:

Номер 1

Сколько сравнений и обращений к памяти требуется в связных списках при обращении к элементу по его номеру?

Ответ:

(1) n/2

(2) 2n

(3) logn

Номер 2

Cложность алгоритма сортировки односвязного списка составляет

Ответ:

(1) O(n)

(2) O(logn)

(3) O(nlogn)

Номер 3

Требования к памяти при сортировке односвязного списка составляет

Ответ:

(1) O(logn)

(2) O(2n)

(3) O(n)

Упражнение 3:

Номер 1

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

Ответ:

(1) O(logn)

(2) O(n)

(3) O(n²)

Номер 2

Идеальной вычислительной сложностью для алгоритма сортировки является

Ответ:

(1) O(n)

(2) O(logn)

(3) O(nlogn)

Номер 3

Сортировка, которая не меняет взаимного расположения равных элементов, носит название

Ответ:

(1) устойчивая

(2) модальная

(3) ассоциативная

Упражнение 4:

Номер 1

Эффективность метода сортировки при обработке уже упорядоченных, или частично упорядоченных данных, называется

Ответ:

(1) ассоциативностью

(2) естественностью

(3) терминальностью

Номер 2

К основным типам сортировки следует отнести

Ответ:

(1) внутреннюю

(2) рекурсивную

(3) вариантную

Номер 3

К алгоритмам устойчивой сортировки следует отнести

Ответ:

(1) сортировку пузырьком

(2) сортировку перемешиванием

(3) блочную сортировку

Упражнение 5:

Номер 1

К алгоритмам неустойчивой сортировки следует отнести

Ответ:

(1) сортировку выбором

(2) цифровую сортировку

(3) сортировку Шелла

Номер 2

Сложность пирамидальной сортировки составляет

Ответ:

(1) O(nlogn)

(2) O(logn)

(3) O(n)

Номер 3

Какова сложность сортировки выбором?

Ответ:

(1) O(n)

(2) O(n²)

(3) O(logn)

Упражнение 6:

Номер 1

К алгоритмам сортировки, не основанным на сравнениях, следует отнести

Ответ:

(1) блочную сортировку

(2) поразрядную сортировку

(3) сортировку подсчётом

Номер 2

Сложность обменной поразрядной сортировки является

Ответ:

(1) кубической

(2) квадратичной

(3) линейной

Номер 3

Каждый ключ при обменной поразрядной сортировке представляется

Ответ:

(1) в десятичном виде

(2) в двоичном виде

(3) в виде модификаторов

Упражнение 7:

Номер 1

Перед использованием поразрядной обменной сортировки необходимо знать

Ответ:

(1) максимальное количество разрядов в сортируемых величинах

(2) количество возможных значений одного разряда

(3) идентификаторы типизированных данных

Номер 2

Сколько времени занимает процедура, предназначенная для создания кучи из неупорядоченного массива входных данных?

Ответ:

(1) O(nlogn)

(2) O(n)

(3) O(n²)

Номер 3

Фибоначчиева куча представляет собой

Ответ:

(1) массив идентификаторов

(2) контейнер ключей и данных

(3) набор деревьев

Упражнение 8:

Номер 1

Сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память, называется

Ответ:

(1) модульной

(2) внешней

(3) контейнерной

Номер 2

Упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин, носит название

Ответ:

(1) ассоциативная сортировка

(2) топологическая сортировка

(3) модульная сортировка

Номер 3

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

Ответ:

(1) рефлексивность

(2) антисимметричность

(3) транзитивность

Упражнение 9:

Номер 1

Время работы алгоритма сортировки слиянием составляет

Ответ:

(1) O(logn)

(2) O(nlogn)

(3) O(n)

Номер 2

Сортировка слиянием может быть

Ответ:

(1) естественной

(2) модульной

(3) конструктивной

Номер 3

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

Ответ:

(1) сортировка простым слиянием

(2) сортировка естественным слиянием

(3) сортировка комплексным слиянием

Упражнение 10:

Номер 1

Сортировка вставками с предварительными "грубыми" проходами лежит в основе

Ответ:

(1) сортировки Эйлера

(2) сортировки Шелла

(3) сортировки Марка

Номер 2

К преимуществам сортировки вставками следует отнести

Ответ:

(1) эффективность на небольших наборах данных

(2) эффективность на наборах данных, которые уже частично отсортированы

(3) устойчивость

Номер 3

Какие из приведенных ниже записей следует отнести к преимуществам сортировки вставками?

Ответ:

(1) сортировка списка по мере его получения

(2) простота реализации

(3) отсутствие изменения порядка элементов, которые уже отсортированы

Упражнение 11:

Номер 1

Каким является В-дерево?

Ответ:

(1) сбалансированным

(2) модальным

(3) комплексным

Номер 2

Свойство каждого узла дерева ссылаться на большое число узлов-потомков носит название

Ответ:

(1) ассоциативность

(2) ветвистость

(3) контекстность

Номер 3

Обобщением B-дерева на многомерный случай является

Ответ:

(1) R-дерево

(2) L-дерево

(3) T-дерево

Упражнение 12:

Номер 1

Рост высоты красно-черного дерева зависит

Ответ:

(1) от типа данных

(2) от числа узлов

(3) от метода идентификации данных

Номер 2

2-3 дерево является

Ответ:

(1) терминальным деревом

(2) В-деревом

(3) рекурсивным деревом

Номер 3

Все данные 2-3-дерева хранятся

Ответ:

(1) в контекстных вершинах

(2) в аддитивных вершинах

(3) в листовых вершинах

Введение в алгоритмы - тест 12