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

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

Вариант 197044606.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

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

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

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

  • Пусть n — это число элементов в массиве
  • В процессе сортировки массива происходит порядка уровней
  • На каждом уровне происходит порядка действий

Для какого алгоритма сортировки все утверждения являются верными?

  1.  Сортировка кучей
  2.  Сортировка пузырьком
  3.  Сортировка слиянием
  4.  Сортировка выбором

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

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

Вопрос 9

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

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.  

Вопрос 10

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

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