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

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

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

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

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

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

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

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

Сколько вершин имеет дерево с 57 ребрами?

Пусть M является целым числом, которое больше единицы. Какая асимптотика роста функции является верной?

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

Какая временная сложность выполнения данного кода?

for (i = n; i > 0; i/= 2){
    for (int j = 1; j < n; j * = 2){
        for (int k = 0; k < n; k + = 2){
        sum + = (i + j * k);
        }
    }
}

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