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

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

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

Предположим, что целевой объект t — это целочисленное значение, хранящееся в некотором элементе целочисленного массива x, который отсортирован в неубывающем порядке, и рассмотрим следующую схему цикла для поиска t

  <initialization of h and k>
  while (x[h] != t)
  {
    P;
  }

Если initialization устанавливает инвариант , какое из следующих определений для P, взятое по отдельности, гарантирует, что цикл завершится с , предпологая, что t появляется в массиве?

• if x[h] < t then h := h + 1
• h := h + 1
• k := k — 1

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

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

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

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

Input

Направленный граф , где

Стоимость для всех , где тогда и только тогда, когда

Definition

длина кратчайшего пути от до для всех

Если нет пути от до , то

Если для всех

Problem

Определить для всех

Алгоритм Флойда-Уоршалла дает решение динамического программирования для определения массива для и по следующим условиям

длина кратчайшего пути от до , для которого все промежуточные узлы на этом пути находятся в (где никакие промежуточные узлы не допускаются, если

Тогда

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

для и

для всех

Каково время работы алгоритма Флойда-Уоршалла ?

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

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

На конвейерном RISC-компьютере, где все арифметические команды имеют одинаковый CPI (cycles per instruction), какие из следующих действий улучшат время выполнения типичной программы?

• Увеличение частоты тактового цикла
• Запрещение любой переадресации в конвейере
• Удвоение размеров кэша интсрукций и кэша данных без изменения времени такта

Что из перечисленного ниже верно в отношении систем виртуальной памяти, использующих страницы?

• Виртуальное адресное пространство может быть больше объема физической памяти
• Программы должны находиться в оперативной памяти на протяжении всего времени их выполнения
• Страницы соответствуют семантическим характеристикам программы

Пусть G = (V, E) — конечный ориентированный ациклический граф с

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

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

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

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

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