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

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

Вариант 3967319274.


Ваше имя*:


Вопрос 1

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

  1.  
  2.  
  3.  
  4.  

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

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

Вопрос 4

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

[svg]

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

Вопрос 5

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

  • I. Подсчет медианы из n элементов занимает времени для любого алгоритма, основанного на сравнении элементов.
  • II. Пусть T является минимальным остовным деревом для графа G. Тогда для любой пары вершин a и b кратчайший путь между ними в G является кратчайшим путем между ними в T.

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

  1.  I-False, II-TRUE
  2.  I-TRUE, II-TRUE
  3.  I-TRUE, II-False
  4.  I-False, II-False

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

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

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

Вопрос 10

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

  • I. Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.
  • II. DFS на ориентированном графе с n вершинами и, по крайней мере, n ребрами гарантированно найдет хотя бы одно обратное ребро.

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

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