Тест по Computer Science — вопросы

Некоторая конвейерная RISC-машина имеет 8 регистров общего назначения R0, R1, …, R7 и поддерживает следующие операции

 ADD Rs1, Rs2, Rd    Add Rs1 to Rs2 and put the sum in Rd
 MUL Rs1, Rs2, Rd    Multiply Rs1 by Rs2 and put the product in Rd

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

Рассмотрим выражение AB ABC BC + +, где переменные A, B, C находятся в регистрах R0, R1, R2

Если содержимое этих трех регистров не должно изменяться, то каково минимальное количество тактов требуется для последовательности операций, которая вычисляет значение AB ABC BC + +?

Ниже приведен граф приоритетов (precedence graph) для набора задач, которые должны быть выполнены в системе параллельных вычислений S

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

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

Система S имеет четыре процессора (CPU)

Если каждая из задач выполняется за одинаковое время, то какова эффективность этой системы S?

Рассмотрите совокупность всех неориентированных графов с 10 вершинами и 6 ребрами

Пусть M и m, соответственно, являются максимальным и минимальным количеством связанных компонентов в любом графе в коллекции

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

Предположим, что Q и R — языки.

Предполагая, что , что из следующего следует, что R отсутствует в P?

Хэш-таблицы могут способствовать эффективному решению всех проблем, описанных ниже КРОМЕ

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

• Датаграммы в источнике должны иметь размер наименьшего максимального блока передачи (MTU) всех соединений на пути к месту назначения
• Дейтаграммы могут быть фрагментированы во время маршрутизации
• Дейтаграммы собираются заново только в пункте назначения

Два процессора, M-5 и M-7, реализуют один и тот же набор инструкций

Процессор M5 использует 5-ступенчатый конвейер и тактовый цикл 10 наносекунд

Процессор M-7 использует 7-ступенчатый конвейер и тактовый цикл 7,5 наносекунд

Что из приведенного ниже верно?

• М-7 имеет лучшую максимальную пропускную способность, чем М-5
• Задержка выполнения одной инструкции в M-7 меньше, чем в M-5
• Программы, выполняемые на M-7, всегда будут выполняться быстрее, чем программы, выполняемые на M-5

Какой из следующих алгоритмов имеет время выполнения O(n²) в наихудшем случае, но O(nlog(n)) в среднем?

Какие из следующих свойств включает в себя объектно-ориентированная парадигма?

• Инкапсуляция
• Наследование
• Рекурсия

Пусть A и B — два набора слов (строк) из ∑* для некоторого алфавита символов ∑

Предположим, что B является подмножеством A

Какое из следующих утверждений всегда должно быть верным для A и B?

• Если A конечно, то и B конечно
• Если A регулярно, то и B регулярно
• Если A не зависит от контекста, то и B не зависит от контекста