Алгоритмы и структуры данных поиска

Упражнение 1:

Номер 1

Какова типичная оценка по времени для наивного алгоритма сортировки?

Ответ:

(1) O(N * log N)

(2) O(N²)

(3) O(N)

(4) O(N³)

Номер 2

Какова оценка по времени для продвинутых алгоритмов сортировки (в худшем или среднем случае)?

Ответ:

(1) O(N²)

(2) O(N * log N)

(3) O(N)

(4) O(log N)

Номер 3

Какие бывают оценки по памяти для алгоритмов сортировки? Выберите наиболее подходящий вариант

Ответ:

(1) O(N), O(N²), O(N³)

(2) O(1), O(log N), O(N)

(3) всегда O(1)

Упражнение 2:

Номер 1

Что означает стабильность алгоритма сортировки?

Ответ:

(1) процент ошибок при сортировке меньше

1

(2) если при работе алгоритма относительный порядок пар с равными ключами не меняется

(3) время работы алгоритма относительно стабильно при различной величине входных данных

Номер 2

Всегда ли свойство стабильности является важным для алгоритма сортировки?

Ответ:

(1) да, так как оно напрямую влияет на качетсво сортировки

(2) нет

(3) да, так как от стабильности зависит скорость работы алгоритма

Номер 3

В каких случаях стабильность алгоритма сортировки важна?

Ответ:

(1) когда имеется большой разброс величнины входных данных

(2) когда алгоритм сортировки применяется как часть чего-то большего, например для алгоритма сортировки подсчетом

(3) когда точность сортировки должна быть максимально возможной и не должно быть нарушений порядка элементов множества

Упражнение 3:

Номер 1

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

Ответ:

(1) для нового неупорядоченного элемента в правой части множества итеративно выбирается место среди уже упорядоченных ключей

(2) итеративно выбирается место среди оставшихся неупорядоченных ключей, найденный минимум или максимум вынимается из текущего множества в ответ

(3) исходная пследовательность A делится на две части A₁ и A₂, которые рекурсивно сортируются

Номер 2

Какая сложность у алгоритма сортировки выбором?

Ответ:

(1) O(N * log N)

(2) Θ(N²)

(3) Θ(N³)

Номер 3

Какая сложность у алгоритма сортировки вставками?

Ответ:

(1) O(N * log N)

(2) Θ(N²)

(3) Θ(N)

Номер 4

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

Ответ:

(1) для нового неупорядоченного элемента в правой части множества итеративно выбирается место среди уже упорядоченных ключей

(2) итеративно выбирается место среди оставшихся неупорядоченных ключей, найденный минимум или максимум вынимается из текущего множества в ответ

(3) исходная пследовательность A делится на две части A₁ и A₂, которые рекурсивно сортируются

Упражнение 4:

Номер 1

Какая сложность у процедуры слияния для алгоритма сортировки слияием (MergeSort) для массива длины L?

Ответ:

(1) O(L²)

(2) O(L₁ + L₂), L₁ и L₂ - длины двух частей массива

(3) O(L₁² + L₂²), L₁ и L₂ - длины двух частей массива

(4) O(L₁² * L₂²), L₁ и L₂ - длины двух частей массива

Номер 2

Для алгоритма сортировки слиянием merge-sort при каком количестве элементов в последовательности рекурсивное деление должно прерываться, в стандартном виде?

Ответ:

(1) 2

(2) 1

(3) 3

Номер 3

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

Ответ:

(1) для нового неупорядоченного элемента в правой части множества итеративно выбирается место среди уже упорядоченных ключей

(2) итеративно выбирается место среди оставшихся неупорядоченных ключей, найденный минимум или максимум вынимается из текущего множества в ответ

(3) исходная пследовательность A делится на две одинаковые по размеру части A₁ и A₂, которые рекурсивно сортируются

Упражнение 5:

Номер 1

При использовании подхода Bottom-up для алгоритма сортировки слиянием, на блоки какого размера разбивается массив размера n на k-ом шаге?

