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

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

Номер 1

Для направленного леса, в операции addEdge(x, y) при каких условиях можно добавлять ребро из x в y?

Ответ:

(1) если x - корень поддерева, если ребро не приводит к возникновению цикла

(2) если y - корень поддерева, если ребро не приводит к возникновению цикла

(3) если y - не корень поддерева, ребро может приводить к возникновению цикла

(4) если x - не корень поддерева, ребро может приводить к возникновению цикла

Номер 2

В чем заключается задача RMQ для массива чисел?

Ответ:

(1) для пары индексов i, j вывести минимум на отрезке [i, j] для массива, скорость не важна

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

(3) для пары индексов i, j вывести количество ключей, попавших в отрезок [i, j]

(4) для пары индексов i, j вывести ключи, попавшие в отрезок [i, j]

(5) для пары индексов i, j вывести сумму значений, попавших в отрезок [i, j]

Номер 3

В чем заключается задача LCA для заданного дерева?

Ответ:

(1) для пары индексов вершин i, j вывести количество ключей, попавших в отрезок [i, j]

(2) для пары индексов вершин i, j вывести значения, попавшие в отрезок [i, j]

(3) для пары индексов вершин i, j вывести всех общих предков

(4) для пары индексов вершин i, j вывести наименьшего общего предка

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

Номер 1

Какую структуру данных нужно использовать, чтобы свести задачу RMQ к LCA?

Ответ:

(1) кучу

(2) декартово дерево

(3) дерево поиска

(4) B-дерево

Номер 2

Для декартова дерева с вершинами (key = N, prior = a_N), если k = lca(i, j), то чем будет являться вершина a_k?

Ответ:

(1) минимум на отрезке [i, j]

(2) любая вершина из отрезка [i, j]

(3) первая вершина из отрезка [i, j]

(4) средняя вершина из отрезка [i, j]

(5) вершина с медианой по значению из отрезка [i, j]

Номер 3

∀ k'∈[i, j], если вершина a_k - минимум на отрезке, то какое неравенство выполняется?

Ответ:

(1) a_k' ≤ a_k

(2) a_k' ≥ a_k

(3) ∃ a_k' < a_k

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

Номер 1

В какой позиции достигается минимум на отрезке [i, j] в последовательности A (декартово дерево с индексами i = 1,...,n)?

Ответ:

(1) k = min(i..j)

(2) k = (j - i)/2

(3) k = lca(i, j)

(4) k = lca(A)

Номер 2

За какое время строится декартово дерево для набора {(1, a₁),...,(n, a_n)}

Ответ:

(1) O(log N)

(2) O(n)

(3) O(N * log N)

(4) O(N²)

Номер 3

Что из перечисленного ниже является задачей offline RMQ??

Ответ:

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

(2) дерево, у которого заранее известны все запросы. То есть дерево T с комплектом пар вершин (x₁, y₁),...,(x_n, y_n), для каждой пары известен z_i = lca(x_i, y_i)

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

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

Номер 1

Какой способ обхода дерева используется для предобработки в задаче offline LCA?

Ответ:

(1) In-order обход

(2) Post-order обход

(3) Pre-order обход

Номер 2

Какая структура данных используется дополнительно в предобработке для offline LCA?

Ответ:

(1) куча

(2) красно-черное дерево

(3) система непересекающихся множеств

(4) хэш-таблица

(5) B-дерево

Номер 3

Какая сложность у алгоритма предобработки offline LCA?

Ответ:

(1) O(log N)

(2) O(N)

(3) O(N * log N)

(4) O(N²)

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

Номер 1

Какие операции из структуры disjoin set union используются в предобработке для задачи offline LCA?

Ответ:

(1) Unite

(2) Create

(3) Remove

(4) Get-min

Номер 2

Отметьте верные свойства функции LCA

Ответ:

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

(2) симметричность, то есть lca(u, v) = lca(v, u)

(3) если u является потомком v или совпадает с ней, то lca(u,v) = v

Номер 3

Как можно ускорить вычисление задачи RMQ online?

Ответ:

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

(2) предварительно построить полную таблицу минимумов для всех возможных границ i, j отрезков

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

(4) предварительно построить таблицу минимумов отрезков [i, j] с номерами j, равными степени 2

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

Номер 1

Как происходит оптимизация в алгоритме поиска LCA для дерева T?

Ответ:

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

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

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

Номер 2

Какая вершина называется наименьшим общим предком для вершин u, v?

Ответ:

(1) любая вершина, находящаяся на пересечении путей от вершин u и v вверх по дереву до корня

(2) первая, максимально удаленная от корня точка пересечения путей от вершин u и v вверх по дереву до корня

(3) минимально удаленная от корня точка пересечения путей от вершин u и v вверх по дереву до корня

(4) наименьшая по значению ключа из вершин u и v

Номер 3

Чему равна длина Эйлерова обхода дерева с N вершинами?

Ответ:

(1) N

(2) N*2 + 1

(3) 2*N - 1

(4) N/2 - 1

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

Номер 1

