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

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

Номер 1

Какие свойства должны быть выполнены для любой вершины v, чтобы дерево являлось бинарным деревом поиска?

Ответ:

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

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

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

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

Номер 2

Какие действия включает в себя операция вставки (Insert(x)) в двоичном дереве поиска?

Ответ:

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

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

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

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

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

Номер 3

Какие действия включает в себя операция удаления (Remove(x)) в двоичном дереве поиска?

Ответ:

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

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

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

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

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

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

Номер 4

Отметьте утверждения, верные для красно-черных деревьев.

Ответ:

(1) все листья черные

(2) если у красного родителя два сына, то их цвета черные

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

(4) у черных вершин все дети красные

(5) каждая вершина либо красная, либо черная

(6) красно-черные деревья сбалансированны

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

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

Номер 1

Для n-арного дерева поиска каждой вершине соответствует:

Ответ:

(1) 1 ключ

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

(3) n ключей

Номер 2

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

Ответ:

(1) Pre-order обход

(2) In-order обход

(3) Post-order обход

Номер 3

что выдает операция Successor(v)?

Ответ:

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

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

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

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

Номер 4

Если в двоичном дереве поиска N вершин, то каким будет время поиска в дереве?

Ответ:

(1) O(N)

(2) O(log N)

(3) O(1)

(4) O(N * log N)

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

Номер 1

Какое дерево называется разбалансированным?

Ответ:

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

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

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

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

Номер 2

Какую высоту имеет красно-черное дерево с n внутреннеми вершинами (не считая Nil-листьев)?

Ответ:

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

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

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

(4) не менее n

Номер 3

За какое время выполняются операции Search, Min, Max, Successor, Predecessor для красно-черного дерева с n вершинами?

Ответ:

(1) O(N)

(2) O(log N)

(3) O(1)

(4) O(N²)

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

Номер 1

Какие действия предпринимают для сохранения свойств красного черного дерева, если при операции вставки вершины x, x и y оказались красными, если y - родитель x, y - корень?

Ответ:

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

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

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

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

Номер 2

Какие действия предпринимают для сохранения свойств красного черного дерева после операции вставки вершины x в следующей ситуации. Если A - родитель x, B - родитель A; B - черная вершина; A, C - красные; C - дядя x

Ответ:

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

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

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

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

Номер 3

Какие действия предпринимают для сохранения свойств красного черного дерева, если после операции вставки вершины x получилось следующее. y - родитель x, z - черный родитель y; t - черный сын z, дядя x

Ответ:

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

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

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

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

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

Номер 1

Отметьте верные утверждения, характеризующие операцию splay(x) в splay-дереве

Ответ:

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

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

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

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

Номер 2

Отметьте верные утверждения, относящиеся к splay-деревьям

Ответ:

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

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

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

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

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

Номер 3

Есть два дерева T₁, T₂. При этом все ключи из T₁ не больше ключей из T₂. Можно ли их склеить в одно дерево, если да, тогда как это сделать?

Ответ:

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

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

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

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

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

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

Номер 1

Какой тип вращения сплэй-дерева изображен на рисунке?

Ответ:

(1) zig-zig

(2) zig

(3) zig-zag

Номер 2

Какой тип вращения сплэй-дерева изображен на рисунке?

Ответ:

(1) zig-zig

(2) zig

(3) zig-zag

Номер 3

Какой тип вращения сплэй-дерева изображен на рисунке?

Ответ:

(1) zigzig

(2) zig

(3) zigzag

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

Номер 1

Если в splay-дереве есть операция, работающая за O(глубина вершины), можно ли ее ускорить до учетного логарифма, если да то как это сделать?

Ответ:

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

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

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

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

Номер 2

В каком случае можно выполить zig-шаг для splay-дерева?

Ответ:

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

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

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

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

Номер 3

В каком случае можно выполить zigzig-шаг для splay-дерева?

Ответ:

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

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

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

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

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

Номер 1

Какой будет учетная стоимость zig-шага для операции splay? Если r - ранг, r' - новый ранг, v - вращаемая вершина, u - корень в начале операции

Ответ:

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

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

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

(4) ≤ 4

Номер 2

Какой будет учетная стоимость zigzig-шага для операции splay? Если r - ранг, r' - новый ранг, v - вращаемая вершина, u - корень в начале операции

