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

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

В курсе рассматриваются базовые алгоритмы и структуры данных, включая хешировани, сложность и модели вычислений, деревья поиска, B-деревья, задачи геометрического поиска, динамическую связность в графах и другое.

Список вопросов:

# Для направленного леса, в операции addEdge(x, y) при каких условиях можно добавлять ребро из x в y?
# В чем заключается задача RMQ для массива чисел?
# В чем заключается задача LCA для заданного дерева?
# Какую структуру данных нужно использовать, чтобы свести задачу RMQ к LCA?
# Для декартова дерева с вершинами (key = N, prior = aN), если k = lca(i, j), то чем будет являться вершина ak?
# ∀ k'∈[i, j], если вершина ak - минимум на отрезке, то какое неравенство выполняется?
# В какой позиции достигается минимум на отрезке [i, j] в последовательности A (декартово дерево с индексами i = 1,...,n)?
# За какое время строится декартово дерево для набора {(1, a1),...,(n, an)}
# Что из перечисленного ниже является задачей offline RMQ??
# Какой способ обхода дерева используется для предобработки в задаче offline LCA?
# Какая структура данных используется дополнительно в предобработке для offline LCA?
# Какая сложность у алгоритма предобработки offline LCA?
# Какие операции из структуры disjoin set union используются в предобработке для задачи offline LCA?
# Отметьте верные свойства функции LCA
# Как можно ускорить вычисление задачи RMQ online?
# Как происходит оптимизация в алгоритме поиска LCA для дерева T?
# Какая вершина называется наименьшим общим предком для вершин u, v?
# Чему равна длина Эйлерова обхода дерева с N вершинами?
# У структуры данных дерево отрезков рассмотрим произвольную вершину v и относящийся к ней отрезок [l, r]. Если l ≠ r, каких сыновей имеет эта вершина?
# Для динамической задачи RMQ, не использующей предобработку, какое время используется на запрос?
# Сколько памяти требуется для предварительного построения таблицы минимумов для всех возможных отрезков [i, j] и какое время будет для запроса RMQ после такой предобработки?
# Сколько памяти потребуется для предварительного построения таблицы минимумов (RMQ) для отрезков [i, j], где j это степень двойки, какое время будет для запроса после такой предобработки?
# Каким должен быть размер блока для алгоритма ±1-RMQ, чтобы сократить сложность предобработки?
# Что значит сделать дерево толстым и обойти его по контуру?
# В алгоритме ±1-RMQ на блоки с минимумами какого размера разбивается исходная последовательность?
# В алгоритме ±1-RMQ после разделения исходной последовательности на блоки, на какие части разделяется отрезок запроса?
# В алгоритме ±1-RMQ исходная последовательность разбивается на блоки с минимумами. Какой блок называется приведенным?
# Для алгоритма ±1-RMQ сколько существуют типов приведенных блоков размера k?
# На сколько различаются глубины соседних вершин в Эйлеровом обходе?
# Какая задача сводится к задаче ±1-RMQ?
# Как длина Эйлерова обхода зависит от числа вершин в дереве?
# Если построить Эйлеров обход дерева и для каждой вершины отложить ее глубину, то чему будет равен LCA двух вершин?
# Что нужно сделать, чтобы найти LCA любых двух вершин, имея Эйлеров обход дерева?
# Какую асимптотику по памяти имеет сведение задачи RMQ к ±1-RMQ?
# Если в алгоритме ±1-RMQ для каждого типа приведенного блока, а также для каждого его начального и конечного отрезка вычислить минимум по данному отрезку, тогда сколько значений всего нужно предпосчитать?
# Какой overhead по сложности имеет сведение задачи RMQ к ±1-RMQ?
# Что нужно посчитать для дерева помимо Эйлерова обхода вершин для нахождения lca при сведении задачи LCA к ±1-RMQ?
# Что нужно предпосчитать для последовательности глубин Эйлерова обхода, чтобы можно было свести LCA к вопросу о том, где минимум в отрезке из этой последовательности?
# Какая структура данных используется для решения задач, связанных с интервалами?
# Какая основная идея применяется для решения задач, связанных с интервалами, с помощью статической структуры данных?
# При построении дерева интервалов какие интервалы попадут в корень дерева?
# На сколько частей разбиваются интервалы на каждом уровне при построении дерева интервалов?
# Какую глубину имеет дерево интервалов? Если N - количество интервалов
# Какой прием можнно использовать, чтобы эффективнее искать интервалы, пересекающие заданную точку с помощью статической структуры данных?
# Сколько стоит по времени поиск интервалов, пересекающих заданную точку?
# Как строится дерево поиска для асимметричного способа построения дерева интервалов?
# Для асимметричного способа построения дерева интервалов в каком случае поиск интервалов, пересекающихся с точкой x нужно вести в левом поддереве? Если x > l для интервала [l, r] в корне
# Если откладывать одномерные интервалы [l, r] на двумерной плоскости, то в какой области будут находиться интервалы, пересекаемые с точкой x?
# Какая структура данных может искать точки в "колодце"(двустороннее ограничение по одной координате и одностороннее ограничение по другой координате)?
# Для структуры дерева поиска, используемой для интервальной задачи поиска точки в "колодце", что будет находиться в корне дерева?
# Отметить НЕверные шаги алгоритма priority search tree, работающего на области поиска в виде "колодца", заданного следующим образом: [l1, l2] x [r1, +∞]?
# По каким критериям выбирается разделитель, делящий на левые и правые поддеревья в приоритетном дереве поиска (priority search tree)?
# Какое время поиска у приоритетного дерева поиска (priority search tree)?
# Какое время построения у приоритетного дерева поиска (priority search tree)?
# При каком значении [l0, r0] в корне дерева Prirority Search Tree не имеет смысла дальше искать в дереве, если область "колодца" задаётся так: [l1, r1] x [r1, +∞]?
# Какой размер имеет структура данных приоритетное дерево поиска?
# Если корень приоритетного дерева поиска выбирается по минимальной r координате отрезка [l, r], то по каким параметрам происходит деление на левые и правые поддеревья?
# Что такое канонический отрезок в дереве отрезков?
# В чём состоит идея оптимизации в структуре двумерное дерево отрезков для задачи поиска в квадратичной области, позволяющая достичь времени работы O(log N)?
# Что такое каскады в структуре Fractional cascading?
# За счёт чего происходит оптимизация у структуры Fractional cascading?
# Какая память необходима для двумерного дерева отрезков?
# Какое время поиска у структуры данных двумерное дерево отрезков, работающей с квадратной области поиска [x1, x2] x [y1, y2]?
# Можно ли узнать заранее размер ответа, то есть сколько будет в ответе "хороших" точек, используя структуру PST для интервальной задачи?
# Какие указатели должны быть в дереве отрезков, работающим за O(log N) по принципу Fractional cascading?
# Пусть есть k списков: L1,...,Lk. В чем заключается задача fractional cascading?
# Если область поиска меняется с "колодца" на прямоугольную добавлением двух ограничивающих точек, то какая структура данных может использоваться для такой задачи?
# Какие действия должна уметь выполнять структура данных для задачи о динамической связности в графах? Для полностью динамического случая
# Какие действия должна уметь выполнять структура данных для задачи о динамической связности в графах? Для инкрементальной связности
# Какие действия должна уметь выполнять структура данных для задачи о динамической связности в графах? Для декрементальной связности
# Какие операции должна уметь выполнять структура данных, которая подошла бы для полностью динамически связного графа
# Какой тип имеет задача о динамической связности в графе, если ответы на все запросы про связность будут получены после обработки всех операций, а не по мере их поступления?
# Какой тип имеет задача о динамической связности в графе, если ответы выдаются сразу после выполнения различных действий с графом и поступления запроса о связности?
# Какое время занимает каждое изменение в динамически полном графе для онлайн версии?
# Если задача такова, что в графе нет и не может быть циклов, то что можно сказать о ней?
# Если исходное дерево без выделенного корня, то можно ли его сделать Эйлеровым графом?
# Какая структура подойдет для реализации динамически полного связного графа?
# Какой обход является конкатенацией двух исходных обходов в операциях со списками для структуры Rope, реализующей динамически связный граф?
# Что такое остовный лес в графе?
# За какое время можно тестировать связаность в графе, если поддерживать для него остовный лес?
# Какой размер должны иметь связные компоненты для графа Gi уровня i с n вершинами?
# Какими свойствами должны обладать леса в остовном лесе?
# Каким образом нужно преобразовать граф, чтобы получить лес?
# Как производится вставка в динамический полный граф? Отметьте верные шаги
# Если до вставки нового ребра E его вершины u и v находились в разных компонентах связности, какие действия предпринимают, чтобы сохранить структуру динамически связного графа?
# Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то что это значит для структуры динамически связного графа?
# Если удаляемого ребра не было в остовном лесе нулевого уровня в графе, то что это значит для структуры динамически связного графа?
# Если удаляемое ребро имеет уровень i = l(u, v) то на каких уровнях леса оно лежит?
# Если при удалении ребра оказалось что оно находилось в остовном лесе, то что это значит?
# Какое время работы операции удаления в динамически полном связном онлайн графе?
# Какое время работы операции вставки в динамически полном связном онлайн графе?
# Какие существуют метрики, отображающие эффективность алгоритма?
# В функциональной парадигме при проектировании алгоритма, какой оценкой на время работы интересуются?
# При размере входных данных N, как рассчитывается время работы алгоритма?
# Считается ли компьютерная память важным ресурсом, учитывающимся при разработке эффективного алгоритма?
# Считается ли процессорное время важным ресурсом, учитывающимся при разработке эффективного алгоритма?
# Возможна ли такая ситуация при проектировании алгоритма, когда можно сэкономить на одном ресурсе в ущерб другому (процессорное время / память)?
# Зависит ли время работы алгоритма от размера входных данных N?
# Если T - время работы алгоритма, N - размер входных данных, что отображает функция max T(I) для N(I) = N?
# При рассмотрении времени работы T(M) и памяти M(N) что нас интересует?
# При оценивании функций какая оценка соответствует символике f = O(g)?
# При оценивании функций символике f = Θ(g) соответствует:
# Если при оценивании фиксированного алгоритма оценки сверху и снизу совпали, то какие действия предпринимаются?
# O-символика датет приближенную оценку. Что нужно сделать, чтобы найти оценку точнее?
# Что означает найти оценку для фиксированного алгоритма?
# Что означает найти оценку снизу на задачу?
# Чем такая схема <CPU - Память> отличается от реальной жизни?
# Какие из перечисленных ниже утверждений относятся к параметру машинное слово w в стандартной модели оперативной памяти (RAM - model)?
# Какие характеристики относятся к стандартной модели оперативной памяти (RAM - model)?
# В чем состоит отличие в работе алгоритма для модели "разрешающие деревья" от RAM - модели и модели машины Тьюринга?
# Что представляе собой программа для модели "разрешающие деревья"?
# Какая нижняя оценка справедлива для задачи сортировки?
# В алгоритмической модели "разрешающее дерево" в каком случае работа алгоритма завершается?
# С какого элемента начинается работа в разрешающем дереве в стандартном случае?
# Что называется бинарным деревом?
# Что нзывается правильным разрешающим деревом?
# Что назыавется сложностью для алгоритма, заданного разрешающим деревом?
# Как оценивается сложность правильного дерева сортировки (в худшем случае)?
# Можно ли сортировать быстрее чем за T = Ω(N*log N), если разрешить дополнительные операции с ключами?
# Сколько листьев должно быть в правильном дереве для множества из N элементов?
# Какое из перечисленных ниже высказываний не характеризует разрешающие деревья?
# Почему модель алгоритма "разрешающее дерево" не очень типична для практики?
# Пусть имеется двоичный счетчик, то есть вектор, состоящий из битов, представляющий двоичное число. Изначально все биты равны 0. Пусть есть операция Increment, какова ее сложность в худшем случае?
# Пусть имеется двоичный счетчик, то есть вектор, состоящий из битов, представляющий двоичное число. Изначально все биты равны 0. Для M операций Increment, какова их сложность в худшем случае?
# Пусть имеется двоичный счетчик, то есть вектор, состоящий из битов, представляющий двоичное число. Изначально все биты равны 0. Для M операций Increment в каком случае справедлива оценка O(M*N)?
# По какому принципу выбирается размер reallocation для аддитивного метода? Если C - старый размер массива.
# По какому принципу выбирается размер reallocation для мультипликативного метода? Если C - старый размер массива.
# Какое время будет затрачено на выполнение последовательности из M операций для аддитивного метода увеличения рамера массива?
# Какое время будет затрачено на выполнение последовательности из M операций для мультипликативного метода увеличения рамера массива?
# Для оценки сложности цепочки инкрементов, пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число 010111, над каждой 1 лежит по 1 у.е., сколько потребуется элементарных действий для операции Increment?
# Пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число, начиная справа имеем k единиц до 0. При текущем балансе -(k+1) (credit: k, debit: 1), если k единиц снять со структуры, 1 положить, сколько нужно попросить у клиента, чтобы выйти в 0?
# Пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число, начиная справа имеем k единиц до 0. При текущем балансе -(k+1) (credit: k, debit: 1), если k единиц снять со структуры, 1 положить, сколько нужно попросить у клиента, чтобы выйти в 0 для 5 запросов?
# Пусть 1 у.е. компьютер требует за 1 элементарную операцию. Пусть записано некоторое двоичное число, начиная справа имеем k единиц до 0. При текущем балансе -(k+1) (credit: k, debit: 1), чему равна учетная стоимость?
# Для библиотеки std::vector, реализующей массив на C++, что происходит, когда нужно добавить еще один элемент в конец массива, если массив полностью заполнен?
# При анализе учетных стоимостей операций C(ai) с каждым из состояний Si связано некоторое вещественное значение ϕi, называемое потенциалом. Тогда чему равняется приведенная стоимоть C'(ai)?
# Для задачи о бинарном поиске, какую нужно использовать функцию потенциала, чтобы получить приведенную стоимость C'(ai) = 2
# Если подобрать такую функцию потенциала ϕ, что приведенная стоимость будет ограничена каким-то числом M: C'(ai) <= M. Тогда какая будет линейная оценка для суммы стоимостей?
# Какие две операции должен выполнять хороший стэк?
# Какова учетная стоимость операций в стэке, реализованном с помощью вектора?
# Что называется гистерезисом с точки зрения структур данных?
# Как будет называться свойство структуры данных, для которой выполняется следующее: если коэффициент заполнения становится больше 1, тогда размер структуры увеличивается (например в 2 раза), если коэффициент заполнения падает до 1/4 раза, тогда размер структуры уменьшается в два раза.
# Какие минусы есть у структуры данных Linked lists при использовании ее для реализации стэка?
# Какие плюсы есть у структуры данных Chunked vector по сравнению с Linked lists, при использовании в качестве стэка?
# Какие высказывания относятся к структуре данных chunked vector?
# Какие высказывания относятся к структуре данных linked lists?
# Как эффективно реализовать стэк с поддержкой минимума?
# Как (с помощью каких структур данных) можно эффективно реализовать очередь с поддержкой минимума?
# Какая будет стоимость операций enqueue и dequeue в учетном смысле, если очередь реализована с помощью двух стэков?
# С помощью каких структур данных, перечисленных ниже, нельзя реализовать очередь?
# Что такое циклическая очередь?
# Что означает свойство persistent (версионирование) для структуры данных?
# Какая существует главная проблема, мешающая реализации immutable очереди с помощью двух стэков?
# Какое время выполнения операции Push у persistent стэка? Если N - длина стэка
# Существует подход для освобождения памяти для persistent stack, называемый подсчет ссылок (ref-counting). Как его можно описать?
# Выберите, чем характеризуется подход для освобождения памяти для persistent stack, называемый подсчет ссылок (ref-counting)?
# Чем характеризуется подход с использованием сборщика мусора для эффективной работы с памятью в peristent-стэке?
# Каких двух строк не хватает в приведенном псевдокоде операции Push persistent-стэка? S - ссылка на стэк, v - данные для новой вершины. Push(S, v) w = new Node() ... ... return w
# Какие строки лишние в приведенном псевдокоде операции Pop для persistent-стэка? S - ссылка на стэк. Pop(S) w = new Node() w.next = S return S.next
# Какова типичная оценка по времени для наивного алгоритма сортировки?
# Какова оценка по времени для продвинутых алгоритмов сортировки (в худшем или среднем случае)?
# Какие бывают оценки по памяти для алгоритмов сортировки? Выберите наиболее подходящий вариант
# Что означает стабильность алгоритма сортировки?
# Всегда ли свойство стабильности является важным для алгоритма сортировки?
# В каких случаях стабильность алгоритма сортировки важна?
# Как можно описать алгоритм сортировки выбором?
# Какая сложность у алгоритма сортировки выбором?
# Какая сложность у алгоритма сортировки вставками?
# Как можно описать алгоритм сортировки вставками?
# Какая сложность у процедуры слияния для алгоритма сортировки слияием (MergeSort) для массива длины L?
# Для алгоритма сортировки слиянием merge-sort при каком количестве элементов в последовательности рекурсивное деление должно прерываться, в стандартном виде?
# Как описывается алгоритм сортировки слиянием?
# При использовании подхода Bottom-up для алгоритма сортировки слиянием, на блоки какого размера разбивается массив размера n на k-ом шаге?
# Какая сложность у алгоритма сортировки слиянием?
# Сколько требуется дополнительной памяти для стандартного алгоритма сортировки слиянием для массива длины N?
# Как описывается алгоритм быстрой сортировки (quick-sort)?
# По какому признаку отрезок разбивается на две части в алгоритме быстрой сортировки (quick-sort)?
# Сколько дополнительной памяти требуется для работы алгоритма quick-sort?
# Для алгоритма quick-sort при способе разбиения массива на две части, называемым Lomuto Partition, что происходит дальше в такой ситуации: первая просмотренная часть A содержит элементы <= λ, вторая просмотренная часть B содержит элементы >= λ, далее справа находится непросмотренная часть с элементом x вначале, если x >= λ?
# Для алгоритма quick-sort при способе разбиения массива на две части, называемым Lomuto Partition, что происходит дальше в такой ситуации: первая просмотренная часть A содержит элементы <= λ, вторая просмотренная часть B содержит элементы >= λ, далее справа находится непросмотренная часть с элементом x вначале, если x < λ?
# Как можно добиться, чтобы логарифмическая оценка для алгоритма быстрой сортировки была справедлива не в среднем, а в худшем случае?
# Выберите утверждения, характерные для алгоритма быстрой сортировки (quick-sort).
# Какой элемент эффективнее использовать в качестве опорного (λ) для алгоритма быстрой сортировки? Выберите один или несколько вариантов
# Пусть на вход алгоритма быстрой сортировки поступает N различных ключей. Тогда каким будет матожидание времени его работы при случайном равномерном и независимом выборе разделителяя?
# Пусть на вход алгоритма быстрой сортировки поступает N различных ключей. Тогда каким будет матожидание глубины рекурсии?
# Рассмотрим вариацию алгоритма Quick-Sort, детерминированно выбирающего в качестве разделителя первый элемент текущего отрезка. Пусть на вход алгоритму поступает случайная последовательность, в которой все ключи различны, а все их перестановки равновероятны. Тогда каким будет матожидание времени его работы?
# Рассмотрим вариацию алгоритма Quick-Sort, детерминированно выбирающего в качестве разделителя первый элемент текущего отрезка. Пусть на вход алгоритму поступает случайная последовательность, в которой все ключи различны, а все их перестановки равновероятны. Тогда каким будет матожидание глубины рекурсии?
# Какой тип случайности используется для алгоритма Quick-sort, когда какая-либо перестановка подается на вход?
# Какие из перечисленных высказываний относятся к внутреннему типу случайности (internal randomness)?
# Какие из перечисленных высказываний относятся к внешнему типу случайности (external randomness)?
# Какие из перечисленных особенностей относятся к внешнему типу случайности (external randomness)?
# Какие из перечисленных особенностей относятся к внутреннему типу случайности (internal randomness)?
# Что можно сделать для алгоритма Quick-sort, чтобы дерево рекурсии было всегда сбалансированным?
# Отметьте высказывания, характерные для алгоритма слияния, работающего с диском
# Отметьте утверждения, характерные для алгоритма сортировки слиянием (Merge-sort), работающего с памятью на диске
# Что нужно сделать, чтобы алгоритм сортировки слиянием работал без дополнительной памяти?
# Для системы кодирования по Хаффману, что означает безпрефиксный код?
# Каким будет оптимальный порядок бинарного слияния всех отрезков L1,...,Ln различной длины в алгоритме сортировки слиянием?
# Где будет находиться наиболее часто встречающийся символ в дереве кодирования Хаффмана?
# В каком месте дереве Хаффмана будут находиться два символа с наименьшими частотами?
# Какую сумму нужно оптимизировать в задаче оптимизации порядка бинарного слияния всех отрезков L1,...,Ln различной длины? Если pi - глубина i-го листа в дереве слияния
# Какая теоретико - информационная оценка на число сравнений при слиянии двух списков длины N и M, если h <= M?
# Как можно ускорить бинарный поиск, если известно что искомые значения чаще находятся в левом конце отрезка?
# Пусть известна последовательность из n ключей, представленная массивом A. Что называется k-ой порядковой статистикой?
# Какое математическое ожидание времени работы у алгоритма поиска k-ой порядковой статистики (Random-варианта)?
# Модификация какого алгоритма ипользуется для рандомизированного способа поиска порядковой статистики?
# За счет чего происходит оптимизация по времени работы для рандомизированного способа поиска порядковой статистики по сравнению со стандартным алгоритмом быстрого поиска?
# В представленном ниже псевдокоде алгоритма поиска порядковой статистики что находится на пропущенном месте? Random-select(A, k) задать λ ... если k <= |A1|: вернуть Random-select(A1, k) иначе: вернуть Random-select(A2, k - |A1|)
# В представленном ниже псевдокоде алгоритма поиска порядковой статистики что находится на пропущенном месте? Random-select(A, k) задать λ разделить (A, λ) -> (A1, A2) ... вернуть Random-select(A1, k) иначе: вернуть Random-select(A2, k - |A1|)
# В представленном ниже псевдокоде алгоритма поиска порядковой статистики что находится на пропущенном месте? Random-select(A, k) задать λ разделить (A, λ) -> (A1, A2) если k <= |A1|: ... иначе: вернуть Random-select(A2, k - |A1|)
# Какие существуют особенности для алгоритма, который ищет k-ую порядковую статистику за линейное время в худшем случае?
# Для приведенного псевдокода поиска k-ой порядковой статистики, выберите строки, которых не хватает для корректной работы алгоритма: Select (A, k) ... partition(A, λ) -> (A1, A2) if k <= |A1| then: return Select(A1, k) else: return Select(A2, k - |A1|)
# Отметьте слагаемые, которые входят в формулу матожидания времени работы рекурсивного алгоритма для поиска k-ой порядковой статистики
# Что такое куча, каково ее назначение?
# Как можно удалить элемент из кучи?
# В каком месте min-кучи достигается минимум приоритетов е элементов?
# Какое условие должно быть выполнено, чтобы дерево T с вершинами v удовлетворяло свойствам min-кучи? pri(v) - приоритет вершины v
# Какие операции есть в структуре данных куча?
# Для кучи, реализованной поверх массива, у каких операций время работы будет O(1)?
# Для кучи, реализованной поверх массива, у каких операций время работы будет O(N)?
# Что делает операция Decrease-key для кучи?
# Что делает операция Extract-min для кучи?
# Что делает операция Get-min для кучи?
# Какое дерево можно назвать полным бинарным?
# Какое дерево можно назвать почти полным бинарным?
# Для вершины с индексом i какие индексы будут у сыновей вершины?
# Для левого и правого сыновей с индексом i, какие индексы будут у их родителя?
# Как можно построить кучу из N элементов за время O(N)?
# За какое время выполняется операция MakeHeap, то есть построение кучи из набора размером N?
# Какое условие должно выполняться для процедуры просеивания вверх (Sift-up), чтобы текущий элемент продолжал просеивание? Для мин-кучи
# Какая сложность у процедур просеивания для куч (sift-up, sift-down)?
# Какие операции включает в себя процедура вставки (Insert(k)) для кучи?
# Какие операции включает в себя процедура извлечения минимума (Extract-min()) для кучи?
# Для каких операций у k-ичной кучи время работы будет O(k * logk N)?
# Для каких операций у k-ичной кучи время работы будет O(logk N)?
# С помощью какой структуры данных можно реализовать сливаемые очереди с приоритетом?
# Как можно реализовать биномиальную кучу размерности T3?
# Сколько узлов имеет биномиальное дерево Ti?
# Если структуру бинарное дерево размера 5(1012) слить со структурой размера 7(1112) получится структура размера:
# Структура бинарного дерева размера 5(1012) включает в себя:
# Как склеить 2 бинарных дерева T1(с корнем α) и T2(с корнем β), если α <= β?
# За какое время выполняется слияние двух деревьев?
# Как находить минимум в сливаемом бинарном дереве за O(1)?
# За какое время работает операция Insert в бинарном дереве?
# За какое время работает операция Extract-min в бинарном дереве?
# За какое время работает операция Decrease-key в бинарном дереве?
# Чему равен ранг вершины v = Null левацкого дерева?
# Если у левацкого дерева вершина v не равна Null, то чему равен ранг этой вершины?
# Сколько вершин содержится в поддереве любой вершины v?
# Ранг любой вершины кучи с N элементами равен:
# При выполнении какого свойства куча будет называться левацкой?
# Можно ли любую кучу превратить в левацкую, если да, то как?
# Как изменяются ранги вершин при движении по правому пути левацкой кучи?
# Отметьте какие утверждения относятся к левацким кучам
# Отметьте, какие утверждения относятся к операции слияния (Meld) двух левацких куч
# Отметьте какие действия нужно дополнительно совершить на каждом шаге рекурсии для процедуры слияния двух левацких куч, чтобы полученная куча тоже была левацкой
# Какие операции поддерживают левацкие кучи?
# В каком случае вершина v(отличная от корня) называется тяжелой для косой кучи?
# Чему равен вес для вершины v w(v) для косой кучи?
# Какая вершина у косой кучи называется плохой?
# Что называется потенциалом косой кучи?
# Для косой кучи выполняется следующее свойство. В дереве из N вершин на любом пути, идущем вниз, содержится:
# Для косой кучи выполняется следующее свойство. У вершины не может быть:
# Чему равно учетное время выполнения операции Meld для косой кучи?
# Какие существуют основные операции для отображений Map/Dictionary?
# С помощью каких структур данных можно реализовать Map/Dictionary?
# В каких случаях можно использовать прямую адресацию при реализации отображения?
# Какая скорость чтения и записи для отображения, реализованного с помощью прямой адресации?
# Что такое хэш-коллизия?
# Какая хэш-функция называется совершенной?
# Для метода цепочек, использующегося при разрешении коллизий в чем заключается основная идея?
# Какие сложности у операций добавления и извлечения для метода цепочек?
# Для метода открытой адресации при разрешении коллизий, какие действия предпринимаются если ячейка с вставляемым хэш-ключем уже занята?
# Какая формула задает линейный способ просматривания ячеек хэш-таблицы?
# Какая формула задает метод двойного хэширования для просматривания ячеек хэш-таблицы?
# Для метода двойного хэширования, использующегося при разрешении коллизий в чем заключается основная идея?
# Какое предположение должно быть выполнено, чтобы была справедлива гипотеза простого равномерного хэширования?
# Пусть мы выполняем запрос Get для некоторого ключа k и пусть перед этим в структуру были вставлены некоторые ключи k1,...,kn. Для каждого ключа ki обозначим через Xi,j случайную величину, равную 1, если h(ki)=h(kj), и 0 в противном случае. Какая будет длина цепочки с индексом i?
# Для независимых, равномерно распределенных на множестве {0, ..., m1} случайных величин для каждого ключа ki обозначим через Xi,j случайную величину, равную 1, если h(ki)=h(kj), и 0 в противном случае. Чему равно матожидание случайной величины?
# Как вычисляется коэффициент заполнения для равномерно распределенной хэш-функции H: k -> {0,..., N-1}?
# В предположении гипотезы простого равномерного хэширования, чему равно среднее время безуспешного поиска ключа для хэш-функции H: k -> {0,..., N-1}?
# Каким значением ограничена вероятность коллизий для двух различных ключей для универсального семейства хэш-функций H: k -> {0,..., N-1}?
# В случае универсального хэширования чему равно среднее время успешного поиска ключа для хэш-функции H: k -> {0,..., N-1}, если k1, ..., kn - все ключи, присутствующие в хеш-таблице?
# Если использовать универсальное семейство хэш-функций для хранения n ключей, то при размере хэш-таблицы M = n2, какова будет вероятность получить хотя бы одну коллизию?
# Каким должне быть минимальный размер хэш-таблицы, чтобы вероятность получить хотя бы одну коллизию не превосходила 1/2, если n - количество ключей?
# При каких условия можно получить свободную от коллизий хэш-функцию?
# Какие характеристики имеет совершенная хэш-функция?
# Отметьте верные утверждения, относящиеся к семейству универсальных хэш-функций: Ha,b = ((a*k + b) mod p) mod m, b - произвольный вычет
# Как зависит размер памяти, необходимый для реализании метода совершенного хэширования от количества ключей n?
# За какое в среднем количество проб можно обнаружить хэш-функцию, не дающую коллизий для второго уровня схемы совершенного хэширования?
# Пусть на первом уровне схемы совершенного хэширования используется хеш-таблица размера m = n, n - количество ключей. Пусть ni обозначает количество ключей, получивших (на первом уровне) хеш-значение i (0 <= i < m). Тогда если использовать в каждой ячейке первого уровня вышеописанную схему, свободную от коллизий, сколько потребуется дополнительной памяти?
# Что означает ложно-положительное срабатывание для интерфейса множества с ошибками фильтр Блюма?
# Для фильтра Блюма как изменяется вероятность ложного срабатывания с увеличением размера хранимого множества (числа вставленных элементов)?
# Для фильтра Блюма как изменяется вероятность ложного срабатывания если объем памяти, заране заданный пользователем для хранения битового массива, увеличивается?
# Какие существуют стандартные операции для интерфейса множества с ошибками, например для фильтра Блюма?
# Какие допустимы ситуации для односторонней ошибки в интерфейсе множества с ошибками?
# Отметьте верные утверждения, относящиеся к фильтру Блюма
# Как можно проверить, попадает ли ключ k в хэш-таблицу T фильтра Блюма, заданного хэш-функциями h1,...,hs: k -> [0, m-1] или нет?
# Как происходит вставка (Insert(k)) ключа k в таблицу T, реализованную фильтром Блюма?
# Предположим, что мы вставили различные k1,...,kn ключей в хэш-таблицу Блюм-фильтра с помощью хэш-функций h1(k),...,hs(k): k -> [0, m-1]. Какая будет вероятность ложного положительного срабатывания?
# Для Блюм-фильтра, заданного хэш-функциями h1(k),...,hs(k): k -> [0, m-1], какая будет вероятность того, что после вставки n ключей произвольно выбранный бит будет равен False?
# Для Блюм-фильтра, заданного хэш-функциями h1(k),...,hs(k): k -> [0, m-1], какая будет вероятность того, что после вставки n ключей одна хэш-функция выдает значение, отличное от произвольно выбранного бита в таблице?
# При реализации структуры приближенного множества (Lossy Map) с помощью более блюмового фильтра, как будет работать операция Get(k)?
# Предположим, что при реализации структуры приближенное множество (Lossy Map) с помощью более блюмового фильтра функция отображает из ключей в один бит. Как можно реализовать такую структуру?
# При реализации структуры приближенное множество (Lossy Map) с помощью двух Блюм-фильтров (использованных для множеств-прообразов 0 и 1) что нужно сделать, чтобы избежать ситуации, когда при запросе Get(k) оба Блюм-фильтра вернули 1?
# Какие свойства должны быть выполнены для любой вершины v, чтобы дерево являлось бинарным деревом поиска?
# Какие действия включает в себя операция вставки (Insert(x)) в двоичном дереве поиска?
# Какие действия включает в себя операция удаления (Remove(x)) в двоичном дереве поиска?
# Отметьте утверждения, верные для красно-черных деревьев.
# Для n-арного дерева поиска каждой вершине соответствует:
# Какой обход дерева нужно использовать, чтобы ключи двоичного дерева поиска были выведены в порядке неубывания?
# что выдает операция Successor(v)?
# Если в двоичном дереве поиска N вершин, то каким будет время поиска в дереве?
# Какое дерево называется разбалансированным?
# Какую высоту имеет красно-черное дерево с n внутреннеми вершинами (не считая Nil-листьев)?
# За какое время выполняются операции Search, Min, Max, Successor, Predecessor для красно-черного дерева с n вершинами?
# Какие действия предпринимают для сохранения свойств красного черного дерева, если при операции вставки вершины x, x и y оказались красными, если y - родитель x, y - корень?
# Какие действия предпринимают для сохранения свойств красного черного дерева после операции вставки вершины x в следующей ситуации. Если A - родитель x, B - родитель A; B - черная вершина; A, C - красные; C - дядя x
# Какие действия предпринимают для сохранения свойств красного черного дерева, если после операции вставки вершины [Большая Картинка]
# Отметьте верные утверждения, характеризующие операцию splay(x) в splay-дереве
# Отметьте верные утверждения, относящиеся к splay-деревьям
# Есть два дерева T1, T2. При этом все ключи из T1 не больше ключей из T2. Можно ли их склеить в одно дерево, если да, тогда как это сделать?
# Какой тип вращения сплэй-дерева изображен на рисунке? [Большая Картинка]
# Какой тип вращения сплэй-дерева изображен на рисунке? [Большая Картинка]
# Какой тип вращения сплэй-дерева изображен на рисунке? [Большая Картинка]
# Если в splay-дереве есть операция, работающая за O(глубина вершины), можно ли ее ускорить до учетного логарифма, если да то как это сделать?
# В каком случае можно выполить zig-шаг для splay-дерева?
# В каком случае можно выполить zigzig-шаг для splay-дерева?
# Какой будет учетная стоимость zig-шага для операции splay? Если r - ранг, r' - новый ранг, v - вращаемая вершина, u - корень в начале операции
# Какой будет учетная стоимость zigzig-шага для операции splay? Если r - ранг, r' - новый ранг, v - вращаемая вершина, u - корень в начале операции
# Для операции Insert учетная стоимость будет складываться из операции splay и операции вставки. Какое время потребуется на все это?
# Какими свойствами обладают декартовы деревья?
# Алгоритм рекурсивного построения декартвого дерева аналогичен алгоритму:
# За какое время в среднем выполняется поиск ключа в структуре данных дуча (treap)?
# Отметьте верные утверждения, характеризующие декартовы деревья.
# Отметить верные утверждения для операции Merge декартового дерева
# Отметьте верные утверждения для операции Split(T, x) в декартовом дереве.
# Как происходит удаление ключа x из декартового дерева T?
# Как происходит добавление ключа x к декартовому дереву T?
# Отметьте верное утверждение для операции построения дучи
# В каком направлении эффективнее двигаться по дереву для точки вставки очередной новой вершины при построении дучи?
# Отметьте верные утверждения, относящиеся к B-деревьям
# Какие операции есть у B-дерева?
# Отметить верные утверждения для операции вставки в B-дереве
# Как происходит объединение двух деревьев в операции Unite(x, y) для ранговой эвристики? Отметьте верные шаги
# Сколько ключей у вершины B-дерева с d сыновьями?
# Какие значения может принимать α (коэффициент заполнения дерева)?
# Отметьте утверждение, не относящееся к работе операции удаления для B-дерева
# Что делает операция Unite(x, y) в системе непересекающихся множеств?
# Как работает операция Equivalent(x, y)?
# Что делает операция Equivalent(x, y)?
# Какое время работы у операций Unite, Equivalent для ранговой эвристики?
# Для эвристики сжатия путей в чем заключается оптимизация дерева?
# Какого времени работы позволяет достичь применение двух эвристик: сжатия путей и ранговой для операций Unite, Equivalent у системы непересекающихся множеств?