У структуры данных дерево отрезков рассмотрим произвольную вершину v и относящийся к ней отрезок [l, r]. Если l ≠ r, каких сыновей имеет эта вершина?

Ответ:

(1) [l, l+1], [l+1, l+2],..., [r-1, r]

(2) [l, m] и [m+1, r], m = (l + r)/2

(3) l и r

(4) [l, m] и [m+1, r], m - любое число меньшее l и большее r

Номер 2

Для динамической задачи RMQ, не использующей предобработку, какое время используется на запрос?

Ответ:

(1) O(N)

(2) O(log N)

(3) O(1)

(4) O(N²)

Номер 3

Сколько памяти требуется для предварительного построения таблицы минимумов для всех возможных отрезков [i, j] и какое время будет для запроса RMQ после такой предобработки?

Ответ:

(1) O(N), O(1)

(2) O(N²), O(1)

(3) O(N * log N), O(1)

(4) O(N²), O(log N)

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

Номер 1

Сколько памяти потребуется для предварительного построения таблицы минимумов (RMQ) для отрезков [i, j], где j это степень двойки, какое время будет для запроса после такой предобработки?

Ответ:

(1) O(N * log N), O(1)

(2) O(N²), O(log N)

(3) O(N²), O(1)

(4) O(N), O(1)

Номер 2

Каким должен быть размер блока для алгоритма ±1-RMQ, чтобы сократить сложность предобработки?

Ответ:

(1) log N

(2) (log N)/2

(3) √N

(4) N/2

Номер 3

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

Ответ:

(1) выполнить In-order обход дерева

(2) выполнить Post-order обход дерева

(3) построить Эйлеров обход дерева

(4) выполнить обход в глубину

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

Номер 1

В алгоритме ±1-RMQ на блоки с минимумами какого размера разбивается исходная последовательность?

Ответ:

(1) на блоки одинакового размера, кроме последнего. Для каждого блока ищется минимум

(2) на блоки единичного размера

(3) на три блока

(4) на два блока

Номер 2

В алгоритме ±1-RMQ после разделения исходной последовательности на блоки, на какие части разделяется отрезок запроса?

Ответ:

(1) на три части: конечный отрезок некоторого блока; второй составлен из целого числа подряд идущих блоков; начальный отрезок некоторого блока

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

(3) на две части: одна содержит первую точку, вторая содержит вторую точку

Номер 3

В алгоритме ±1-RMQ исходная последовательность разбивается на блоки с минимумами. Какой блок называется приведенным?

Ответ:

(1) первый элемент которого равен нулю

(2) для которого посчитан минимум

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

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

Номер 1

Для алгоритма ±1-RMQ сколько существуют типов приведенных блоков размера k?

Ответ:

(1) 2 * k - 1

(2) 2^k-1

(3) 2^k+1

(4) k² - 1

Номер 2

На сколько различаются глубины соседних вершин в Эйлеровом обходе?

Ответ:

(1) на 2

(2) на 1

(3) на разное число

Номер 3

Какая задача сводится к задаче ±1-RMQ?

Ответ:

(1) Задача RMQ, которая получается при сведении от задачи LCA

(2) Задача LCA, которая получается при сведении от задачи RMQ

(3) построение splay-дерева

(4) построение левацкой кучи

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

Номер 1

Как длина Эйлерова обхода зависит от числа вершин в дереве?

Ответ:

(1) квадратично

(2) линейно

(3) экспоненциально

(4) логарифмически

Номер 2

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

Ответ:

(1) вершина с наибольшей глубиной между исходными двумя вершинами

(2) вершина с наименьшей глубиной между исходными двумя вершинами

(3) вершина с наименьшей глубиной, ближайшая к одной из двух вершин

(4) вершина с наименьшей глубиной среди всех отложенных вершин

Номер 3

Что нужно сделать, чтобы найти LCA любых двух вершин, имея Эйлеров обход дерева?

Ответ:

(1) построить In-order обход дерева

(2) построить Pre-order обход дерева

(3) для каждой вершины отложить ее глубину

(4) найти все пути между всеми вершинами

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

Номер 1

Какую асимптотику по памяти имеет сведение задачи RMQ к ±1-RMQ?

Ответ:

(1) квадратичную

(2) линейную

(3) логарифмическую

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

Номер 2

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

Ответ:

(1) 2 * k - 1

(2) 2^k-1

(3) k * 2^k

(4) k² - 1

Номер 3

Какой overhead по сложности имеет сведение задачи RMQ к ±1-RMQ?

Ответ:

(1) квадратичный

(2) линейный

(3) логарифмический

(4) константный

Номер 4

Что нужно посчитать для дерева помимо Эйлерова обхода вершин для нахождения lca при сведении задачи LCA к ±1-RMQ?

Ответ:

(1) пути к соседним вершинам

(2) пути до корня

(3) RMQ

(4) глубины вершин

Номер 5

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

Ответ:

(1) пути к соседним вершинам

(2) пути до корня

(3) RMQ

(4) ±1-RMQ

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