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

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

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

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

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

Предположим, что у определенного программного продукта средняя наработка на отказ составляет 10 000 часов, а среднее время ремонта — 20 часов.

Если продуктом пользуются 100 клиентов, какова его доступность?

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

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

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

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

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

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

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

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

Логическая схема имеет три входных бита: где  — младший бит, а  — старший бит

Выходной сигнал схемы равен 1, если на ее входе указано любое из 3-разрядных чисел 1, 4, 5 или 6; в противном случае выходной сигнал равен 0

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

Хэш-таблицы могут способствовать эффективному среднему решению всех проблем, описанных ниже КРОМЕ

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

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

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