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

Инвариантом для приведенного ниже цикла является и

  x := b; k := n; z := 1;
  while (k != 0)
  {
    if odd(k) then z := z*x;
    x := x*x;
    k := [k/2];
  }

Когда цикл завершается, что из перечисленного ниже должно быть истинным?

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

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

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

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

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

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

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

Каково время работы алгоритма Флойда-Уоршалла ?

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

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

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

Рассмотрите совокупность всех неориентированных графов с 10 вершинами и 6 ребрами

Пусть M и m, соответственно, являются максимальным и минимальным количеством связанных компонентов в любом графе в коллекции

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

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

Некоторая конвейерная 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 + +?