Ответ:

(1) n/2^k

(2) 2^k

(3) n/k

(4) k

Номер 2

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

Ответ:

(1) O(N)

(2) O(N * log N)

(3) O(N²)

(4) O(log N)

Номер 3

Сколько требуется дополнительной памяти для стандартного алгоритма сортировки слиянием для массива длины N?

Ответ:

(1) O(log N)

(2) O(N)

(3) O(N²)

Упражнение 6:

Номер 1

Как описывается алгоритм быстрой сортировки (quick-sort)?

Ответ:

(1) для нового неупорядоченного элемента в правой части множества итеративно выбирается место среди уже упорядоченных ключей

(2) массив делится рекурсивно на две части, элементы массива переставляются так, чтобы в левой части оказались элементы, которые не больше чем элементы в правой части

(3) итеративно выбирается место среди оставшихся неупорядоченных ключей, найденный минимум или максимум вынимается из текущего множества в ответ

(4) исходная пследовательность A делится на две одинаковые по размеру части A₁ и A₂, которые рекурсивно сортируются

Номер 2

По какому признаку отрезок разбивается на две части в алгоритме быстрой сортировки (quick-sort)?

Ответ:

(1) разбивается поровну

(2) в левую часть помещаются ключи <=λ, в правую часть помещаются ключи >=λ, λ выбирается определенным образом(часто случайно)

(3) в левую часть помещаются ключи, делящиеся на цело на λ, в правую часть помещаются ключи, не делящиеся на цело на λ

(4) в левую часть помещаются ключи <=λ, в правую часть помещаются ключи >=λ, λ является медианой отрезка на каждой итерации

Номер 3

Сколько дополнительной памяти требуется для работы алгоритма quick-sort?

Ответ:

(1) O(N)

(2) алгоритм не использует дополнительную память

(3) O(N²)

Номер 4

Для алгоритма quick-sort при способе разбиения массива на две части, называемым Lomuto Partition, что происходит дальше в такой ситуации: первая просмотренная часть A содержит элементы <= λ, вторая просмотренная часть B содержит элементы >= λ, далее справа находится непросмотренная часть с элементом x вначале, если x >= λ?

Ответ:

(1) x меняется местами с первым элементом B

(2) граница части B смещается вправо на один элемент, алгоритм переходит к следующему элементу

(3) x меняется местами с последним элементом B

Номер 5

Для алгоритма quick-sort при способе разбиения массива на две части, называемым Lomuto Partition, что происходит дальше в такой ситуации: первая просмотренная часть A содержит элементы <= λ, вторая просмотренная часть B содержит элементы >= λ, далее справа находится непросмотренная часть с элементом x вначале, если x < λ?

Ответ:

(1) граница части B смещается вправо на один элемент, алгоритм переходит к следующему элементу

(2) x меняется местами с первым элементом части B

(3) x меняется местами с последним элементом части B

(4) x меняется местами с последним элементом части A

Упражнение 7:

Номер 1

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

Ответ:

(1) элиминация хвостовой рекурсии

(2) рекурсивный вызов для меньшего подотрезка делать последним

(3) в качестве разделителя использовать медиану из трех элементов последовательности: левой границы, правой границы и середины

(4) если глубина рекурсии превышает определенное критичное значение, то использовать другой алгоритм

Номер 2

Выберите утверждения, характерные для алгоритма быстрой сортировки (quick-sort).

Ответ:

(1) на каждой итерации массив делится на две части: больше и меньше разделителя λ

(2) алгоритм использует top-down подход

(3) на каждой итерации массив делится на две равные части

(4) алгоритм использует bottom-up подход

(5) сложность алгоритма O(N * log N)

Номер 3

Какой элемент эффективнее использовать в качестве опорного (λ) для алгоритма быстрой сортировки? Выберите один или несколько вариантов

Ответ:

(1) первый элемент последовательности

(2) медиану из трех элементов последовательности: левой границы, правой границы и середины

(3) последний элемент последовательности

