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

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

Вариант 3355431309.


Ваше имя*:


Вопрос 1

Сколько существует различных бинарных деревьев с 8 узлами?

  1.  128
  2.  256
  3.  64
  4.  248

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

Пусть структура данных поддерживает операцию `foo`, таким образом, что последовательность из n операций `foo` занимает времени в худшем случае. Каково амортизационное время операции `foo`?

  1.  
  2.  
  3.  
  4.  

Вопрос 4

Рассмотрим массив из n элементов. Какую временную сложность имеет алгоритм поиска максимальной суммы трех элементов в массиве?

  1.  
  2.  
  3.  
  4.  

Вопрос 5

Пусть и что из ниже перечисленного является верным?

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

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.  

Вопрос 7

Пусть G = (V, E) неориентированный граф, какие утверждения ниже являются верными?

  • I. Если G является деревом, то между двумя любыми вершинами G существует единственный уникальный путь.
  • II. Если G = (V, E) является связным, и E = V - 1, тогда G является деревом.
  • III. Удаление ребра из цикла не может сделать граф несвязным.
  1.  I, II, III
  2.  Только I, II
  3.  Только II
  4.  Только III

Вопрос 8

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

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

Вопрос 9

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

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

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

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

Вопрос 10

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

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