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

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

Вариант 3018187262.


Ваше имя*:


Вопрос 1

Запустим алгоритм Дейкстры, начиная с вершины S, чтобы найти кратчайший путь T, и рассмотрим следующие утверждения:

  • I. Алгоритм Дейкстры возвращает кратчайший путь с минимальным общим весом.
  • II. Алгоритм Дейкстры возвращает кратчайший путь с минимальным количеством ребер.

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

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

Вопрос 4

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

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.  

Вопрос 5

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

  • I.
  • II.

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

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

Вопрос 6

Предположим, что символы a,b,c,d,e встречаются с частотами . Какие получатся коды Хаффмана для букв a,b,c соответственно?

  1.  1100, 1101, 111
  2.  1100, 10, 0
  3.  1101, 111, 1101
  4.  1101, 1100, 111

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

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

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.  

Вопрос 10

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

  1.  
  2.  
  3.  
  4.