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

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Тест по Computer Science, подготовил Участник:Akazikov

Вариант 867068504.


Прошло 00:00:03.
Ваше имя*:


Вопрос 1

Какое из следующих условий может быть выражено логической формулой в логических переменных и связующие элементы and, or, (без not)

  • По крайней мере три из верны
  • Ровно три из верны
  • Чётное число из верны
  1.  Только 3
  2.  1 и 3
  3.  Только 2
  4.  2 и 3
  5.  Только 1

Вопрос 2

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

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

  1.  Q находится в NP, а Q за полиномиальное время сводится к R
  2.  Q является NP-полным, а Q за полиномиальное время сводится к R
  3.  Q является NP-полным, а R за полиномиальное время сводится к Q
  4.  Q находится в NP, а R за полиномиальное время сводится к Q
  5.  R находится в NP

Вопрос 3

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

  double power(double base, unsigned int exponent)
  {
  if (exponent == 0)
    return 1.0;
  else
    if (even(exponent))
      return power(base*base, exponent/2);
    else
      return power(base*base, exponent/2)*base;
  }


Сколько умножений выполняется в результате использования вызова power(5.0, 12)?

(В эту сумму не включайте деления)

  1.  6
  2.  12
  3.  9
  4.  5
  5.  8

Вопрос 4

Пусть 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
  1.  Только 3
  2.  Только 2
  3.  1 и 2
  4.  Только 1
  5.  2 и 3

Вопрос 5

Пусть M — одноленточная детерминированная машина Тьюринга с ленточным алфавитом {blank, 0, 1}, и C обозначает (возможно, бесконечное) вычисление M, начинающееся с пустой ленты

Входными данными для каждой задачи, приведенной ниже, являются M и целое положительное число n

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

  • Вычисление C длится не менее n шагов
  • Вычисление C длится не менее n шагов, и M выводит 1 в какой-то момент после n-го шага
  • M сканирует не менее n различных квадратов ленты во время вычисления C
  1.  1 и 2
  2.  Только 3
  3.  Нет правильных ответов
  4.  1 и 3
  5.  1, 2, 3

Вопрос 6

Некоторая конвейерная RISC-машина имеет 8 регистров общего назначения R0, R1, …, R7 и поддерживает следующие операции

 ADD Rs1, Rs2, Rd    Add Rs1 to Rs2 and put the sum in Rd
 MUL Rs1, Rs2, Rd    Multiply Rs1 by Rs2 and put the product in Rd

Операция обычно занимает один цикл; однако операция занимает два цикла, если она дает результат, необходимый для выполнения непосредственно следующей операции в последовательности операций.

Рассмотрим выражение AB ABC BC + +, где переменные A, B, C находятся в регистрах R0, R1, R2

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

  1.  5
  2.  9
  3.  6
  4.  7
  5.  8

Вопрос 7

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

  • Датаграммы в источнике должны иметь размер наименьшего максимального блока передачи (MTU) всех соединений на пути к месту назначения
  • Дейтаграммы могут быть фрагментированы во время маршрутизации
  • Дейтаграммы собираются заново только в пункте назначения
  1.  Только 1
  2.  2 и 3
  3.  Только 2
  4.  1 и 3
  5.  Только 3

Вопрос 9

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

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

  1.  Ни , ни не являются контекстно-свободными
  2.   и являются регулярными
  3.  Ни , ни не являются регулярными, но оба они не зависят от контекста
  4.   является контекстно-свободным, но не регулярным, и не является контекстно-свободным
  5.   регулярный, а контекстно-свободный, но не регулярный

Вопрос 10

Согласно стандарту IEEE, 32-разрядное число с плавающей запятой одинарной точности N определяется как

где S — знаковый бит, F — дробная мантисса, а E — смещенный показатель степени

Число с плавающей запятой хранится в формате S : E : F, где S, E и F хранятся в 1 бите, 8 битах и 23 битах соответственно

Каково десятичное значение числа с плавающей запятой C1E00000 (шестнадцатеричная система счисления)?

  1.  26
  2.  −26
  3.  −59
  4.  −28
  5.  −15