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

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

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

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

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

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

Пусть N — множество всех натуральных чисел.

Какие из следующих множеств счетные?

• Совокупность всех функций от N до {0, 1}
• Набор всех функций от {0, 1} до N
• Наибольшее подмножество из N

Для связного неориентированного графа G = (V, E), какое из следующих условий должно быть верно?

• являются чётными
• G имеет по крайней мере одну вершину со степенью 1

Рассмотрим следующую грамматику

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

• Грамматика неоднозначна
• Грамматика подходит для нисходящего анализа
• Грамматика подходит для восходящего анализа

Какое из следующих условий может быть выражено логической формулой в логических переменных и связующие элементы and, or, (без not)

• По крайней мере три из верны
• Ровно три из верны
• Чётное число из верны

Предположим, что отладчик устанавливает точку останова на инструкции загрузки по виртуальному адресу 0x77E81234 (шестнадцатеричная запись) в отлаживаемом процессе P

Если текстовый сегмент P начинается по адресу с 0x77E80000 в виртуальном адресном пространстве P и если отладчик сопоставил этот же текстовый сегмент на 0x010000000 в своем виртуальном адресном пространстве

Какой из следующих виртуальных адресов используется отладчиком в операции ЗАПИСИ, а также описание того, как отладчик сопоставил страницу виртуальной памяти, содержащую этот адрес?

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

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

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

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

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