"Продвинутые" алгоритмы для школьников

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

Номер 1

Что такое строка?

Ответ:

(1) набор символов

(2) матрица идентификаторов

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

Номер 2

Что представляет собой строка?

Ответ:

(1) абстрактный тип данных

(2) набор символов

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

Номер 3

Из каких элементов состоит строка?

Ответ:

(1) из символов

(2) из идентификаторов

(3) из обобщений

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

Номер 1

Является ли запись fdlks строкой?

Ответ:

(1) да, является

(2) нет, не является

(3) только для языков программирования

Номер 2

Какие символы может содержать строка?

Ответ:

(1) только буквы латинского алфавита

(2) только цифры

(3) как буквы, так и цифры

Номер 3

Можно ли считать запись e38ff строкой?

Ответ:

(1) нет, нельзя

(2) да, можно

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

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

Номер 1

Что такое префикс строки?

Ответ:

(1) несколько первых символов

(2) длина строки

(3) тип данных строки

Номер 2

Несколько первых символов строки представляют собой

Ответ:

(1) суффикс

(2) префикс

(3) постфикс

Номер 3

Может ли префикс строки быть равен 0?

Ответ:

(1) да, может

(2) нет, не может

(3) только для обобщенных строк

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

Номер 1

Может ли строка быть префиксом самой себя?

Ответ:

(1) нет, это исключено

(2) да, может

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

Номер 2

Что такое суффикс строки?

Ответ:

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

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

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

Номер 3

Несколько последних символов строки представляют собой

Ответ:

(1) суффикс

(2) корень

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

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

Номер 1

Префикс какого-либо суффикса строки называется

Ответ:

(1) метастрокой

(2) подстрокой

(3) гиперстрокой

Номер 2

Подстрока - это

Ответ:

(1) элемент матрицы надежности строки

(2) префикс суффикса строки

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

Номер 3

Несколько символов строки, идущих подряд, представляют собой

Ответ:

(1) подстроку

(2) маркированный суффикс

(3) контейнер

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

Номер 1

Подстрокой любой строки является

Ответ:

(1) бесконечная строка

(2) пустая строка

(3) гиперстрока

Номер 2

Если длина одной строки N, а второй - M, то поиск вхождений строки M в строку N займет времени

Ответ:

(1) O(NM)

(2) O(logM)

(3) O(logN)

Номер 3

За какое время в строке длины N можно найти наибольший префикс, являющийся суффиксом?

Ответ:

(1) O(N)

(2) O(logN)

(3) O(N²)

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

Номер 1

Что такое образец в строке?

Ответ:

(1) подстрока

(2) суффикс

(3) префикс

Номер 2

Подстрока строки носит название

Ответ:

(1) образец

(2) контейнер

(3) маркер

Номер 3

Является ли rt образцом строки dkrtp?

Ответ:

(1) да, является

(2) нет, не является

(3) это контейнер строки

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

Номер 1

Для чего предназначен алгоритм Кнута-Морриса-Прата?

Ответ:

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

(2) для поиска подстроки в строке

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

Номер 2

Для каких из приведенных ниже операций применяется алгоритм Кнута-Морриса-Прата?

Ответ:

(1) поиск подстроки в строке

(2) формирование матрицы достижимости

(3) вывод из ассоциативного массива

Номер 3

Для поиска подстроки в строке можно использовать алгоритм

Ответ:

(1) Флойда-Уоршелла

(2) Кронекера-Капелли

(3) Кнута-Морриса-Прата

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

Номер 1

Каким образом можно увеличить размер сдвига образца?

Ответ:

(1) выводом в ассоциативный массив

(2) запомнив части текста, совпадающие с образцом

(3) сформировав матрицу инцидентности

Номер 3

Увеличение размера сдвига образца

Ответ:

(1) увеличивает скорость алгоритма КМП

(2) уменьшает скорость алгоритма КМП

(3) не изменяет скорость алгоритма КМП

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

Номер 1

Длина наиболее длинного префикса, являющегося одновременно суффиксом - это

Ответ:

(1) суффикс-функция

(2) префикс-функция

(3) постфикс-функция

Номер 2

Префикс-функция зависит

Ответ:

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

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

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

Номер 3

Каким образом определяется префикс-функция?

Ответ:

(1) с помощью префикса

(2) с помощью матрицы инцидентности

(3) с помощью алгоритма Флойда-Уоршелла

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

Номер 1

Дерево, в котором хранятся несколько строк, носит название

Ответ:

(1) лес

(2) бор

(3) массив

Номер 2

Что представляет собой бор?

Ответ:

(1) дерево со строками

(2) контейнер

(3) массив инцидентности

Номер 3

Дерево в бору является

Ответ:

(1) подвешенным

(2) маркированным

(3) комплексным

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

Номер 1

Корнем бора является

Ответ:

(1) гиперстрока

(2) пустая строка

(3) симплекс-строка

Номер 2

Из приведенных ниже записей выделите элементы ассоциативного массива:

Ответ:

(1) ключ

(2) ссылка

(3) значение

Номер 3

Верно ли, что ассоциативный массив не может хранить две пары с одинаковыми ключами?

Ответ:

(1) да, это верно

(2) нет, это неверно

(3) только для маркированных массивов

"Продвинутые" алгоритмы для школьников - тест 9