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

Выходные данные процедуры mystery зависят от используемого метода передачи параметров

 procedure mystery
   a : integer;
   b : integer;
   procedure enigma(x,y)
   begin
     y = y + b;
     x = b + x;
     b = x + b;
     a = y;
   end enigma;
 begin
   a = 2; b = 7;
   enigma(a,b);
   write(a); write(b);
 end mystery;

Предположим, что все параметры передаются по ссылке

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

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

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

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

Рассмотрим следующий псевдокод

  x := 1;
  i := 1;
  while (x <= 1000)
  begin
    x := 2^x;
    i := i + 1;
  end;

Каково значение i в конце псевдокода?

Предположим, что целевой объект  — это целочисленное значение, хранящееся в некотором элементе целочисленного массива , который отсортирован в неубывающем порядке, и рассмотрим следующую схему цикла для поиска .

 <initialization of h and k>
 while (x[h] != t)
 {
   P;
 }

Если <initialization> устанавливает инвариант то какое из следующих определений для , взятое отдельно, гарантирует, что цикл завершится с помощью , предпологая, что появится в массиве ?

• if x[h] < t then h := h + 1
• h := h + 1
• k := k — 1

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

Input

Ориентированный граф , где

Стоимость для любых , где и если только

Definition

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

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

Если для любого

Problem

Определить для любого

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

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

Тогда

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

для и

для любого

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

Логическая схема имеет три входных бита: где  — младший бит, а  — старший бит

Выходной сигнал схемы равен 1, если на ее входе указано любое из 3-разрядных чисел 1, 4, 5 или 6; в противном случае выходной сигнал равен 0

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

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

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

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

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

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

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

Определенный рандомизированный алгоритм 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 ?