wayground logo

Free Printable Worksheets

NEW

Font size

S
M
L
XL
Worksheets

МОИБ2025 РК1

Total questions: 30

Worksheet time: 10mins

Name
Class
Date
1.

Что такое алгоритм с полиномиальной сложностью

a)

Выполняется за n^k шагов

b)

Выполняется за 2^n шагов

c)

Выполняется бесконечно

d)

Всегда выполняется за константу

2.

Алгоритмы с экспоненциальной сложностью работают

a)

Быстрее линейных

b)

Быстрее полиномиальных

c)

Намного медленнее полиномиальных

d)

За постоянное время

3.

Что является основной моделью вычислений

a)

Автомат Мили

b)

Машина Тьюринга

c)

Машина Поста

d)

Сеть Петри

4.

Машина Тьюринга работает с

a)

Памятью в виде ленты

b)

Массивом

c)

Двумя регистрами

d)

Только с числами

5.

Универсальная машина Тьюринга способна

a)

Решать только арифметические задачи

b)

Моделировать работу любого алгоритма

c)

Работать только с бинарными числами

d)

Работать только с простыми числами

6.

Класс P включает задачи, решаемые

a)

За полиномиальное время

b)

За экспоненциальное время

c)

Только приближённо

d)

Никак не решаемые

7.

Класс NP включает задачи, для которых

a)

Проверка решения быстрая (полиномиальная)

b)

Решение всегда невозможно

c)

Решение экспоненциальное

d)

Решения не существует

8.

Если задача NP-полная, то

a)

Она всегда быстрее решается

b)

Она одна из самых трудных в NP

c)

Она проще, чем задачи в P

d)

Её можно решить только на квантовом компьютере

9.

Что относится к трудным задачам

a)

Сортировка чисел

b)

Поиск НОД

c)

Задача коммивояжёра

d)

Умножение чисел

10.

НОД двух чисел — это

a)

Наибольший общий делитель

b)

Наименьший общий делитель

c)

Наименьшее общее кратное

d)

Наиболее общее краткое

11.

Алгоритм Евклида используется для

a)

Возведения в степень

b)

Нахождения НОД

c)

Поиска простых чисел

d)

Решения квадратных уравнений

12.

Результат: НОД(54,24) =

a)

6

b)

-1

c)

0

d)

1

13.

В модульной арифметике

a)

Сравниваются остатки при делении

b)

Используется только сложение

c)

Запрещено умножение

d)

Деление всегда возможно

14.

17mod5=

a)

2

b)

1

c)

0

d)

7

15.

−7mod4=

a)

1

b)

3

c)

-1

d)

2

16.

В криптографии активно используется

a)

Арифметика остатков

b)

Двоичная арифметика

c)

Десятичная арифметика

d)

Только сложение

17.

Если a≡b(mod m), то

a)

a и b равны

b)

a и b имеют одинаковый остаток при делении на m

c)

a всегда больше b

d)

b кратно m

18.

НОК и НОД связаны формулой

a)

НОК(a,b)=a⋅b/НОД(a,b)

b)

НОК(a,b)=НОД(a,b)+a+b

c)

НОД(a,b)=НОК(a,b)−1

d)

НОД(a,b)=1-НОК(a,b)

19.

Полиномиальная формула имеет вид

a)

n^k

b)

2^n

c)

n!

d)

a^b

20.

Экспоненциальная формула имеет вид

a)

2^n

b)

n^2

c)

n+1

d)

sqrt{n}

21.

Числа Мерсена имеют вид

a)

2^p - 1

b)

2^p + 1

c)

2^2p - 1

d)

2^2p + 1

22.

Псевдопростые числа — это

a)

Составные числа, которые проходят тесты на простоту

b)

Всегда простые

c)

Только степени двойки

d)

Числа вида 2^p-1

23.

Какой тест простоты вероятностный

a)

Решето Эратосфена

b)

Тест Миллера–Рабина

c)

Алгоритм Евклида

d)

Метод НОД

24.

Для чего применяют тест Миллера

a)

Для проверки составных чисел

b)

Для вероятностной проверки простоты

c)

Для нахождения НОД

d)

Для поиска НОК

25.

В криптографии важны большие

a)

Простые числа

b)

Числа Фибоначчи

c)

Составные числа

d)

НОД и НОК

26.

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

a)

Делимость чисел

b)

Выполнение шаг за шагом

c)

Применимость к классу задач

d)

Случайность шагов

27.

Массовость алгоритма означает

a)

Применимость к целому классу задач

b)

Использование большого массива

c)

Применимость только к одной задаче

d)

Бесконечность шагов

28.

Принцип рекурсии — это

a)

Повторение шагов через условие

b)

Определение функции через саму себя

c)

Остановка алгоритма

d)

Работа только с циклами

29.

Что не является свойством алгоритма

a)

Дискретность

b)

Определённость

c)

Бесконечность

d)

Конечность

30.

  • Эффективный алгоритм — это

a)

  • Случайный

b)

  • Долгий

c)

  • Быстрый и ресурсосберегающий

d)

  • Непредсказуемый

Similar Resources on Wayground

3 Scrum

30 questions

3 Scrum

quiz

Worksheet

•

University