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

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

Вариант 803603671.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

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

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

Вопрос 4

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

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

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

Пусть G = (V, E) неориентированный граф, какие утверждения ниже являются верными?

  • I. Если G является деревом, то между двумя любыми вершинами G существует единственный уникальный путь.
  • II. Если G = (V, E) является связным, и E = V - 1, тогда G является деревом.
  • III. Удаление ребра из цикла не может сделать граф несвязным.
  1.  Только III
  2.  Только I, II
  3.  I, II, III
  4.  Только II

Вопрос 7

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

  1.  
  2.   
  3.  
  4.  

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

Существует несколько способов определить порядок умножения матриц 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.  , , ,