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

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

Вариант 3256247138.


Ваше имя*:


Вопрос 1

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

  1.  
  2.  
  3.  
  4.  

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

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

Вопрос 5

Сколько раз происходит обращение ко всем вершинам в графе G(V, E) в процессе работы алгоритма поиска в глубину?

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

Вопрос 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

Алгоритм Беллмана-Форда решает задачу кратчайшего пути из вершины в случае, когда веса ребер могут быть отрицательными, какова временная сложность выполнения алгоритма Беллмана-Форда?

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

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.  

Вопрос 9

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

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

Вопрос 10

Чтобы выполнить поиск элемента в dynamic set, какой из следующих методов является асимптотически наиболее эффективным по времени в наихудшем случае для операции поиска?

  1.  Все вышеперечисленное.
  2.  Сохранять элемент в несортированном массиве и применять линейный поиск.
  3.  Сохранять элемент в хэш-таблице и использовать хэширование.
  4.  Сохранять элемент в отсортированном массиве и применять бинарный поиск.