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

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

Вариант 202385667.


Ваше имя*:


Вопрос 1

Предположим, что символы a,b,c,d,e встречаются с частотами . Какие получатся коды Хаффмана для букв a,b,c соответственно?

  1.  1100, 10, 0
  2.  1101, 1100, 111
  3.  1100, 1101, 111
  4.  1101, 111, 1101

Вопрос 2

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

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

Вопрос 3

Рассмотрим следующие утверждения об алгоритме обхода графа в глубину:

  • I. Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.
  • II. DFS на ориентированном графе с n вершинами и, по крайней мере, n ребрами гарантированно найдет хотя бы одно обратное ребро.

Какие из данных утверждений верны?

  1.  Ни одно
  2.  Оба
  3.  Только II
  4.  Только I

Вопрос 4

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

  1.  
  2.   
  3.  
  4.  

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

y = y + z
for i in range(1, n + 1):
    k = k + 2;
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x = x + 1;

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

  1.  
  2.  
  3.  
  4.  

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

Существует несколько способов определить порядок умножения матриц A, B, C, D: (A(BC)D), A(B(CD)), (AB)(CD), ((AB)C)D), A((BC)D)

Эффективность умножения зависит от числа скалярных произведений, для (A(BC))D получится:

Для (A(B(CD))):

Какие размерности у матриц A, B, C, D соответственно?

  1.  , , ,
  2.  , , ,
  3.  , , ,
  4.  , , ,

Вопрос 10

Сколько раз происходит обращение ко всем вершинам в графе G(V, E) в процессе работы алгоритма поиска в глубину?

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