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

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

Вариант 1698787873.


Ваше имя*:


Вопрос 1

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

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

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

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

Вопрос 2

Какой из следующих алгоритмов имеет время выполнения O(n²) в наихудшем случае, но O(nlog(n)) в среднем?

  1.  Турнирная (Tournament) сортировка
  2.  Сортировка слиянием
  3.  Пирамидальная сортировка (сортировка кучей)
  4.  Быстрая сортировка
  5.  Пузырьковая сортировка

Вопрос 3

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

  1.  Приоритет оператора
  2.  Преобразование типов
  3.  Длина идентификатора
  4.  Совместимость типов
  5.  Максимальный уровень вложенности

Вопрос 4

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

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

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

Вопрос 6

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

  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.  12
  3.  8
  4.  6
  5.  9

Вопрос 7

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

  • Инкапсуляция
  • Наследование
  • Рекурсия
  1.  Только 1
  2.  2 и 3
  3.  1 и 2
  4.  Только 2
  5.  1, 2, 3

Вопрос 8

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

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

Вопрос 9

Рассмотрите совокупность всех неориентированных графов с 10 вершинами и 6 ребрами

Пусть M и m, соответственно, являются максимальным и минимальным количеством связанных компонентов в любом графе в коллекции

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

  1.  M = 7, m = 4
  2.  M = 6, m = 4
  3.  M = 6, m = 3
  4.  M = 10, m = 1
  5.  M = 10, m = 10

Вопрос 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.