(4) элемент, стоящий на случайном месте

(5) средний элемент в последовательности

Упражнение 8:

Номер 1

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

Ответ:

(1) O(N²)

(2) O(N * log N)

(3) непределенное

(4) O(N)

(5) O(log N)

Номер 2

Пусть на вход алгоритма быстрой сортировки поступает N различных ключей. Тогда каким будет матожидание глубины рекурсии?

Ответ:

(1) O(N * log N)

(2) O(N²)

(3) O(N)

(4) O(log N)

Номер 3

Рассмотрим вариацию алгоритма Quick-Sort, детерминированно выбирающего в качестве разделителя первый элемент текущего отрезка. Пусть на вход алгоритму поступает случайная последовательность, в которой все ключи различны, а все их перестановки равновероятны. Тогда каким будет матожидание времени его работы?

Ответ:

(1) O(N²)

(2) O(N)

(3) O(N * log N)

(4) O(log N)

Номер 4

Рассмотрим вариацию алгоритма Quick-Sort, детерминированно выбирающего в качестве разделителя первый элемент текущего отрезка. Пусть на вход алгоритму поступает случайная последовательность, в которой все ключи различны, а все их перестановки равновероятны. Тогда каким будет матожидание глубины рекурсии?

Ответ:

(1) O(N²)

(2) O(N)

(3) O(N * log N)

(4) O(log N)

Номер 5

Какой тип случайности используется для алгоритма Quick-sort, когда какая-либо перестановка подается на вход?

Ответ:

(1) внутренняя

(2) внутренняя и внешняя

(3) внешняя

(4) ни та ни другая

Упражнение 9:

Номер 1

Какие из перечисленных высказываний относятся к внутреннему типу случайности (internal randomness)?

Ответ:

(1) алгоритм сам генерирует значения, использует их для принятия решений

(2) на вход приходят случайные данные. Тогда на множестве входов есть некоторое распределение

(3) анализ происходит по внутреннему датчику случайности

(4) сложность изучается в среднем относительно меры на множестве входов

Номер 2

Какие из перечисленных высказываний относятся к внешнему типу случайности (external randomness)?

Ответ:

(1) алгоритм сам генерирует значения, использует их для принятия решений

(2) на вход приходят случайные данные. Тогда на множестве входов есть некоторое распределение

(3) анализ происходит по внутреннему датчику случайности

(4) сложность изучается в среднем относительно меры на множестве входов

Номер 3

Какие из перечисленных особенностей относятся к внешнему типу случайности (external randomness)?

Ответ:

(1) на некотором входе алгоритм может плохо работать

(2) входные данные не являются абсолютно случайными

(3) нельзя точно определить рапределение

(4) отдельные запуски могут работать долго, но в среднем время работы может быть ограничено функцией

Номер 4

Какие из перечисленных особенностей относятся к внутреннему типу случайности (internal randomness)?

Ответ:

(1) на некотором входе алгоритм может плохо работать

(2) входные данные не являются абсолютно случайными

(3) нельзя точно определить рапределение

(4) отдельные запуски могут работать долго, но в среднем время работы может быть ограничено функцией

Номер 5

Что можно сделать для алгоритма Quick-sort, чтобы дерево рекурсии было всегда сбалансированным?

Ответ:

(1) заменить рекурсию на цикл

(2) выбирать правильный разделитель (pivot)

(3) элиминировать, то есть уменьшить число рекурсий в рекурсивной функии

(4) увеличить количество рекурсивных вызовов для функции

Упражнение 10:

Номер 1

Отметьте высказывания, характерные для алгоритма слияния, работающего с диском

Ответ:

(1) входной массив считывается блоками одной длины M (в байтах)

(2) все блоки входного массива считываются в оперативную память одновременно и каждый блок сортируется с помощью merge-sort, затем происходит слияние по одному блоку

(3) при слиянии данные считываются параллельно в двух местах, параллельно вычисляется минимум

