игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Алгоритмы и структуры данных поиска / Тест 12

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

Упражнение 1:
Номер 1 
Какая структура данных используется для решения задач, связанных с интервалами?

Ответ:

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

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

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

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

Номер 2 
Какая основная идея применяется для решения задач, связанных с интервалами, с помощью статической структуры данных?

Ответ:

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

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

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

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

Номер 3 
При построении дерева интервалов какие интервалы попадут в корень дерева?

Ответ:

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

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

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

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

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

Ответ:

 (1) на k частей, заранее определенных 

 (2) на 2 части 

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

 (4) на 4 части 

Упражнение 2:
Номер 1 
Какую глубину имеет дерево интервалов? Если N - количество интервалов

Ответ:

 (1) O(N) 

 (2) O(log N) 

 (3) O(N2) 

 (4) O(N * log N) 

Номер 2 
Какой прием можнно использовать, чтобы эффективнее искать интервалы, пересекающие заданную точку с помощью статической структуры данных?

Ответ:

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

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

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

Номер 3 
Сколько стоит по времени поиск интервалов, пересекающих заданную точку?

Ответ:

 (1) O(N) 

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

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

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

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

Ответ:

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

 (2) по левым границам интервалов 

 (3) по левым и правым границам интервалов 

 (4) по длинам интервалов 

 (5) по удаленности от разделяющей точки 

Номер 5 
Для асимметричного способа построения дерева интервалов в каком случае поиск интервалов, пересекающихся с точкой x нужно вести в левом поддереве? Если x > l для интервала [l, r] в корне

Ответ:

 (1) x < max(i∈α) ri, αi = [li, ri] - интервалы в левом поддереве 

 (2) x > max(i∈α) ri, αi = [li, ri] - интервалы в левом поддереве 

 (3) x > min(i∈β) li, βi = [li, ri] - интервалы в правом поддереве 

 (4) x > min(i∈β) ri, αi = [li, ri] - интервалы в левом поддереве 

Упражнение 3:
Номер 1 
Если откладывать одномерные интервалы [l, r] на двумерной плоскости, то в какой области будут находиться интервалы, пересекаемые с точкой x?

Ответ:

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

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

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

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

Номер 2 
Какая структура данных может искать точки в "колодце"(двустороннее ограничение по одной координате и одностороннее ограничение по другой координате)?

Ответ:

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

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

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

 (4) куча 

Номер 3 
Для структуры дерева поиска, используемой для интервальной задачи поиска точки в "колодце", что будет находиться в корне дерева?

Ответ:

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

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

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

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

Номер 4 
Отметить НЕверные шаги алгоритма priority search tree, работающего на области поиска в виде "колодца", заданного следующим образом: [l1, l2] x [r1, +∞]?

Ответ:

 (1) ищем такие поддеревья что все точки в них попадают в отрезок [l1, l2] по l координатам 

 (2) для найденных поддеревьев по l координатам ищем по r координатам в них 

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

 (4) если r в вершине меньше чем r1, то в поддеревьях ничего не найдём, останавливаемся 

 (5) если r в вершине больше чем r1, то идём в одно из поддеревьев 

Упражнение 4:
Номер 1 
По каким критериям выбирается разделитель, делящий на левые и правые поддеревья в приоритетном дереве поиска (priority search tree)?

Ответ:

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

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

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

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

Номер 2 
Какое время поиска у приоритетного дерева поиска (priority search tree)?

Ответ:

 (1) O(log N) 

 (2) O(log N + k) 

 (3) O(log N * k) 

 (4) O(N + k) 

Номер 3 
Какое время построения у приоритетного дерева поиска (priority search tree)?

Ответ:

 (1) O(N2) 

 (2) O(N * log N) 

 (3) O(log N) 

 (4) O(N) 

Номер 4 
При каком значении [l0, r0] в корне дерева Prirority Search Tree не имеет смысла дальше искать в дереве, если область "колодца" задаётся так: [l1, r1] x [r1, +∞]?

Ответ:

 (1) l0 > l1, r0 > r1 

 (2) r0 < r1, точка находится ниже дна "колодца" 

 (3) l0 < l2, r0 > r1 

 (4) l0 < l1, r0 > r1 

Упражнение 5:
Номер 1 
Какой размер имеет структура данных приоритетное дерево поиска?

Ответ:

 (1) O(N2) 

 (2) O(N * log N) 

 (3) O(log N) 

 (4) O(N) 

Номер 2 
Если корень приоритетного дерева поиска выбирается по минимальной r координате отрезка [l, r], то по каким параметрам происходит деление на левые и правые поддеревья?

Ответ:

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

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

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

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

Номер 3 
Что такое канонический отрезок в дереве отрезков?

Ответ:

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

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

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

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

Упражнение 6:
Номер 1 
В чём состоит идея оптимизации в структуре двумерное дерево отрезков для задачи поиска в квадратичной области, позволяющая достичь времени работы O(log N)?

Ответ:

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

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

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

Номер 2 
Что такое каскады в структуре Fractional cascading?

Ответ:

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

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

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

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

Номер 3 
За счёт чего происходит оптимизация у структуры Fractional cascading?

Ответ:

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

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

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

Упражнение 7:
Номер 1 
Какая память необходима для двумерного дерева отрезков?

Ответ:

 (1) O(N) 

 (2) O(N * log N) 

 (3) O(N2) 

 (4) O(log2 N) 

