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

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

Вариант 3843887769.


Ваше имя*:


Вопрос 1

Пусть 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.  Только 2
  2.  2 и 3
  3.  Только 1
  4.  Только 3
  5.  1 и 2

Вопрос 2

Массив 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.  1024
  2.  0
  3.  256
  4.  2048
  5.  4096

Вопрос 3

Выходные данные процедуры 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 = 14 b = 16
  2.  a = 2 b = 7
  3.  a = 30 b = 30
  4.  a = 2 b = 9
  5.  a = 9 b = 14

Вопрос 4

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

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

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

Вопрос 5

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

  1.  Шифр Цезаря, шифр подстановки
  2.  DES (Data Encryption Standard), алгоритм с симметричным ключом
  3.  Одноразовый блокнот
  4.  Энигма, перестановочный шифр
  5.  RSA, алгоритм с открытым ключом

Вопрос 6

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

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

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

  1.  Значения в машинных регистрах
  2.  Глобальные переменные программы
  3.  Динамически выделяемые объекты в куче
  4.  Локальные переменные в стеке вызовов
  5.  Фактические параметры активных процедур

Вопрос 7

Два процессора, M-5 и M-7, реализуют один и тот же набор инструкций

Процессор M5 использует 5-ступенчатый конвейер и тактовый цикл 10 наносекунд

Процессор M-7 использует 7-ступенчатый конвейер и тактовый цикл 7,5 наносекунд

Что из приведенного ниже верно?

  • М-7 имеет лучшую максимальную пропускную способность, чем М-5
  • Задержка выполнения одной инструкции в M-7 меньше, чем в M-5
  • Программы, выполняемые на M-7, всегда будут выполняться быстрее, чем программы, выполняемые на M-5
  1.  2 и 3
  2.  1 и 3
  3.  Только 1
  4.  1, 2, 3
  5.  Только 2

Вопрос 8

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

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

Из следующих задач, касающихся данного неориентированного графа G, о котором в настоящее время известно, что он разрешим за полиномиальное время?

  1.  Нахождение раскраски вершин G (в которой соседние вершины имеют разные цвета) с минимальным количеством цветов
  2.  Нахождение крупнейшей клики в G
  3.  Нахождение всех прямых деревьев G
  4.  Нахождение самого длинного простого цикла в G
  5.  Нахождение кратчайшего цикла в G

Вопрос 10

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

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

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

  1.  
  2.  
  3.  
  4.  
  5.