(4) последовательное чтение с диска работает эффективнее, чем случайное, поэтому Merge-sort хорошо подходит для работы с диском

(5) алгоритм сортировки слиянием эффективен при работе с данными на диске

(6) оперативная память экономится, чтобы считываемые данные не были равны размеру входа

Номер 2

Отметьте утверждения, характерные для алгоритма сортировки слиянием (Merge-sort), работающего с памятью на диске

Ответ:

(1) область сортировки разбивается на части размера M, где M - размер оперативной памяти

(2) запись на диск происходит поэлементно, то есть блоками минимального размера

(3) блоки сливаются не парами, а на большее число потоков, чтобы умеьшить высоту дерева рекурсии

(4) считываемые в оперативную память блоки нужно брать как можно меньшего размера, лучше поэлементно

Номер 3

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

Ответ:

(1) операцию присваивания заменить на операцию обмена

(2) при разделении входной последовательности A на две части A₁, A₂, в качечстве временной памяти для сортировки A₁ использовать участок A₂

(3) после сортировки одной из половин массива A, можно использовать ее как временную память для сортировки второй половины

(4) после сортировки одной из половин массива A, вторую половину снова разделить на две части и использовать одну часть как память для второй. И так далее

Упражнение 11:

Номер 1

Для системы кодирования по Хаффману, что означает безпрефиксный код?

Ответ:

(1) любой из кодов символа алфавита является префиксом для любого другого символа

(2) любой из кодов символа алфавита не является префиксом для любого другого символа

(3) любой из кодов символа алфавита не состоит из кода другого символа

Номер 2

Каким будет оптимальный порядок бинарного слияния всех отрезков L₁,...,L_n различной длины в алгоритме сортировки слиянием?

Ответ:

(1) сначала нужно сливать отрезки наименьшей длины, затем прибавлять к полученному отрезку следующий по длине отрезок и так далее

(2) использовать n-ичное дерево Хаффмана для определения порядка слияния для каждого L_i, n зависит от количества отрезков и разброса их длин

(3) использовать бинарное дерево кодирования Хаффмана для определения порядка слияния для каждого L_i, на нижнем уровне дерева будут находиться отрезки наименьшей длины, на верхнем уровне - отрезки наибольшей длины

(4) использовать бинарное дерево кодирования Хаффмана для определения порядка слияния для каждого L_i, на верхнем уровне дерева будут находиться отрезки наименьшей длины, на нижнем - уровне отрезки наибольшей длины

Номер 3

Где будет находиться наиболее часто встречающийся символ в дереве кодирования Хаффмана?

Ответ:

(1) на нижнем уровне дерева

(2) на вернем уровне дерева

(3) может находиться в любом месте

(4) в самой крайней левой вершине

(5) в самой крайней правой вершине

Упражнение 12:

Номер 1

В каком месте дереве Хаффмана будут находиться два символа с наименьшими частотами?

Ответ:

(1) в соседних листьях на верхнем уровне

(2) в соседних листьях на нижнем уровне

(3) на разных уровнях дерева

Номер 2

Какую сумму нужно оптимизировать в задаче оптимизации порядка бинарного слияния всех отрезков L₁,...,L_n различной длины? Если p_i - глубина i-го листа в дереве слияния

Ответ:

(1) Φ = Σ l_i / p_i

(2) Φ = Σ l_i p_i

(3) Φ = Σ l_i + p_i

Номер 3

Какая теоретико - информационная оценка на число сравнений при слиянии двух списков длины N и M, если h <= M?

Ответ:

(1) N * log (M/N + 1)

(2) N * log (M*N + 1)

(3) N * log (N/M + 1)

(4) log (N/M + 1)

Номер 4

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

Ответ:

(1) это невозможно

(2) просматривая список слева направо, удваивать текущее значение поиска всякий раз, когда текущее значение больше чем то, которое ищем. Затем применить бинарный поиск к этой области

(3) применить бинарный поиск сначала к левой половине отрезка, затем к правой

Алгоритмы и структуры данных поиска - тест 3