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

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

Вариант 2551699051.


Ваше имя*:


Вопрос 1

Для какой из изображенных ниже куч на минимум будут получены элементы массива в порядке возрастания, если для кучи применяется обход preorder traversal?

  1.  [svg]
  2.  [svg]
  3.  [svg]
  4.  [svg]

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

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

  1.  
  2.  
  3.  
  4.   

Вопрос 5

Хэш функция с линейным зондированием используется для вставки ключей 37, 38, 72, 68, 98, 11, 74 в хэш-таблицу с индексом (0-6). Какой индекс соответствует ключу 74?

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

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  

Вопрос 7

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

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

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

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

Вопрос 8

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

[svg]

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

Вопрос 9

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

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

Вопрос 10

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

  1.  
  2.  
  3.  
  4.