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

Рассмотрите следующую функцию

  f(k)
  {
    x = 2;
    for i = 1 to k
      x = x * x;
    return x;
  }

Если n и k — целые положительные числа, то наименьшее значение k, при котором приблизительно равно?

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

Некоторый рандомизированный алгоритм A предназначен для определения, является ли данное положительное целое число n простым, путем генерации случайной битовой строки r и, основываясь на значениях n и r, путем вывода либо Yes (n является простым), либо No (n является составным)

Выполнение алгоритма А гарантирует следующее

• Если n — простое число, то результатом A всегда будет Yes
• Если n является составным, то существует вероятность p > 0, такое что результатом A будет No с вероятностью p и Yes с вероятностью 1 — p

На входе m алгоритм A выполняется k раз (k > 0) и генерирует случайную строку при i-м выполнении , где являются взаимно независимыми

Если m является составным, какова вероятность того, что в каждом из k различных вариантов выполнения результат A будет YES?

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

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

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

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

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

Предположим, что Q и R — языки.

Предполагая, что , что из следующего следует, что R отсутствует в P?

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

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

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

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

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

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

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

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