Data Structures and Algorithms Quiz

Що з наведеного нижче має найвищу часову складність?

• O(1)

• O(n log n)

• O(n)

• O(n^2)

Яка з наступних структур даних використовується в алгоритмі Дейкстри?

• Стек

• Черга

• Пріоритетна черга

• Купа

При використанні ефективної реалізації черги з пріоритетом, яку складність мають додавання елементу та видалення максимуму?

• а) O(1) та O(log n)

• б) O(log n) та O(log n)

• в) O(1) та O(n)

• г) O(log n) та O(1)

Яка структура даних слідує принципу "останнім прийшов - першим вийшов" (LIFO)?

• Stack

• Queue

• Heap

• Graph

Яка (які) з наступних операцій з ArrayList має складність O(1)?

• Отримання елемента за індексом

• Вставлення елемента в початок

• Видалення елемента з середини

• Отримання довжини

Яка структура даних зазвичай використовується для реалізації пріоритетної черги?

• Стек

• Черга

• Купа

• ArrayList

За який час можна найоптимальнішим чином відповісти на питання, чи є у відсортованому списку заданий елемент?

• O(1)

• O(log n)

• O(n)

• O(n^2)

Яка з наступних властивостей не є характерною для кістякового дерева (spanning tree)?

• Воно з'єднує всі вершини в графі

• Воно не містить циклів

• Це підграф вихідного графа

• Воно має охоплювати всі ребра вихідного графа

Яка з наступних операцій не підтримується стеком?

• Push

• Pop

• Peek (Pop + push)

• Remove

У алгоритмі A*, що оцінює евристична функція?

• а) Фактична вартість від початкової вершини до поточної вершини

• б) Відстань від поточної вершини до цільової вершини

• в) Мінімальна вартість від початкової вершини до цільової вершини, проходячи через поточну вершину

• г) Кількість вже досліджених вершин