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

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

Вариант 3810835440.


Ваше имя*:


Вопрос 1

Пусть M является целым числом, которое больше единицы. Какая асимптотика роста функции является верной?

  1.  
  2.  
  3.  
  4.  

Вопрос 2

Какие из следующих алгоритмов используют подход Разделяй и Властвуй?

  1.  Все выше перечисленные
  2.  Бинарный поиск и умножение Штрассена
  3.  Быстрая сортировка
  4.  Сортировка слиянием

Вопрос 3

Рассмотрим следующие выражения:

  • I.
  • II.

Какие утверждения верные, а какие нет?

  1.  I-TRUE, II-TRUE
  2.  I-False, II-False —
  3.  I-TRUE, II-False
  4.  I-False, II-TRUE

Вопрос 4

Для какой из изображенных ниже куч на минимум будут получены элементы массива в порядке возрастания, если для кучи применяется обход preorder traversal?

  1.  [svg]

  2.  [svg]
  3.  [svg]
  4.  [svg]

Вопрос 5

Какое из представленных ниже регулярных выражений задает строки вида , где m, p, n больше либо равно 2.

  1.   —
  2.  
  3.  
  4.  

Вопрос 6

Рассмотрим следующие утверждения (h(k) — хэш-функция):

  • I. если даже .
  • II. для любых .
  • III. для любых .
  1.  Только I —
  2.  I, II, III
  3.  Только II, III
  4.  Только I, II

Вопрос 7

Рассмотрим следующее рекуррентное соотношение: Какое из следующих утверждений является верным?

  1.  Данное соотношение подходит для случая 2 Master теоремы
  2.  Master теорема не может быть применена, поскольку не является константой —
  3.  Данное соотношение подходит для случая 3 Master теоремы
  4.  Данное соотношение подходит для случая 1 Master теоремы

Вопрос 8

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

  1.  
  2.   —
  3.  
  4.  

Вопрос 9

Хэш функция с линейным зондированием используется для вставки ключей 37, 38, 72, 68, 98, 11, 74 в хэш-таблицу с индексом (0-6). Какой индекс соответствует ключу 74?

  1.  2
  2.  4
  3.  1 —
  4.  3

Вопрос 10

Какая временная сложность выполнения данного кода?

for (i = n; i > 0; i/= 2){
    for (int j = 1; j < n; j * = 2){
        for (int k = 0; k < n; k + = 2){
        sum + = (i + j * k);
        }
    }
}
  1.  
  2.  
  3.  
  4.   —