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

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

  double power(double base, unsigned int exponent)
  {
  if (exponent == 0)
    return 1.0;
  else
    if (even(exponent))
      return power(base*base, exponent/2);
    else
      return power(base*base, exponent/2)*base;
  }

Сколько умножений выполняется в результате использования вызова power(5.0, 12)?

(В эту сумму не включайте деления)

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

Чтобы найти решение уравнения для полинома степени с производной , метод Ньютона делает итерации вида

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

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

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

Массив 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];

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

Предположим, что целевой объект 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

Какое из приведенных ниже названий является структурой данных в компиляторе, которая отвечает за управление информацией о переменных и их атрибутах?

k-ary tree — это дерево, в котором каждый узел имеет не более k детей.

В k-ary tree с n узлами и высотой h, какое из следующих значений является верхней границей для максимального количества листьев в зависимости от h, k и n?

Рассмотрите следующие два языка

Что из нижеследующего верно в отношении и  ?

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

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

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