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

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

Сортировка слиянием выполняется путем разделения списка из n чисел пополам, рекурсивной сортировки каждой половины и объединения двух половин

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

• Односвязный список
• Двусвязный список
• Массив

Рассмотрите следующие два языка

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

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

• Если задача(конечная) строка w, является ли w префиксом десятичного представления числа π?
• При наличии программы и входных данных, является ли вывод программы десятичным представления числа π?
• Если задана программа, которая принимает в качестве входных данных префикс десятичного представления числа π, всегда ли выходные данные программы одинаковы для каждого префикса?

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

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

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

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

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

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

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

Какой из следующих алгоритмов имеет время выполнения O(n²) в наихудшем случае, но O(nlog(n)) в среднем?