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

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

Вариант 83644711.


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


Вопрос 1

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

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

Вопрос 2

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

[svg]

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

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

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

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

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

Вопрос 3

Предположим, что целевой объект t — это целочисленное значение, хранящееся в некотором элементе целочисленного массива x, который отсортирован в неубывающем порядке, и рассмотрим следующую схему цикла для поиска t

  <initialization of h and k>
  while (x[h] != t)
  {
    P;
  }

Если initialization устанавливает инвариант , какое из следующих определений для P, взятое по отдельности, гарантирует, что цикл завершится с , предпологая, что t появляется в массиве?

  • if x[h] < t then h := h + 1
  • h := h + 1
  • k := k — 1
  1.  1 и 2
  2.  Только 1
  3.  Только 3
  4.  Только 2
  5.  1 и 3

Вопрос 4

Пусть N — множество всех натуральных чисел.

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

  • Совокупность всех функций от N до {0, 1}
  • Набор всех функций от {0, 1} до N
  • Наибольшее подмножество из N
  1.  1 и 3
  2.  1, 2, 3
  3.  Нет правильных ответов
  4.  1 и 2
  5.  2 и 3

Вопрос 5

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

Вопрос 6

Центральный процессор имеет арифметический модуль, который складывает байты, а затем устанавливает свои флаговые биты V, C и Z следующим образом

Бит V устанавливается, если происходит арифметическое переполнение (в арифметике с двумя дополнениями)

Бит C устанавливается, если во время операции генерируется перенос из самого старшего бита

Бит Z устанавливается, если результат равен нулю

Каковы значения флагов битов V, C и Z после добавления 8-битных байтов 1100 1100 и 1000 1111 ?

  1.  V = 0 °C = 1 Z = 0
  2.  V = 1 °C = 1 Z = 1
  3.  V = 1 °C = 1 Z = 0
  4.  V = 0 °C = 0 Z = 0
  5.  V = 0 °C = 0 Z = 1

Вопрос 7

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

  • Нахождение минимального остовного дерева в неориентированном графе с целыми положительными весами ребер
  • Нахождение максимальной клики в неориентированном графе
  • Нахождение максимального потока от узла-источника к узлу-приемнику в ориентированном графе с целыми положительными значениями пропускной способности ребер
  1.  1 и 2
  2.  1, 2, 3
  3.  Только 1
  4.  Только 2
  5.  Только 3

Вопрос 8

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

  • Если задача(конечная) строка w, является ли w префиксом десятичного представления числа π?
  • При наличии программы и входных данных, является ли вывод программы десятичным представления числа π?
  • Если задана программа, которая принимает в качестве входных данных префикс десятичного представления числа π, всегда ли выходные данные программы одинаковы для каждого префикса?
  1.  Только 1
  2.  1 и 2
  3.  Только 3
  4.  1, 2, 3
  5.  Только 2

Вопрос 9

Предположим, что у некоторого программного продукта средняя наработка на отказ составляет 10 000 часов, а среднее время на ремонт — 20 часов.

Если продуктом пользуются 100 клиентов, какова его доступность?

  1.  100%
  2.  98%
  3.  99.8%
  4.  80%
  5.  90%

Вопрос 10

Выходные данные процедуры mystery зависят от используемого метода передачи параметров

  procedure mystery
    a : integer;
    b : integer;
    procedure enigma(x,y)
    begin
      y = y + b;
      x = b + x;
      b = x + b;
      a = y;
    end enigma;
  begin
    a = 2; b = 7;
    enigma(a,b);
    write(a); write(b);
  end mystery;

Предположим, что все параметры передаются по значению

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

  1.  a = 9 b = 14
  2.  a = 30 b = 30
  3.  a = 14 b = 16
  4.  a = 2 b = 7
  5.  a = 2 b = 9