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

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

Вариант 47607562.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

Компания X поставила 5 компьютерных чипов, 1 из которых оказался бракованным, а компания Y поставила 4 компьютерных чипа, 2 из которых оказались бракованными

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

Если обнаружится, что выбранный чип бракованный, какова вероятность того, что чип был изготовлен компанией Y?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 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.  5
  2.  9
  3.  6
  4.  12
  5.  8

Вопрос 4

Что из перечисленного НЕ является разумным обоснованием выбора режима активного ожидания для асинхронного события?

  1.  Ожидается, что ожидание будет недолгим
  2.  Цикл ожидания занятости проще в программировании, чем обработчик прерываний
  3.  Программа выполняется в системе с разделением времени
  4.  Задача должна быть выполнена в сжатые сроки в режиме реального времени
  5.  Процессору не нужно выполнять никакой другой задачи

Вопрос 5

Для каждого неотрицательного целого числа n пусть  — максимально возможное число областей, на которые плоскость может быть разделена n прямыми линиями

Например, и

Тогда имеет порядок

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 7

Пусть k — целое число, большее 1. Какое из следующих значений соответствует порядку возрастания выражения в зависимости от n?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

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

  • Грамматика неоднозначна
  • Грамматика подходит для нисходящего анализа
  • Грамматика подходит для восходящего анализа
  1.  1, 2, 3
  2.  Только 2
  3.  Только 3
  4.  2 и 3
  5.  Только 1

Вопрос 9

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

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

Вопрос 10

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

  1.  только 1
  2.  2 и 3
  3.  только 3
  4.  1 и 2
  5.  1 и 3