ФИТ ИС Алгоритмы и структуры данных (аттестация) 360

M13E1T60

Строковые алгоритмы

V1

Для чего используется алгоритм Бойера – Мура?

1

Для поиска подстроки в строке

Для поиска простых чисел

Для нахождения числа Пи

Для раскраски графа

Для построения выпуклой оболочки

V2

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

1

Для поиска подстроки в строке

Для нахождения простых чисел

Для нахождения числа Пи

Для раскраски графа

Для построения выпуклой оболочки

V3

Для чего используется алгоритм Рабина?

1

Для поиска подстроки в строке

Для нахождения простых чисел

Для нахождения числа Пи

Для раскраски графа

Для построения выпуклой оболочки

V4

Как ведется поиск подстроки в строке в алгоритме Боера – Мура?

1

С начала строки, с конца подстроки

С начала строки, с начала подстроки

С конца строки, с начала подстроки

С конца строки, с конца подстроки

С середины строки, с середины подстроки

V5

В каком алгоритме используется понятие Безопасный суффикс?

1

В алгоритме Боера – Мура

В алгоритме Эратосфена

В алгоритме Евклида

В алгоритме Кнута – Морриса – Пратта

В алгоритме Рабина

V6

В каком алгоритме используется понятие Стоп-символ?

1

В алгоритме Боера – Мура

В алгоритме Эратосфена

В алгоритме Евклида

В алгоритме Кнута – Морриса – Пратта

В алгоритме Рабина

V7

При поиске в строке "Пригородные кассы" строки "Новгород" алгоритмом Боера – Мура что является безопасным суффиксом?

1

"город"

"род"

"горо"

"Пригород"

"При"

V8

При поиске в строке "Пригородные кассы" строки "Новгород" алгоритмом Боера – Мура что является стоп-символом?

1

"и"

"в"

"ы"

"П"

"д"

V9

В каком алгоритме используется понятие Стоп-символ?

1

В алгоритме Боера – Мура

В алгоритме Эратосфена

В алгоритме Евклида

В алгоритме Кнута – Морриса – Пратта

В алгоритме Рабина

V10

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

1

С начала строки, с начала подстроки

С начала строки, с конца подстроки

С конца строки, с начала подстроки

С конца строки, с конца подстроки

С середины строки, с середины подстроки

V11

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

1

С начала строки, с начала подстроки

С конца строки, с конца подстроки

С середины строки, с середины подстроки

С середины строки, с начала подстроки

С середины строки, с конца подстроки

V12

Сколько сравнений символов будет произведено при стандартном поиске в строке "мама мыла раму" подстроки "мыла"?

1

11

4

5

6

7

V13

Сколько сравнений символов будет произведено при стандартном поиске в строке "Петропавловск" подстроки "тропа"?

1

7

3

5

4

13

M14E1T60

Отладка и тестирование

V1

Отладчик НЕ позволяет

1

Гарантировать правильность программы

Устанавливать в программе точки останова

Посматривать значения переменных в точках останова

Продолжить выполнение программы после останова с другого места

Выполнять программу последовательно оператор за оператором

V2

С помощью отладчика можно

1

Устанавливать в программе точки останова

Посылать электронные письма

Принимать электронные письма

Вести поиск информации в интернете

Переводить on-line документацию

V3

С помощью отладчика можно

1

Посматривать значения переменных в точках останова

Посылать электронные письма

Принимать электронные письма

Вести поиск информации в интернете

Переводить on-line документацию

V4

С помощью отладчика можно

1

Продолжить выполнение программы после останова с другого места

Посылать электронные письма

Принимать электронные письма

Вести поиск информации в интернете

Переводить on-line документацию

V5

С помощью отладчика можно

1

Выполнять программу последовательно оператор за оператором

Посылать электронные письма

Принимать электронные письма

Вести поиск информации в интернете

Переводить on-line документацию

V6

При тестировании методом черного ящика

1

Текст программы тестеру неизвестен

Текст программы тестеру известен

Назначение программы тестеру неизвестно

Назначение программы тестеру известно

Тестирование производится в сторонней организации

V7

При тестировании методом белого ящика

1

Текст программы тестеру известен

Текст программы тестеру неизвестен

Назначение программы тестеру неизвестно

Назначение программы тестеру известно

Тестирование производится в сторонней организации

V8

Тестирование желательно проводить лицами

1

Не принимавшими участия в написании кода программы

Не знающими иностранного языка

Работающими сверхурочно

Работающими бесплатно

Пенсионного возраста

M15E1T60

Книжка вопросник

V1

Последовательный поиск в массиве из 100 элементов требует

Масимум 100 проверок

Масимум 10 проверок

В среднем 50 проверок

В среднем Log2(100) проверок

1

Масимум 100 проверок и в среднем 50 проверок

V2

Алгоритм Евклида – это алгоритм нахождения

1

НОД двух целых неотрицательных чисел

НОК двух целых неотрицательных чисел

НОД двух вещественных чисел

НОД двух целых отрицательных чисел

Простых чисел

V3

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

1

Алгоритм

Частичный алгоритм

Блок-схема

Граф

Список

V4

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

Программа

Процедура

1

Функция

Модуль

Рекурсия

V5

Укажите число сравнений в строго обменном алгоритме

C = (n² + n) / 2

C = (n – n²) / 2

1

C = (n² – n) / 2

C = (n² – n) * 2

C = (n² – n) / 3

V6

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

Программа

1

Процедура

Функция

Модуль

Рекурсия

V7

Подпрограммой называют

Часть программы, содержающие неоднократно выполнимые команды

