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

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

Вариант 1296946887.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

Дан неориентированный граф G = (V, E) и положительное целое число K, имеет ли G K вершин, которые образуют полный подграф, и если да, то каково минимальное значение K?

  1.  4
  2.  3
  3.  2
  4.  Ничего и перечисленного

Вопрос 5

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

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

Вопрос 6

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

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

Запустим алгоритм Дейкстры, начиная с вершины S, чтобы найти кратчайший путь T, и рассмотрим следующие утверждения:

  • I. Алгоритм Дейкстры возвращает кратчайший путь с минимальным общим весом.
  • II. Алгоритм Дейкстры возвращает кратчайший путь с минимальным количеством ребер.

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

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