ФИТ ИС Алгоритмы и структуры данных (аттестация) 360
.doc
|
M10E1T60 |
Сортировки |
|
V1 |
Как называется сортировка, шаги которой показаны ниже? 4, 7, 6, 2, 5, 3 – исходный массив 4, 6, 2, 5, 3, 7 4, 2, 5, 3, 6, 7 2, 4, 3, 5, 6, 7 2, 3, 4, 5, 6, 7 2, 3, 4, 5, 6, 7 – результат |
|
1 |
Пузырьковая сортировка |
|
|
Шейкерная сортировка |
|
|
Сортировка вставками (включением) |
|
|
Сортировка выбором |
|
|
Быстрая сортировка |
|
V2 |
Как называется сортировка, шаги которой показаны ниже? 2, 4, 5, 3, 1 – исходный массив 2, 4, 3, 1, 5 2, 3, 1, 4, 5 2, 1, 3, 4, 5 1, 2, 3, 4, 5 – результат |
|
1 |
Пузырьковая сортировка |
|
|
Шейкерная сортировка |
|
|
Сортировка вставками (включением) |
|
|
Сортировка выбором |
|
|
Сортировка слиянием |
|
V3 |
К какому алгоритму относится следующий фрагмент кода? for ii=n-1 to 1 step –1 for jj=0 to ii-1 if (arrA(jj) > arrA(jj)) then tmp = arrA(jj) arrA(jj) = arrA(jj+1) arrA(jj+1) = tmp end if next next |
|
1 |
Пузырьковая сортировка |
|
|
Сортировка вставками (включением) |
|
|
Двоичный поиск |
|
|
Вычисление факториала |
|
|
Нахождение простых чисел |
|
V4 |
Как называется сортировка, шаги которой показаны ниже? 4, 7, 6, 2, 5, 3 – исходный массив 4, 6, 2, 5, 3, 7 2, 4, 6, 3, 5, 7 2, 4, 3, 5, 6, 7 2, 3, 4, 5, 6, 7 2, 3, 4, 5, 6, 7 – результат |
|
1 |
Шейкерная сортировка |
|
|
Сортировка вставками (включением) |
|
|
Пузырьковая сортировка |
|
|
Быстрая сортировка |
|
|
Сортировка слиянием |
|
V5 |
Как называется сортировка, шаги которой показаны ниже? 5, 8, 3, 4, 1, 6, 7, 2, 9 – исходный массив 5, 3, 4, 1, 6, 7, 2, 8, 9 1, 5, 3, 4, 2, 6, 7, 8, 9 1, 3, 4, 2, 5, 6, 7, 8, 9 1, 2, 3, 4, 5, 6, 7, 8, 9 1, 2, 3, 4, 5, 6, 7, 8, 9 – результат |
|
1 |
Шейкерная сортировка |
|
|
Сортировка вставками (включением) |
|
|
Пузырьковая сортировка |
|
|
Быстрая сортировка |
|
|
Сортировка слиянием |
|
V6 |
Как называется сортировка, шаги которой показаны ниже? 4, 7, 6, 2, 5, 3 – исходный массив 4, 7, 6, 2, 5, 3 4, 6, 7, 2, 5, 3 2, 4, 6, 7, 5, 3 2, 4, 5, 6, 7, 3 2, 3, 4, 5, 6, 7 – результат |
|
1 |
Сортировка вставками (включением) |
|
|
Пузырьковая сортировка |
|
|
Шейкерная сортировка |
|
|
Быстрая сортировка |
|
|
Сортировка слиянием |
|
V7 |
Как называется сортировка, шаги которой показаны ниже? 2, 4, 5, 3, 1 – исходный массив 2, 4, 5, 3, 1 2, 4, 5, 3, 1 2, 3, 4, 5, 1 1, 2, 3, 4, 5 – результат |
|
1 |
Сортировка вставками (включением) |
|
|
Пузырьковая сортировка |
|
|
Шейкерная сортировка |
|
|
Быстрая сортировка |
|
|
Сортировка слиянием |
|
V8 |
К какому алгоритму относится следующий фрагмент кода? for ii=1 to N-1 curItem = arrA(ii) for jj=ii-1 to 0 step –1 if arrA(jj) > curItem then arr(jj+1) = arrA(jj) else exit for end if next arr(jj+1) = curItem next |
|
1 |
Сортировка вставками (включением) |
|
|
Пузырьковая сортировка |
|
|
Двоичный поиск |
|
|
Вычисление факториала |
|
|
Нахождение простых чисел |
|
V9 |
Каково минимальное количество сравнений ключей при сортировке массива из N элементов методом прямого включения? |
|
1 |
N – 1 |
|
|
N |
|
|
2 * N |
|
|
N * N |
|
|
N! |
|
V10 |
Каково минимальное количество сравнений ключей при сортировке массива из 10 элементов методом прямого включения? |
|
1 |
9 |
|
|
10 |
|
|
5 |
|
|
3 |
|
|
2 |
|
V11 |
Каково минимальное количество сравнений ключей при сортировке массива из 100 элементов методом прямого включения? |
|
1 |
99 |
|
|
10 |
|
|
50 |
|
|
7 |
|
|
1 |
|
V12 |
Каково максимальное количество сравнений ключей при сортировке массива из 4 элементов методом прямого включения? |
|
1 |
6 |
|
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
V13 |
Что используется в сортировке методом двоичного включения? |
|
1 |
Двоичный поиск |
|
|
Последовательный поиск |
|
|
Нахождение медианы |
|
|
Нахождение факториала |
|
|
Функция Аккермана |
|
V14 |
Как называется сортировка, шаги которой показаны ниже? 4, 7, 6, 2, 5, 3 – исходный массив 2, 7, 6, 4, 5, 3 2, 3, 6, 4, 5, 7 2, 3, 4, 6, 5, 7 2, 3, 4, 5, 6, 7 2, 3, 4, 5, 6, 7 – результат |
|
1 |
Сортировка выбором |
|
|
Сортировка вставками (включением) |
|
|
Пузырьковая сортировка |
|
|
Шейкерная сортировка |
|
|
Сортировка слиянием |
|
V15 |
Как называется сортировка, шаги которой показаны ниже? 2, 4, 5, 3, 1 - исходный массив 1, 4, 5, 3, 2 1, 2, 5, 3, 4 1, 2, 3, 5, 4 1, 2, 3, 4, 5 - результат
|
|
1 |
Сортировка выбором |
|
|
Сортировка вставками (включением) |
|
|
Пузырьковая сортировка |
|
|
Шейкерная сортировка |
|
|
Сортировка слиянием |
|
V16 |
К какому алгоритму относится следующий фрагмент кода? for ii=0 to n-2 minZ = arrA(ii) ii_min = ii for jj=ii+1 to n-1 if minZ > arrA(jj) then minZ = arrA(jj) ii_min = jj end if next if ii_min > ii then arr(ii_min) = arrA(ii) arrA(ii) = minZ end if next
|
|
1 |
Сортировка выбором |
|
|
Сортировка вставками (включением) |
|
|
Пузырьковая сортировка |
|
|
Шейкерная сортировка |
|
|
Сортировка слиянием |
|
V17 |
Как соотносятся числа, стоящие в вершинах сортирующего дерева? |
|
1 |
Число, стоящее в любой вершине дерева, должно быть не больше числа из ее родительской вершины |
|
|
Число, стоящее в любой вершине дерева, должно быть не меньше числа из ее родительской вершины |
|
|
Число, стоящее в любой вершине дерева, должно быть равно числу из ее родительской вершины |
|
|
Число, стоящее в любой вершине дерева, должно быть больше или равно числу из ее родительской вершины |
|
|
В вершинах сортирующего дерева могут быть любые числа |
|
V18 |
На сколько может отличаться глубина листьев в сортирующем дереве? |
|
1 |
Масимум на 1 |
|
|
Масимум на 2 |
|
|
Не должны отличаться |
|
|
Минимум на 1 |
|
|
Минимум на 2 |
|
V19 |
Какое дерево является сортирующим деревом? |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
V20 |
Какая сортировка использует сортирующее дерево? |
|
1 |
Пирамидальная сортировка |
|
|
Пузырьковая сортировка |
|
|
Шейкерная сортировка |
|
|
Сортировка выбором |
|
|
Быстрая сортировка |
|
V21 |
Какая сортировка иллюстрируется следующим рисунком? o o o o o o o o o o o – исходный массив o o o o o o o * o o o o o o * o o o * o * o o * o * o * o * * * * * * * * * * * * * * * – результат |
|
1 |
Быстрая сортировка |
|
|
Пузырьковая сортировка |
|
|
Шейкерная сортировка |
|
|
Сортировка выбором |
|
|
Сортировка вставками (включением) |
|
V22 |
К чему относится метод слияния? |
|
1 |
К сортировке |
|
|
К поиску |
|
|
К умножению матриц |
|
|
К вычислению значения многочлена |
|
|
К обходу дерева |
|
V23 |
Почему внутрение сортировки называют внутренними? |
|
1 |
Потому что сортируемые массивы полностью хранятся в оперативной памяти компьютера с прямым (случайным) доступом |
|
|
Потому что сортируемые массивы полностью хранятся в сверхбыстрой регистровой памяти компьютера |
|
|
Потому что сортируемые массивы хранятся в емкой памяти на магнитных лентах |
|
|
Потому что сортируемые массивы хранятся в ПЗУ |
|
|
Потому что сортируемые массивы не входят в память компьютера |
|
V24 |
Почему внешние сортировки называют внешними? |
|
1 |
Потому что сортируемые массивы хранятся в емкой памяти на магнитных лентах |
|
|
Потому что сортируемые массивы полностью хранятся в оперативной памяти компьютера с прямым (случайным) доступом |
|
|
Потому что сортируемые массивы полностью хранятся в сверхбыстрой регистровой памяти компьютера |
|
|
Потому что сортируемые массивы хранятся в ПЗУ |
|
|
Потому что сортируемые массивы не входят в память на магнитных лентах |
|
V25 |
Чему равна медиана в массиве чисел 4, 3, 5, 1, 7, 6, 9? |
|
1 |
5 |
|
|
1 |
|
|
3 |
|
|
9 |
|
|
7 |
|
V26 |
Чему равна медиана в массиве чисел 8, 4, 5, 1, 7, 9, 6? |
|
1 |
6 |
|
|
1 |
|
|
5 |
|
|
9 |
|
|
7 |
|
M11E1T60 |
Рекурсии |
|
V1 |
В рекурсивном алгоритме обязательно должна быть ветка, которая дает решение без чего? |
|
1 |
Без рекурсивного вызова |
|
|
Без массивов |
|
|
Без параметров |
|
|
Без умолчаний |
|
|
Без диагностических сообщений |
|
V2 |
Что делается при каждом рекурсивном вызове процедуры? |
|
1 |
Из стека программы выделяется память |
|
|
Увеличивается индекс массива |
|
|
Проверяется условие выхода за границы |
|
|
Выдается информационное сообщение |
|
|
Срабатывает точка останова |
|
V3 |
Чем больше рекурсивных вызовов, тем больше чего? |
|
1 |
Расход памяти из стека программы |
|
|
Элементов массива |
|
|
Количество исполнения тела цикла |
|
|
Сумма аргументов |
|
|
Правил умолчаний |
|
V4 |
Что может произойти при слишком большом числе рекурсивных вызовов функции? |
|
1 |
Нехватка памяти в стеке программы |
|
|
Деление на ноль |
|
|
Выход из цикла |
|
|
Условие станет истинным |
|
|
Условие станет ложным |
|
V5 |
Как называются числа, вычисляемые по следующей рекуррентной формуле: F(n) = F(n – 1) + F(n – 2); F(1) = F(2) = 1; ? |
|
1 |
Числа Фибоначчи |
|
|
Простые числа |
|
|
Совершенные числа |
|
|
Четные числа |
|
|
Счастливые числа |
|
V6 |
К какому алгоритму относится следующий фрагмент кода? function f(n) if n <= 2 then f = 1 else f = f(n-1) + f(n-2) end if end function |
|
1 |
Нахожение чисел Фибоначчи с помощью рекурсии |
|
|
Нахожение факториала числа |
|
|
Нахождение простых чисел |
|
|
Нахождение наибольшего общего делителя |
|
|
Решение задачи о ханойских башнях |
|
V7 |
К какому алгоритму относится следующий фрагмент кода? function f(n) arrF(1) = 1 arrF(1) = 2 for i = 3 to n arrF(i) = arrF(i–1) + arrF(i–2) next end function |
|
1 |
Нахожение чисел Фибоначчи с помощью массивов |
|
|
Нахожение факториала числа |
|
|
Нахождение простых чисел |
|
|
Нахождение наибольшего общего делителя |
|
|
Решение задачи о ханойских башнях |
|
V8 |
К какому алгоритму относится следующий фрагмент кода? function f(n) if n = 1 then f = 1 else f = n * f(n-1) end if end function |
|
1 |
Нахожение факториала числа с помощью рекурсии |
|
|
Нахожение чисел Фибоначчи |
|
|
Нахождение простых чисел |
|
|
Нахождение наибольшего общего делителя |
|
|
Решение задачи о ханойских башнях |
|
V9 |
К какому алгоритму относится следующий фрагмент кода? function f(n) f = 1 for ii = 1 to n f = f * ii next end function |
|
1 |
Нахожение факториала числа с помощью итераций |
|
|
Нахожение чисел Фибоначчи |
|
|
Нахождение простых чисел |
|
|
Нахождение наибольшего общего делителя |
|
|
Решение задачи о ханойских башнях |
|
V10 |
Что это за функция? A(m,n) = n + 1; при m=0 A(m,n) = A(m-1, 1); при n=0 A(m,n) = A(m-1, A(m, n-1)); в остальных случаях |
|
1 |
Функция Аккермана |
|
|
Функция Стирлинга |
|
|
Функция Ньютона |
|
|
Функция Фибоначчи |
|
|
Функция Евклида |
|
V11 |
Чем является функция Аккермана? |
|
1 |
Примером сложной рекурсии |
|
|
Частью алгоритма сортировки |
|
|
Способом декомпозиции задачи |
|
|
Трехмерным массивом |
|
|
Алгоритмом линейной сложности |
|
V12 |
Сколько аргументов у функции Аккермана? |
|
1 |
2 |
|
|
1 |
|
|
3 |
|
|
0 |
|
|
4 |
|
V13 |
Какая задача классически решается с помощью рекурсии? |
|
1 |
Головоломка Ханойские башни |
|
|
Вычисление значение многочлена |
|
|
Вычисление корней квадратного уравнения |
|
|
Вычисление определенного интеграла |
|
|
Упаковка рюкзака |
|
V14 |
Какой алгоритм НЕ использует рекурсию? |
|
1 |
Линейный поиск |
|
|
Пирамидальная сортировка |
|
|
Быстрая сортировка |
|
|
Вычисление функции Аккермана |
|
|
Головоломка Ханойские башни |
|
V15 |
К какому алгоритму относится следующий фрагмент кода? function moveTower(n, from, to, tmp) if n = 1 then moveDisk(from, to) else moveTower(n-1, from, tmp, to) moveDisk(from, to) moveTower(n-1, tmp, to, from) end if end function |
|
1 |
Головоломка Ханойские башни |
|
|
Вычисление значение многочлена |
|
|
Вычисление корней квадратного уравнения |
|
|
Вычисление определенного интеграла |
|
|
Упаковка рюкзака |
|
M12E1T60 |
Численные алгоритмы |
|
V1 |
Какое число называется простым? |
|
1 |
Число большее 1, которое делится без остатка только на само себя и на 1 |
|
|
Однозначное |
|
|
Запись которого состоит из одинаковых цифр |
|
|
Равное сумме своих цифр |
|
|
Равное сумме своих делителей |
|
V2 |
Для чего применяется алгоритм Решето Эратосфена? |
|
1 |
Для нахождения простых чисел |
|
|
Для нахождения чисел Фибоначчи |
|
|
Для нахождения наибольшего общего делителя двух целых чисел |
|
|
Для нахождения наименьшего общего кратного двух целых чисел |
|
|
Для вычисления факториала числа |
|
V3 |
В каком порядке вычеркиваются числа при поиске простых чисел методом Решета Эратосфена в интервале до 11? |
|
1 |
4, 6, 8, 10, 6, 9 |
|
|
4, 6, 8, 10, 4, 8, 6, 9 |
|
|
4, 6, 8, 10, 6, 9, 11 |
|
|
4, 6, 8, 10, 6, 9, 5, 10 |
|
|
4, 6, 8, 6, 9 |
|
V4 |
В каком порядке вычеркиваются числа при поиске простых чисел методом Решета Эратосфена в интервале до 11? |
|
1 |
4, 6, 8, 10, 6, 9 |
|
|
4, 6, 8, 5, 10, 6, 9 |
|
|
6, 9, 4, 6, 8, 10 |
|
|
4, 6, 8, 10 |
|
|
4, 6, 8, 9 |
|
V5 |
К какому алгоритму относится следующий фрагмент кода? for curStep=2 to sqr(N)+1 if arrN(curStep) = true then for ii = 2*curStep to N-1 step curStep arrN(ii) = false next end If next |
|
1 |
Нахождение простых чисел методом Решета Эратосфена |
|
|
Нахождение чисел Фибоначчи |
|
|
Вычисление функции Аккермана |
|
|
Нахождение наибольшего общего делителя двух целых чисел алгоритмом Евклида |
|
|
Вычисление факториала числа |
|
V6 |
Почему при нахождении простых чисел в пределах 20 не надо проводить вычеркивания с шагом 4? |
|
1 |
Потому что все, что можно вычеркнуть с шагом 4, уже вычеркнуто с шагом 2 |
|
|
Потому что 4 является квадратом числа |
|
|
Так как 4 есть корень из 16 |
|
|
Так как 4 = 3 + 1 |
|
|
Так как 4 = 5 – 1 |
|
V7 |
Почему при нахождении простых чисел в пределах 20 не надо проводить вычеркивания с шагом 11? |
|
1 |
Потому что первый кандидат на вычеркивание будет больше 20 |
|
|
Потому что число 11 нечетное |
|
|
Так как число 11 записывается одинаковыми цифрами |
|
|
Так как 11 = 5 + 6 |
|
|
Так как 11 = 3 + 8 |
|
V8 |
Для чего применяется алгоритм Евклида? |
|
1 |
Для нахождения наибольшего общего делителя двух целых чисел |
|
|
Для нахождения простых чисел |
|
|
Для нахождения чисел Фибоначчи |
|
|
Для нахождения наименньшего общего кратного двух целых чисел |
|
|
Для вычисления факториала числа |
|
V9 |
Для чего применяется алгоритм Евклида? |
|
1 |
Для нахождения наибольшего общего делителя двух целых чисел |
|
|
Для нахождения простых чисел |
|
|
Для вычисления значений многочленов |
|
|
Для нахождения наименньшего общего кратного двух целых чисел |
|
|
Для вычисления факториала числа |
|
V10 |
К какому алгоритму относится следующий фрагмент кода? function f(a, b) if b = 0 then f = a else f = f(b, a MOD b) end if end function |
|
1 |
Нахождение наибольшего общего делителя алгоритмом Евклида |
|
|
Нахождение простых чисел методом Решета Эратосфена |
|
|
Нахождение чисел Фибоначчи |
|
|
Вычисление функции Аккермана |
|
|
Вычисление факториала числа |
|
V11 |
Чему равен НОД (наибольший общий делитель) чисел 250 и 105? |
|
1 |
5 |
|
|
2 |
|
|
3 |
|
|
6 |
|
|
15 |
|
V12 |
Для чего служит алгоритм Винограда? |
|
1 |
Для умножения матриц |
|
|
Для сортировки |
|
|
Для нахождения простых чисел |
|
|
Для решения системы линейных уравнений |
|
|
Для вычисления факториала числа |
|
V13 |
Для чего служит алгоритм Винограда? |
|
1 |
Для умножения матриц |
|
|
Для нахождения наибольшего общего делителя двух целых чисел |
|
|
Для нахождения простых чисел |
|
|
Для нахождения наименньшего общего кратного двух целых чисел |
|
|
Для вычисления факториала числа |
|
V14 |
Для чего служит алгоритм Штрассена? |
|
1 |
Для умножения матриц |
|
|
Для нахождения наибольшего общего делителя двух целых чисел |
|
|
Для нахождения простых чисел |
|
|
Для нахождения наименньшего общего кратного двух целых чисел |
|
|
Для вычисления факториала числа |
|
V15 |
Для чего служит схема Горнера? |
|
1 |
Для вычисления значений многочленов |
|
|
Для умножения матриц |
|
|
Для поиска наибольшего общего делителя двух целых чисел |
|
|
Для нахождения простых чисел |
|
|
Для вычисления факториала числа |
|
V16 |
Для чего служит схема Горнера? |
|
1 |
Для вычисления значений многочленов |
|
|
Для умножения матриц |
|
|
Для решения системы линейных уравнений |
|
|
Для поиска наибольшего общего делителя двух целых чисел |
|
|
Для поиска простых чисел |
|
V17 |
С помощью чего вычисляются значения многочленов? |
|
1 |
С помощью схемы Горнера |
|
|
С помощью функции Аккермана |
|
|
С помощью алгоритма Евклида |
|
|
С помощью сортировки |
|
|
С помощью двоичного поиска |
|
V18 |
Записать многочлен 4x4 + 2x3+ 2x2 – 12x + 6 согласно схеме Горнера |
|
1 |
(((4x + 2)x + 2)x – 12)x + 6 |
|
|
(4x + 2)x + 2)x – 12)x + 6 |
|
|
2 (2x4 + x3+ x2 – 6x + 3) |
|
|
2(2x4 + x3+ x2) – 6(2x + 1) |
|
|
2x2 (2x2 + x + 1) – 6(2x + 1) |
|
V19 |
Записать многочлен 2x3 + 10x2 – 3x + 5 согласно схеме Горнера |
|
1 |
((2x + 10)x – 3)x + 5 |
|
|
((2x – 10)x – 3)x – 5 |
|
|
(2x + 10(x – 3)x + 5 |
|
|
x(2x2 – 3) + 5 (2x2 + 1) |
|
|
x(2x2 + 10x – 3) + 5 |
|
V20 |
Для чего служит метод Гаусса-Жордана? |
|
1 |
Для решения системы линейных уравнений |
|
|
Для вычисление значений многочленов |
|
|
Для умножения матриц |
|
|
Для нахождения наибольшего общего делителя двух целых чисел |
|
|
Для нахождения простых чисел |
|
V21 |
Для чего служит метод Гаусса-Жордана? |
|
1 |
Для решения системы линейных уравнений |
|
|
Для вычисление значений многочленов |
|
|
Для умножения матриц |
|
|
Для сортировки |
|
|
Для нахождения порядковых статистик |
|
V22 |
Какой массив используется в методе Гаусса-Жордана для решения системы из N линейных уравнений с N неизвестными? |
|
1 |
Двумерный из N строк и N+1 столбцов |
|
|
Двумерный из N строк и N столбцов |
|
|
Двумерный из N строк и 2 * N столбцов |
|
|
Одномерный из 2 * N элементов |
|
|
Одномерный из N+1 элементов |
|
V23 |
Какая структура данных используется в методе Гаусса-Жордана для решения системы из N линейных уравнений с N неизвестными? |
|
1 |
Двумерный массив из N строк и N+1 столбцов
|
|
|
Стек на основе массива из N элементов |
|
|
Очередь основе массива из N элементов |
|
|
Запись с 2 * N полями |
|
|
Дерево из N узлов |
|
V24 |
К какому виду приводится массив в методе Гаусса-Жордана для решения системы из 3 линейных уравнений с 3 неизвестными? |
|
1 |
1 0 0 a 0 1 0 b 0 0 1 c |
|
|
1 0 0 a 1 0 0 b 1 0 0 c |
|
|
0 1 0 a 0 1 0 b 0 1 0 c |
|
|
0 0 0 a 0 0 0 b 1 1 1 c |
|
|
1 0 0 0 0 1 0 0 0 0 1 0 |