ФИТ ИС Алгоритмы и структуры данных (аттестация) 360
.doc
|
M16E1T60 |
Строковые алгоритмы и дополнительные алгоритмы |
|
V1 |
Для чего используется алгоритм Бойера – Мура? |
|
1 |
Для поиска подстроки в строке |
|
|
Для умножения матриц |
|
|
Для нахождения НОД |
|
|
Для обхода дерева |
|
|
Для вычисления определенного интеграла |
|
V2 |
Для чего используется алгоритм Кнута – Морриса – Пратта? |
|
1 |
Для поиска подстроки в строке |
|
|
Для умножения матриц |
|
|
Для нахождения НОД |
|
|
Для обхода дерева |
|
|
Для вычисления определенного интеграла |
|
V3 |
Для чего используется алгоритм Рабина-Карпа? |
|
1 |
Для поиска подстроки в строке |
|
|
Для умножения матриц |
|
|
Для нахождения НОД |
|
|
Для обхода дерева |
|
|
Для вычисления определенного интеграла |
|
V4 |
Как ведется поиск подстроки в строке в алгоритме Кнута-Морриса-Пратта? |
|
1 |
С начала строки, с начала подстроки |
|
|
С начала строки, с конца подстроки |
|
|
С конца строки, с начала подстроки |
|
|
С конца строки, с конца подстроки |
|
|
С середины строки, с середины подстроки |
|
V5 |
В каком алгоритме поиска подстроки в строке производится предварительная обработка искомой строки? |
|
1 |
В алгоритме Кнута-Морриса-Пратта |
|
|
В алгоритме Боера – Мура |
|
|
В стандартном алгоритме |
|
|
Во всех алгоритмах |
|
|
Ни в каком алгоритме |
|
V6 |
Для какой строки поиска в алгоритме Кнута-Морриса-Пратта сравнений символов исходной строки с символами искомой строки будет меньше, чем в стандартном алгоритме? |
|
1 |
abcab |
|
|
abcde |
|
|
abcdd |
|
|
abccc |
|
|
abbbb |
|
V7 |
За счет чего алгоритм Кнута-Морриса-Пратта по поиску в строке подстроки работает быстрее стандартного алгоритма? |
|
1 |
За счет более длинных сдвигов искомой подстроки вдоль исходной строки |
|
|
За счет исключения из исходной строки стоп-символов |
|
|
За счет отказа от рекурсии |
|
|
За счет хранения строк в ОЗУ вместо внешней памяти |
|
|
За счет более скоростного процессора |
|
V8 |
Сложность алгоритма Кнута-Морриса-Пратта |
|
1 |
Линейно зависит от длины исходной строки |
|
|
Квадратично зависит от длины исходной строки |
|
|
Кубически зависит от длины исходной строки |
|
|
Логарифмически зависит от длины исходной строки |
|
|
Никак не зависит от длины исходной строки |
|
V9 |
В каком алгоритме используется понятие Стоп-символ? |
|
1 |
В алгоритме Боера – Мура |
|
|
В алгоритме Винограда |
|
|
В линейном алгоритме |
|
|
В алгоритме перебора |
|
|
В алгоритме построения выпуклой оболочки |
|
V10 |
В каком алгоритме используется понятие Безопасный суффикс? |
|
1 |
В алгоритме Боера – Мура |
|
|
В алгоритме Винограда |
|
|
В линейном алгоритме |
|
|
В алгоритме перебора |
|
|
В алгоритме построения выпуклой оболочки |
|
V11 |
При поиске подстроки алгоритмом Боера-Мура где находится стоп-символ? |
|
1 |
В исходной строке |
|
|
В искомой подстроке |
|
|
В исходной строке и в искомой подстроке одновременно |
|
|
В безопасном суффиксе |
|
|
В цикле |
|
V12 |
При поиске подстроки алгоритмом Боера-Мура где находится безопасный суффикс? |
|
1 |
В исходной строке и в искомой подстроке одновременно |
|
|
В начале исходной строки |
|
|
В начале искомой строки |
|
|
В середине искомой строки |
|
|
Перед стоп-символом |
|
V13 |
Каково минимальное число сравнений символов про неудачном поиске в 10-символьной строке 5-символьной подстроки алгоритмом Боера-Мура? |
|
1 |
2 |
|
|
10 |
|
|
5 |
|
|
1 |
|
|
0 |
|
V14 |
Каково минимальное число сравнений символов про удачном поиске в 10-символьной строке 5-символьной подстроки алгоритмом Боера-Мура? |
|
1 |
5 |
|
|
10 |
|
|
2 |
|
|
1 |
|
|
0 |
|
V15 |
Сколько сравнений будет произведено для получения результата при поиске в строке “123456789” подстроки “ABC” алгоритмом Боера – Мура |
|
1 |
3 |
|
|
1 |
|
|
2 |
|
|
4 |
|
|
5 |
|
V16 |
Сколько сравнений будет произведено для получения результата при поиске в строке “123456789” подстроки “456” алгоритмом Боера – Мура |
|
1 |
4 |
|
|
1 |
|
|
2 |
|
|
3 |
|
|
5 |
|
V17 |
Какой алгоритм поиска подстрок использует хеш-функцию? |
|
1 |
Рабина-Карпа |
|
|
Кнута-Морриса-Пратта |
|
|
Боера-Мура |
|
|
Стандартный |
|
|
Никакой |
|
V18 |
В каком алгоритм поиска в строке подстроки на подстроку смотрят как на число в X-ричной системе счисления (где X – количество символов в используемом алфавите) ? |
|
1 |
В алгоритме Рабина-Карпа |
|
|
В алгоритме Кнута-Морриса-Пратта |
|
|
В алгоритме Боера-Мура |
|
|
В стандартном алгоритме |
|
|
Во всех алгоритмах |
|
V19 |
Что активно использутся при построении выпуклой оболочки? |
|
1 |
Поиск минимума |
|
|
Умножение матриц |
|
|
Нахождение простых чисел |
|
|
Нахождение факториала |
|
|
Нахождение НОД |
|
V20 |
К какому разделу относится алгоритм построения выпуклой оболочки? |
|
1 |
Вычислительная геометрия |
|
|
Вычислительная алгебра |
|
|
Вычислительная техника |
|
|
Алгоритмы поиска |
|
|
Линейные алгоритмы |
|
V21 |
В чем суть метода решета? |
|
1 |
Метод решета рассматривает конечное множество возможных решений и исключает из него все элементы, не представляющие интереса |
|
|
Метод решета рассматривает пустое множество возможных решений и добавляет к нему все элементы, представляющие интерес |
|
|
Метод решета рассматривает непустое множество возможных решений и добавляет к нему или исключает из него определенные элементы |
|
|
Метод решета должен использовать процедуры |
|
|
Метод решета должен использовать функции |
|
V22 |
Сколько элементов в однонаправленном кольцевом списке может иметь пустое (NIL) значение ссылки? |
|
1 |
0 |
|
|
1 |
|
|
2 |
|
|
Все элементы |
|
|
Не более половины элементов |