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

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

Вариант 1860267753.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

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

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

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

Вопрос 4

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

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

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

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

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  

Вопрос 7

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

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

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

Вопрос 8

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

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

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