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

Выходные данные процедуры mystery зависят от используемого метода передачи параметров

  procedure mystery
    a : integer;
    b : integer;
    procedure enigma(x,y)
    begin
      y = y + b;
      x = b + x;
      b = x + b;
      a = y;
    end enigma;
  begin
    a = 2; b = 7;
    enigma(a,b);
    write(a); write(b);
  end mystery;

Предположим, что все параметры передаются по ссылке

Какие из следующих значений выводятся при вызове процедуры mystery?

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

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

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

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

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

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

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

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

Какое из следующих условий может быть выражено логической формулой в логических переменных и связующие элементы and, or, (без not)

• По крайней мере три из верны
• Ровно три из верны
• Чётное число из верны

Сортировка слиянием выполняется путем разделения списка из n чисел пополам, рекурсивной сортировки каждой половины и объединения двух половин

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

• Односвязный список
• Двусвязный список
• Массив

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

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

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

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

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

Пусть 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