Базовые и "продвинутые" алгоритмы для школьников

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

Номер 1

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

Ответ:

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

(2) сортировка подсчетом

(3) градиентная сортировка

Номер 2

При сортировке подсчетом считается

Ответ:

(1) число одинаковых элементов

(2) число ключей

(3) число маркеров

Номер 3

Когда в массиве много элементов, но все они достаточно малы, следует применять

Ответ:

(1) сортировку композицией

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

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

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

Номер 1

К методам обхода и разметки вершин графа следует отнести

Ответ:

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

(2) список

(3) маркер

Номер 2

Операция для доступа к элементам внутри списка носит название

Ответ:

(1) модификатор

(2) селектор

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

Номер 3

Функция для списка, возвращающая булевское значение в зависимости от некоторых условий, носит название

Ответ:

(1) объект

(2) предикат

(3) маркер

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

Номер 1

Количество элементов в списке, исключая последний элемент, носит название

Ответ:

(1) размер списка

(2) порядок списка

(3) глубина списка

Номер 2

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

Ответ:

(1) тип элементов

(2) отсортированность

(3) возможность доступа

Номер 3

Данные, хранимые в списках должны быть

Ответ:

(1) однотипными

(2) массивными

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

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

Номер 1

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

Ответ:

(1) проход по списку

(2) составление дерева списка

(3) конкретизацию ключей списка

Номер 2

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

Ответ:

(1) модуляция списка

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

(3) включение в список

Номер 3

Объект, предназначенный для перебора элементов внутри списка, носит название

Ответ:

(1) итератор

(2) селектор

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

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

Номер 1

К методам обхода и разметки вершин графа следует отнести

Ответ:

(1) поиск в ширину

(2) маркированный поиск

(3) модульный поиск

Номер 2

Поиск в ширину пометит все вершины графа, если этот граф

Ответ:

(1) контекстный

(2) связный

(3) модификативный

Номер 3

Поиск в ширину реализуется с помощью структуры

Ответ:

(1) стек

(2) список

(3) очередь

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

Номер 1

Структура данных с дисциплиной доступа к элементам "первый пришёл  - первый вышел" носит название

Ответ:

(1) стек

(2) массив

(3) очередь

Номер 2

Добавление элемента возможно

Ответ:

(1) только в конец очереди

(2) только в начало очереди

(3) как в конец, так и в начало очереди

Номер 3

Очередь с приоритетом хранит

Ответ:

(1) ключ

(2) значение

(3) маркер

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

Номер 1

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

Ответ:

(1) алгоритм Шелла

(2) алгоритм Дейкстры

(3) алгоритм Марка

Номер 2

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

Ответ:

(1) положительного веса

(2) отрицательного веса

(3) нулевого веса

Номер 3

Применим ли алгоритм Дейкстры для графов с ребрами отрицательного веса?

Ответ:

(1) да, применим

(2) нет, не применим

(3) только для орграфов

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

Номер 1

Для чего протокол OSPF использует алгоритм Дейкстры?

Ответ:

(1) для вывода данных

(2) для устранения кольцевых маршрутов

(3) для формирования массивов индексов вершин

Номер 2

Для каких графов применяется алгоритм Дейкстры?

Ответ:

(1) для формализованных

(2) для взвешенных

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

Номер 3

Минимальное известное расстояние между вершинами носит название

Ответ:

(1) глубина

(2) метка

(3) маршрут

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

Номер 1

От чего зависит сложность алгоритма Дейкстры?

Ответ:

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

(2) от способа нахождения вершины

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

Номер 2

Сложность алгоритма Дейкстры зависит

Ответ:

(1) от способа хранения множества непосещенных вершин

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

(3) от класса графа

Номер 3

В простейшем случае сложность алгоритма Дейкстры составляет

Ответ:

(1) O(n² + m)

(2) O(logn)

(3) O(n)

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

Номер 1

Для разреженных графов сложность алгоритма Дейкстры составляет

Ответ:

(1) O(nlogn + mlogn)

(2) O(mlogn)

(3) O(nlogm)

Номер 2

Удаление для фибоначчиевой кучи происходит в среднем за время

Ответ:

(1) O(logn)

(2) O(n)

(3) O(n²)

Номер 3

Уменьшение значения для фибоначчиевой кучи составляет

Ответ:

(1) O(1)

(2) O(n)

(3) O(logn)

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

Номер 1

Поразрядная сортировка происходит

Ответ:

(1) за линейное время

(2) за логарифмическое время

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

Номер 2

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

Ответ:

(1) в линейном виде

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

(3) в матричном виде

Номер 3

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

Ответ:

(1) по младшему значимому двоичному разряду

(2) по старшему значимому двоичному разряду

(3) по нулевому двоичному разряду

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

Номер 1

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

Ответ:

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

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

(3) глубину рекурсии

Номер 2

Количество проходов при поразрядной сортировке равно

Ответ:

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

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

(3) глубине дерева поиска

Номер 3

Количество возможных значений одного разряда при поразрядной сортировке составляет 7. Чему равно количество проходов алгоритма?

Ответ:

(1) 6

(2) 7

(3) 8

Базовые и "продвинутые" алгоритмы для школьников - тест 2