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

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

Вариант 3817707153.


Ваше имя*:


Вопрос 1

Какова временная сложность выполнения алгоритма Беллмана-Форда на K-регулярном графе ()?

  1.  
  2.  
  3.  
  4.  

Вопрос 2

Сколько существует различных бинарных деревьев с 8 узлами?

  1.  256
  2.  64
  3.  248
  4.  128

Вопрос 3

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

  • 1)
  • 2)
  • 3),  — константа
  • 4)
  1.  i, ii, iii
  2.  ii, iii
  3.  i, ii, iv
  4.  i, ii

Вопрос 4

Сколько вершин имеет дерево с 57 ребрами?

  1.  56
  2.  58
  3.  57
  4.  2**6 — 4

Вопрос 5

Алгоритм Беллмана-Форда решает задачу кратчайшего пути из вершины в случае, когда веса ребер могут быть отрицательными, какова временная сложность выполнения алгоритма Беллмана-Форда?

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

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

Вопрос 7

Сколько остовных деревьев имеет данный граф (все ребра имеют одинаковый вес)?

[svg]

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

Вопрос 8

Рассмотрим массив из n элементов. Какую временную сложность имеет алгоритм поиска максимальной суммы трех элементов в массиве?

  1.  
  2.  
  3.  
  4.  

Вопрос 9

Пусть структура данных поддерживает операцию `foo`, таким образом, что последовательность из n операций `foo` занимает времени в худшем случае. Каково амортизационное время операции `foo`?

  1.  
  2.  
  3.  
  4.  

Вопрос 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.