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

1

2

3

4

Тест по Computer Science, подготовил Участник:Akazikov

Вариант 3562820387.

Ваше имя*:

Вопрос 1

Рассмотрите следующие два языка

Что из нижеследующего верно в отношении и ?

является контекстно-свободным, но не регулярным, и не является контекстно-свободным
регулярный, а контекстно-свободный, но не регулярный
Ни , ни не являются контекстно-свободными
и являются регулярными
Ни , ни не являются регулярными, но оба они не зависят от контекста

Вопрос 2

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

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

Вопрос 3

Массив A содержит 256 элементов по 4 байта каждый. Его первый элемент хранится по физическому адресу 4096

Массив B содержит 512 элементов по 4 байта каждый. Его первый элемент хранится по физическому адресу 8192

Предположим, что только массивы A и B могут быть кэшированы в изначально пустом, физически адресованном, физически помеченном, напрямую отображаемом кэше объемом 2 Кб с размером блока 8 байт

Затем выполняется следующий цикл

  for (i = 0; i < 256; i++)
    A[i] = A[i] + B[2*i];

Сколько байт будет записано в память во время выполнения цикла, если в кэше действует политика сквозной записи?

Вопрос 4

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

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

Вопрос 5

Сортировка слиянием выполняется путем разделения списка из n чисел пополам, рекурсивной сортировки каждой половины и объединения двух половин

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

Односвязный список
Двусвязный список
Массив

Вопрос 6

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

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

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

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

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

Вопрос 7

Выходные данные процедуры 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;