Номер 2 
Какое время поиска у структуры данных двумерное дерево отрезков, работающей с квадратной области поиска [x1, x2] x [y1, y2]?

Ответ:

 (1) O(N) 

 (2) O(log2 N) 

 (3) O(N2) 

 (4) O(log N) 

Номер 3 
Можно ли узнать заранее размер ответа, то есть сколько будет в ответе "хороших" точек, используя структуру PST для интервальной задачи?

Ответ:

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

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

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

Упражнение 8:
Номер 1 
Какие указатели должны быть в дереве отрезков, работающим за O(log N) по принципу Fractional cascading?

Ответ:

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

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

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

Номер 2 
Пусть есть k списков: L1,...,Lk. В чем заключается задача fractional cascading?

Ответ:

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

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

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

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

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

Ответ:

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

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

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

Упражнение 9:
Номер 1 
Какие действия должна уметь выполнять структура данных для задачи о динамической связности в графах? Для полностью динамического случая

Ответ:

 (1) ChangeEdge 

 (2) AddEdge 

 (3) RemoveEdge 

 (4) Connected 

 (5) FindEdge 

Номер 2 
Какие действия должна уметь выполнять структура данных для задачи о динамической связности в графах? Для инкрементальной связности

Ответ:

 (1) ChangeEdge 

 (2) AddEdge 

 (3) RemoveEdge 

 (4) Connected 

 (5) FindEdge 

Номер 3 
Какие действия должна уметь выполнять структура данных для задачи о динамической связности в графах? Для декрементальной связности

Ответ:

 (1) ChangeEdge 

 (2) AddEdge 

 (3) RemoveEdge 

 (4) Connected 

 (5) FindEdge 

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

Ответ:

 (1) Insert() 

 (2) Split(α, i) = β, γ, α - список, i - разделитель; β, γ - два новых списка 

 (3) Concat(α, β) = γ - объединить списки α, β в новый список γ 

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

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

Ответ:

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

 (2) оффлайн 

 (3) онлайн 

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

Номер 2 
Какой тип имеет задача о динамической связности в графе, если ответы выдаются сразу после выполнения различных действий с графом и поступления запроса о связности?

Ответ:

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

 (2) оффлайн 

 (3) онлайн 

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

Номер 3 
Какое время занимает каждое изменение в динамически полном графе для онлайн версии?

Ответ:

 (1) O(log N) 

 (2) O(log2 N) 

 (3) O(N * log N) 

 (4) O(N) 

 (5) O(1) 

Упражнение 11:
Номер 1 
Если задача такова, что в графе нет и не может быть циклов, то что можно сказать о ней?

Ответ:

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

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

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

Номер 2 
Если исходное дерево без выделенного корня, то можно ли его сделать Эйлеровым графом?

Ответ:

 (1) нет 

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

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

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

Номер 3 
Какая структура подойдет для реализации динамически полного связного графа?

Ответ:

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

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

 (3) RMQ 

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

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

Упражнение 12:
Номер 1 
Какой обход является конкатенацией двух исходных обходов в операциях со списками для структуры Rope, реализующей динамически связный граф?

Ответ:

 (1) Pre-order 

 (2) In-order 

 (3) Post-order 

Номер 2 
Что такое остовный лес в графе?

Ответ:

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

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

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

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

Номер 3 
За какое время можно тестировать связаность в графе, если поддерживать для него остовный лес?

Ответ:

 (1) O(log N) 

 (2) O(log2 N) 

 (3) O(N * log N) 

 (4) O(N) 

Номер 4 
Какой размер должны иметь связные компоненты для графа Gi уровня i с n вершинами?

Ответ:

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

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

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

Упражнение 13:
Номер 1 
Какими свойствами должны обладать леса в остовном лесе?

Ответ:

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

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

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

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

Номер 2 
Каким образом нужно преобразовать граф, чтобы получить лес?

Ответ:

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

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

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

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

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

Номер 3 
Как производится вставка в динамический полный граф? Отметьте верные шаги

Ответ:

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

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

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

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

Упражнение 14:
Номер 1 
Если до вставки нового ребра E его вершины u и v находились в разных компонентах связности, какие действия предпринимают, чтобы сохранить структуру динамически связного графа?

Ответ:

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

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

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

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

Номер 2 
Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то что это значит для структуры динамически связного графа?

Ответ:

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

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

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

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

Номер 3 
Если удаляемого ребра не было в остовном лесе нулевого уровня в графе, то что это значит для структуры динамически связного графа?

Ответ:

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

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

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

Упражнение 15:
Номер 1 
Если удаляемое ребро имеет уровень i = l(u, v) то на каких уровнях леса оно лежит?

Ответ:

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

 (2) от F0 до Fi 

 (3) только Fi 

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

Номер 2 
Если при удалении ребра оказалось что оно находилось в остовном лесе, то что это значит?

Ответ:

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

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

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

Номер 3 
Какое время работы операции удаления в динамически полном связном онлайн графе?

Ответ:

 (1) O(log N) 

 (2) O(log2 N) 

 (3) O(N * log N) 

 (4) O(N) 

Номер 4 
Какое время работы операции вставки в динамически полном связном онлайн графе?

Ответ:

 (1) O(log N) 

 (2) O(log2 N) 

 (3) O(N * log N) 

 (4) O(N) 



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