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

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

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

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

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

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

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

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

Что из перечисленного не является свойством растровой графики (Bitmap graphics)?

Пусть M — одноленточная детерминированная машина Тьюринга с ленточным алфавитом {blank, 0, 1}, и C обозначает (возможно, бесконечное) вычисление M, начинающееся с пустой ленты

Входными данными для каждой задачи, приведенной ниже, являются M и целое положительное число n

Какая из следующих проблем является разрешимой?

• Вычисление C длится не менее n шагов
• Вычисление C длится не менее n шагов, и M выводит 1 в какой-то момент после n-го шага
• M сканирует не менее n различных квадратов ленты во время вычисления C

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

Рассмотрите следующие возможные структуры данных для набора из n различных целых чисел

• Минимальная куча
• Массив длиной n, отсортированный в порядке возрастания
• Сбалансированное дерево бинарного поиска

Для какой из этих структур данных требуется количество шагов, чтобы найти и удалить 7-й по величине элемент O(logn) в наихудшем случае?

Какое из следующих утверждений об Ethernet-сетях является ЛОЖНЫМ?

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

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

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

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

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