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

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

Вариант 1077026443.


Ваше имя*:


Вопрос 1

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

  1.  
  2.  
  3.  
  4.   —

Вопрос 2

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

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

Вопрос 3

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

[svg]

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

Вопрос 4

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

  1.   —
  2.  
  3.  
  4.  

Вопрос 5

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

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

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

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

Вопрос 6

Какая временная сложность выполнения данного кода?

for (i = n; i > 0; i/= 2){
    for (int j = 1; j < n; j * = 2){
        for (int k = 0; k < n; k + = 2){
        sum + = (i + j * k);
        }
    }
}
  1.  
  2.   —
  3.  
  4.  

Вопрос 7

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

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

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

Вопрос 8

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

  1.   —
  2.  
  3.  
  4.  

Вопрос 9

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

  • I. Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.
  • II. DFS на ориентированном графе с n вершинами и, по крайней мере, n ребрами гарантированно найдет хотя бы одно обратное ребро.

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

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

Вопрос 10

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

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