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

1

2

3

4

Тест по Computer Science, подготовил Участник:Akazikov

Вариант 2029059892.

Ваше имя*:

Вопрос 1

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

Вопрос 2

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

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

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

Вопрос 3

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

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

Вопрос 4

Рассмотрите следующие два языка

Что из нижеследующего верно в отношении и ?

регулярный, а контекстно-свободный, но не регулярный
Ни , ни не являются регулярными, но оба они не зависят от контекста
является контекстно-свободным, но не регулярным, и не является контекстно-свободным
и являются регулярными
Ни , ни не являются контекстно-свободными

Вопрос 5

Массив 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];

Сколько байт будет записано в память во время выполнения цикла, если в кэше предусмотрена политика обратной записи?

Вопрос 6

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

Нахождение раскраски вершин G (в которой соседние вершины имеют разные цвета) с минимальным количеством цветов
Нахождение всех прямых деревьев G
Нахождение самого длинного простого цикла в G
Нахождение кратчайшего цикла в G
Нахождение крупнейшей клики в G

Вопрос 7

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

Вопрос 8

Какое из следующих утверждений об удаленном вызове процедуры (RPC) верно?

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

Вопрос 9

Предположим, что P(x, y) означает «x является родителем y», а M(x) означает «x — мужчина»

Если F(v, w) равно , каково значение выражения F(v, w)?

v является двоюродным братом w
v является братом w
v является дедом w
v является дядей w
v является племянником w

Вопрос 10

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

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

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