Основы алгоритмизации и программирования
Какую задачу позволяет решить алгоритм Дейкстры?a) Данный алгоритм формирует матрицу достижимости для каждой вершины
b) Данный алгоритм осуществляет обход графа, при этом проходит по каждой из вершин исключительно один раз
c) Данный алгоритм находит кратчайшее расстояние из заданной вершины во все остальные
Какова асимптотическая оценка для быстрого алгоритма возведения числа в целочисленную степень, применяя только операцию умножения?a) O(2n)
b) O(log2n)
c) O(n2)
d) O(1)
e) O(n)
Выберите задачи, которые относятся к NP-полнымa) Задача о сумме подмножества
b) Задача о коммивояжере
c) Определение наличия в графе Эйлерова цикла
d) Определение наличия в графе Гамильтонова цикла
Для любой сортировки, основанной на сравнениях, в наихудшем случае для n элементов нужно произвести не менее n*lg(n) сравнений.a) верно
b) неверно
Существуют ли, на данный момент, алгоритмы проверки числа на простоту с полиномиальной сложностью?a) Да
b) Нет
Отметьте задачи, которые классически решаются с помощью рекурсии:a) Вычисление числа π
b) Задача «Ханойские башни»
c) Сортировка
d) Вычисления факториала числа n
e) Вычисления n-ого числа Фибоначчи
В чём разница между расширенным алгоритмом Евклида и обычным?a) Расширенный алгоритм работает быстрее, но более сложный в реализации
b) Между ними нет существенной разницы
c) Расширенный алгоритм Евклида позволяет извлечь дополнительную информацию
d) Ничего из вышеперечисленного
Выберите алгоритмы сортировки для которых асимптотическая оценка в наихудшем случае O(n2)a) Шелла
b) выбором
c) пузырьковая
d) быстрая
e) слиянием
Задачу о Ханойской башне (оптимальная последовательность перекладываний) обычно решают с помощью... (Выберите все подходящие варианты.)a) теории графов
b) формулы
c) массива констант
d) рекурсии
e) итерации
f) динамического программирования
Какого оператора безусловного перехода нет в Pascal?a) Return
b) Break
c) Exit
d) Continue
Что верно о NP-полных задачах?a) Для их решения в настоящий момент не разработаны алгоритмы с полиномиальным временем работы
b) Для них не существует алгоритмов решения
c) Они относятся к задачам по теории чисел
d) Их невозможно реализовать на классическом компьютере
Что выведет следующая программа:var
b1, b2, b3: Boolean;
begin
b1 := TRUE;
b2 := 0;
b3 := b1 xor b2;
Writeln(b3);
end.
a) TRUE
b) FALSE
c) 1
d) Возникнет ошибка компиляции
e) Возникнет ошибка времени выполнения (runtime)
Выберите алгоритмы построения выпуклой оболочки.a) Грэхема
b) Метод меток Форда-Фалкерсона
c) Штрассена
d) Обход по Джарвису
Что из ниже перечисленного не входит в набор основных символов Турбо Паскаля?a) латинские строчные и прописные буквы
b) служебные слова
c) десять цифр
d) русские строчные и прописные буквы
e) знак подчеркивание
Истинно ли утверждение: "Ориентированный и неориентированный графы являются частными случаями смешанного"?a) Да
b) Нет
Какой оператор не относится к группе операторов ввода-вывода языка Паскаль?a) Read(A1,A2,...AK);
b) WriteLn(A1,A2,...AK);
c) PrintLn;
d) ReadLn;
Что вычисляет следующая рекурсивная функция для произвольного аргумента n?F(n)
1 if n=0
2 then return 0
3 else return 1 + F(n & (n-1))
a) количество цифр в двоичном представлении n
b) количество нулей в двоичном представлении n
c) количество единиц в двоичном представлении n
d) ничего из вышеперечисленного
Какие из следующих описаний множеств являются правильными?a) set of integer
b) set of 10..100
c) set of 200..300
d) set of char
e) set of 'a'..'z'
f) set of -10..10
"Жадный" алгоритм это?a) алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.
b) алгоритм, заключающийся в принятии глобально оптимальных решений на каждом этапе, допуская, что локальное решение также окажется оптимальным.
c) алгоритм, заключающийся в принятии глобально оптимальных решений на каждом этапе, допуская, что локальное решение может оказаться и не оптимальным.
d) алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение может оказаться и не оптимальным.
a) Существует
b) Не существует
Эйлеров цикл - это...a) ... цикл, который проходит по всем вершинам ровно по одному разу, хотя может проходить через ребра несколько раз
b) ... цикл, который проходит по всем ребрам ровно по одному разу, хотя может проходить через вершины несколько раз
c) ... цикл, который проходит по всем вершинам и ребрам ровно по одному разу
Какие типы циклов существуют в языке Паскаль?a) for
b) do...while
c) while
d) repeat...until
e) loop
Отметьте истинные утверждения:a) Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком
b) Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
c) Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Какие из типов относятся к стандартным?a) Целый
b) Интервальный
c) Символьный
d) Логический
e) Перечисляемый
Каким способом рациональнее всего вычислить площадь произвольного многоугольника?a) С помощью алгоритма сложности O(1)
b) С помощью итерационного алгоритма сложности O(n)
c) С помощью рекурсивного алгоритма сложности O(n2)
d) Не для всех многоугольников можно точно вычислить площадь алгоритмическим путём
Правильно ли утверждение, что лучший на практике алгоритм сортировки "Алгоритм Хоара" фактически является существенной модификацией одного из худший алгоритмов "Алгоритм пузырька"?a) Да
b) Нет
Дан фрагмент блок-схемы: Он представляет алгоритм, который содержит две команды ветвления, -
a) команду ветвления в сокращенной форме, в которую вложена команда ветвления в полной форме
b) обе команды ветвления в полной форме, одна из которой вложена в другую
c) обе команды ветвления в сокращенной форме, одна из которой вложена в другую
d) команду ветвления в полной форме, в которую вложена команда ветвления в сокращенной форме
Какое зарезервированное слово подключает к программе внешние модули?Ваш ответ: ____________
Укажите все вещественные типы:a) Single
b) Char
c) Boolean
d) Float
e) Double
Числа в языке Pascal различают как:a) вещественные
b) правильные дроби
c) натуральные
d) целые
e) комплексные
Ответы
Вопрос | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
Ответ | c | b | a, b,d | a | a | b, d,e | c | b, c,d | d, e,f | a | a | d | a, d | d | a |
16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
c | c | b, d,e, f | a | b | b | a, c,d | a, b,c | a, c,e | b | a | b | uses | a, e | a, d |
Список используемой литературы
алгоритмизация и программирование на Turbo Pascal: от простых до олимпиадных задач: Учебное пособие. – СПб.: Питер, 2005. – 237.: ил. скусство программирования для ЭВМ. Т. 1: Получисленные алгоритмы. 3-е изд. – М.: Издательский дом «Вильямс», 2000. 828 с. , Турбо Паскаль 7.0. - М.: "ДМК", 2000. - 416 с. Turbo Pascal. Практическое программирование. - Приор,1997. - 336с. Практикум по программированию. Начальный курс. - Переяславль-Залесский, 1997. Turbo Pascal 7.0. Начальный курс. - Нолидж, 1998. -620 с. Алгоритмы и программы на Турбо Паскале.