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

Рассмотрим следующую грамматику

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

• Грамматика неоднозначна
• Грамматика подходит для нисходящего анализа
• Грамматика подходит для восходящего анализа

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

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

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

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

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

Что из перечисленного НЕ является разумным обоснованием выбора режима активного ожидания для асинхронного события?

Предположим, что целевой объект t — это целочисленное значение, хранящееся в некотором элементе целочисленного массива x, который отсортирован в неубывающем порядке, и рассмотрим следующую схему цикла для поиска t

  <initialization of h and k>
  while (x[h] != t)
  {
    P;
  }

Если initialization устанавливает инвариант , какое из следующих определений для P, взятое по отдельности, гарантирует, что цикл завершится с , предпологая, что t появляется в массиве?

• if x[h] < t then h := h + 1
• h := h + 1
• k := k — 1

Какая из перечисленных ниже схем шифрования наиболее близка к абсолютно безопасной?

Расписание транзакций является сериализуемым, если его действие эквивалентно действию некоторого последовательного расписания

Рассмотрим бухгалтерскую операцию, состоящую из двух транзакций — и , — которые необходимы для сохранения суммы A + B + C неизменной

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

 Lock A;        Lock B;
 A = A - 10;    B = B - 20;
 Unlock A;      Unlock B;
 B = B + 10;    C = C + 20;

 A = A - 10;    Lock B;
 Lock B;        B = B - 20;
 B = B + 10;    Unlock B;
 Unlock B;      C = C + 20;

 Lock A;        Lock A;
 A = A - 10;    B = B - 20;
 Unlock A;      Unlock A;
 B = B + 10;    C = C + 20;

Некоторая конвейерная 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 + +?

Для каждого неотрицательного целого числа n пусть  — максимально возможное число областей, на которые плоскость может быть разделена n прямыми линиями

Например, и

Тогда имеет порядок

Схема Эйлера неориентированного графа — это схема, в которой каждое ребро графа встречается ровно один раз

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

• Полный граф с 12 вершинами
• Полный граф с 13 вершинами
• Дерево с 13 вершинами