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

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

Вариант 3245820098.


Ваше имя*:


Вопрос 1

Пусть T(n) определяется как и для всех целых чисел

Какое из следующих утверждений представляет порядок роста T(n) как функции n?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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

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

Вопрос 3

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

Например, и

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

Выходные данные процедуры 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 = 2 b = 9
  3.  a = 30 b = 30
  4.  a = 2 b = 7
  5.  a = 14 b = 16

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

Что из приведенного ниже представляет собой обратный (post-order) обход T?

[svg]

  1.  P Q U W X V Y Z
  2.  X Z U W Y Q V P
  3.  U Q X W P V Z Y
  4.  U X W Q Z Y V P
  5.  U X Z Q W Y V P

Вопрос 10

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

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

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