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

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Тест по Computer Science, подготовил Участник:Akazikov

Вариант 373432152.


Ваше имя*:


Вопрос 1

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

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

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

  • Если A конечно, то и B конечно
  • Если A регулярно, то и B регулярно
  • Если A не зависит от контекста, то и B не зависит от контекста
  1.  1 и 2
  2.  только 3
  3.  только 2
  4.  1, 2, 3
  5.  только 1

Вопрос 2

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

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

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

  1.  Фактические параметры активных процедур
  2.  Локальные переменные в стеке вызовов
  3.  Глобальные переменные программы
  4.  Динамически выделяемые объекты в куче
  5.  Значения в машинных регистрах

Вопрос 3

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

  1.  Ожидается, что ожидание будет недолгим
  2.  Программа выполняется в системе с разделением времени
  3.  Процессору не нужно выполнять никакой другой задачи
  4.  Задача должна быть выполнена в сжатые сроки в режиме реального времени
  5.  Цикл ожидания занятости проще в программировании, чем обработчик прерываний

Вопрос 4

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 5

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

  • Нахождение минимального остовного дерева в неориентированном графе с целыми положительными весами ребер
  • Нахождение максимальной клики в неориентированном графе
  • Нахождение максимального потока от узла-источника к узлу-приемнику в ориентированном графе с целыми положительными значениями пропускной способности ребер
  1.  Только 1
  2.  Только 2
  3.  1, 2, 3
  4.  Только 3
  5.  1 и 2

Вопрос 6

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

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

  1.  256
  2.  2048
  3.  1024
  4.  0
  5.  4096

Вопрос 7

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

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

Вопрос 8

Шаблон проектирования Singleton используется, чтобы гарантировать, что может быть создан только один экземпляр класса

Что из приведенного ниже верно для этого шаблона проектирования?

  • Класс Singleton имеет статический фабричный метод для cоздания своего экземпляра
  • Класс Singleton может быть подклассом другого класса
  • У класса Singleton есть собственный конструктор
  1.  1 и 3
  2.  Только 1
  3.  Только 3
  4.  1, 2, 3
  5.  Только 2

Вопрос 9

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

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

Вопрос 10

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

  • Дана комбинационная схема с n входами и m выходами и вентилями, где каждый вентиль является либо AND, OR, или NOT, и заданы m значений в качестве выходных данных или определяют, что не является возможным выходным сигналом схемы
  • Учитывая n на n матриц A с рациональными числовыми элементами, либо найдите точное значение, обратное для A, либо определите, что не существует. (Предположим, что каждое рациональное число выражается в виде пары целых чисел a/b (), где a и b выражены в двоичной системе счисления)
  • Задан ориентированный граф с узлами, пронумерованными , и заданными целыми положительными весами, присвоенными ребрам, либо найдите длину кратчайшего пути от узла 1 до узла n, либо определите, что такого пути не существует. (Здесь длина контура равна сумме длин реберных весов на контуре)
  1.  Только 2
  2.  1 и 2
  3.  Только 1
  4.  Только 3
  5.  2 и 3