Тест по 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

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

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

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

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

Что из приведенного ниже представляет собой обратный (post-order) обход T?

Какое из следующих утверждений об Ethernet-сетях является ЛОЖНЫМ?

Одним из подходов к обработке данных нечеткой логики может быть разработка компьютера с использованием троичной логики (base-3), чтобы данные могли храниться в виде «true», «false» и «unknown»

Если каждый элемент троичной логики называется flit, то сколько таких элементов требуется для представления как минимум 256 различных значений?

Хэш-таблицы могут способствовать эффективному решению всех проблем, описанных ниже КРОМЕ

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

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

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

Рассмотрите языки и , каждый по алфавиту {a, b}, где

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

• Если регулярный, то регулярный
• Если не зависит от контекста, то не зависит от контекста
• Если рекурсивный, то рекурсивный

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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