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

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

Вариант 1161903930.


Ваше имя*:


Вопрос 1

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

  1.  
  2.  
  3.  
  4.  

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

  • I. Диграф — это граф, имеющий ровно 2 вершины.
  • II. Остовное дерево в графе всегда должно содержать как минимум ребер.
  • III. Алгоритм сортировки ребер для решения задачи коммивояжера всегда дает оптимальный результат.

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

  1.  Только II
  2.  I, II
  3.  I, III
  4.  II, III

Вопрос 4

Каково число подстрок любой длины, за исключением пустой строки, может быть получено из заданной строки длиной n?

  1.  
  2.  
  3.  
  4.  

Вопрос 5

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

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

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

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  

Вопрос 7

Чтобы выполнить поиск элемента в dynamic set, какой из следующих методов является асимптотически наиболее эффективным по времени в наихудшем случае для операции поиска?

  1.  Сохранять элемент в отсортированном массиве и применять бинарный поиск.
  2.  Все вышеперечисленное.
  3.  Сохранять элемент в несортированном массиве и применять линейный поиск.
  4.  Сохранять элемент в хэш-таблице и использовать хэширование.

Вопрос 8

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

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

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