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

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

Вариант 1331915732.


Ваше имя*:


Вопрос 1

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

  • I. Подсчет медианы из n элементов занимает времени для любого алгоритма, основанного на сравнении элементов.
  • II. Пусть T является минимальным остовным деревом для графа G. Тогда для любой пары вершин a и b кратчайший путь между ними в G является кратчайшим путем между ними в T.

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

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

Вопрос 2

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

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.  

Вопрос 3

Рассмотрим следующий код:

y = y + z
for i in range(1, n + 1):
    k = k + 2;
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x = x + 1;

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

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

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

Вопрос 5

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

[svg]

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

Вопрос 6

Пусть M является целым числом, которое больше единицы. Какая асимптотика роста функции является верной?

  1.  
  2.  
  3.  
  4.  

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

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