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

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Тест по Computer Science, подготовил Участник:Akazikov

Вариант 2118680011.


Ваше имя*:


Вопрос 1

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

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

  1.  4096
  2.  256
  3.  2048
  4.  0
  5.  1024

Вопрос 2

Пусть T — дерево поиска в глубину связного неориентированного графа G Для каждой вершины v из T пусть:

  • prev(v) — количество посещенных узлов до v включительно во время обхода T по предварительному обходу, и
  • prev(v) — количество посещенных узлов до v включительно во время обхода T после обхода

Наименьшим общим предком вершин u и v в T является вершина w из T, такая, что w является предком как u, так и v, и ни один дочерний элемент w не является предком, как u, так и v

Пусть (u, v) — ребро в G, которого нет в T, такое, что pre(u) < pre(v)

Какое из следующих утверждений относительно u и v должно быть истинным?

  • post(u) < post(v)
  • u является предком v в T
  • Если w является наименьшим общим предком u и v в T, то w = u
  1.  1 и 2
  2.  Только 2
  3.  2 и 3
  4.  Только 1
  5.  Только 3

Вопрос 3

Рассмотрим следующую грамматику

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

  • Грамматика неоднозначна
  • Грамматика подходит для синтаксического анализа «сверху вниз»
  • Грамматика подходит для анализа по принципу «снизу вверх»
  1.  2 и 3
  2.  Только 2
  3.  Только 3
  4.  1, 2, 3
  5.  Только 1

Вопрос 4

График транзакций является сериализуемым, если его действие эквивалентно действию некоторого последовательного графика

Рассмотрим бухгалтерскую операцию, состоящую из двух транзакций — и , — которые необходимы для сохранения суммы A + B + C неизменной

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

 Lock A;        Lock B;
 A = A - 10;    B = B - 20;
 Unlock A;      Unlock B;
 B = B + 10;    C = C + 20;
 A = A - 10;    Lock B;
 Lock B;        B = B - 20;
 B = B + 10;    Unlock B;
 Unlock B;      C = C + 20;
 Lock A;        Lock A;
 A = A - 10;    B = B - 20;
 Unlock A;      Unlock A;
 B = B + 10;    C = C + 20;
  1.  2 и 3
  2.  1 и 2
  3.  Только 3
  4.  Только 1
  5.  Только 2

Вопрос 5

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

  1.  Он не может передавать параметры по ссылке
  2.  Он используется для вызова процедур на внешнем уровне вложенности
  3.  Он не может вернуть значение
  4.  Он используется для вызова процедур с адресами, удаленными более чем на байта
  5.  Он не может вызывать процедуры, реализованные на другом языке

Вопрос 6

k-ary tree — это дерево, в котором каждая вершина имеет не более k дочерних элементов

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 7

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

  1.  Чтобы определить аппаратный адрес заданного имени хоста
  2.  Для определения аппаратного адреса данного IP-адреса
  3.  Для преобразования веб-адресов в имена хостов
  4.  Чтобы определить подходящий маршрут для дейтаграммы
  5.  Чтобы определить IP-адрес заданного имени хоста

Вопрос 8

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

  • Нахождение минимального остовного дерева в неориентированном графе с целыми положительными весами ребер
  • Нахождение максимальной клики в неориентированном графе
  • Нахождение максимального потока от узла-источника к узлу-приемнику в ориентированном графе с целыми положительными значениями пропускной способности ребер
  1.  Только 3
  2.  Только 2
  3.  1 и 2
  4.  1, 2, 3
  5.  Только 1

Вопрос 9

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

  1.  a = 2 b = 9
  2.  a = 2 b = 7
  3.  a = 14 b = 16
  4.  a = 30 b = 30
  5.  a = 9 b = 14

Вопрос 10

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

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

  1.  4000
  2.  2000
  3.  0
  4.  1024
  5.  256