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

Пусть T — дерево поиска в глубину связного неориентированного графа G Для каждой вершины v из T пусть:

• prev(v) — количество посещенных узлов до v включительно во время обхода T по предварительному обходу, и
• prev(v) — количество посещенных узлов до v включительно во время обхода T после обхода

Наименьшим общим предком вершин u и v в T является вершина w из T, такая, что w является предком как u, так и v, и ни один дочерний элемент w не является предком, как u, так и v

Пусть (u, v) — ребро в G, которого нет в T, такое, что pre(u) < pre(v)

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

• post(u) < post(v)
• u является предком v в T
• Если w является наименьшим общим предком u и v в T, то w = u

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

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

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

Расписание транзакций является сериализуемым, если его действие эквивалентно действию некоторого последовательного расписания

Рассмотрим бухгалтерскую операцию, состоящую из двух транзакций — и , — которые необходимы для сохранения суммы A + B + C неизменной

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

 Lock A;        Lock B;
 A = A - 10;    B = B - 20;
 Unlock A;      Unlock B;
 B = B + 10;    C = C + 20;

 A = A - 10;    Lock B;
 Lock B;        B = B - 20;
 B = B + 10;    Unlock B;
 Unlock B;      C = C + 20;

 Lock A;        Lock A;
 A = A - 10;    B = B - 20;
 Unlock A;      Unlock A;
 B = B + 10;    C = C + 20;

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

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

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

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

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

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

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

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

• Если A конечно, то и B конечно
• Если A регулярно, то и B регулярно
• Если A не зависит от контекста, то и B не зависит от контекста

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

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