Алгоритмы и модели вычислений

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

(2) 2

(3) множество

Номер 2

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

Ответ:

(1) одна

(2) более трех

(3) множество

Номер 3

Расписание, при котором каждая работа получает в точности определенное время процессора (длительность), и выполняется в директивном интервале, носит название

Ответ:

(1) вариативное

(2) идеальное

(3) допустимое

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

Номер 1

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

Ответ:

(1) величине директивного интервала

(2) модулю работы

(3) коэффициенту связности

Номер 2

Слово в алгоритме упаковки имеет размер

Ответ:

(1) O(lgT)

(2) O(T)

(3) O(2T)

Номер 3

Количество операций алгоритма упаковки оценивается значением

Ответ:

(1) O(n)

(2) O(logn)

(3) O(n²)

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

Номер 1

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

Ответ:

(1) O(n)

(2) O(nlgT)

(3) O(lgT)

Номер 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

Максимальное количество прерываний и переключений в алгоритме Танаева составляет

Ответ:

(1) 2m

(2) m

(3) m-1

Номер 2

Чтобы полностью определить допустимое расписание в алгоритме Танаева с помощью алгоритма Карзанова нужно

Ответ:

(1) O(lgn) операций

(2) O(2n) операций

(3) O(n³) операций

Номер 3

Чтобы полностью определить допустимое расписание в алгоритме Танаева с помощью алгоритма упаковки нужно

Ответ:

(1) O(lgn) операций

(2) O(n) операций

(3) O(n²) операций

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

Номер 1

В худшем случае алгоритм Танаева выполняется

Ответ:

(1) за O(n) операций

(2) за O(n²)

(3) за O(n³)

Номер 2

В двоичном дереве с n вершинами вершины с номерами [n/2]+1… n называются

Ответ:

(1) контейнерами

(2) листьями

(3) потомками

Номер 3

В двоичном дереве левого и правого потомка

Ответ:

(1) имеет любая вершина

(2) не может иметь ни одна вершина

(3) имеет любая вершина, кроме листа

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

Номер 1

Число дуг в самом длинном пути, ведущем из вершины в лист, называется

Ответ:

(1) высотой

(2) мощностью

(3) модулем

Номер 2

Двоичное дерево, в котором значение в любой вершине больше (меньше), чем значения ее потомков, носит название

Ответ:

(1) стек

(2) куча

(3) массив

Номер 3

Высота кучи определяется высотой

Ответ:

(1) листов

(2) маркеров

(3) корневого узла

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

Номер 1

Высота кучи равна

Ответ:

(1) O(logn)

(2) O(n)

(3) O(n²)

Номер 2

Для создания кучи из неупорядоченного массива входных данных необходимо

Ответ:

(1) O(n) операций

(2) O(nlogn) операций

(3) O(2n) операций

Номер 3

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

Ответ:

(1) O(2n-1)

(2) O(n)

(3) O(logn)

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

Номер 1

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

Ответ:

(1) O(n)

(2) O(logn)

(3) O(nlogn)

Номер 2

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

Ответ:

(1) сложность реализации

(2) неустойчивость

(3) плохое сочетание с кэшированием

Номер 3

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

Ответ:

(1) наличие доказанной оценки худшего случая O(logn)

(2) всего O(1) дополнительной памяти в специфических случаях

(3) хорошее сочетание с подкачкой памяти

Алгоритмы и модели вычислений - тест 3