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

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

Вариант 2062818112.


Прошло 00:00:02.
Ваше имя*:


Вопрос 1

Что из перечисленного НЕ является разумным обоснованием выбора режима активного ожидания для асинхронного события?

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

Вопрос 2

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

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

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

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

Вопрос 3

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

Вопрос 4

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

  1.  1 и 2
  2.  2 и 3
  3.  только 1
  4.  только 3
  5.  1 и 3

Вопрос 5

Предположим, что P(x, y) означает «x является родителем y», а M(x) означает «x — мужчина»

Если F(v, w) равно , каково значение выражения F(v, w)?

  1.  v является дедом w
  2.  v является братом w
  3.  v является дядей w
  4.  v является племянником w
  5.  v является двоюродным братом w

Вопрос 6

Для связного неориентированного графа G = (V, E), какое из следующих условий должно быть верно?

  • являются чётными
  • G имеет по крайней мере одну вершину со степенью 1
  1.  Только 1
  2.  Только 3
  3.  2 и 3
  4.  Только 2
  5.  1 и 2

Вопрос 7

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

Вопрос 8

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

Некоторая конвейерная RISC-машина имеет 8 регистров общего назначения R0, R1, …, R7 и поддерживает следующие операции

 ADD Rs1, Rs2, Rd    Add Rs1 to Rs2 and put the sum in Rd
 MUL Rs1, Rs2, Rd    Multiply Rs1 by Rs2 and put the product in Rd

Операция обычно занимает один цикл; однако операция занимает два цикла, если она дает результат, необходимый для выполнения непосредственно следующей операции в последовательности операций.

Рассмотрим выражение AB ABC BC + +, где переменные A, B, C находятся в регистрах R0, R1, R2

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

  1.  5
  2.  6
  3.  9
  4.  8
  5.  7

Вопрос 10

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

  f(k)
  {
    x = 2;
    for i = 1 to k
      x = x * x;
    return x;
  }

Если n и k — целые положительные числа, то наименьшее значение k, при котором приблизительно равно?

  1.  
  2.  
  3.  
  4.  
  5.