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

Рассмотрите языки и , каждый по алфавиту {a, b}, где

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

• Если регулярный, то регулярный
• Если не зависит от контекста, то не зависит от контекста
• Если рекурсивный, то рекурсивный

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

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

Пусть k — целое число, большее 1. Какое из следующих значений соответствует порядку возрастания выражения в зависимости от n?

Что из перечисленного не является свойством растровой графики (Bitmap graphics)?

Пусть T — дерево поиска в глубину связного неориентированного графа G Для каждой вершины v из T пусть:

• prev(v) — количество посещенных узлов до v включительно во время обхода T по предварительному обходу, и
• prev(v) — количество посещенных узлов до v включительно во время обхода T после обхода

Наименьшим общим предком вершин u и v в T является вершина w из T, такая, что w является предком как u, так и v, и ни один дочерний элемент w не является предком, как u, так и v

Пусть (u, v) — ребро в G, которого нет в T, такое, что pre(u) < pre(v)

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

• post(u) < post(v)
• u является предком v в T
• Если w является наименьшим общим предком u и v в T, то w = u

Предположим, что P(x, y) означает «x является родителем y», а M(x) означает «x — мужчина»

Если F(v, w) равно , каково значение выражения F(v, w)?

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

Рассмотрите следующую функцию

  f(k)
  {
    x = 2;
    for i = 1 to k
      x = x * x;
    return x;
  }

Если n и k — целые положительные числа, то наименьшее значение k, при котором приблизительно равно?

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

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

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

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

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

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

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