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

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

Рассмотрим бухгалтерскую операцию, состоящую из двух транзакций — и , — которые необходимы для сохранения суммы 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, если на ее входе указано любое из трехбитовых чисел 1, 4, 5 или 6; в противном случае выход схемы равен 0

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

Некоторый рандомизированный алгоритм A предназначен для определения, является ли данное положительное целое число n простым, путем генерации случайной битовой строки r и, основываясь на значениях n и r, путем вывода либо Yes (n является простым), либо No (n является составным)

Выполнение алгоритма А гарантирует следующее

• Если n — простое число, то результатом A всегда будет Yes
• Если n является составным, то существует вероятность p > 0, такое что результатом A будет No с вероятностью p и Yes с вероятностью 1 — p

На входе m алгоритм A выполняется k раз (k > 0) и генерирует случайную строку при i-м выполнении , где являются взаимно независимыми

Если m является составным, какова вероятность того, что в каждом из k различных вариантов выполнения результат A будет YES?

Согласно стандарту IEEE, 32-разрядное число с плавающей запятой одинарной точности N определяется как

где S — знаковый бит, F — дробная мантисса, а E — смещенный показатель степени

Число с плавающей запятой хранится в формате S : E : F, где S, E и F хранятся в 1 бите, 8 битах и 23 битах соответственно

Каково десятичное значение числа с плавающей запятой C1E00000 (шестнадцатеричная система счисления)?

Центральный процессор имеет арифметический модуль, который складывает байты, а затем устанавливает свои флаговые биты V, C и Z следующим образом

Бит V устанавливается, если происходит арифметическое переполнение (в арифметике с двумя дополнениями)

Бит C устанавливается, если во время операции генерируется перенос из самого старшего бита

Бит Z устанавливается, если результат равен нулю

Каковы значения флагов битов V, C и Z после добавления 8-битных байтов 1100 1100 и 1000 1111 ?

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

Для каждого неотрицательного целого числа n пусть  — максимально возможное число областей, на которые плоскость может быть разделена n прямыми линиями

Например, и

Тогда имеет порядок

Компания X поставила 5 компьютерных чипов, 1 из которых оказался бракованным, а компания Y поставила 4 компьютерных чипа, 2 из которых оказались бракованными

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

Если обнаружится, что выбранный чип бракованный, какова вероятность того, что чип был изготовлен компанией Y?

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

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

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

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

• Нахождение минимального остовного дерева в неориентированном графе с целыми положительными весами ребер
• Нахождение максимальной клики в неориентированном графе
• Нахождение максимального потока от узла-источника к узлу-приемнику в ориентированном графе с целыми положительными значениями пропускной способности ребер