ФИТ ИС Алгоритмы и структуры данных (аттестация) 360
.doc
|
M7E1T60 |
Динамические структуры данных |
|
V1 |
Что означает аббревиатура LIFO? |
|
1 |
Last input, first output |
|
|
Let input, first output |
|
|
Live input, first output |
|
|
Level input, first output |
|
|
Last input, fire output |
|
V2 |
Как переводится Last input, first output (LIFO)? |
|
1 |
Последний пришел, первый ушел |
|
|
Последний ушел, первый пришел |
|
|
Последний пришел, последний ушел |
|
|
Первый пришел, первый ушел |
|
|
Первый пришел, последний ушел |
|
V3 |
В какой структуре данных вставка и удаление происходят на одном конце? |
|
1 |
Стек |
|
|
Очередь |
|
|
Дерево |
|
|
Массив |
|
|
Запись |
|
V4 |
Что делает операция Push? |
|
1 |
Помещает данные в стек |
|
|
Извлекает данные из стека |
|
|
Очищает стек |
|
|
Помещает данные в очередь |
|
|
Извлекает данные из очереди |
|
V5 |
Что делает операция Pop? |
|
1 |
Извлекает данные из стека |
|
|
Помещает данные в стек |
|
|
Очищает стек |
|
|
Помещает данные в очередь |
|
|
Извлекает данные из очереди |
|
V6 |
Если в стек последовательно помещены числа 1, 2, 3, 4, 5, то в каком порядке они будут удаляться из него? |
|
1 |
5, 4, 3, 2, 1 |
|
|
1, 2, 3, 4, 5 |
|
|
1, 3, 5, 2, 4 |
|
|
2, 4, 1, 3, 5 |
|
|
5, 3, 1, 4, 2 |
|
V7 |
Если в стек последовательно помещены буквы S, K, G, U то в каком порядке они будут удаляться из него? |
|
1 |
U, G, K, S |
|
|
S, K, G, U |
|
|
S, K, U, G |
|
|
G, U, K, S |
|
|
S, G, K, U |
|
V8 |
Стек S первоначально пуст. Показать его содержимое после выполнения операций: push(S, 1), push(S, 2), push(S, 3), pop(S), push(S, 5), push(S, 6), pop(S), push(S, 8), pop(S), push(S, 10). |
|
1 |
1, 2, 5, 10 |
|
|
5, 6, 8, 10 |
|
|
1, 2, 3, 5, 10 |
|
|
1, 2, 3, 10 |
|
|
1, 2, 6 , 8 |
|
V9 |
Стек S первоначально пуст. Показать его содержимое после выполнения операций: push(S, 1), pop(S), push(S, 3), push(S, 4), push(S, 5), push(S, 6), pop(S), pop(S), push(S, 9) , push(S, 10). |
|
1 |
3, 4, 9, 10 |
|
|
5, 6, 9, 10 |
|
|
3, 4, 6, 10 |
|
|
1, 3, 5, 9, 10 |
|
|
3, 4, 5, 10 |
|
V10 |
Что означает аббревиатура FIFO? |
|
1 |
First input, first output |
|
|
First input, fire output |
|
|
First input for output |
|
|
Five input, four output |
|
|
First input, first option |
|
V11 |
Как переводится First input, first output (FIFO)? |
|
1 |
Первый пришел, первый ушел |
|
|
Последний пришел, первый ушел |
|
|
Последний ушел, первый пришел |
|
|
Последний пришел, последний ушел |
|
|
Первый пришел, последний ушел |
|
V12 |
В какой структуре данных вставка происходит на на одном конце, а удаление на другом? |
|
1 |
Очередь |
|
|
Стек |
|
|
Дерево |
|
|
Массив |
|
|
Запись |
|
V13 |
Если в очередь последовательно помещены числа 1, 2, 3, 4, 5, то в каком порядке они будут удаляться из нее? |
|
1 |
1, 2, 3, 4, 5 |
|
|
5, 4, 3, 2, 1 |
|
|
1, 3, 5, 2, 4 |
|
|
2, 4, 1, 3, 5 |
|
|
5, 3, 1, 4, 2 |
|
V14 |
Если в очередь последовательно помещены буквы S, K, G, U то в каком порядке они будут удаляться из него? |
|
1 |
S, K, G, U |
|
|
U, G, K, S |
|
|
S, K, U, G |
|
|
G, U, K, S |
|
|
S, G, K, U |
|
V15 |
В какой структуре данных и вставка и удаление могут происходить на обоих концах? |
|
1 |
Дек |
|
|
Очередь |
|
|
Стек |
|
|
Дерево |
|
|
Запись |
|
V16 |
Что такое дерево? |
|
1 |
Это граф без циклов, одна из вершин в нем считается корнем дерева |
|
|
Это граф без ребер, одна из вершин в нем считается корнем дерева |
|
|
Это граф без вершин, только из ребер |
|
|
Это граф, в котором нет петель |
|
|
Это граф, в котором имеются все возможные между вершинами ребра |
|
V17 |
Что такое двоичное (бинарное) дерево? |
|
1 |
Это дерево, каждый узел (вершина) которого имеет не более двух потомков |
|
|
Это дерево, каждый узел (вершина) которого имеет по два потомка |
|
|
Это дерево, в котором не более двух ребер |
|
|
Это дерево, в котором ровно два ребра |
|
|
Это дерево, в котором имеется два корня |
|
V18 |
Какие бывают обходы двоичного (бинарного) дерева? |
|
1 |
Прямой обход, обратный обход, концевой обход |
|
|
Левый обход, правый обход |
|
|
Верхний обход, средний обход, нижний обход |
|
|
Быстрый обход, медленный обход |
|
|
Корневой обход, вершинный обход, реберный обход |
|
V19 |
Выполнить прямой обход следующего двоичного (бинарного) дерева
|
|
1 |
A, B, C, D, E, F, G, H |
|
|
C, B, E, D, A, G, F, H |
|
|
C, E, D, B, G, H, F, A |
|
|
H, G, F, E, D, C, D, A |
|
|
A, B, F, C, D, G, H, E |
|
V20 |
Выполнить обратный обход следующего двоичного (бинарного) дерева
|
|
1 |
C, B, E, D, A, G, F, H |
|
|
A, B, C, D, E, F, G, H |
|
|
C, E, D, B, G, H, F, A |
|
|
H, G, F, E, D, C, D, A |
|
|
A, B, F, C, D, G, H, E |
|
V21 |
Выполнить концевой обход следующего двоичного (бинарного) дерева
|
|
1 |
C, E, D, B, G, H, F, A |
|
|
C, B, E, D, A, G, F, H |
|
|
A, B, C, D, E, F, G, H |
|
|
H, G, F, E, D, C, D, A |
|
|
A, B, F, C, D, G, H, E |
|
V22 |
Какая структура данных отражает иерархические связи элементов? |
|
1 |
Дерево |
|
|
Очередь |
|
|
Стек |
|
|
Массив |
|
|
Запись |
|
V23 |
С помощью чего можно реализовать структуру данных дерево? |
|
1 |
С помощью многосвязного списка |
|
|
С помощью односвязного списка |
|
|
С помощью стека |
|
|
С помощью очереди |
|
|
С помощью тела цикла |
|
V24 |
Каких ссылок достаточно в элементе списка, чтобы с помощью него можно было поддерживать структуру данных дерево? |
|
1 |
Ссылка на сыновний элемент и на соседний (братский) элемент |
|
|
Ссылка на сыновний элемент и на родительский элемент |
|
|
Ссылка на родительский элемент и на сыновний элемент |
|
|
Ссылка на сыновний элемент и на дочерний элемент |
|
|
Ссылка на сыновний элемент и на внучатый элемент |
|
V25 |
Что такое дерево? |
|
1 |
Это граф без циклов, одна вершина в котором считается корнем дерева |
|
|
Это граф без ребер, одна вершина в котором считается корнем дерева |
|
|
Это граф, в котором нет вершин |
|
|
Это граф, в котором нет петель |
|
|
Это граф, в котором нет подграфов |
|
V26 |
Какие есть ссылки у элементов односвязного списка? |
|
1 |
Ссылка на следующий элемент |
|
|
Ссылка на последний элемент |
|
|
Ссылка на первый элемент |
|
|
Ссылка на максимальный элемент |
|
|
Ссылка на минимальный элемент |
|
V27 |
Какие есть ссылки у элементов двусвязного списка? |
|
1 |
Ссылка на следующий элемент, ссылка на предыдущий элемент |
|
|
Ссылка на следующий элемент, ссылка на последний элемент |
|
|
Ссылка на первый элемент, ссылка на последний элемент |
|
|
Ссылка на предыдущий элемент, ссылка на первый элемент |
|
|
Ссылка на предыдущий элемент, ссылка на средний элемент |
|
V28 |
Какой список является кольцевым (циклическим, замкнутым)? |
|
1 |
В последнем элементе односвязного списка есть ссылка на первый элемент, а в случае двусвязного списка в крайних элементах есть ссылки друг на друга. |
|
|
В последнем элементе односвязного списка есть ссылка на минимальный элемент. |
|
|
В последнем элементе односвязного списка есть ссылка на максимальный элемент. |
|
|
В первом элементе односвязного списка есть ссылка на средний элемент. |
|
|
В первом элементе односвязного списка есть ссылка на максимальный элемент, а в последнем элементе двусвязного списка есть ссылка на минимальный элемент. |
|
M8E1T60 |
Анализ алгоритмов |
|
V1 |
Что оценивается при анализе алгоритмов? |
|
1 |
К количество элементарных операций, которые необходимо выполнить для решения задачи с помощью данного алгоритма. |
|
|
Количество подпрограмм в программе, реализующей алгоритм |
|
|
Длину текста программы, реализующей алгоритм |
|
|
Количество программистов, необходимых для программирования алгоритма |
|
|
Количество устройств ввода-выводп, необходимых для исполнения алгоритма |
|
V2 |
Что означает запись f(n) = O (g(n))? |
|
1 |
f(n) не превосходит по порядку g(n), то есть существует такая константа C, что для любого n выполняется f(n) < С g(n) |
|
|
f(n) растет линейно |
|
|
f(n) растет квадратично |
|
|
f(n) растет полиноминально |
|
|
f(n) растет экспоненциально |
|
V3 |
Что означает трудоемкость (сложность) алгоритма составляет O (g(n))? |
|
1 |
Решение задачи требует порядка O (g(n)) операций, где n характеризует размер входных данных |
|
|
Решение задачи требует порядка O (g(n)) байт памяти, где n характеризует размер входных данных |
|
|
Решение задачи получить невозможно |
|
|
Решение задачи не существует |
|
|
Входные данные шифруются функцией g() с ключем n |
|
V4 |
Что означает трудоемкость (сложность) алгоритма равна O(1)? |
|
1 |
Время работы алгоритма не зависит от размера входных данных |
|
|
Время работы алгоритма линейно зависит от размера входных данных |
|
|
Время работы алгоритма квадратично зависит от размера входных данных |
|
|
Время работы алгоритма логарифмически зависит от размера входных данных |
|
|
Время работы алгоритма экспоненциально зависит от размера входных данных |
|
V5 |
Что означает трудоемкость (сложность) алгоритма равна O(n)? |
|
1 |
Время работы алгоритма линейно зависит от размера входных данных |
|
|
Время работы алгоритма не зависит от размера входных данных |
|
|
Время работы алгоритма квадратично зависит от размера входных данных |
|
|
Время работы алгоритма логарифмически зависит от размера входных данных |
|
|
Время работы алгоритма экспоненциально зависит от размера входных данных |
|
V6 |
Что означает трудоемкость (сложность) алгоритма равна O(n2)? |
|
1 |
Время работы алгоритма квадратично зависит от размера входных данных |
|
|
Время работы алгоритма не зависит от размера входных данных |
|
|
Время работы алгоритма линейно зависит от размера входных данных |
|
|
Время работы алгоритма логарифмически зависит от размера входных данных |
|
|
Время работы алгоритма экспоненциально зависит от размера входных данных |
|
V7 |
Что означает трудоемкость (сложность) алгоритма равна O(nc), где c константа? |
|
1 |
Время работы алгоритма полиноминально зависит от размера входных данных |
|
|
Время работы алгоритма не зависит от размера входных данных |
|
|
Время работы алгоритма линейно зависит от размера входных данных |
|
|
Время работы алгоритма логарифмически зависит от размера входных данных |
|
|
Время работы алгоритма экспоненциально зависит от размера входных данных |
|
V8 |
Что означает трудоемкость (сложность) алгоритма равна O(cn), где c константа? |
|
1 |
Время работы алгоритма экспоненциально зависит от размера входных данных |
|
|
Время работы алгоритма не зависит от размера входных данных |
|
|
Время работы алгоритма линейно зависит от размера входных данных |
|
|
Время работы алгоритма логарифмически зависит от размера входных данных |
|
|
Время работы алгоритма полиноминально зависит от размера входных данных |
|
V9 |
Что означает трудоемкость (сложность) алгоритма равна O(log2n)? |
|
1 |
Время работы алгоритма логарифмически зависит от размера входных данных |
|
|
Время работы алгоритма не зависит от размера входных данных |
|
|
Время работы алгоритма линейно зависит от размера входных данных |
|
|
Время работы алгоритма полиноминально зависит от размера входных данных |
|
|
Время работы алгоритма экспоненциально зависит от размера входных данных |
|
V10 |
Что означает трудоемкость (сложность) алгоритма равна O(n!)? |
|
1 |
Время работы алгоритма факториально зависит от размера входных данных |
|
|
Время работы алгоритма не зависит от размера входных данных |
|
|
Время работы алгоритма линейно зависит от размера входных данных |
|
|
Время работы алгоритма полиноминально зависит от размера входных данных |
|
|
Время работы алгоритма экспоненциально зависит от размера входных данных |
|
V11 |
Что вычисляется по формуле Стирлинга? |
|
1 |
Приближенное значение факториала |
|
|
Числа Фибоначчи |
|
|
Простые числа |
|
|
Совершенные числа |
|
|
Наибольший общий делитель |
|
V12 |
По какой формуле призводится приближенное вычисление факториала? |
|
1 |
По формуле Стирлинга |
|
|
По формуле Эратосфена |
|
|
По формуле Фибоначчи |
|
|
По формуле Евклида |
|
|
По формуле Аккермана |
|
V13 |
Какова сложность алгоритма последовательного поиска? |
|
1 |
Линейная O(n) |
|
|
Квадратичная O(n2) |
|
|
Кубическая O(n3) |
|
|
Логарифмическая O(log2n) |
|
|
Экспоненциальная O(cn) |
|
V14 |
Какова сложность алгоритма двоичного поиска? |
|
1 |
Логарифмическая O(log2n) |
|
|
Линейная O(n) |
|
|
Квадратичная O(n2) |
|
|
Кубическая O(n3) |
|
|
Экспоненциальная O(cn) |
|
V15 |
Какова сложность алгоритма пузырьковой сортировки? |
|
1 |
Квадратичная O(n2) |
|
|
Логарифмическая O(log2n) |
|
|
Линейная O(n) |
|
|
Кубическая O(n3) |
|
|
Экспоненциальная O(cn) |
|
V16 |
Какова сложность алгоритма сортировки вставками (включением)? |
|
1 |
Квадратичная O(n2) |
|
|
Логарифмическая O(log2n) |
|
|
Линейная O(n) |
|
|
Кубическая O(n3) |
|
|
Экспоненциальная O(cn) |
|
M9E1T60 |
Алгоритмы поиска |
|
V1 |
Для поиска в чем предназначен Последовательный поиск? |
|
1 |
В неупорядоченном (неотсортированном) массиве |
|
|
В упорядоченном (отсортированном) массиве |
|
|
В дереве |
|
|
В символьных строках |
|
|
В формальных параметрах |
|
V2 |
Сколько сравнений потребуется при последовательном поиске в массиве из 100 элементов? |
|
1 |
Максимум 100 |
|
|
Максимум 20 |
|
|
Минимум 5 |
|
|
Минимум 25 |
|
|
В среднем 20 |
|
V3 |
Сколько сравнений потребуется при последовательном поиске в массиве из 100 элементов? |
|
1 |
В среднем 50 |
|
|
Максимум 10 |
|
|
Максимум 5 |
|
|
Минимум 25 |
|
|
В среднем 20 |
|
V4 |
Сколько сравнений потребуется при последовательном поиске в массиве из 100 элементов? |
|
1 |
Минимум 1 |
|
|
Максимум 10 |
|
|
Максимум 5 |
|
|
Минимум 25 |
|
|
В среднем 20 |
|
V5 |
Сколько сравнений чисел будет произведено при последовательном поиске числа 4 в массиве чисел 5, 2, 6, 7, 9, 4, 3? |
|
1 |
6 |
|
|
5 |
|
|
4 |
|
|
3 |
|
|
7 |
|
V6 |
Сколько сравнений чисел будет произведено при последовательном поиске числа 6 в массиве чисел 5, 2, 6, 7, 9, 4, 3? |
|
1 |
3 |
|
|
4 |
|
|
5 |
|
|
6 |
|
|
7 |
|
V7 |
Сколько сравнений чисел будет произведено при последовательном поиске числа 4 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
4 |
|
|
5 |
|
|
6 |
|
|
1 |
|
|
2 |
|
V8 |
Сколько сравнений чисел будет произведено при последовательном поиске числа 4 в массиве чисел 7, 6, 5, 4, 3, 2, 1? |
|
1 |
4 |
|
|
5 |
|
|
6 |
|
|
1 |
|
|
2 |
|
V9 |
Сколько сравнений чисел будет произведено при последовательном поиске числа 10 в массиве чисел 7, 6, 5, 4, 3, 2, 1? |
|
1 |
7 |
|
|
10 |
|
|
1 |
|
|
2 |
|
|
0 |
|
V10 |
Для поиска в чем предназначен Двоичный поиск? |
|
1 |
В упорядоченном (отсортированном) массиве |
|
|
В неупорядоченном (неотсортированном) массиве |
|
|
В дереве |
|
|
В символьных строках |
|
|
В формальных параметрах |
|
V11 |
Как еще называют Двоичный поиск? |
|
1 |
Бинарный поиск, Метод деления пополам, Дихотомия |
|
|
Четный |
|
|
Двойственный |
|
|
Парный |
|
|
Сдвоенный |
|
V12 |
Сколько сравнений потребуется при двоичном поиске в массиве из 100 элементов? |
|
1 |
Максимум 7 |
|
|
Максимум 5 |
|
|
Максимум 2 |
|
|
Минимум 5 |
|
|
Минимум 2 |
|
V13 |
Сколько сравнений потребуется при двоичном поиске в массиве из 100 элементов? |
|
1 |
Минимум 1 |
|
|
Минимум 10 |
|
|
Минимум 3 |
|
|
Максимум 3 |
|
|
Максимум 10 |
|
V14 |
Сколько сравнений потребуется при последовательном поиске в массиве из 100 элементов? |
|
1 |
Минимум 1 |
|
|
Максимум 10 |
|
|
Максимум 5 |
|
|
Минимум 25 |
|
|
В среднем 20 |
|
V15 |
Сколько сравнений чисел будет произведено при двоичном поиске числа 4 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
V16 |
С какими числами будут сравнения при двоичном поиске числа 4 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
4 |
|
|
1, 2, 3, 4 |
|
|
1, 7, 4 |
|
|
7, 1, 4 |
|
|
2, 4 |
|
V17 |
Сколько сравнений чисел будет произведено при двоичном поиске числа 2 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
1 |
|
V18 |
С какими числами будут сравнения при двоичном поиске числа 2 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
4, 2 |
|
|
1, 2 |
|
|
1, 7, 4, 2 |
|
|
7, 1, 4, 2 |
|
|
2 |
|
V19 |
Сколько сравнений чисел будет произведено при двоичном поиске числа 6 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
1 |
|
V20 |
С какими числами будут сравнения при двоичном поиске числа 6 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
4, 6 |
|
|
1, 2, 6 |
|
|
1, 7, 4, 6 |
|
|
7, 1, 4, 6 |
|
|
6 |
|
V21 |
Сколько сравнений чисел будет произведено при двоичном поиске числа 1 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
3 |
|
|
4 |
|
|
5 |
|
|
1 |
|
|
2 |
|
V22 |
С какими числами будут сравнения при двоичном поиске числа 1 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
4, 2, 1 |
|
|
4, 7, 1 |
|
|
7, 1 |
|
|
7, 4, 1 |
|
|
1 |
|
V23 |
Сколько сравнений чисел будет произведено при двоичном поиске числа 5 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
3 |
|
|
4 |
|
|
5 |
|
|
1 |
|
|
2 |
|
V24 |
С какими числами будут сравнения при двоичном поиске числа 5 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
4, 6, 5 |
|
|
4, 6, 7, 5 |
|
|
1, 7, 4, 5 |
|
|
1, 3, 5 |
|
|
5 |
|
V25 |
Сколько сравнений чисел будет произведено при двоичном поиске числа 7 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
3 |
|
|
1 |
|
|
2 |
|
|
4 |
|
|
7 |
|
V26 |
С какими числами будут сравнения при двоичном поиске числа 7 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
4, 6, 7 |
|
|
4, 6, 5, 7 |
|
|
4, 3, 5, 7 |
|
|
1, 2, 3, 4, 5, 6, 7 |
|
|
7 |
|
V27 |
Сколько сравнений чисел будет произведено при двоичном поиске числа 8 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
3 |
|
|
1 |
|
|
2 |
|
|
4 |
|
|
7 |
|
V28 |
С какими числами будут сравнения при двоичном поиске числа 8 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
4, 6, 7 |
|
|
4, 6, 5, 7 |
|
|
4, 3, 5, 7 |
|
|
1, 2, 3, 4, 5, 6, 7 |
|
|
7 |
|
V29 |
Сколько сравнений чисел будет произведено при двоичном поиске числа 0 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
3 |
|
|
1 |
|
|
2 |
|
|
4 |
|
|
7 |
|
V30 |
С какими числами будут сравнения при двоичном поиске числа 0 в массиве чисел 1, 2, 3, 4, 5, 6, 7? |
|
1 |
4, 2, 1 |
|
|
4, 2, 3 |
|
|
4, 6, 3, 1 |
|
|
7, 6, 5, 4, 3, 2, 1 |
|
|
1 |