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

Для следующего кода смещение каждой условной ветви в коде указано на графике потока управления справа

Например, логическое выражение if_condition принимает значение true в половине случаев выполнения этого выражения

  do
  {
   U;
   if (if_condition)
   {
     V;
     if (break_condition)
       break;
   }
   else
     W;
   X;
   } while (loop_condition);
   Y;

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

Рассмотрите следующие два языка

Что из нижеследующего верно в отношении и  ?

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

• Дана комбинационная схема с n входами и m выходами и вентилями, где каждый вентиль является либо AND, OR, или NOT, и заданы m значений в качестве выходных данных или определяют, что не является возможным выходным сигналом схемы
• Учитывая n на n матриц A с рациональными числовыми элементами, либо найдите точное значение, обратное для A, либо определите, что не существует. (Предположим, что каждое рациональное число выражается в виде пары целых чисел a/b (), где a и b выражены в двоичной системе счисления)
• Задан ориентированный граф с узлами, пронумерованными , и заданными целыми положительными весами, присвоенными ребрам, либо найдите длину кратчайшего пути от узла 1 до узла n, либо определите, что такого пути не существует. (Здесь длина контура равна сумме длин реберных весов на контуре)

Массив A содержит 256 элементов по 4 байта каждый. Его первый элемент хранится по физическому адресу 4096

Массив B содержит 512 элементов по 4 байта каждый. Его первый элемент хранится по физическому адресу 8192

Предположим, что только массивы A и B могут быть кэшированы в изначально пустой, физически адресуемой, физически маркированной, кэш-памяти с прямым отображением, объемом 2 Кбайт и размером блока 8 байт

Затем выполняется следующий цикл

  for (i = 0; i < 256; i++)
    A[i] = A[i] + B[2*i];

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

Что из перечисленного ниже верно в отношении систем виртуальной памяти, использующих страницы?

• Виртуальное адресное пространство может быть больше объема физической памяти
• Программы должны находиться в оперативной памяти на протяжении всего времени их выполнения
• Страницы соответствуют семантическим характеристикам программы

Из следующих задач, касающихся данного неориентированного графа G, о котором в настоящее время известно, что он разрешим за полиномиальное время?

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

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

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

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

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

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

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

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

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

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

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

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

Какое из следующих утверждений об удаленном вызове процедуры (RPC) верно?