В функциональной парадигме при проектировании алгоритма какой оценкой на время работы интересуются

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

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

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

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

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

(2) интервальное дерево

(3) интервальная хэш-таблица

(4) дерево сегментов

(1) процессорное время, память

(2) надежность, масштабируемость

(3) адаптивность, простота реализации

(1) O(N * log N)

(2) O(N²)

(3) O(N)

(4) O(N³)

(1) k-ый элемент в массиве A

(2) элемент в массиве A, встречающийся k раз

(3) k-ый в порядке возрастания ключ в массиве A

(4) частота встречаемости k-го элемента в массиве A

(1) Insert(v) — вставить значение v в конец словаря

(2) Set(k, v) — назначить ключу k значение v

(3) Get(k) — получить по ключу k значение v

(4) Extract-min — получить ключ для минимального значения

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

(2) для любой вершины x в левом поддереве вершины v справедливо неравенство key(x) <= key(v)

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

(4) для любой вершины y в правом поддереве вершины v справедливо неравенство key(v) <= key(y)

(1) кучу

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

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

(4) B-дерево

(1) O(N)

(2) O(log N)

(3) O(N2)

(4) O(N * log N)

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

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

В представленном ниже псевдокоде алгоритма поиска порядковой статистики что находится на пропущенном месте?

Random-select(A, k)
задать λ
…
если k <= |A₁|:
вернуть Random-select(A₁, k)
иначе:
вернуть Random-select(A₂, k — |A₁|)

(1) пустая строка, ничего не пропущено

(2) разделить (A, λ) -> (A₁, A₂)

(3) разделить (A, k) -> (A₁, A₂)

(4) разделить (A, |A| — k) -> (A₁, A₂)

(1) O(log N)

(2) O(1)

(3) O(N)

(1) 1 ключ

(2) (n-1) ключей

(3) n ключей

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

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

(3) k = lca(i, j)

(4) k = lca(A)

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

(2) если от точки (x, x) провести лучи вверх и влево, то слева сверху будет находиться искомая область

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

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

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

(2) время работы алгоритма в лучшем случае при рассмотрении всех входов (I) размера N

(3) время работы алгоритма в худшем случае при рассмотрении всех входов (I) размера N

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

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

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

(1) используется рандомизированный выбор разделителя

(2) используется приближенная медиана в качестве разделителя

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

(4) поиск разделителя производится с помощью рекурсивного вызова

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

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

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

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

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

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

(3) если значения ключей в левом поддереве намного меньше значений ключей в правом поддереве

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

(1) In-order обход

(2) Post-order обход

(3) Pre-order обход

(1) случайным образом

(2) делит отрезки примерно поровну

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

(4) по среднему значению отсортированных правых концов отрезков

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

(2) берется сумма оценок сверху и снизу и делится на 2

(3) это означает что оценка произведена неверно

(1) O(L²)

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

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

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

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

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

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

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

(1) h(k,j) = (h₀(k) + j * h₁(k)) mod m

(2) h(k,j) = (h₀(k) + j) mod m

(3) h(k,j) = (h₀(k) + j * h₀(k)) mod m

(1) x — становится черным

(2) y — становится черным

(3) ничего не предпринимают

(4) x и y — становятся черными

(1) Unite

(2) Create

(3) Remove

(4) Get-min

(1) O(N2)

(2) O(N * log N)

(3) O(log N)

(4) O(N)

(1) может быть несколько CPU в одном модуле

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

(3) CPU может отсутствовать

(4) память устроена гораздо сложнее

(5) не учтена внешняя память

(6) память может отсутствовать

(1) n/2^k

(2) 2^k

(3) n/k

(4) k

(1) Insert(k)

(2) Remove(k)

(3) Get-min()

(4) Extract(k)

(5) Extract-min()

(6) Decrease-key(k)

(1) значение хеш-функции от ключа k является случайной величиной, равномерно распределенной на множестве {0, …, M1}

(2) для различных ключей k₁ и k₂ хеш-коды h(k₁) и h(k₂) зависят друг от друга

(3) вероятность появления коллизий<= 0.01

(4) количество значений не должно превышать 2⁶⁴ — 1

(1) при поднятии x вращения не совершаются

(2) x становится корнем

(3) T(время работы операции) = Θ(глубина x)

(4) учетная стоимость любой операции splay O(log N)

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

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

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

(1) на всех уровнях дерева запоминаются пезультаты работы алгоритма для всех запросов

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

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

(1) алгоритм неограничен в своих дейстиях

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

(3) в такой модели можно программировать

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

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

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

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

(1) извлекает минимальное значение и возвращает его

(2) возвращает миниальное значение без извлечения

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

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

(1) α = N/M

(2) α = M/N

(3) α = 1 + M/N

(4) α = 1 + N/M

(1) zig-zig

(2) zig

(3) zig-zag

