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

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

• 1)

• 2)

• 3),  — константа

• 4)

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

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

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

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

Рассмотрим следующие утверждения (h(k) — хэш-функция):

• I. если даже .

• II. для любых .

• III. для любых .

Хэш функция с линейным зондированием используется для вставки ключей 37, 38, 72, 68, 98, 11, 74 в хэш-таблицу с индексом (0-6). Какой индекс соответствует ключу 74?

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

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

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

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

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