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

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

Вариант 4148053089.


Ваше имя*:


Вопрос 1

Предположим, что P(x, y) означает «x является родителем y», а M(x) означает «x — мужчина»

Если F(v, w) равно , каково значение выражения F(v, w)?

  1.  v является племянником w
  2.  v является дедом w
  3.  v является двоюродным братом w
  4.  v является братом w
  5.  v является дядей w

Вопрос 2

Для следующего кода смещение каждой условной ветви в коде указано на графике потока управления справа

Например, логическое выражение if_condition принимает значение true в половине случаев выполнения этого выражения

[svg]

  do
  {
   U;
   if (if_condition)
   {
     V;
     if (break_condition)
       break;
   }
   else
     W;
   X;
   } while (loop_condition);
   Y;

Какое ожидаемое количество раз выполняется U?

  1.  1.5
  2.  2
  3.  1
  4.  0.5
  5.  Больше 10

Вопрос 3

Некоторый рандомизированный алгоритм 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-м выполнении , где являются взаимно независимыми

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

Ниже приведен граф приоритетов (precedence graph) для набора задач, которые должны быть выполнены в системе параллельных вычислений S

[svg]

Эффективность определяется как соотношение между ускорением и количеством процессоров

(Ускорение определяется как отношение времени, затраченного на выполнение набора задач на одном процессоре, к времени, затраченному на выполнение того же набора задач на параллельном процессоре)

Система S имеет четыре процессора (CPU)

Если каждая из задач выполняется за одинаковое время, то какова эффективность этой системы S?

  1.  100%
  2.  %
  3.  125%
  4.  25%
  5.  50%

Вопрос 5

Некоторая конвейерная 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.  7
  3.  8
  4.  9
  5.  6

Вопрос 6

Логическая схема имеет три входных бита: где  — младший бит, а  — старший бит

Выход схемы равен 1, если на ее входе указано любое из трехбитовых чисел 1, 4, 5 или 6; в противном случае выход схемы равен 0

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 7

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

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

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

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

Вопрос 8

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

  1.  Длина сетей, подключенных с помощью Ethernets, ограничена несколькими сотнями метров
  2.  Ethernets-сети используют коммутацию каналов для отправки сообщений
  3.  В Ethernet-сетях используются шины с несколькими ведущими устройствами
  4.  Пакеты, отправляемые по Ethernet-сетям, ограничены по размеру
  5.  Протоколы Ethernet используют метод обнаружения коллизий для обеспечения правильной передачи сообщений

Вопрос 9

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

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

  • Полный граф с 12 вершинами
  • Полный граф с 13 вершинами
  • Дерево с 13 вершинами
  1.  1 и 3
  2.  Только 3
  3.  Только 1
  4.  Только 2
  5.  1 и 2

Вопрос 10

Некоторый рандомизированный алгоритм 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?

  1.  
  2.  
  3.  
  4.  
  5.