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

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

Пусть 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

Сортировка слиянием выполняется путем разделения списка из n чисел пополам, рекурсивной сортировки каждой половины и объединения двух половин

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

• Односвязный список
• Двусвязный список
• Массив

Для следующего кода смещение каждой условной ветви в коде указано на графике потока управления справа

Например, логическое выражение if_condition принимает значение true в половине случаев выполнения этого выражения

  do
  {
   U;
   if (if_condition)
   {
     V;
     if (break_condition)
       break;
   }
   else
     W;
   X;
   } while (loop_condition);
   Y;

Какое ожидаемое количество раз выполняется U?

Схема Эйлера неориентированного графа — это схема, в которой каждое ребро графа встречается ровно один раз

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

• Полный граф с 12 вершинами
• Полный граф с 13 вершинами
• Дерево с 13 вершинами

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

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

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

Предположим, что Q и R — языки.

Предполагая, что , что из следующего следует, что R отсутствует в P?

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

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

Рассмотрите следующие возможные структуры данных для набора из n различных целых чисел

• Минимальная куча
• Массив длиной n, отсортированный в порядке возрастания
• Сбалансированное дерево бинарного поиска

Для какой из этих структур данных требуется количество шагов, чтобы найти и удалить 7-й по величине элемент O(logn) в наихудшем случае?

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