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

Предположим, что Q и R — языки.

Предполагая, что , что из следующего следует, что R отсутствует в P ?

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

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

Input

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

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

Definition

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

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

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

Problem

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

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

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

Тогда

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

для и

для любого

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

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

Если T — это бинарное дерево поиска с меньшими элементами в левом поддереве, то какой из следующих узлов содержит четвертый наименьший элемент в T?

Предположим, что у определенного программного продукта средняя наработка на отказ составляет 10 000 часов, а среднее время ремонта — 20 часов.

Если продуктом пользуются 100 клиентов, какова его доступность?

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

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

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

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

• Класс Singleton имеет статический фабричный метод для предоставления своего экземпляра
• Класс Singleton может быть подклассом другого класса
• У класса Singleton есть собственный конструктор

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

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

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

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

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

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

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