Независимый программный модуль

Произвольный фрагмент программы

1

Набор операторов, следующих в программе за оператором GOSUB

Часть программы, служащей для решения некоторой вспомогательной задачи

V8

Что из перечисленного может вызвать переполнение стека?

Большая величина локальной переменной

Связанные списки

1

Рекурсивные алгоритмы

Большая величина локальной переменной и рекурсивные алгоритмы

Низкая скорость выполнения алгоритма

V9

Как называется констурция, которая определяет подпрограмму до обращения к ней

Отстающее описание

Сильная типизация языка

1

Опережающее описание

Рекурсивное описание

Стековое описание

V10

Поиск подстроки в строке. Алгоритм Р.Байера и Дж.Мура

1

Поиск ведется от начала строки, но с конца искомой подстроки x

Поиск ведется с конца строки s, но с начала искомой подстроки x

Поиск ведется с начала строки s и с начала искомой подстроки x

Поиск ведется с середины строки

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

V11

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

Декомпозиция частного случая

Построение модели

Параметризация задач

1

Поиск тривиального случая

Декомпозиция общего случая

V12

Бинарный поиск предназначен для

Сортированного связанного списка

1

Сортированного массива

Любого массива

Двух чисел

Сортировки строки

V13

Бинарный поиск в отсортированном массиве из 100 элементов

1

Требует не более 7 проверок

В среднем требует 50 проверок

Требует не более 100 проверок

Требует более 10 проверок

Требует более 7 проверок

V14

Формальные параметры процедуры

1

Описываются в ее заголовке

Перечисляются при вызове процедуры

Указываются при описании данных в процедуре

Декларируются при описании промежуточных переменных процедуры

Присваиваются в процессе выполнения программы

V15

Геометрическая фигура

Блок заголовка цикла

1

Блок комментария

Блок присваивания

Блок условий

Блок подпрограмм

V16

Почему сортировку массивов называют внутренней?

1

Массивы хранятся в быстрой оперативной памяти машины со случайным доступом

Массивы хранятся в медленной емкой внешней памяти машины, на устройствах основанных на механических перемещениях

Массивы хранятся в быстрой оперативной памяти машины упорядоченным доступом

Массивы хранятся в быстрой внешней памяти машины, на устройствах основанных на механических перемещениях

Массивы хранятся в чипах

V17

Фактические параметры процедуры

Описываются в ее заголовке

Указываются при описании данных в программе

1

Перечисляются при ее вызове

Нигде не указываются

Указываются при описании промежуточных переменных процедуры

V18

Как называется метод сортировки, если в процессе сортировки относительное расположение элементов с равными ключами не изменяется?

Устойчиво зависимый

Положительно определенный

1

устойчивый

Не устойчивый

Постоянный

V19

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

1

n – 1

n + 1

n * n

n

2 * n

V20

Геометрическая фигура, изображенная на рисунке Означает

Начало и конец блок-схемы

Блок ввода-вывода данных

Блок присваивания

1

Блок условий

Блок подпрограмм

V21

Если условие B ложно

1

То выполняется блок S1

То выполняется блок S2

Не выполняется ни один из блоков

Выполняются оба блока

Выполняется один из блоков

V22

Найдите максимальное число перестановок элементов массива в методе прямого включения

(n² – 3 * n – 4) / 2

(n² + n – 4) / 2

(n² + 3 * n – 4) / 2

1

n

(n² – n – 4) / 4

V23

Алгоритмы классифицируются в соответствии с их временной сложностью. Сложность оценивается как O(n*n)

1

Квадратный

Линейный

Постоянный

Кубический, полиноминальный

факториальный

V24

В чем заключается свойство алгоритмов – массовость?

Алгоритм должен иметь дискретную структуру (должен быть разбит на последовательность отдельных шагов)

Записывая алгоритм для конкретного исполнителя, можно использовать лишь те комангды, что входя в систему его команд

1

Алгоритм должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа

При точном исполнении всех команд алгоритма процесс должен прератиться за конечное число шагов, приведя к определенному результату

Исполнитель алгоритма не должен принимать решения, не предусмотренные составителем алгоритма

V25

Найдите минимальное число сравнений ключей в методе прямого включения, n=10

1

9

10

11

12

8

V26

Укажите результат выполнения блок-схемы

Сумма элементолв заданной матрицы A(3,5)

Сумма элементолв заданной последовательности A(15)

Сумма элементолв заданной последовательности A(5)

1

Сумма элементолв заданной матрицы A(5,3)

Сумма арифметической прогрессии

V27

Символ используется для изображения унифицированных структур

1

Развилка полная, развилка неполная, выбор, цикл-до, цикл-пока

Развилка полная, развилка неполная,

Выбор

Цикл-до, цикл-пока

Цикл-до, развилка полная

V28

Дайте определение алгоритма

Блок-схема

1

Ряд определений, сформулированных на языке понятном исполнителю и определяющих цепочку действий, в результате выполнения которых, мы приходим от исходных данных к искомому результату

Ряд предписаний

Программа

Графическое представление программы

V29

Алгоритм имеет сложность порядка O(f(n))

1

Если время выполнения алгоритма алгоритма растет пропорционально функции f(n) с увеличением размерности исходных данных N

Если время выполнения алгоритма алгоритма уменьшается пропорционально функции f(n) с увеличением размерности исходных данных N

Если время выполнения алгоритма алгоритма растет пропорционально функции f(n) с уменьшением размерности исходных данных N

Если время не изменяется

Если время выполнения алгоритма алгоритма равно константе