Вариант 1385081766.
Пусть T — дерево поиска в глубину связного неориентированного графа G Для каждой вершины v из T пусть:
Наименьшим общим предком вершин u и v в T является вершина w из T, такая, что w является предком как u, так и v, и ни один дочерний элемент w не является предком, как u, так и v
Пусть (u, v) — ребро в G, которого нет в T, такое, что pre(u) < pre(v)
Какое из следующих утверждений относительно u и v должно быть истинным?
Некоторый рандомизированный алгоритм A предназначен для определения, является ли данное положительное целое число n простым, путем генерации случайной битовой строки r и, основываясь на значениях n и r, путем вывода либо Yes (n является простым), либо No (n является составным)
Выполнение алгоритма А гарантирует следующее
На входе m алгоритм A выполняется k раз (k > 0) и генерирует случайную строку при i-м выполнении , где являются взаимно независимыми
Предположим, что в каждом из k различных вариантов выполнения результат A равен No. Какова вероятность того, что m является составным?
Пусть A и B — два набора слов (строк) из ∑* для некоторого алфавита символов ∑
Предположим, что B является подмножеством A
Какое из следующих утверждений всегда должно быть верным для A и B?
Два процессора, M-5 и M-7, реализуют один и тот же набор инструкций
Процессор M5 использует 5-ступенчатый конвейер и тактовый цикл 10 наносекунд
Процессор M-7 использует 7-ступенчатый конвейер и тактовый цикл 7,5 наносекунд
Что из приведенного ниже верно?
Чтобы найти решение уравнения для полинома степени с производной , метод Ньютона делает итерации вида
начиная с некоторого начального значения , достаточно близкого к желаемому решению , чтобы обеспечить сходимость к для фиксированных значений и , что из приведенного ниже представляет порядок увеличения минимального числа итераций, необходимого для вычисления с точностью до бит как функции из ?
Центральный процессор имеет арифметический модуль, который складывает байты, а затем устанавливает свои флаговые биты V, C и Z следующим образом
Бит V устанавливается, если происходит арифметическое переполнение (в арифметике с двумя дополнениями)
Бит C устанавливается, если во время операции генерируется перенос из самого старшего бита
Бит Z устанавливается, если результат равен нулю
Каковы значения флагов битов V, C и Z после добавления 8-битных байтов 1100 1100 и 1000 1111 ?
Рассмотрим следующий псевдокод, где n — неотрицательное целое число
x = 0; i = 0; while i < n do x = x + 2^i; i = i + 1; end
Что из приведенного ниже является инвариантом цикла для оператора while?
(Примечание: инвариант цикла для оператора while — это утверждение, которое верно каждый раз, когда сторожевое условие оценивается во время выполнения оператора while)
Массив 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];
Сколько байт будет записано в память во время выполнения цикла, если в кэше действует политика сквозной записи?
В системах с поддержкой автоматического управления памятью, сборщик мусора обычно отвечает за возврат выделенных объектов памяти, содержимое которых не может повлиять на какие-либо будущие допустимые вычисления
Такие объекты идентифицируются путем того, что к ним невозможно получить доступ из корневого набора
Что из приведенного ниже не является часть корневого набора в типичном сборщике мусора?
Рассмотрите языки и , каждый по алфавиту {a, b}, где
Что из нижеследующего должно быть верно в отношении и ?