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

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

Вариант 1065745613.


Прошло 00:00:00.
Ваше имя*:


Вопрос 1

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

  1.  
  2.  
  3.   
  4.  

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

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

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

Вопрос 5

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

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

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

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

Вопрос 6

Сколько вершин имеет дерево с 57 ребрами?

  1.  57
  2.  58
  3.  56
  4.  2**6 — 4

Вопрос 7

Сколько остовных деревьев имеет данный граф (все ребра имеют одинаковый вес)?

[svg]

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

Вопрос 8

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

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

Вопрос 9

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

  • I.
  • II.

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

  1.  I-False, II-False
  2.  I-TRUE, II-False
  3.  I-False, II-TRUE
  4.  I-TRUE, II-TRUE

Вопрос 10

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

  1.  
  2.  
  3.  
  4.