Утверждено
жүктеу/скачать 298,1 Kb. Pdf көрінісі
|
Тесты ТА
- Бұл бет үшін навигация:
- «ВЯЗЕМСКИЙ ПОЛИТЕХНИЧЕСКИЙ ТЕХНИКУМ»
- ТЕСТЫ
| СМОЛЕНСКОЕ ОБЛАСТНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ОДОБРЕНО УТВЕРЖДЕНО Протоколом Методического совета СОГБОУ СПО «Вяземский политехнический техникум» Протоколом Педагогического совета СОГБОУ СПО «Вяземский политехнический техникум» «27» августа 2013 г № 1 «28» августа 2013 г. № 1
ТЕСТЫ Дисциплина: Теория алгоритмов. Специальность: 230115 «Программирование в компьютерных системах» Форма обучения: очная, заочная (дистанционная) Разработал: преподаватель Коростелёв М. К.
№ Вопрос Варианты ответов 1 Граф задается: 1) множеством точек с координатами; 2) парой множеств: множеством вершин и множеством ребер; 3) множеством вершин; 4) множеством ребер.
2 Если ребра
графа определяются упорядоченными парами вершин, то граф называется: 1) семантическим; 2) ориентированным; 3) простым; 4) циклом.
3
если: 1) начала и концы ребер совпадают; 2) цепь из этих ребер замкнута; 3) их вершины соединены двумя или более ребрами; 4) они концевые.
4
1) начала и концы ребер совпадают; 2) цепь из этих ребер замкнута; 3) их вершины соединены двумя или более ребрами; 4) они концевые.
5 Какой граф называется простым: 1) с замкнутой простой цепью;
2) без петель и параллельных ребер;
3) если все ребра параллельны; 4) состоящий из одной петли?
6 Цепь графа — это: 1) если все определяемые маршрутом ребра смежные; 2) если ребра в маршруте не образуют петель; 3) маршрут, в котором все определяемые им ребра различны; 4) если граф простой.
7
1) неориентированный связный граф; 2) ориентированный несвязный граф; 3) граф со смежными вершинами; 4) ориентированный связный граф.
8
представление алгоритма: 1) последовательность формул; 2) блок-схема; 3) таблица; 4) словесное описание?
9 На рисунке представлена часть блок- схемы. Как называется такая вершина: 1) предикатная; 2) объединяющая; 3) функциональная; 4) сквозная?
10
На рисунке представлена часть блок- схемы. Как называется такая вершина: 1) предикатная; 2) объединяющая; 3) функциональная; 4) сквозная?
11
На рисунке представлена часть блок- схемы. Как она называется:
1) альтернатива; 2) композиция; 3) цикл с предусловием; 4) итерация?
12 На рисунке представлена часть блок- схемы.
Как она называется: 1) альтернатива; 2) композиция; 3) цикл с предусловием; 4) цикл с постусловием?
13
На рисунке представлена часть блок-схемы. Как она называется:
1) альтернатива; 2) композиция; 3) цикл с предусловием; 4) цикл с постусловием?
14 Как называется конструкция блок-схемы, изображенная на рисунке:
1) выполнение операций; 2) цикл с параметром; 3) вызов вспомогательного алгоритма; 4) ввод/вывод данных?
15
Как называется конструкция блок-схемы, изображенная на рисунке:
1) выполнение операций; 2) начало-конец алгоритма; 3) вызов вспомогательного алгоритма; 4) ввод/вывод данных?
16
Как называется конструкция блок-схемы, изображенная на рисунке:
1) выполнение операций; 2) начало-конец алгоритма; 3) вызов вспомогательного алгоритма; 4) ввод/вывод данных?
17
Как называется конструкция блок-схемы, изображенная на рисунке:
1) выполнение операций; 2) начало-конец алгоритма; 3) вызов вспомогательного алгоритма; 4) ввод/вывод данных?
18
Свойство алгоритма записываться в виде упорядоченной совокупности отделенных друг от друга предписаний (директив): 1) понятность; 2) определенность; 3)
дискретность;
4) массовость. 19
Свойство алгоритма записываться в виде только тех команд, которые находятся в системе команд исполнителя, называется: 1)
понятность;
2) определенность; 3) дискретность; 4) результативность.
20
Свойство алгоритма записываться только директивами однозначно и одинаково интерпретируемыми разными 1)
детерминированность ;
2) понятность; 3) определенность; исполнителями: 4) результативность.
21
Свойство алгоритма, что при точном исполнении всех предписаний процесс должен прекратиться за конечное число шагов
с определенным ответом на
поставленную задачу: 1) понятность; 2) детерминированность; 3) дискретность; 4) результативность.
22 Свойство алгоритма обеспечения решения не одной задачи, а целого класса задач этого типа: 1) понятность; 2) определенность; 3) дискретность; 4) массовость.
23 Что называют служебными словами в алгоритмическом языке: 1) слова, употребляемые для записи команд, входящих в СКИ; 2) слова, смысл и способ употребления которых задан раз и навсегда; 3) вспомогательные алгоритмы, которые используются в составе других алгоритмов; 4) константы с постоянным значением?
Рекурсия в алгоритме будет прямой, когда:
1) рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение; 2) порядок следования команд определяется в зависимости от результатов проверки некоторых условий; 3) команда обращения алгоритма к самому себе находится в самом алгоритме; 4) один вызов алгоритма прямо следует за другим.
25
Рекурсия в алгоритме будет косвенной, когда:
1) рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение;
2) порядок следования команд определяется в зависимости от результатов проверки некоторых условий; 3) команда обращения алгоритма к самому себе находится в самом алгоритме; 4) один вызов алгоритма прямо следует за другим.
26
Какова функция сложности программ, когда каждый элемент входных данных требуется обработать лишь линейное число 1) 0(1); 2) 0(N); 3) 0(N
2 ), 0(N
3 ), 0(N
n );
4) 0(Log(N)). 27
Алгоритмы константной сложности характеризуются следующей функцией сложности: 1)
0(1); 2)
0(N); 3)
0(N 2 ), 0(N 3 ), 0(N
n ).
4) 0(Log(N)); 28 Алгоритмы полиномиальной сложности характеризуются следующей функцией сложности: 1) 0(1); 2) 0(N); 3) 0(N
2 ), 0(N
3 ), 0(N
n );
4) 0(Log(N)). 29
Какова функция сложности программ, которые делят большую проблему на маленькие и решают их по отдельности: 1) 0(1); 2) 0(N); 3) 0(N
2 ), 0(N
3 ), 0(N
n );
4) 0(Log(N)). 30
Какова функция сложности программ, которые делят большую проблему на маленькие, а затем, решив их, соединяют их решения: 1) 0(N*Log(N)) 2) 0(1);
3) 0(N);
4) 0(N
2 ), 0(N
3 ), 0(N
n );
31 Какова функция сложности программ, которые возникают в результате подхода, именуемого методом грубой силы: 1) 0(N*Log(N)) 2) 0(1); 3) 0(N); 4) 0(2
N ) 32 Какова функция сложности называется логарифмической: 1) 0(1); 2) 0(N*Log(N)) ; 3) 0(N 2
3 ), 0(N
n );
4) 0(Log(N)).
33
Какова функция сложности называется экспоненциальной: 1) 0(2
N ) 2) 0(N*Log(N)) 3) 0(1); 4) 0(N); 34 Сложность этого алгоритма: For i:=l to N do For j:=l to N do Begin …
1) 0(1); 2) 0(N); 3) 0(N
2 );
4) 0(Log(N)). 35 Сложность этого алгоритма: For i:=l to N do Begin
… End;
1) 0(2 N ) ; 2) 0(N*Log(N)) ; 3) 0(1); 4) 0(N); 36
Метод фон
Неймана является разновидностью сортировки: 1) Вставкой; 2) Выбором; 3) Обменом. 37 Сначала в неупорядоченном списке выбирается и отделяется от остальных наименьший элемент. После
этого исходный список оказывается измененным. Измененный список
принимается за
исходный. Процесс продолжается до тех пор, пока все элементы не буду выбраны. Как называется этот вид сортировки?
1) Вставкой; 2) Выбором; 3) Обменом;
4) Шейкерная. 38 Сложность сортировки методом выбора составляет: 1) 0(1); 2) 0(N); 3)
0(N 2 ); 4) 0(Log(N)). 39 Из неупорядоченной последовательности элементов выбирается поочередно каждый элемент, сравнивается с предыдущим, уже упорядоченным, и помещается на соответствующее место. Как называется этот вид сортировки? 1)
Вставкой; 2) Выбором;
3) Обменом; 4) Шелла.
40
Сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив. Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания эле- ментов одного из массивов. Затем остаток другого массива дописывается в новый массив. Как называется этот вид сортировки? 1) Фон Неймана; 2) Хоара;
3) Обменом; 4) Шелла.
41
Сортировка, в которой элементы списка
последовательно сравниваются между собой и меняются местами в том случае, если предшествующий элемент больше последующего называется: 1) Фон Неймана; 2) Хоара;
3) Обменом; 4) Шелла.
42
Проводится попарное сравнение элементов. При этом первый проход осуществляется слева направо, второй — справа налево и т. д. Иными словами, меняется направление просмотра элементов списка.
Как называется этот вид
сортировки? 1) Фон Неймана; 2) Хоара;
3) Шейкерная; 4) Шелла.
43
Сравниваются элементы, 1) Фон Неймана;
расположенные на расстоянии d= [n/2] (где d — шаг между
сравниваемыми элементами, [ ] — целая часть от числа). После каждого
просмотра шаг
d уменьшается вдвое. На
последнем просмотре он сокращается до d = 1. Как называется этот вид сортировки? 2) Хоара;
3) Шейкерная; 4) Шелла.
44 Фиксируется какой-либо ключ
(базовый), относительно которого все элементы с большим
весом перебрасываются вправо, а с меньшим — влево. При этом весь список элементов делится относительно базового ключа на две части. Для каждой части процесс повторяется. Как называется этот вид сортировки? 1) Фон Неймана; 2) Шелла;
3) Шейкерная; 4) Хоара.
45 Производится попарное сравнение вершин дерева снизу вверх. Найденный максимальный элемент помещается в результирующее множество. В результате будет получено упорядоченное множество. Как называется этот вид сортировки?
1) Фон Неймана; 2) Шелла; 3)
Турнирная; 4) Пирамидальная. 46 В
каждой триады
располагается элемент с большим весом; •
листья бинарного дерева располагаются либо в одном уровне, либо в двух соседних; •
листья нижнего
уровня располагаются левее листьев
более высокого уровня. В ходе преобразования элементы триад сравниваются дважды, при этом элемент с большим весом перейдет вверх, а с меньшим — вниз. Как называется этот вид сортировки?
1) Фон Неймана; 2) Шелла;
3) Турнирная; 4) Пирамидальная.
47
Исходное множество не упорядочение, т. е. имеется произвольный набор ключей {к 1
2 , к
3 , ..., к
п }. Метод заключается в том, что отыскиваемый ключ к, последовательно сравнивается со всеми
элементами множества. При этом поиск заканчивается досрочно, если
ключ найден.
Как называется этот вид поиска? 1) Последовательный; 2) Бинарный; 3) Фибоначчиев; 4) По бинарному дереву. 48 Исходное множество должно быть упорядочено по возрастанию. Отыскиваемый ключ сравнивается с центральным элементом множества, если он меньше центрального, то поиск продолжается в левом подмножестве, в 1) Последовательный; 2) Бинарный; 3) Фибоначчиев; 4) По бинарному дереву.
противном случае — в правом. Номер
центрального элемента находится по формуле № элемента= [n/2] + 1, где квадратные скобки обозначают, что от деления берется только целая часть (всегда округляется в меньшую сторону). Как называется этот вид поиска? 49 В
поиске анализируются элементы, находящиеся в позициях, равных числам. Числа получаются по следующему правилу: каждое последующее число равно сумме двух предыдущих чисел, например: {1,2,3,5,8, 13,21,34,55,...}. Поиск продолжается до тех пор, пока не будет найден интервал между двумя ключами, где
может располагаться отыскиваемый ключ. 1) Последовательный; 2) Бинарный; 3) Фибоначчиев; 4) По бинарному дереву. 50
Первоначальное сравнение осуществляется на расстоянии шага d, который
определяется по
формуле:
Идея метода заключается в следующем: шаг d меняется после каждого этапа по формуле, приведенной выше. Алгоритм заканчивает работу при d= 0, при этом анализируются соседние элементы, после чего делается окончательное решение о результатах поиска.
1) Последовательный; 2) Бинарный; 3) Фибоначчиев; 4) Интерполяционный. 51
Как называются эти деревья? Выберите правильное соответствие. 1
1) Бинарное дерево -1. Сбалансированное дерево -2;
2) Бинарное дерево -2. Сбалансированное дерево -1. 52
К алгоритмам обработки словесной информации относятся: 1) Бора; 2) Кнута-Мориса-Пратта; 3) Бойера-Мура; 4) Рабина; 5) Шелла.
53
Рекурсия — это: 1) повторение выполнения функции или процедуры внутри себя; 2) оператор; 3) цикл; 4) метод определения функции или процедуры. 54
Очередью называется: 1)
набор именованных компонент разного типа, объединенных общим именем;
2) линейно упорядоченный набор следующих друг за другом компонент; 3) однородный набор величин одного и того же типа, идентифицируемых вычисляемым индексом; 4) множество элементов. 55 Когда
доступ к элементам осуществляется следующим образом: новые компоненты могут добавляться только в хвост и значения компонент могут читаться только в порядке следования от головы к хвосту, то эта структура: 1)
массив; 2)
очередь; 3)
множество; 4)
запись.
56 Когда доступ
к элементам осуществляется в любой момент времени и к любому элементу с помощью индексов, то эта структура: 1)
массив; 2)
очередь; 3)
множество; 4)
запись.
57 Когда доступ
к элементам осуществляется только путем проверки принадлежности элемента к структуре 1) массив;
2) очередь; 3) множество; 4) запись. 58
Сортировка — это: 1) процесс нахождения в заданном множестве объекта; 2) процесс перегруппировки заданного множества объектов в некотором порядке;
3)
установка индексов элементов в возрастающем порядке; 4) обработка элементов в алфавитном порядке.
59 Процедура линейного поиска — это: 1) просмотр массива с конца; 2) просмотр массива с середины; 3) сравнение эталона осуществляется с элементом, расположенным в середине массива; 4)
последовательный просмотр всех элементов массива и сравнение их с эталоном.
60 Цикл называется _______, если он проходит через все ребра графа и при этом только по одному разу. 1)
Эйлеровым; 2) Гамильтоновым; 3) Ньютоновым. 61
Цикл называется________, если он проходит через все вершины графа по одному разу. 1) Эйлеровым; 2) Гамильтоновым; 3) Ньютоновым 62 Циклометрическое число вычисляется по формуле: 1) Цикломатическое число равно увеличенной на единицу разности между количеством ребер и количеством вершин графа; 2) Цикломатическое число равно увеличенной на единицу разности между количеством вершин и количеством ребер графа; 3) Цикломатическое число равно разности между количеством вершин и количеством ребер графа. 63 Для построения остовного дерева графа используются алгоритмы: 1) Эйлера; 2) Крускала и Прима; 3) Гамильтона. 64
рисунке представлена схема алгоритма: 1) Эйлера; 2)
Крускала; 3) Гамильтона
65
От исходного графа переходим к его представлению в виде матрицы смежности. На графе
выбирается произвольная вершина. Выбранная вершина образует первоначальный фрагмент остовного дерева. Затем анализируются веса ребер от выбранной вершины до
оставшихся 1) Метод Прима: 2) Метод Эйлера; 3) Метод Гамильтона.
невыбранных вершин.
Выбирается минимальное ребро, которое указывает на следующую выбранную вершину, и т. д. Величины, найденные на предыдущем шаге, автоматически переносятся на
следующий шаг. Процесс продолжается до тех пор, пока в остовное дерево не будут включены все вершины исходного графа. 66 Метод построения дерева решений обычно используется для нахождения _____________ в ориентированном графе. 1) Кратчайшего пути; 2) Циклометрического числа; 3) Матрицы смежности. 67 Метод
динамического программирования основан на пошаговой оптимизации целевой функции, где в качестве целевой функции могут быть: 1) Стоимость; 2) Ресурсные затраты; 3) Кратчайшие пути; 4) Финансово- экономические затраты.
68 Идея алгоритма следующая: сначала выберем путь до начальной вершины равным нулю, заносим эту вершину во множество уже выбранных, расстояние от которых до оставшихся невы-бранных вершин определено. На каждом этапе находим следующую невыбранную вершину, расстояние до которой наимень- шее, и соединенную ребром с какой-нибудь вершиной из множества выбранных (это расстояние будет равно расстоянию до уже выбранной вершины плюс длина ребра). 1) Алгоритм Эйлера; 2) Алгоритм Крускала и Прима; 3) Алгоритм Дейкстры; 4) Алгоритм Гамильтона.
69 Алгоритмы нахождения кратчайших путей на графах: 1) Дейкстры: 2) Флойда: 3) Йена; 4) Беллмана-Форда.
70
К эвристическим алгоритмам относятся: 1) Двухлучевой, 2) Четырехлучевои, 3) Маршрутный, 4) Алгоритмы составления расписания. 5) Отыскания кратчайшего пути 6) Волновой;
71 Методы генерации случайных чисел: 1) Середины квадрата; 2) Линейный конгруэнтный метод;
3) Полярный метод; 4) Метод Йена.
Преподаватель__________________Коростелев М.К.
Рассмотрено на заседании ПЦК проф. дисциплин специальностей 2301130, 230115, 230401 Протокол № 1 от «26» августа 2013 г. Председатель ПЦК____________Никитина С.Ю.
жүктеу/скачать 298,1 Kb. Достарыңызбен бөлісу:
|