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

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

Номер 1

Какое время занимает алгоритм быстрой сортировки?

Ответ:

(1) O(nlogn)

(2) O(logn)

(3) O(n)

Номер 2

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

Ответ:

(1) O(n²)

(2) O(n)

(3) O(nlogn)

Номер 3

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

Ответ:

(1) 1-2 элемента

(2) 5-6 элементов

(3) все элементы

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

Номер 1

Алгоритм быстрой сортировки является улучшенным вариантом алгоритма сортировки

Ответ:

(1) с помощью прямого обмена

(2) с ветвлением

(3) с концентрацией

Номер 2

К вариантам алгоритма с помощью прямого обмена следует отнести

Ответ:

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

(2) шейкерную сортировку

(3) модификативную сортировку

Номер 3

Разновидностью сортировки обменом является

Ответ:

(1) быстрая сортировка

(2) сортировка Райта

(3) сортировка композицией

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

Номер 1

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

Ответ:

(1) C_N = 2C_N/2+N

(2) C_N = NlogN

(3) C_N = 2C_2N

Номер 2

Сколько сравнений происходит в худшем случае при использовании быстрой сортировки?

Ответ:

(1) O(n²)

(2) O(nlogn)

(3) O(logn)

Номер 3

При большом количестве элементов быстрая сортировка приведет

Ответ:

(1) к исчерпанию памяти

(2) к вызову дополнительной ветви рекурсии

(3) к зацикливанию процедуры

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

Номер 1

При выборе опорного элемента из данного диапазона случайным образом ожидаемое время выполнения алгоритма быстрой сортировки составляет

Ответ:

(1) O(nlogn)

(2) O(logn)

(3) O(n²)

Номер 2

Самым быстродействующим из всех существующих алгоритмов обменной сортировки является

Ответ:

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

(2) алгоритм быстрой сортировки

(3) алгоритм массивной сортировки

Номер 3

Деградация алгоритма быстрой сортировки по скорости составляет

Ответ:

(1) O(n²)

(2) O(logn)

(3) O(2n)

Упражнение 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) O(nlogn)

(2) O(logn)

(3) O(n)

Номер 2

Расход памяти для сортировки слиянием

Ответ:

(1) ниже, чем для быстрой сортировки

(2) выше, чем для быстрой сортировки

(3) равен быстрой сортировке

Номер 3

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

Ответ:

(1) не более 3

(2) 2

(3) 1

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

Номер 1

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

Ответ:

(1) диапазон чисел

(2) маркировка данных

(3) проверка числа вхождений в массив

Номер 2

Диапазон чисел сортируемого массива при сортировке подсчетом используется

Ответ:

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

(2) для подсчёта совпадающих элементов

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

Номер 3

Когда нужно сортировать множество чисел из одного диапазона применяется алгоритм

Ответ:

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

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

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

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

Номер 1

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

Ответ:

(1) алгоритм со списком

(2) массивный алгоритм

(3) контекстный алгоритм

Номер 2

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

Ответ:

(1) устойчивый алгоритм

(2) модификативный алгоритм

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

Номер 3

Когда массив данных нужно отсортировать по ключам используется

Ответ:

(1) алгоритм со списком

(2) модульный алгоритм

(3) устойчивый алгоритм

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

Номер 1

Является ли алгоритм со списком устойчивым?

Ответ:

(1) не всегда

(2) да, является

(3) нет, не является

Номер 2

Алгоритм со списком занимает времени

Ответ:

(1) O(n)

(2) O(logn)

(3) O(n²)

Номер 3

Сколько времени занимает устойчивый алгоритм?

Ответ:

(1) O(2n)

(2) O(logn)

(3) O(n)

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

Номер 1

Линейная вычислительная сложность цифровой сортировки составляет

Ответ:

(1) O(logn)

(2) O(3n)

(3) O(n)

Номер 2

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

Ответ:

(1) возрастает

(2) падает

(3) остается неизменной

Номер 3

Является ли цифровая сортировка устойчивой?

Ответ:

(1) да, является

(2) нет, не является

(3) только для целых чисел

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

Номер 1

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

Ответ:

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

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

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

Номер 2

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

Ответ:

(1) модульную сортировку

(2) комплексную сортировку

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

Номер 3

Быстрая сортировка представляет собой

Ответ:

(1) обобщенную сортировку подсчетом

(2) массивную сортировку

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

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