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

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

Вариант 1268418068.


Ваше имя*:


Вопрос 1

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

  1.  
  2.  
  3.  
  4.  

Вопрос 2

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

Вопрос 3

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

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

Вопрос 4

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

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

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

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

Вопрос 5

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

  1.  
  2.   
  3.  
  4.  

Вопрос 6

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

  • Пусть n — это число элементов в массиве
  • В процессе сортировки массива происходит порядка уровней
  • На каждом уровне происходит порядка действий

Для какого алгоритма сортировки все утверждения являются верными?

  1.  Сортировка слиянием
  2.  Сортировка кучей
  3.  Сортировка выбором
  4.  Сортировка пузырьком

Вопрос 7

Пусть имеется два отсортированных списка размера K и L соответственно. Сколько потребуется сравнений элементов, для того чтобы получить отсортированный список размера K + L, состоящий из элементов этих списков?

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

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

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

Вопрос 10

Какое из представленных ниже регулярных выражений задает строки вида , где m, p, n больше либо равно 2.

  1.  
  2.  
  3.  
  4.