Алгоритмы: построение и анализ

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

Номер 1

С помощью чего можно решать задачу поиска образца в наборе строк?

Ответ:

(1) хеш таблиц

(2) суффиксных деревьев

(3) венгерского алгоритма

(4) жадного алгоритма

(5) конечных автоматов

Номер 2

Конечный автомат решающий задачу поиска образца в наборе строк не допускает слово если ...

Ответ:

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

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

(3) он просмотрел все слово, но еще не спустился до листовой вершины в дереве своих состояний

(4) он спустился до листовой вершины в дереве своих состояний, но еще не просмотрел все слово

Номер 3

Конечный автомат решающий задачу поиска образца в наборе строк длины которых  работает за время

Ответ:

(1)

(2)

(3)

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

Номер 1

Построим бор по словам "good","bad","bed","better". Какое утверждение верно?

Ответ:

(1) в боре 5 листовых вершин

(2) глубина бора равна 6

(3) у корня 2 потомка

Номер 2

Построим бор по словам "good","bad","bed","better". Какое утверждение верно?

Ответ:

(1) в боре 4 листовых вершин

(2) глубина бора равна 6

(3) у корня 4 потомка

Номер 3

Построим бор по словам "good","bad","bed","better". Какое утверждение верно?

Ответ:

(1) в боре 5 листовых вершин

(2) глубина бора равна 7

(3) у корня 4 потомка

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

Номер 1

Для того чтобы решать задачу поиска подстроки в тексте, нужно построить ...

Ответ:

(1) бор всех суффиксов

(2) бор всех подслов

(3) бор всех префиксов

Номер 2

Для того чтобы построить бор по слову длины n надо ...

Ответ:

(1) O(n³) операций

(2) O(n²) операций

(3) O(n*log n ) операций

Номер 3

Для того чтобы хранить бор для слова длины n надо

Ответ:

(1) O(n³) памяти

(2) O(n²) памяти

(3) O(n*log n ) памяти

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

Номер 1

Какие утверждения верны?

Ответ:

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

(2) каждой листовой вершине в боре соответствует суффикс в исходном слове

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

(4) число вершин в боре не меньше числа суффиксов в исходном слове

Номер 2

Какие утвеждения верны?

Ответ:

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

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

(3) суффиксная ссылка из вершины для строки s, ведет в вершину для строки соответствующей наиьольшему собственному суффиксу s

Номер 3

Сколько суффиксных ссылок в боре на n вершинах?

Ответ:

(1) n

(2) 2*n

(3) n-1

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

Номер 1

Пусть мы имеем бор для строки "abc", и хотим из него получить бор для строки "abca"

Ответ:

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

(2) тогда нужно добавить 4 вершины и 5 суффиксных ссылок

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

Номер 2

Пусть мы имеем бор для строки "abca", и хотим из него получить бор для строки "abcad"

Ответ:

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

(2) тогда нужно добавить 4 вершины и 5 суффиксных ссылок

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

Номер 3

Пусть мы имеем бор для строки "aba", и хотим из него получить бор для строки "abaa"

Ответ:

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

(2) тогда нужно добавить 4 вершины и 5 суффиксных ссылок

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

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

Номер 1

Какие утверждения верны для сжатого суффиксного бора?

Ответ:

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

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

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

(4) на ребрах записаны два числа - начало и конец подслова в исходном слове

Номер 2

Пусть у нас усть суффиксное дереводля слова s1 на очередном шаге мы добавляем один символ и строим суффиксное дерево для слова s2. Тогда вершине "end point" соответствеут ...

Ответ:

(1) наибольший суффикс слова s2, являющийся суффиксом s1

(2) наибольший суффикс слова s2 являющийся подсловом s1

(3) наибольший суффикс слова s2, являющийся префиксом s1

Номер 3

Вершина "dummy" добавляется для того чтобы ...

Ответ:

(1) не писать лишние if в коде алгоритма

(2) усложнить алгоритм

(3) увеличить высоту дерева

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

Номер 1

Что понимается под неявной вершиной?

Ответ:

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

(2) дополнительная вершина над корнем

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

Номер 2

По какой формуле можно посчитать количество неявных вершин в суффиксом дереве для слова s

Ответ:

(1) (количество символов в s) - (количество вершин в дереве) + (+2 из-за dummy и корня)

(2) (количество символов в s) - (количество ребер в дереве) + (+2 из-за dummy и корня)

(3) (количество символов в s) - (количество ребер в дереве)

(4) (количество символов в s) - (количество вершин в дереве)

Номер 3

Какие вершины являются явными?

Ответ:

(1) корень

(2) dummy

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

(4) листовые вершины

(5) вершины дерева у которых два и более ребенка

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

Номер 1

Из какой вершины может идти суффиксная ссылка в неявную вершину?

Ответ:

(1) из вершины у которой два сына

(2) из неявной вершины

(3) из листовой вершины

Номер 2

Проблема суффиксных ссылок из листьев в неявные вершины решается с помощью

Ответ:

(1) добавления этих неявных вершин в дерево

(2) отказа от суффиксных ссылок в листьях

(3) добавления ссылок на фиктивные вершины

Номер 3

В каком порядке идут вершины в "boundary-path"?

Ответ:

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

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

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

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

Номер 1

Как называется первая нелистовая вершина в "boundary-path"?

Ответ:

(1) end point

(2) active point

(3) root

Номер 2

Где использутся символ бесконечности?

Ответ:

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

(2) в неявных вершинах

(3) в листьях

Номер 3

Что позволяет символ бесконечности?

Ответ:

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

(2) быстро просматривать листья

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

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

Номер 1

Какое утверждение верно?

Ответ:

(1) end point k-го шага это родитель active point (k+1)-го шага

(2) active point k-го шага это родитель end point (k+1)-го шага

(3) end point k-го шага это родитель active point k-го шага

Номер 2

Какое утверждение верно?

Ответ:

(1) active point и end point это два названия одного и того же объекта

(2) active point и end point никогда не совпадают

(3) active point и end point могут совпадать

Номер 3

В алгоритме Укконена при добавлении нового символа

Ответ:

(1) просматривается весь новый boundary-path

(2) просматривается только та часть boundary-path, которая идет после active point

(3) просматривается только та часть boundary-path, которая идет между active point и end point

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

Номер 1

Пусть явная вершина v соответствует суффиксу abc, тогда reference pair для суффикса abcde это

Ответ:

(1) (v, abcde)

(2) (v, de)

(3) (abc, de)

Номер 2

Пусть (v, de) это reference pair для префикса abcde, тогда

Ответ:

(1) v - это явная вершина

(2) префиксу abcde соответствует явная вершина

(3) v соответствует префиксу abc

(4) v соответствует префиксу abcde

Номер 3

Какие утверждения верны?

Ответ:

(1) для каждого суффикса существует единственная reference pair

(2) для каждого суффикса существует единственная каноническая reference pair

(3) reference pair существует только для неявных вершин

(4) reference pair существует для всех вершин

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

Номер 1

Время работы алгоритма Укконена для входного слова длины n равно

Ответ:

(1) O(n)

(2) O(n²)

(3) O(n * log n)

Номер 2

Память необходимая для хранения суффиксного дерева для входного слова длины n из алфавита мощности m равна

Ответ:

(1) O(n*m)

(2) O(n²)

(3) O(n)

Номер 3

Память необходимая для хранения суффиксного массива для входного слова длины n из алфавита мощности m равна

Ответ:

(1) O(n*m)

(2) O(n²)

(3) O(n)

Алгоритмы: построение и анализ - тест 9