Алгоритмы и структуры данных.sa_Python0 — вариант 10

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

21 вопрос Вариант 10 Доступ 7 дней

Содержание теста

Вопросы и варианты

Без отметок и подсказок к правильным ответам

Вопрос 1

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

Жадный алгоритм
Динамическое программирование
Разделяй и властвуй
Поиск с возвратом

Вопрос 2

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

Мемоизация
Жадность
Поиск в глубину
Перебор

Вопрос 3

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

Алгоритм Паскаля
Алгоритм Флойда Уоршелла
Алгоритм Краскала
Алгоритм Прима

Вопрос 4

… - техника, при которой задачи решаются снизу вверх, начиная с базовых случаев

Мемоизация
Рекурсия
Итерация
Табуляция

Вопрос 5

… оптимально решать методом динамического программирования

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

Вопрос 6

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

Решение задачи о рюкзаке
Построение остовного дерева
Поиск минимального пути
Генерация всех подмножеств множества

Вопрос 7

То, что задача … указывает на необходимость применения динамического программирования

имеет одно решение
может быть решена жадным алгоритмом
имеет подзадачи, которые решаются многократно
требует полного перебора

Вопрос 8

Мемоизация …

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

Вопрос 9

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

таблицу

Вопрос 10

Метод “...” позволяет избегать повторных вычислений одной и той же подзадачи.

мемоизация

Вопрос 11

Для решения задачи о рюкзаке с использованием динамического программирования необходимо заполнить ...

таблицу

Вопрос 12

... используется для вычисления наименьших затрат на выполнение цепочки операций

Динамическое программирование

Вопрос 13

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

перекрывающимися

Вопрос 14

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

Динамическое программирование

Вопрос 15

Динамическое программирование решает задачи путём ... подзадач

рекурсии

Вопрос 16

Метод табуляции предполагает, что задачи решаются ...

снизу вверх

Вопрос 17

Установите соответствие между термином и его определением:

мемоизация
табуляция
перекрывающиеся подзадачи
оптимальное подструктурирование
сохранение результатов для повторного использования
решение задач снизу вверх
подзадачи, которые используются в решении других подзадач
структура задачи позволяет решать её частично и использовать эти результаты

Вопрос 18

Установите соответствие между задачей и подходом к её решению:

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

Вопрос 19

Расположите порядок действий при решении задачи с помощью мемоизации:

проверить, решена ли уже подзадача
если не решена, решить её
сохранить результат
вернуть сохраненный результат

Вопрос 20

Расположите порядок действий при решении задачи о рюкзаке с использованием динамического программирования:

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

Вопрос 21

Задача … может быть решена с помощью динамического программирования

поиска в ширину
поиска кратчайшего пути в графе
поиска наибольшей возрастающей подпоследовательности
сортировки пузырьком