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

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

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

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

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

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

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

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

Пусть 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

Пусть T(n) определяется как и для всех целых чисел

Какое из следующих утверждений представляет порядок роста T(n) как функции n?

Центральный процессор имеет арифметический модуль, который складывает байты, а затем устанавливает свои флаговые биты V, C и Z следующим образом

Бит V устанавливается, если происходит арифметическое переполнение (в арифметике с двумя дополнениями)

Бит C устанавливается, если во время операции генерируется перенос из самого старшего бита

Бит Z устанавливается, если результат равен нулю

Каковы значения флагов битов V, C и Z после добавления 8-битных байтов 1100 1100 и 1000 1111 ?

Схема Эйлера неориентированного графа — это схема, в которой каждое ребро графа встречается ровно один раз

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

• Полный граф с 12 вершинами
• Полный граф с 13 вершинами
• Дерево с 13 вершинами

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

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

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

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

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

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