(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

(1) O(N)

(2) O(N * log N)

(3) O(N2)

(4) O(log2 N)

(1) если алгоритм дошел до корня

(2) если алгоритм дошел до листа

(3) если алгоритм перебрал все листья

(4) если алгоритм перебрал все ключи

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

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

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

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

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

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

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

(1) Θ(1)

(2) Θ(M/N + 1)

(3) Θ(M)

(4) Θ(N)

(1) этого сделать нельзя

(2) исключить операцию splay

(3) в конце операции вызывать процедуру splay от той вершины, до которой дошли

(4) в начале операции вызывать процедуру splay для текущей вершины

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

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

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

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

(1) указатель на место, откуда точка переместилась и указатель на предыдущий элемент

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

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

(1) это количество всех возможныз путей в дереве

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

(3) это количество листьев в дереве, то есть элементов на нижних уровнях

(1) O(N²)

(2) O(N * log N)

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

(4) O(N)

(5) O(log N)

(1) создать пустую кучу, применить операцию Insert для каждого элемента

(2) это невозможно, потому что все операции в куче работают за O(log N)

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

(1) использовать метод открытой адресации

(2) если неизвестно с какими ключами предстоит иметь дело

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

(4) выбирать хэш-функции из универсального семейства

(1) ≤ r'(v) - r(v)

(2) ≤ 1 + 3(r'(v) - r(v))

(3) ≤ 1 + 3(r'(u) - r(u))

(4) ≤ 4

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

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

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

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

(1) ChangeEdge

(2) AddEdge

(3) RemoveEdge

(4) Connected

(5) FindEdge

(1) O(1)

(2) Θ(N)

(3) O(N²)

(4) O(log N)

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

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

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

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

(1) приписывание ключа в конец кучи

(2) Sift-up()

(3) Sift-down()

(4) приписывание ключа в начало (корень) кучи

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

(2) линейно

(3) константно

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

(1) деревья поиска и хэш-функции

(2) деревья поиска и кучи

(3) кучи и хэш-функции

(4) деревья поиска с вершинами-массивами

(1) 2 * k — 1

(2) 2^k-1

(3) 2^k+1

(4) k² — 1

(1) динамический

(2) оффлайн

(3) онлайн

(4) инкрементальный

(1) C’ = C*d, d — константа > 1

(2) C’ = C + d, d — число добавляемых элементов

(3) C’ = C²/d, d — константа > 1

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

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

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

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

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

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

(1) построить троичную бинарную кучу из бинарных куч размерности T₁

(2) объединить корни куч размерностей T₁ и T₂

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

(1) ключ в множестве есть, а операция Contains(k) выдает False

(2) операция Contains(k) выдала True, а ключа в множестве нет

(3) при попытке удаления ключа (Remove(k)) создается его резервная копия

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

(1) сложность рекурсивного построения дерева в худшем случае O(log N)

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

(3) структура дуча имеет логарифмическое матожидание высоты в худшем случае

(4) может поддерживать операции split, merge

(5) дерево можно построить рекурсивно

(6) быстрее чем за O(N2) построить декартово дерево нельзя

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

(2) линейно

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

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

(1) значит задача не может быть решена быстро, за время O(log N)

(2) задача сводится к задаче связности в деревьях Эйлерова обхода. Время O(log N)

(3) задача может быть решена быстро, за время O(N)

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

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

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

(1) соеденить α с β, α — родитель

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

(3) соеденить β с α, β — родитель

(1) Remove(k)

(2) Insert(k)

(3) Contains(k)

(4) Get(k)

(1) вершина удаляется аналогично удалению из кучи

(2) вызыватся split(T, x), получаются деревья T1, T2. Если x∈T, удалить вершину с ключем x из T1, выполнить Merge(T1, T2)

(3) вершина удаляется аналогично удалению из дерева поиска

(4) вершина удаляется без дополнительных операций

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

(2) линейную

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

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

(1) Pre-order

(2) In-order

(3) Post-order

(1) происходит ошибка

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

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

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

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

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

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

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

(1) O(1)

(2) O(N)

(3) O(log N)

(4) O(N * log N)

(1) вычислить логическое ИЛИ по всем значениям T[h_i(k)]. Если оно равно 0 то не попадает, если 1, то попадает

(2) вычислить логическое И по всем значениям T[h_i(k)]. Если оно равно 0 то не попадает, если 1, то попадает

(3) вычислить T[∑ h_i(k)]. 0 — не попадает, 1 — попадает

(1) степень вершины не может быть больше 2

(2) ключи, вставленные операцией Insert, хранятся в листьях

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

(4) в каждой вершине содержатся максимальные ключи из всех поддеревьев с d-сыновьями

(5) данные находятся во всех вершинах

(6) B-дерево всегда полностью сбалансированно

(1) первый граф в цепочке остовных лесов это граф без ребер

(2) остовные леса вложены друг в друга

(3) последний граф в цепочке остовных лесов это граф без ребер

(4) связные компоненты для графа Gi с n вершинами в цепочке имеют размер не более n/(2i)

(1) push, get

(2) push, pop

(3) insert, get

(4) enqueue, decueue

(1) 1

(2) 0

(3) Null

(4) может принимать любое значение

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

(2) может выдать правильное значение, если функция определена в этой точке или если функция неопределена в этой точке, то выдать случайное значение. Или выдает Null, если функция неопределена в этой точке

(3) выдает значение, если функция определена в этой точке, либо выдает Null, если функция неопределена в этой точке

(1) d

(2) d-1

(3) d+1

(4) 2*d

(5) 1

(1) добавляем в остовный лес на любом уровне ребро E

(2) добавляем в остовный лес на нулевом уровне ребро E

(3) добавлять ребро E в граф нельзя

(4) добавляем в остовный лес на всех уровнях ребро E

(1) локальность с точки зрения кэшироваия

(2) много мелких аллокаций (переопределений памяти)

(3) memory overhead (много дополнительного места для поддержания структуры)

(4) нельзя хранить разные типы даных

(1) rank(left(v)) >= rank(right(v)) для любой вершины v

(2) rank(left(v)) <= rank(right(v)) для любой вершины v

(3) rank(v) <= rank(parent(v)) для любой вершины v

(4) rank(v) >= rank(parent(v)) для любой вершины v

(5) rank(left(v)) = rank(right(v)) для любой вершины v

(1) объединяет множества, содержащие x, y в одно

(2) отображает, в одном или в разных множествах содержатся x, y

(3) объединяет два элемента x, y в один элемент по заранее определенной функции

(4) объединяет одноэлементные множества x, y в одно множество

(1) от Fi до последнего

(2) от F0 до Fi

(3) только Fi

(4) на всех уровнях

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

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

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

(1) ранг правого сына всегда на 1 меньше чем ранг родителя

(2) ранг растет линейно по числу элементов

(3) Операция Insert сводится к созданию кучи из одного элемента, а затем к слиянию

(4) левацкая куча хранит в каждой вершине помимо ее приоритета также ранг

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

(1) O(N)

(2) O(log N)

(3) O(N * log N)

(4) O(1)

(1) структура данных изменяет свои свойства в зависимости от текущей задачи

(2) структура данных хранит историю своего развития и модификаций

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

(1) weight(v) >= 1/2weight(parent(v))

(2) weight(v) > 1/2weight(parent(v))

(3) weight(v) > weight(parent(v))

(4) weight(v) <= 1/2weight(parent(v))

(1) он корректен

(2) необходимо хранить счетчик на каждую вершину

(3) структура при этом не является неизменияемой (immutable)

(4) помечаются все элементы, достижимые из корней

(5) структура эффективна в многопоточном режиме

(1) количество хороших вершин в ней

(2) количество плохих вершин в ней

(3) общее количество вершин в ней

(4) количество тяжелых вершин в ней

(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]

(1) Линейное программирование

(2) Разделяй и властвуй

(3) Жадные алгоритмы

(4) Динамическое программирование

(1) оценкой в худшем случае

(2) оценкой в среднем

(3) оценкой в лучшем случае

(1) O(N²)

(2) O(N * log N)

(3) O(N)

(4) O(log N)

(1) O(log N)

(2) O(N)

(3) O(N * log N)

(4) O(N²)

(1) простого массива

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

(3) односвязного или двусвязного списка

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

(1) поиск ключа x в дереве

(2) если поиск завершился неудачей, создадим новую вершину w с ключем x

(3) если поиск завершился удачей, создадим новую вершину w с ключем x

(4) вершину w объявим левым сыном v, если key(v) > key(w)

(5) вершину w объявим правым сыном v, если key(v) < key(w)

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

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

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

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

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

(1) Эффективные прямого перебора ничего не придумано

(2) Вести поиск только по правым или по левым концам интервалов

(3) Разделить интервалы на дерево групп, для более быстрого доступа к соответствующей группе или интервалу

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

(2) нет

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

В представленном ниже псевдокоде алгоритма поиска порядковой статистики что находится на пропущенном месте?

Random-select(A, k)
задать λ
разделить (A, λ) -> (A₁, A₂)
…
вернуть Random-select(A₁, k)
иначе:
вернуть Random-select(A₂, k — |A₁|)

(1) если k > |A₁|:

(2) если k <= |A₁|:

(3) если k > |A₂|:

(4) если k == λ

(1) совпадение хэш-кодов различных ключей

(2) совпадение хэш-кодов для одинаковых значений из множества

(3) совпадение хэш-кодов одинаковых ключей

(1) Pre-order обход

(2) In-order обход

(3) Post-order обход

(1) O(log N)

(2) O(n)

(3) O(N * log N)

(4) O(N²)

(1) очередь с приоритетами

(2) приоритетное дерево поиска (priority search tree)

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

(4) куча

(1) точный вид функций T(N) и M(N)

(2) приближенный до константы вид функций. Используется O-символика

(3) приближенный вид функций. Используется o-символика

(1) O(N * log N)

(2) Θ(N²)

(3) Θ(N³)

Для приведенного псевдокода поиска k-ой порядковой статистики, выберите строки, которых не хватает для корректной работы алгоритма:

Select (A, k)
…
partition(A, λ) -> (A₁, A₂)
if k <= |A₁| then:
return Select(A₁, k)
else:
return Select(A₂, k — |A₁|)

(1) group by 5 elements

(2) group by k elements

(3) sort groups

(4) λ = median of medians

(5) λ = random of medians

(1) O(L), O(L), L — длина цепочки для текущей хэш-функции

(2) O(L), O(L * N), L — длина цепочки для текущей хэш-функции

(3) O(L), O(L), L — длина цепочки для текущей хэш-функции

(4) O(1), O(L), L — длина цепочки для текущей хэш-функции

(1) не менее 2 * lg(n+1)

(2) не больше 2 * lg(n+1)

(3) не менее n/2

(4) не менее n

(1) куча

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

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

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

(5) B-дерево

(1) O(log N)

(2) O(log N + k)

(3) O(log N * k)

(4) O(N + k)

(1) выполнить болшее количество тестов

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

(3) изменить входные данные

(1) по переданному значению

(2) по переданному ключу или итератору

(3) по ключу или значению

(1) h(k,j) = (h₀(k) + j * h₁(k)) mod m

(2) h(k,j) = (h₀(k) + j) mod m

(3) h(k,j) = (h₀(k) + j * h₀(k)) mod m

(1) ничего делать не нужно

(2) A и C сделать черными, B — красным

(3) A сделать черными, x — красным

(4) x сделать черными

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

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

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

(1) по r координате

(2) по l координате

(3) по l и r координатам

(4) по другим параметрам

(1) w это количество ячеек в памяти

(2) w это число бит в одной ячейке памяти

(3) w это максимально допустимый размер переменной

(4) w хранит числа ограниченной битности

(5) w это число бит, необходимых для представления одной буквы или цифры

(1) O(N)

(2) O(N * log N)

(3) O(N²)

(4) O(log N)

(1) Get-min()

(2) Extract-min()

(3) Insert(k)

(4) Remove(k)

(5) Decrease-key(k)

(1) Σ(i=1..n)1/X_i,j

(2) Σ(i=1..n)X_i,j

(3) Σ(i=1..n)(X_i,j * h(k_i))

(1) время работы операции splay может быть больше чем O(log N)

(2) операция Find включает операцию splay

(3) сплэй-деревья не поддерживают баланс постоянно, вместо этого они остаются сбалансированными в среднем

(4) дерево самобалансируется за счет вызовов операции splay

(5) splay-деревья не поддерживают объединения

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

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

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

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

(1) нижние поддеревья в дереве поиска

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

(3) части, на которые разбиваются исходные списки

(4) ответы на запросы для каждого списка

(1) программа на языке, похожем на Assembler, C

(2) структура в виде дерева

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

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

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

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

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

(1) извлекает минимальное значение и возвращает его

(2) возвращает миниальное значение без извлечения

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

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

(1) Θ(M/N)

(2) Θ(log M/N)

(3) Θ(M * N)

(4) Θ(M/N + 1)

(1) zig-zig

(2) zig

(3) zig-zag

(1) O(N)

(2) O(log N)

(3) O(1)

(4) O(N²)

(1) O(N)

(2) O(log2 N)

(3) O(N2)

(4) O(log N)

(1) с листьев

(2) с корня

(3) с любого возможного ключа

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

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

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

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

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

(1) каждая вершина либо лист, либо имеет двух или одного сына: левого или правого

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

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

(1) не больше 2/3

(2) не больше 1/2

(3) меньше 1/M

(4) меньше 1/N

(1) если рассматриваемая вершина находится на глубине 0

(2) если рассматриваемая вершина находится на глубине 1

(3) если рассматриваемая вершина находится на глубине 2

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

(1) log N

(2) (log N)/2

(3) √N

(4) N/2

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

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

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

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

(1) T = Ω(log N)

(2) T = Ω(N*log N)

(3) T = Ω(N²)

(4) T = O(N)

(1) O(N * log N)

(2) O(N²)

(3) O(N)

(4) O(log N)

(1) O(N * log N)

(2) O(N)

(3) O(N²)

(4) O(N² * log N)

(1) имеет вероятность получения коллизий <= 1/m², m — количество ключей

(2) просто вычислима, за O(1) в худшем случае

(3) линейное в среднем время построения

(4) не дает коллизий на ограниченном множестве {k₁,…,k_n}

(1) ≤ r'(v) - r(v)

(2) ≤ 1 + 3(r'(v) - r(v))

(3) ≤ 1 + 3(r'(u) - r(u))

(4) ≤ 3(r'(v) - r(v))

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

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

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

(1) ChangeEdge

(2) AddEdge

(3) RemoveEdge

(4) Connected

(5) FindEdge

(1) O(M + N)

(2) O(M*N)

(3) O(N)

(4) O(M)

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

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

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

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

(1) Sift-up()

(2) Sift-down()

(3) приписывание ключа в конец кучи

(4) перемещение конечного элемента кучи в начало(корень) кучи

(1) O(N)

(2) O(1)

(3) O(N²)

(4) O(log N)

(1) сортировка слиянием

(2) быстрая сортировка

(3) двоичный поиск

(4) сортировка кучей

(1) на 2

(2) на 1

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

(1) динамический

(2) оффлайн

(3) онлайн

(4) инкрементальный

(1) C’ = C*d, d — константа > 1

(2) C’ = C + d, d — число добавляемых элементов

(3) C’ = C²/d, d — константа > 1

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

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

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

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

(1) i

(2) 2ⁱ

(3) 2ⁱ⁺¹

(4) i²

(1) уменьшается

(2) увеличивается

(3) не изменяется

(1) Merge(T, Null) = T, Merge(Null, t) ≠ T

(2) для деревьев T₁ с корнем u, T₂ с корнем v, p(u) < p(v), при их слиянии корнем будет v

(3) сложность O(log N)

(4) для T1(α — левое поддерево, β — правое поддерево) с корнем u, T2(γ — левое поддерево, δ — правое поддерево) с корнем v, p(u) < p(v), то при слиянии корнем нового дерева будет u, левым поддеревом α, правым результат Merge(β, T2)

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

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

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

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

(1) нет

(2) да, если его удвоить, обойдя Эйлеровым обходом

(3) оно и так уже является Эйлеровым графом

(4) да, если добавить к нему корень

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

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

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

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

(1) O(N)

(2) O(log N)

(3) O(1)

(4) O(N * log N)

(1) разрешается ложноотрицательное срабатывание, когда ключ в множестве есть, а операция Contains(k) выдает False

(2) разрешается ложноположительное срабатывание, при котором операция Contains(k) выдалет True, а ключа в множестве нет

(3) запрещается ложноположительное срабатывание

(4) запрещается ложноотрицательное срабатывание

(1) выполняется Split(T, x), получаем T1, T2, вершину (x, p), p — приоритет, x — ключ. Выполняется Merge(T1, (x, p)) = T1x. Выполняется Merge(T1x, T2)

(2) выполняется Merge(T, x)

(3) вершина добавляется аналогично операции добавления для кучи

(4) вершина добавляется аналогично операции добавления для дерева поиска

(1) 2 * k — 1

(2) 2^k-1

(3) k * 2^k

(4) k² — 1

(1) лес в графе, минимальный с точки зрения связности

(2) лес в графе, максимальный с точки зрения связности

(3) граф с полным набором всех его ребер

(4) граф с дополнительным набором ребер, обеспечивающих полную связность

(1) C'(a_i) = C(a_i) + ϕ_i — ϕ_i-1

(2) C'(a_i) = C(a_i) — C(a_i-1)

(3) C'(a_i) = C(a_i) + ϕ_i-1 + ϕ_i

(1) Φ = Σ l_i / p_i

(2) Φ = Σ l_i p_i

(3) Φ = Σ l_i + p_i

(1) O(1)

(2) O(N)

(3) O(log N)

(4) O(N * log N)

(1) вычислить хэш-коды h₁(k),…,h_s(k), после чего в получившиеся индексы ячеек булева массива T записать значение True

(2) вычислить сумму ∑ h_i(k) и записать в таблицу T, в ячейку с получившимся индексом значение True

(3) по хэш-функции h(k) определяется булево значение и вставляется в индекс таблицы T

(4) вычислить хэш-коды h₁(k),…,h_s(k), после чего в соответствующие значения записать ключ k

(1) Get(x)

(2) Insert(x)

(3) Remove(x)

(4) Find(x)

(5) Get-min/Get-max

(1) для графа строится Эйлеров обход

(2) ребрам приписываются уровни E -> {0, 1, ..., log N}

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

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

(5) остовные леса на каждом уровне должны быть вложены друг в друга

(1) O(N)

(2) O(1)

(3) O(log N)

(1) 1 + min(left(v), right(v))

(2) min(left(v), right(v))

(3) 1 + max(left(v), right(v))

(1) Такую структуру реализовать нельзя

(2) с помощью одного Блюм-фильтра для области определения функции, значению 0 будет выдаваться если функция неопределена в этой точке, 1 если функция определена или неопределена для случая ложноположительного срабатывания

(3) С помощью двух множеств: прообраз всех значений 0 и прообраз всех значений 1. Построить два Блюм-фильтра для этих двух множеств

(1) от 1/2 до 1

(2) от 1 до d/2(количество вершин на нижнем уровне)

(3) от 0 до d(количество вершин на нижнем уровне)

(4) от 0 до 1/2

(1) связность между вершинами может нарушиться

(2) связность между любой парой вершин сохранится

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

(4) необходимо выяснить является ли данное ребро мостом в графе

(1) доступ к элементу по индексу происходит быстрее

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

(3) лучше локальность с точки зрения кэширования

(4) лучше с точки зрения аллокаций

(1) нельзя

(2) если обменять левого и правого сына в тех вершинах v, для которых свойство левацкости (rank(left(v)) >= rank(right(v))) нарушается

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

(4) если удалить те вершины, у которых свойство левацкости нарушается

(1) сравниваются ключи x, y

(2) сравниваются корни деревьев, содержащих элементы x и y

(3) сравниваются хэш-функции от x, y, заранее определенные для данного типа множества

(4) определяется соответствие x, y какому-то заданному свойству или условию

(1) связность не пострадает и ничего дополнительно делать не нужно

(2) необходимо выяснить является ли данное ребро мостом в графе и выполнить соответствующие действия

(3) связность графа точно нарушится

(1) с помощью очереди и стэка

(2) с помощью двух стэков

(3) очередь с дополнительной переменной

(4) с помощью очереди и функции для вычисления минимума

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

(2) операция слияния выполняется рекурсивно

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

(4) время выполнения операции слияния двух левацких куч O(log N)

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

(1) для всех листьев дополнительно делается ссылка на корень дерева

(2) для каждой вершины на пути операции Get-root перебросить ее родителя так, чтобы родителем стал корень дерева

(3) дерево поддерживается сбалансированным всегда

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

(1) большой объем памяти для хранения структуры

(2) трудность анализа учетных стоимостей

(3) сложность реализации

(4) низкая производительность

(1) рангу вершины v

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

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

(4) приоритету вершины, умноженному на ее ранг

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

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

(3) структура при этом по настоящему неизменяема

(4) такая структура эффективна в многопоточном режиме

(1) не более log N тяжелых вершин

(2) не более log N легких вершин

(3) не более log N плохих вершин

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

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

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

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

(1) Находящиеся с левого края на интервальной прямой

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

(3) Находящиеся с правого края на интервальной прямой

(4) Больше всех пересекающиеся между собой

(1) не зависимо от N

(2) в сравнении с N

(3) как функция от параметра N

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

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

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

(1) Merge-sort

(2) сортировка вставкой

(3) Quick-sort

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

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

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

(4) если множество ключей k = {0,…, 2⁶⁴ — 1}

(1) поиск ключа x в дереве

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

(3) если найден лист, то он просто удаляется

(4) если найден лист, то он меняется местами с родителем

(5) если у найденной вершины v один сын w, то v удаляется, вершина w занимает место v

(6) если у найденной вершины v два сына, то копируется ключ из вершины v', предшествующей v, в v. v' удаляется

(1) a_k’ ≤ a_k

(2) a_k’ ≥ a_k

(3) ∃ a_k’ < a_k

(1) O(N)

(2) O(log N + k), k — размер ответа, N — количество интервалов

(3) O(k), k — размер ответа

(4) O(log N * k), k — размер ответа, N — количество интервалов

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

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

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

В представленном ниже псевдокоде алгоритма поиска порядковой статистики что находится на пропущенном месте?

Random-select(A, k)
задать λ
разделить (A, λ) -> (A₁, A₂)
если k <= |A₁|:
…
иначе:
вернуть Random-select(A₂, k — |A₁|)

(1) вернуть Random-select(A₁, k — |A₁|)

(2) вернуть Random-select(A₁, k)

(3) возврат

(4) вернуть Random-select(A₁, k — |A₂|)

(1) имеющая время работы операций чтения/записи O(1)

(2) не имеющая коллизий

(3) не использующая дополнительной памяти для работы

(1) правого сына вершины v

(2) предыдущую вершину перед v в порядке расположения ключей

(3) следущую после v вершину в порядке расположения ключей

(4) родителя вершины v

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

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

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

(1) крайняя левая точка в «колодце» по координате с двухсторонним ограничением

(2) максимальная по координате с односторонним ограничением точка в «колодце»

(3) крайняя правая точка в «колодце» по координате с двухсторонним ограничением

(4) максимальная верхняя точка

(1) оценка снизу

(2) оценка сверху

(3) асимптотическое равенство

(1) O(N * log N)

(2) Θ(N²)

(3) Θ(N)

(1) T((3/10) * N)

(2) O(N)

(3) T(N/5)

(4) T((7/10) * N)

(5) O(log N)

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

(2) перезаписывают ячейку с новым ключем

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

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

(1) O(N)

(2) O(log N)

(3) O(1)

(4) O(N2)

(1) O(log N)

(2) O(N)

(3) O(N * log N)

(4) O(N²)

(1) O(N2)

(2) O(N * log N)

(3) O(log N)

(4) O(N)

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

(2) нужно найти оценку снизу, сверху. Если оценки совпали, то оценка равна Θ(N). И как правило оценка сводится к наихудшиму случаю

(3) означает что нужно найти среднюю оценку для алгоритма

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

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

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

(1) в листьях

(2) в корне

(3) может быть в любом месте кучи

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

(5) в левом крайнем листе

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

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

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

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

(1) ничего не нужно делать

(2) y сделать черным. Левым сыном y вместо x сделать красный z с левым сыном t, правым x

(3) t, y сделать черными, z — красным

(4) t, y сделать красными, x — черным

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

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

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

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

(1) отрезок, соответствующий листу дерева

(2) тот отрезок, для которого эта вершина или поддерево построены

(3) отрезок, ассоциированный с корнем вершины

(4) отрезок, поиск которого производится в дереве

(1) каждая ячейка памяти имеет динамический размер

(2) память это набор ячеек

(3) каждая ячейка это число ограниченной битности

(4) манипуляции с числами, хранящимися в ячейке, выполняются за константое время

(5) ячеек в теоретической модели памяти бесконечно много, как в машине Тьюринга

(1) O(log N)

(2) O(N)

(3) O(N²)

(1) Get-min()

(2) Extract-min()

(3) Insert(k)

(4) Remove(k)

(5) Decrease-key(k)

(1) EX_i,j = 1 если h(k_i) ≠ h(k_j). EX_i,j = 0 если h(k_i) = h(k_j)

(2) EX_i,j = 1/m если h(k_i) ≠ h(k_j). EX_i,j = 1 если h(k_i) = h(k_j)

(3) EX_i,j = 1/(m²) если h(k_i) ≠ h(k_j). EX_i,j = 0 если h(k_i) = h(k_j)

(1) если у корня T1 нет правого сына, тогда T2 приклеивается к нему

(2) у T1 найти максимальный элемент, применить к нему операцию splay, приклеить к правому сыну дерева T2

(3) у T2 найти максимальный элемент, применить к нему операцию splay, приклеить к правому сыну дерева T1

(4) у T2 найти максимальный элемент, на его место поставить дерево T1

(5) у T1 найти максимальный элемент, на его место поставить дерево T2

(1) N

(2) N*2 + 1

(3) 2*N — 1

(4) N/2 — 1

(1) каждый список разбивается на много частей

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

(3) в каждом списке уже сохранены все возможные ответы

(1) O(log N)

(2) Ω(N*log N)

(3) O(N²)

(1) O(N)

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

(3) O(N²)

(1) извлекает минимальное значение и возвращает его

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

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

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

(1) P[h(a) = h(b)] <= 0.5

(2) P[h(a) = h(b)] <= 1/N

(3) P[h(a) = h(b)] <= 1

(1) zigzig

(2) zig

(3) zigzag

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

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

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

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

(1) можно найти заранее размер ответа не выполняя все шаги алгоритма

(2) размер ответа выясняется только после просмотра всех точек в ответе

(3) это зависит от размера входных данных

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

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

(3) в вершинах которого хранятся двоичные значения

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

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

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

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

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

(1) i/2, (i-1)/2

(2) 2*i + 1, 2*i + 2

(3) i, 2*i

(1) n!

(2) n²

(3) n³

(4) 2ⁿ

(5) n

(1) если рассматриваемая вершина находится на глубине 0

(2) если рассматриваемая вершина находится на глубине 1

(3) если рассматриваемая вершина находится на глубине 2

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

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

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

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

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

(1) PST, как и для области поиска точек в виде «колодца»

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

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

(1) нет

(2) да, за T = Ω(N*log(log N)), но это нереализуемо на практике

(3) да, за T = Ω(N*log(log N)) и это реализуемо на практике

(1) O(N²)

(2) O(N)

(3) O(N * log N)

(4) O(log N)

(1) key(i) > key(parent(i))

(2) key(i) < key(parent(i))

(3) key(i) < key(i-1)

(4) key(i) < key(i+1)

(1) p — первое простое число, следующее после m

(2) семейство хэш-функций универсально, так как вероятность получить коллизию не превосходит 1/m

(3) m — количество ключей

(4) среднее время успешного поиска ключа Θ(α + 1)

(5) a — произвольный вычет по модулю p

(1) O(N)

(2) O(N * log N)

(3) O(log N)

(4) O(1)

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

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

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

(1) ChangeEdge

(2) AddEdge

(3) RemoveEdge

(4) Connected

(5) FindEdge

(1) в лучшем случае

(2) в худшем случае

(3) в среднем

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

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

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

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

(1) Insert(k)

(2) Extract-min()

(3) Decrease-key(k)

(4) Increase-key(k)

(1) O(∑ n_i)

(2) O(∑ n_i²)

(3) O(n)

(4) O(n²)

(1) O(1)

(2) O(log N)

(3) O(N)

(4) O(N2)

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

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

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

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

(1) O(log N)

(2) O(log2 N)

(3) O(N * log N)

(4) O(N)

(5) O(1)

(1) O(M * log M)

(2) O(M²)

(3) O(M)

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

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

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

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

(1) 4(100₂)

(2) 12(1100₂)

(3) 8(1000₂)

(4) 7(111₂)

(1) увеличивается

(2) уменьшается

(3) не изменяется

(1) в результате может получиться два дерева T1, T2, где x не входит ни в одно из них

(2) в результате операции получается три дерева: T1 (< x), вершина с ключем x,T₂(> x)

(3) если x = корень T, α — левое поддерево, β — правое поддерево, то Split(T, x) = α, x, β

(4) если ключ корня дерева T < x, то нужно вызвать рекурсивно Split(β, x) = γ, v, δ. Получатся деревья T1 (α — левое поддерево, γ — правое, v — корень), T2 = δ

(5) сложность операции O(N * log N)

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

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

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

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

(1) Rope (веревка)

(2) Приоритетное дерево поиска

(3) RMQ

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

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

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

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

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

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

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

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

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

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

(1) конструктивно данный фильтр представляет собой булев массив

(2) для проверки на принадлежность ключа k вычисляют его хэш-коды h₁(k), … , h_s(k), если соответствующие ячейки равны True, то ключ принадлежит множеству

(3) в его реализации используется одна хэш-функция

(4) для добавления ключа k вычисляются его хеш-коды h₁(k), … , h_s(k), после чего в соответствующие ячейки записывается значение True

(5) удаление элементов из фильтра Блюма можно реализовать, если он задан таблицей булевых значений

(1) если ключи в парах отсортированы, то построение выполняется за O(log N)

(2) для отсортированных Ti пар в дереве с различными приоритетами. Чтобы найти место в соотвтествии с приоритетами (p) для новой вершины (xi+1) вершина (k, p) вставляется правым сыном xi, остальные вершины, начиная с xi+1, вставляются левым сыном для вершины (k, p)

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

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

(2) линейный

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

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

(1) O(log N)

(2) O(log2 N)

(3) O(N * log N)

(4) O(N)

(1) ϕ(S) = #(1 in S) — количество единиц в состоянии S

(2) ϕ(S) = -#(1 in S) — количество единиц в состоянии S

(3) ϕ(S) = k + 1 — количество единиц справа до 0 в состоянии S

(4) ϕ(S) = k — количество единиц слева до 0 в состоянии S

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

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

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

(4) log (N/M + 1)

(1) O(1)

(2) O(N)

(3) O(log N)

(4) O(N * log N)

(1) (1 — 1/m)^s*n

(2) (1 — (1 — 1/m)^s*n)^s

(3) 1 — (1 — 1/m)^s*n

(4) (1 — (1 — 1/m)ⁿ)^s

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

(2) сложность операции O(N)

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

(1) уровень можно брать любой, сколь угодно большой

(2) нужно добавить ребро в граф

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

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

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

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

(3) если в структуре данных хранятся все предыдущие ее модификации

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

(1) 2^r(v)

(2) не менее 2^r(v) — 1

(3) 2 * r(v)

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

(2) на образованном такими значениями множестве C изготавливают два более мелких Блюм-фильтра для множеств-прообразов 0 и 1, затем продолжают создание иерархии таких множеств, пока они не перестанут пересекаться

(3) признают такие значения равными 0

(4) удаляют все такие значения из множества

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

(2) если у вершины было α*d ключей, то вершина просто удаляется

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

(4) если у найденной вершины было α*d ключей и у брата нет лишних ключей, то вершина сливается с братом

(1) связность графа точно нарушится

(2) связность графа точно не пострадает

(3) связность графа возможно нарушится

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

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

(3) эта структура используется для реализации стэка

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

(5) время доступа к элементу константное

(1) ранги не изменяются

(2) уменьшаются ровно на 1 при каждом шаге

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

(4) уменьшаются на 1 при каждом шаге или не меняются

(1) объединяет множества, содержащие x, y

(2) отображает, в одном или в разных множествах содержатся элементы x, y

(3) отображает равенство значений заранее определенной функции, взятой от x, y

(4) отображает, соответствуют ли x, y какому-то заданному свойству или условию

(1) O(log N)

(2) O(log2 N)

(3) O(N * log N)

(4) O(N)

(1) O(N)

(2) O(1)

(3) O(log N)

(4) O(N * log N)

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

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

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

(1) O(log N)

(2) O(log*n)

(3) O(1)

(4) O(N)

(1) O(log N)

(2) O(1)

(3) O(N)

(1) если она является легким правым сыном

(2) если она является тяжелым правым сыном

(3) если у нее легкий правый сын

(4) если ее вес равен 0

Каких двух строк не хватает в приведенном псевдокоде операции Push persistent-стэка? S — ссылка на стэк, v — данные для новой вершины.

Push(S, v)
w = new Node()
…
…
return w

(1) w.data = v

(2) w.next = S

(3) w = S

(4) S.data = v

(5) S.next = w

(1) одновременно легкого и тяжелого сыновей

(2) два тяжелых сына

(3) два плохих сына

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

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

(3) RMQ

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

(1) не менее n/(2i)

(2) не более n/(2i)

(3) не меньше n

(1) Σ(i..n)C(a_i) = ΣC'(a_i) — ϕ(S_n)

(2) Σ(i..n)C(a_i) = ΣC'(a_i) — ϕ(S₁) + ϕ(S_n)

(3) Σ(i..n)C(a_i) = ΣC'(a_i) + ϕ(S_n)

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

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

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

(1) (1 — 1/m)^s*n

(2) (1 — 1/m)

(3) 1 — (1 — 1/m)^s*n

(4) (1 — n/m)^s)

(1) сначала находим корни соответствующих поддеревьев x' и y'. Если они равны, элементы x и y уже содержатся в одном множестве

(2) для объединения деревьев Tx (содержащего x) и Ty (содержащего y) в одно дерево добавляют дугу между ними

(3) если высота дерева Tx (содержащего x) меньше чем высота Ty (содержащее y), то следует выполнить p(y') = x'. x', y' — корни соответствующих поддеревьев, p — родитель. Иначе p(x') = y'

(4) если r(x') = r(y') (высоты деревьев равны), то выполняется p(x') = y', иначе p(y') = x'

(5) значения высот поддеревьев вычисляются каждый раз заново в процессе работы

(1) на k частей, заранее определенных

(2) на 2 части

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

(4) на 4 части

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

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

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

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

(1) все листья черные

(2) если у красного родителя два сына, то их цвета черные

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

(4) у черных вершин все дети красные

(5) каждая вершина либо красная, либо черная

(6) красно-черные деревья сбалансированны

(7) высота поддеревьев различается не более чем на 1

(1) по правым границам интервалов

(2) по левым границам интервалов

(3) по левым и правым границам интервалов

(4) по длинам интервалов

(5) по удаленности от разделяющей точки

(1) O(N)

(2) O(log N)

(3) O(1)

(4) O(N * log N)

(1) ищем такие поддеревья что все точки в них попадают в отрезок [l1, l2] по l координатам

(2) для найденных поддеревьев по l координатам ищем по r координатам в них

(3) для найденных поддеревьев по l и r координатам, если идти вглубь дерева, то найдётся по крайней мере один ответ

(4) если r в вершине меньше чем r1, то в поддеревьях ничего не найдём, останавливаемся

(5) если r в вершине больше чем r1, то идём в одно из поддеревьев

(1) оценка снизу

(2) оценка сверху

(3) асимптотическое равенство

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

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

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

(1) l0 > l1, r0 > r1

(2) r0 < r1, точка находится ниже дна «колодца»

(3) l0 < l2, r0 > r1

(4) l0 < l1, r0 > r1

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

(2) нужно найти оценки снизу, сверху. Если оценки совпали, то оценка равна Θ(N). И как правило оценка сводится к наихудшиму случаю

(3) означает что нужно найти среднюю оценку для алгоритма

(1) pri(v_i) >= pri(v_i+1) для всех вершин v. i — порядковый индекс элемента

(2) pri(v_i) <= pri(v_i+1) для всех вершин v. i — порядковый индекс элемента

(3) pri(parent(v)) >= pri(v) для всех вершин v, кроме корня

(4) pri(parent(v)) <= pri(v) для всех вершин v, кроме корня

(1) Insert()

(2) Split(α, i) = β, γ, α — список, i — разделитель; β, γ — два новых списка

(3) Concat(α, β) = γ — объединить списки α, β в новый список γ

(4) помнить указатель на дерево, в котором находимся в настоящий момент

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

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

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

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

(1) Insert(k)

(2) Extract-min()

(3) Decrease-key(k)

(4) Increase-key(k)

(1) O(log N)

(2) O(log2 N)

(3) O(N * log N)

(4) O(N)

(1) linked lists

(2) один стэк

(3) chunked vector

(4) два стэка

(1) Get-min

(2) Extract-min

(3) Decrease-key

(4) Insert

(5) Meld

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

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

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

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

(1) i/2, (i-1)/2

(2) (i+1)/2, (i-1)/2

(3) 2*i + 1, 2*i + 2

(4) i, 2*i

(1) N²

(2) N!

(3) N*log N

(4) 2^N

(1) O(N²)

(2) O(N)

(3) O(N * log N)

(4) O(log N)

(1) O(N)

(2) O(log N)

(3) O(1)

(4) O(N * log N)

(1) O(M * log M)

(2) O(M)

(3) O(M²)

(1) бинарные деревья T₂ и T₃

(2) бинарные деревья T₀ и T₂

(3) бинарные деревья T₀,…,T₄

(1) сверху вниз

(2) снизу вверх

(3) слева направо

(4) это не важно

(1) амортизация

(2) гистерезис

(3) persistant (версионирование)

(1) O(N)

(2) O(log N)

(3) O(N * log N)

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

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

(3) эта структура используется для реализации стэка

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

(5) время доступа к элементу константное

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

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

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

Какие строки лишние в приведенном псевдокоде операции Pop для persistent-стэка? S — ссылка на стэк.

Pop(S)
w = new Node()
w.next = S
return S.next

(1) w = new Node()

(2) w.next = S

(3) return S.next

(1) O(N * log N)

(2) O(log N)

(3) O(N)

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

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

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

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

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

(3) RMQ

(4) ±1-RMQ

(1) (1 — 1/m)^s*n

(2) (1 — n/m)

(3) 1 — (1 — 1/m)^s*n

(4) (1 — 1/m)

(1) x < max(i∈α) ri, α_i = [l_i, r_i] — интервалы в левом поддереве

(2) x > max(i∈α) ri, α_i = [l_i, r_i] — интервалы в левом поддереве

(3) x > min(i∈β) li, β_i = [l_i, r_i] — интервалы в правом поддереве

(4) x > min(i∈β) ri, α_i = [l_i, r_i] — интервалы в левом поддереве

(1) разрешающее дерево не является алгоритмом в общем понимании этого слова

(2) для решения алгоритмической задачи всегда строится одно разрешающее дерево

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

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

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

(3) внешняя

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

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

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

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

(4) очередь, динамически изменяющая свой размер

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

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

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

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

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

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

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

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

(1) биномиальная очередь

(2) min-куча

(3) max-куча

(4) левацкая куча

78

76

Очень сложно

Сложно

Средне

Легко

Очень легко