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

Некоторый рандомизированный алгоритм 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-м выполнении , где являются взаимно независимыми

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

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

Например, и

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

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

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

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

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

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

Хэш-таблицы могут способствовать эффективному решению всех проблем, описанных ниже КРОМЕ

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

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

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

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

Пусть A и B — два набора слов (строк) из ∑* для некоторого алфавита символов ∑

Предположим, что B является подмножеством A

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

• Если A конечно, то и B конечно
• Если A регулярно, то и B регулярно
• Если A не зависит от контекста, то и B не зависит от контекста

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

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

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

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

Пусть G = (V, E) — конечный ориентированный ациклический граф с

Что из следующего должно быть верным?

• У G есть вершина без входящего ребра
• G имеет вершину без исходящего ребра
• G имеет изолированную вершину, то есть вершину, не имеющe. ни входящего, ни исходящего ребра

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

• Инкапсуляция
• Наследование
• Рекурсия