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

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

Вариант 123040971.


Ваше имя*:


Вопрос 1

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

[svg]

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

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

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

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

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

Вопрос 2

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

Вопрос 3

Хэш-таблицы могут способствовать эффективному решению всех проблем, описанных ниже КРОМЕ

  1.  Поиск в таблице символов: по заданному идентификатору программы найдите ее тип и адрес
  2.  Поиск по диапазону: по заданным значениям a и b найдите все записи, ключевое значение которых находится в диапазоне [a, b]
  3.  Поиск пересечений: При наличии двух наборов ключей найдите все значения ключей, общие для обоих наборов
  4.  Динамический словарь: Поддерживает операции вставки, удаления и поиска в словаре
  5.  Подсчет различных значений: При наличии набора из n ключей определите количество различных значений ключа

Вопрос 4

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

Input

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

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

Definition

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

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

Если для всех

Problem

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

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

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

Тогда

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

для и

для всех

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 5

Что из перечисленного не является свойством растровой графики (Bitmap graphics)?

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

Вопрос 6

Рассмотрим следующий псевдокод

  x := 1;
  i := 1;
  while (x <= 1000)
  begin
    x := 2^x;
    i := i + 1;
  end;

Каково значение i в конце псевдокода?

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

Вопрос 7

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

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

Вопрос 8

Шаблон проектирования Singleton используется, чтобы гарантировать, что может быть создан только один экземпляр класса

Что из приведенного ниже верно для этого шаблона проектирования?

  • Класс Singleton имеет статический фабричный метод для cоздания своего экземпляра
  • Класс Singleton может быть подклассом другого класса
  • У класса Singleton есть собственный конструктор
  1.  Только 1
  2.  Только 2
  3.  Только 3
  4.  1, 2, 3
  5.  1 и 3

Вопрос 9

Что из перечисленного ниже верно в отношении систем виртуальной памяти, использующих страницы?

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

Вопрос 10

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

[svg]

  1.  X
  2.  Q
  3.  V
  4.  W
  5.  Z