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

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

Пусть k — целое число, большее 1. Какое из следующих значений соответствует порядку возрастания выражения в зависимости от n?

Схема Эйлера неориентированного графа — это схема, в которой каждое ребро графа встречается ровно один раз

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

• Полный граф с 12 вершинами
• Полный граф с 13 вершинами
• Дерево с 13 вершинами

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

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

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

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

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

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

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

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

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

• Нахождение минимального остовного дерева в неориентированном графе с целыми положительными весами ребер
• Нахождение максимальной клики в неориентированном графе
• Нахождение максимального потока от узла-источника к узлу-приемнику в ориентированном графе с целыми положительными значениями пропускной способности ребер

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

Что из перечисленного ниже верно в отношении систем виртуальной памяти, использующих страницы?

• Виртуальное адресное пространство может быть больше объема физической памяти
• Программы должны находиться в оперативной памяти на протяжении всего времени их выполнения
• Страницы соответствуют семантическим характеристикам программы

Сортировка слиянием выполняется путем разделения списка из n чисел пополам, рекурсивной сортировки каждой половины и объединения двух половин

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

• Односвязный список
• Двусвязный список
• Массив

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

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

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