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

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

Предположим, что отладчик устанавливает точку останова на инструкции загрузки по виртуальному адресу 0x77E81234 (шестнадцатеричная запись) в отлаживаемом процессе P

Если текстовый сегмент P начинается по адресу с 0x77E80000 в виртуальном адресном пространстве P и если отладчик сопоставил этот же текстовый сегмент на 0x010000000 в своем виртуальном адресном пространстве

Какой из следующих виртуальных адресов используется отладчиком в операции ЗАПИСИ, а также описание того, как отладчик сопоставил страницу виртуальной памяти, содержащую этот адрес?

Шаблон проектирования Singleton используется, чтобы гарантировать, что может быть создан только один экземпляр класса

Что из приведенного ниже верно для этого шаблона проектирования?

• Класс Singleton имеет статический фабричный метод для cоздания своего экземпляра
• Класс Singleton может быть подклассом другого класса
• У класса Singleton есть собственный конструктор

Пусть T(n) определяется как и для всех целых чисел

Какое из следующих утверждений представляет порядок роста T(n) как функции n?

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

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

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

• Нахождение минимального остовного дерева в неориентированном графе с целыми положительными весами ребер
• Нахождение максимальной клики в неориентированном графе
• Нахождение максимального потока от узла-источника к узлу-приемнику в ориентированном графе с целыми положительными значениями пропускной способности ребер

Инвариантом для приведенного ниже цикла является и

  x := b; k := n; z := 1;
  while (k != 0)
  {
    if odd(k) then z := z*x;
    x := x*x;
    k := [k/2];
  }

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

Выходные данные процедуры 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?

Для связного неориентированного графа G = (V, E), какое из следующих условий должно быть верно?

• являются чётными
• G имеет по крайней мере одну вершину со степенью 1

Какая из следующих задач является (являются) разрешимой?

• Если задача(конечная) строка w, является ли w префиксом десятичного представления числа π?
• При наличии программы и входных данных, является ли вывод программы десятичным представления числа π?
• Если задана программа, которая принимает в качестве входных данных префикс десятичного представления числа π, всегда ли выходные данные программы одинаковы для каждого префикса?