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

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

Вариант 313707726.


Ваше имя*:


Вопрос 1

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

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

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

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

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

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

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  

Вопрос 5

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

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

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

Вопрос 6

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

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

Вопрос 7

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

[svg]

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

Вопрос 8

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

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

Пусть дана последовательность n случайных чисел. Какая будет временная сложность для нахождения элемента, который встречается больше, чем n/2 раз (если такой элемент существует)?

  1.  
  2.  
  3.  
  4.