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

У G есть вершина без входящего ребра
G имеет вершину без исходящего ребра
G имеет изолированную вершину, то есть вершину, не имеющe. ни входящего, ни исходящего ребра

Вопрос 3

Какое из следующих утверждений об Ethernet-сетях является ЛОЖНЫМ?

Протоколы Ethernet используют метод обнаружения коллизий для обеспечения правильной передачи сообщений
Пакеты, отправляемые по Ethernet-сетям, ограничены по размеру
В Ethernet-сетях используются шины с несколькими ведущими устройствами
Длина сетей, подключенных с помощью Ethernets, ограничена несколькими сотнями метров
Ethernets-сети используют коммутацию каналов для отправки сообщений

Вопрос 4

Рассмотрим следующий псевдокод, где n — неотрицательное целое число

  x = 0;
  i = 0;
  while i < n do
    x = x + 2^i;
    i = i + 1;
  end

Что из приведенного ниже является инвариантом цикла для оператора while?

(Примечание: инвариант цикла для оператора while — это утверждение, которое верно каждый раз, когда сторожевое условие оценивается во время выполнения оператора while)

x > 0 and 1 <= i < n
x = 2^i — 1 and 0 <= i < n
x = 2^i — 1 and 0 <= i <= n
x = 2^(i+1) — 1 and 0 <= i <= n
x = 2^(i+1) — 1 and 0 <= i < n

Вопрос 5

Два процессора, M-5 и M-7, реализуют один и тот же набор инструкций

Процессор M5 использует 5-ступенчатый конвейер и тактовый цикл 10 наносекунд

Процессор M-7 использует 7-ступенчатый конвейер и тактовый цикл 7,5 наносекунд

Что из приведенного ниже верно?

М-7 имеет лучшую максимальную пропускную способность, чем М-5
Задержка выполнения одной инструкции в M-7 меньше, чем в M-5
Программы, выполняемые на M-7, всегда будут выполняться быстрее, чем программы, выполняемые на M-5

Вопрос 6

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

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

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

Вопрос 7

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

Дана комбинационная схема с n входами и m выходами и вентилями, где каждый вентиль является либо AND, OR, или NOT, и заданы m значений в качестве выходных данных или определяют, что не является возможным выходным сигналом схемы
Учитывая n на n матриц A с рациональными числовыми элементами, либо найдите точное значение, обратное для A, либо определите, что не существует. (Предположим, что каждое рациональное число выражается в виде пары целых чисел a/b (), где a и b выражены в двоичной системе счисления)
Задан ориентированный граф с узлами, пронумерованными , и заданными целыми положительными весами, присвоенными ребрам, либо найдите длину кратчайшего пути от узла 1 до узла n, либо определите, что такого пути не существует. (Здесь длина контура равна сумме длин реберных весов на контуре)