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

Массив A содержит 256 элементов по 4 байта каждый. Его первый элемент хранится по физическому адресу 4096

Массив B содержит 512 элементов по 4 байта каждый. Его первый элемент хранится по физическому адресу 8192

Предположим, что только массивы A и B могут быть кэшированы в изначально пустой, физически адресуемой, физически маркированной, кэш-памяти с прямым отображением, объемом 2 Кбайт и размером блока 8 байт

Затем выполняется следующий цикл

  for (i = 0; i < 256; i++)
    A[i] = A[i] + B[2*i];

Сколько байт будет записано в память во время выполнения цикла, если в кэше действует политика сквозной записи?

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

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

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

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

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

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

Пусть N — множество всех натуральных чисел.

Какие из следующих множеств счетные?

• Совокупность всех функций от N до {0, 1}
• Набор всех функций от {0, 1} до N
• Наибольшее подмножество из N

Одним из подходов к обработке данных нечеткой логики может быть разработка компьютера с использованием троичной логики (base-3), чтобы данные могли храниться в виде «true», «false» и «unknown»

Если каждый элемент троичной логики называется flit, то сколько таких элементов требуется для представления как минимум 256 различных значений?

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

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

Такие объекты идентифицируются путем того, что к ним невозможно получить доступ из корневого набора

Что из приведенного ниже не является часть корневого набора в типичном сборщике мусора?

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

Рассмотрим следующий псевдокод

  x := 1;
  i := 1;
  while (x <= 1000)
  begin
    x := 2^x;
    i := i + 1;
  end;

Каково значение i в конце псевдокода?

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

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

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