Ответ:

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

Номер 3

Для операции Insert учетная стоимость будет складываться из операции splay и операции вставки. Какое время потребуется на все это?

Ответ:

(1) O(N)

(2) O(N * log N)

(3) O(log N)

(4) O(1)

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

Номер 1

Какими свойствами обладают декартовы деревья?

Ответ:

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

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

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

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

Номер 2

Алгоритм рекурсивного построения декартвого дерева аналогичен алгоритму:

Ответ:

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

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

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

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

Номер 3

За какое время в среднем выполняется поиск ключа в структуре данных дуча (treap)?

Ответ:

(1) O(1)

(2) O(log N)

(3) O(N)

(4) O(N²)

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

Номер 1

Отметьте верные утверждения, характеризующие декартовы деревья.

Ответ:

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

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

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

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

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

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

Номер 2

Отметить верные утверждения для операции Merge декартового дерева

Ответ:

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

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

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

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

Номер 3

Отметьте верные утверждения для операции Split(T, x) в декартовом дереве.

Ответ:

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

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

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

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

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

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

Номер 1

Как происходит удаление ключа x из декартового дерева T?

Ответ:

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

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

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

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

Номер 2

Как происходит добавление ключа x к декартовому дереву T?

Ответ:

(1) выполняется Split(T, x), получаем T₁, T₂, вершину (x, p), p - приоритет, x - ключ. Выполняется Merge(T₁, (x, p)) = T_1x. Выполняется Merge(T_1x, T₂)

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

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

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

Номер 3

Отметьте верное утверждение для операции построения дучи

Ответ:

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

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

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

Номер 4

В каком направлении эффективнее двигаться по дереву для точки вставки очередной новой вершины при построении дучи?

Ответ:

(1) сверху вниз

(2) снизу вверх

(3) слева направо

(4) это не важно

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

Номер 1

Отметьте верные утверждения, относящиеся к B-деревьям

Ответ:

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

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

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

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

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

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

Номер 2

Какие операции есть у B-дерева?

Ответ:

(1) Get(x)

(2) Insert(x)

(3) Remove(x)

(4) Find(x)

(5) Get-min/Get-max

Номер 3

Отметить верные утверждения для операции вставки в B-дереве

Ответ:

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

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

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

Номер 4

Как происходит объединение двух деревьев в операции Unite(x, y) для ранговой эвристики? Отметьте верные шаги

Ответ:

(1) сначала находим корни соответствующих поддеревьев x' и y'. Если они равны, элементы x и y уже содержатся в одном множестве

(2) для объединения деревьев T_x (содержащего x) и T_y (содержащего y) в одно дерево добавляют дугу между ними

(3) если высота дерева T_x (содержащего x) меньше чем высота T_y (содержащее y), то следует выполнить p(y') = x'. x', y' - корни соответствующих поддеревьев, p - родитель. Иначе p(x') = y'

(4) если r(x') = r(y') (высоты деревьев равны), то выполняется p(x') = y', иначе p(y') = x'

(5) значения высот поддеревьев вычисляются каждый раз заново в процессе работы

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

Номер 1

Сколько ключей у вершины B-дерева с d сыновьями?

Ответ:

(1) d

(2) d-1

(3) d+1

(4) 2*d

(5) 1

Номер 2

Какие значения может принимать α (коэффициент заполнения дерева)?

Ответ:

(1) от 1/2 до 1

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

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

(4) от 0 до 1/2

Номер 3

Отметьте утверждение, не относящееся к работе операции удаления для B-дерева

Ответ:

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

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

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

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

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

Номер 1

Что делает операция Unite(x, y) в системе непересекающихся множеств?

Ответ:

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

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

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

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

Номер 2

Как работает операция Equivalent(x, y)?

Ответ:

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

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

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

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

Номер 3

Что делает операция Equivalent(x, y)?

Ответ:

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

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

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

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

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

Номер 1

Какое время работы у операций Unite, Equivalent для ранговой эвристики?

Ответ:

(1) O(N)

(2) O(log N)

(3) O(N * log N)

(4) O(1)

Номер 2

Для эвристики сжатия путей в чем заключается оптимизация дерева?

Ответ:

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

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

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

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

Номер 3

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

Ответ:

(1) O(log N)

(2) O(log*n)

(3) O(1)

(4) O(N)

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