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

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

Вариант 188106499.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

Пусть дана последовательность n случайных чисел. Какая будет временная сложность для нахождения элемента, который встречается больше, чем n/2 раз (если такой элемент существует)?

  1.   —
  2.  
  3.  
  4.  

Вопрос 3

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

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

Вопрос 4

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

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


Вопрос 5

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

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

Вопрос 6

Пусть и что из ниже перечисленного является верным?

  1.   —
  2.  
  3.  
  4.  

Вопрос 7

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

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.   —

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

Рассмотрим следующее AVL-дерево: [svg]

Если в данное дерево требуется вставить элемент со значением 12, сколько поворотов необходимо сделать для балансировки дерева?

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