Ответы на тесты / РОСДИСТАНТ / Алгоритмы и структуры данных / 128 вопросов / Тесты 1-19
В файле собраны ответы к тестам из курса РОСДИСТАНТ / Алгоритмы и структуры данных.
После покупки Вы получите файл, где будет 128 вопросов с ответами.
Верный ответ выделен по тексту.
В демо-файлах представлен пример, как выделены ответы.
Все набрано в Word, можно искать с помощью поиска.
Ниже список вопросов, которые представлены в файле.
Также Вы можете заказать решение тестов и других работ у меня на странице по ссылке:
Промежуточный тест 1
Вопрос 1
Алгоритм обрабатывает массив (см. рисунок). Входные данные алгоритма — k, t, n. От каких из перечисленныз входных данных зависит время работы алгоритма?
Выберите один ответ:
От k, t, n
От k и t
От t и n
От n
Не зависит от входных данных
Вопрос 2
Пусть X — задача из NP. Какое утверждение справедливо для задачи X?
Выберите один ответ:
X может быть неразрешима
Если X можно решить за полиномиальное время на ДМТ, то P = NP
Нет полиномиального алгоритма для X
X — NP-трудная задача
Если X — NP-трудная задача, то она NP-полная
Вопрос 3
Какова сложность алгоритма?
Выберите один ответ:
O(n)
O(k + n)
O(k(n – 1))
O(k)
Вопрос 4
Алгоритм нахождения минимального элемента массива был модифицирован. Теперь он ищет минимальный и максимальный элемент массива. В этом случае асимптотическая сложность алгоритма
Выберите один ответ:
не изменится
увеличится на порядок
уменьшится на порядок
уменьшится в два раза
Вопрос 5
Укажите два наилучших алгоритма по критерию трудоемкости.
Выберите один или несколько ответов:
Алгоритм с логарифмической скоростью роста
Алгоритм с линейной скоростью роста
Алгоритм с линейно-логарифмической скоростью роста
Алгоритм с квадратичной скоростью роста
Вопрос 6
Алгоритм некоторым образом обрабатывает массив (см. рисунок). Алгоритм состоит из двух вложенных циклов. Как асимптотическая сложность зависит от переменной n?
Выберите один ответ:
O(4 * n)
Не зависит от n
O(n)
O((i + j)n)
Вопрос 7
Что понимается под временной сложностью алгоритма?
Выберите один ответ:
Минимальное количество машинного кода для представления алгоритма в ЭВМ
Функция размера входных и выходных данных, равная минимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи данного размера
Максимальное количество машинного кода для представления алгоритма в ЭВМ
Нет го ответа
Вопрос 8
Рассмотрите программу ниже и определите её сложность.
void function(int n) {
int i, j, count=0;
for (i=n/2; i <= n; i++)
for (j = 1; j <= n; j = j*2)
count++;}
Выберите один ответ:
O(log n)
O(n²)
O(n² log n)
O(n log n)
Вопрос 9
Алгоритм F имеет оценку сложности O(n2), а алгоритм G — O(n). Тогда
Выберите один или несколько ответов:
F может быть быстрее G на любом входе
F может быть медленнее G на любом входе
F может быть таким, что для любого n он делает n2 операций на некотором входе размера n
G может быть таким, что для любого n он делает n2 операций на некотором входе размера n
Вопрос 10
Если f(n) = O(n), то какие оценки верны?
Выберите один или несколько ответов:
f(n) = O(10n)
f(n) = O(0.001n)
f(n) = O(n + 1000 / n)
f(n) = o(2n + 5)
f(n) = o(n2)
f(n) = o(0.001n3 + 1000)
f(n) = Θ(n + 10 / n)
f(n) = Θ(n)
Промежуточный тест 2
Вопрос 1
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n при n ≤ 2,
F(n) = F(n − 1) + 3 • F(n − 2) при n > 2.
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Вопрос 2
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 2 при n ≤ 2,
F(n) = F(n − 1) + 3 • F(n − 2) при n > 2.
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.
Вопрос 3
Задан алгоритм вычисления значения функции F(n), где n – натуральное число, который представлен следующими соотношениями:
F(1) = 1, F(2) = 1, F(n) = F(n – 1) * n − 2 * F(n – 2) при n > 2.
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Вопрос 4
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 2 при n ≤ 2,
F(n) = 2 • F(n − 1) + F(n − 2) при n > 2.
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.
Вопрос 5
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n при n ≤ 2,
F(n) = 3 • F(n − 1) − F(n − 2) при n > 2.
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Вопрос 6
Последовательность чисел трибоначчи задается рекуррентным соотношением:
F(1) = 0, F(2) = 1, F(3) = 1, F(n) = F(n – 3) + F(n – 2) + F(n–1) при n > 3, где n – натуральное число.
Чему равно девятое число в последовательности трибоначчи?
В ответе запишите только натуральное число.
Вопрос 7
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 3, F(n) = F(n − 1) * F(n − 2) + (n − 2) при n > 2.
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.
Вопрос 8
Представленный алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 3, F(n) = F(n – 1) * n + F(n–2) * (n – 1) при n > 2.
Каково значение функции F(5)?
В ответе запишите только натуральное число.
Вопрос 9
Последовательность чисел Люка задается рекуррентным соотношением:
F(1) = 2, F(2) = 1, F(n) = F(n – 2) + F(n – 1) при n > 2, где n – натуральное число.
Чему равно десятое число в последовательности Люка?
В ответе запишите только натуральное число.
Вопрос 10
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n при n ≤ 2,
F(n) = F(n − 1) • F(n − 2) при n > 2.
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Промежуточный тест 3
Вопрос 1
Ниже на языке программирования C++ записаны две рекурсивные функции: F и G. Чему будет равно значение, вычисленное при выполнении вызова F(7)?
int F (int n)
{
if (n>2)
return F(n-1)+G(n-2);
else return 1;
}
int G(int n)
{
if(n>2)
return G(n-1)+F(n-2);
else return 1;
}
Вопрос 2
Формирование какой последовательности описывает рекурсивная функция Rec, код которой приведен ниже?
int Rec(int n) {
if (n<4) return n;
return Rec(Rec(n-3));
}
Выберите один ответ:
1, 2, 3, 4, 5, 6, 7, 8, 9, …
1, 2, 3, 1, 2, 3, 1, 2, 3, …
1, 2, 3, 3, 3, 3, 3, 3, 3, …
1, 2, 3, 3, 2, 1, 1, 2, 3, …
Вопрос 3
Ниже на языке программирования C++ записаны две рекурсивные функции: F и G. Чему будет равно значение, вычисленное при выполнении вызова G(6)?
int F (int n)
{
if (n>2)
return F(n-1)+G(n-2);
else return 1;
}
int G(int n)
{
if(n>2)
return G(n-1)+F(n-2);
else return n+1;
}
Вопрос 4
Формирование какой последовательности описывает рекурсивная функция Rec, код которой приведен ниже?
int Rec(int n) {
if (n<5) return n;
return Rec(n-1)+Rec(n%4);
}
Выберите один ответ:
1, 2, 3, 4, 1, 2, 3, 4, ...
1, 2, 3, 4, 5, 6, 7, 8, ...
1, 2, 3, 4, 5, 7, 10, 10, ...
1, 2, 3, 4, 6, 8, 10, 12, ...
Вопрос 5
Формирование какой последовательности описывает рекурсивная функция Rec, код которой приведен ниже?
int Rec(int n) {
if (n<4) return n;
return Rec(Rec(n-3));
}
Выберите один ответ:
1, 2, 3, 1, 2, 3, 1, 2, 3, ...
1, 2, 3, 4, 5, 6, 7, 8, 9, ...
1, 2, 3, 3, 2, 1, 1, 2, 3, ...
Нет го ответа
Промежуточный тест 4
Вопрос 1
Простыми типами данных в С++ являются
Выберите один ответ:
целые — int, вещественные — float или double, символьные — string
целые — int, вещественные — float или double, символьные — char
целые — bool, вещественные — float или double, символьные — string
целые — int, вещественные — float или real, символьные — char
Вопрос 2
Структура объявления переменных в С++ имеет вид
Выберите один ответ:
[=];< идент. 2>,…
[:=], < идент. 2>,…
[=], < идент. 2>,…
[==]; < идент. 2>,…
Вопрос 3
Какой из перечисленных типов данных не является типом данных в С++?
Выберите один ответ:
float
double
int
real
Вопрос 4
Назовите определение типа данных (выберите 2 варианта ответа).
Выберите один или несколько ответов:
Возможность ввода/вывода данных
Множество (диапазон) значений, которые могут принимать величины этого типа
Наименование библиотек для подключения функций
Операции и функции, которые можно применять к данным этого типа
Вопрос 5
Какое ключевое слово указывает на то, что целая переменная не может принимать отрицательные значения?
Выберите один ответ:
positive
long
unsigned
Другое
Нет такого зарезервированного слова
Промежуточный тест 5
Вопрос 1
Каков порядковый номер последнего элемента массива, если размер массива 19?
Выберите один ответ:
19
18
Порядковый номер определяется программистом
100
Вопрос 2
В какой из представленных строк выполняется обращение к седьмому элементу массива, если размер массива равен 10?
Выберите один ответ:
mas
mas(7)
mas[6]
mas[7]
Вопрос 3
Словосочетание «Hello world!» может быть сохранено в символьном массиве размером n элементов. Чему равно n?
Выберите один ответ:
12
10
13
11
Вопрос 4
Укажите строку, которая возвращает адрес первого элемента в массиве arr.
Выберите один ответ:
&arr
arr[1]
arr[0]
arr
Вопрос 5
В каком из вариантов ответов объявлен двумерный массив?
Выберите один ответ:
int array[20, 20]
array anarray[20][20]
int anarray[20][20]
char array[20]
Вопрос 6
Таблицы в языке программирования С++ бывают
Выберите один ответ:
только одномерными
только двумерными
только однострочными и двустрочными
одномерными и двумерными
Промежуточный тест 6
Вопрос 1
Определите основной недостаток использования связного представления данных (обращения к данным через указатели).
Выберите один ответ:
Размер структуры ограничивается только доступным объемом машинной памяти
При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей
На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память
Нет го ответа
Вопрос 2
Укажите зарезервированное ключевое слово для высвобождения выделенной памяти.
Выберите один ответ:
free
remove
delete
clear
Вопрос 3
Как освободить память от удаленного из списка элемента?
Выберите один ответ:
p=getnode
ptr(p)=nil
freenode(p)
p=lst
Вопрос 4
Определите характеристику динамической структуры данных (укажите 2 параметра).
Выберите один или несколько ответов:
Размерность структуры может меняться в процессе выполнения программы
Она не имеет имени
Она работает только с массивами
Она не требует дополнительной памяти
Вопрос 5
В чем заключается недостаток связного представления данных (обращения к данным через указатели)?
Выберите один ответ:
Размер структуры ограничивается только доступным объемом машинной памяти
При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей
Большая гибкость структуры
Доступ к элементам связной структуры может быть менее эффективным по времени
Вопрос 6
Укажите структуру, в которой доступ к элементам осуществляется в любой момент времени и к любому элементу с помощью индексов.
Выберите один ответ:
Множество
Массив
Очередь
Запись
Вопрос 7
Укажите достоинства связного представления данных (обращения к данным через указатели). (Выберите 2 показателя.)
Выберите один или несколько ответов:
При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей
Большая гибкость структуры
Доступ к элементам связной структуры может быть менее эффективным по времени
На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память
Вопрос 8
Какая структура является динамическими? (Укажите 2 параметра.)
Выберите один или несколько ответов:
Ей выделяется память в процессе выполнения программы
Она не имеет имени
Она работает только с массивами
Она не требует дополнительной памяти
Вопрос 9
Укажите зарезервированное ключевое слово для динамического выделения памяти.
Выберите один ответ:
new
value
create
malloc
Вопрос 10
В чем заключаются достоинства связного представления данных (обращения к данным через указатели)? (Выберите 2 показателя.)
Выберите один или несколько ответов:
Размер структуры ограничивается только доступным объемом машинной памяти
При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей
Доступ к элементам связной структуры может быть менее эффективным по времени
На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память
Промежуточный тест 7
Вопрос 1
Что позволяет делать процедура, показанная ниже?
Выберите один ответ:
Добавлять узел в начало двусвязного списка
Добавлять узел в конец двусвязного списка
Добавлять узел после заданного узла в двусвязном списке
Добавлять узел перед заданным узлом в двусвязном списке
Вопрос 2
Что можно объявить с помощью представленного ниже кода?
Выберите один ответ:
Односвязный список
Двусвязный список
Стек
Очередь
Дерево
Вопрос 3
Что можно объявить с помощью кода, представленного ниже?
Выберите один ответ:
Односвязный список
Двусвязный список
Стек
Очередь
Дерево
Вопрос 4
Что объявляется с помощью кода, представленного ниже?
Выберите один или несколько ответов:
Односвязный список
Двусвязный список
Стек
Очередь
Дерево
Вопрос 5
Что позволяет делать процедура, представленная ниже?
Выберите один ответ:
Добавлять узел в начало двусвязного списка
Добавлять узел в конец двусвязного списка
Добавлять узел после заданного узла в двусвязном списке
Добавлять узел перед заданным узлом в двусвязном списке
Вопрос 6
Что можно объявить с помощью кода, указанного ниже?
Выберите один или несколько ответов:
Односвязный список
Двусвязный список
Стек
Очередь
Дерево
Вопрос 7
С помощью кода можно объявить
Выберите один или несколько ответов:
односвязный список
двусвязный список
стек
очередь
дерево
Вопрос 8
Что позволяет делать процедура, показанная ниже?
Выберите один ответ:
Добавлять узел в начало списка
Добавлять узел в конец списка
Добавлять узел после заданного узла в списке
Добавлять узел перед заданным узлом в списке
Вопрос 9
Очередью называется
Выберите один ответ:
однородный набор величин одного и того же типа, идентифицируемых вычисляемым индексом
линейно упорядоченный набор следующих друг за другом компонент
набор именованных компонент разного типа, объединенных общим именем
множество элементов
Вопрос 10
С помощью какой структуры данных наиболее рационально реализовать очередь?
Выберите один ответ:
С помощью стека
С помощью списка
С помощью дека
С помощью массива
Вопрос 11
Процедура позволяет
Выберите один ответ:
добавлять узел в начало списка
добавлять узел в конец списка
добавлять узел после заданного узла в списке
добавлять узел перед заданным узлом в списке
Промежуточный тест 8
Вопрос 1
Какие структуры являются динамическими? (Укажите 2 вида.)
Выберите один или несколько ответов:
Однонаправленные (односвязные) списки
Циклические списки
Массивы
Структуры
Вопрос 2
Какое из приведенных утверждений ?
А. Указатели разных типов нельзя присваивать друг другу без операции приведения типа.
Б. Указатель, объявленный как void, может быть разыменован.
Выберите один ответ:
Только А
Только Б
Верны оба утверждения
Оба утверждения ложны
Вопрос 3
Динамической структурой данных является
Выберите один ответ:
очередь
запись
дерево
массив
Вопрос 4
К динамическим структурам относятся (выберите 2 вида):
Выберите один или несколько ответов:
двунаправленные (двусвязные) списки
стек
массивы
структуры
Вопрос 5
Структура данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов, называется
Выберите один ответ:
однонаправленные (односвязные) списки
дерево
стек
очередь
Промежуточный тест 9
Вопрос 1
Как вычисляется коэффициент заполнения для равномерно распределенной хэш-функции H: k -> {0,..., N-1}?
Выберите один ответ:
α = N/M
α = M/N
α = 1 + M/N
α = 1 + N/M
Вопрос 2
Если использовать универсальное семейство хэш-функций для хранения n ключей, то какова будет вероятность получить хотя бы одну коллизию при размере хэш-таблицы M = n2?
Выберите один ответ:
Не больше 2/3
Не больше 1/2
Меньше 1/M
Меньше 1/N
Вопрос 3
В предположении гипотезы простого равномерного хэширования чему равно среднее время безуспешного поиска ключа для хэш-функции H: k -> {0,..., N-1}?
Выберите один ответ:
Θ(M/N)
Θ(log M/N)
Θ(M * N)
Θ(M/N + 1)
Вопрос 4
В случае универсального хэширования чему равно среднее время успешного поиска ключа для хэш-функции H: k -> {0,..., N-1}, если k1, ..., kn — все ключи, присутствующие в хэш-таблице?
Выберите один ответ:
Θ(1)
Θ(M/N + 1)
Θ(M)
Θ(N)
Вопрос 5
Какая формула задает линейный способ просматривания ячеек хэш-таблицы?
Выберите один ответ:
h(k,j) = (h0(k) + j) mod m
h(k,j) = (h0(k) + j * h1(k)) mod m
h(k,j) = (h0(k) + j * h0(k)) mod m
h(k,j) = (h0(k) + k) mod m
Промежуточный тест 10
Вопрос 1
Укажите общие критерии оценки алгоритмов сортировки.
Выберите один или несколько ответов:
Вид алгоритма сортировки
Время работы в лучшем и худшем случаях
Реализация на конкретном языке программирования
Поведение алгоритма сортировки
Вопрос 2
Определите тип сортировки.
Выберите один ответ:
Пузырьковая
Сортировка отбором
Сортировка вставками
Сортировка Шелла
Вопрос 3
Какая процедура приведена ниже?
void Exchange (int i, int j, int *x) {
int tmp;
tmp=x[i];
x[i]=x[j];
x[j]=tmp;
}
Выберите один ответ:
Процедура упорядочения по убыванию
Процедура упорядочения по возрастанию
Процедура сортировки элементов
Процедура обмена двух элементов
Вопрос 4
Ниже представлен алгоритм. К какому типу сортировки он относится?
Выберите один ответ:
К пузырьковой сортировке
К сортировке отбором
К сортировке вставками
К сортировке Шелла
Вопрос 5
Как можно ускорить алгоритм сортировки «пузырьком»?
Выберите один ответ:
Добавить во внутренний цикл проверку на отсутствие перестановок
Добавить перестановку с шагом (increment)
Добавить во внешний цикл проверку на отсутствие перестановок
Добавить возможность сортировки по убыванию
Промежуточный тест 11
Вопрос 1
Дан массив с элементами (35,08,10,15,20,11,18,25,23,30,40). Какой массив будет получен после применения алгоритма Шелла с шагом 4 при сортировке по возрастанию? Последовательность запишите через запятую без пробелов.
Вопрос 2
Какие утверждения справедливы для медианного элемента массива?
Выберите один или несколько ответов:
Поиск медианы равносилен сортировке массива
Медианный элемент является идеальным с точки зрения выбора опорного элемента
Медианный элемент всегда находится в середине массива
Медиана — это среднее арифметическое всех элементов массива
Вопрос 3
При какой сортировке происходит быстрая перестановка далеких неупорядоченных пар значений (сортировка таких пар обычно требует большого количества перестановок, если используется сравнение только соседних элементов)?
Выберите один ответ:
При сортировке слиянием
При бинарной пирамидальной сортировке
При сортировке Хоара
При сортировке Шелла
Вопрос 4
Некоторый массив размером N был отсортирован за время, пропорциональное N1,27. По какому алгоритму выполнялась сортировка?
Выберите один ответ:
Хоара
Шелла
Перестановками
Отбором
Вставками
Вопрос 5
Дан массив элементов: 4, 7, 3, 8, 5, 6, 3, 7, 2, 6, 8. Укажите порядок элементов этого массива после выполнения второго прохода сортировки Хоара по неубыванию. Опорный элемент расположен на средней позиции.
Выберите один ответ:
4, 3, 3, 2, 5, 6, 7, 7, 8, 6, 8
2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8
3, 4, 5, 7, 8, 2, 3, 6, 6, 7, 8
3, 2, 4, 3, 5, 6, 6, 7, 7, 8, 8
Промежуточный тест 12
Вопрос 1
Какие утверждения справедливы для сортировки массивов методом слияния?
Выберите один или несколько ответов:
Сортировка основана на выделении и слиянии упорядоченных серий
Сортировка заканчивается, когда в массиве получена единственная серия
С каждым этапом сортировки в массиве образуются всё более длинные серии
Сортировка слиянием работает быстрее улучшенных методов
Вопрос 2
Дан файл 5 7 3 2 8 4 1. Какой файл получится при применении алгоритма сортировки простым слиянием после первого прохода? (Введите числа через пробел.)
Вопрос 3
Дан файл 3 2 17 7 8 9 1 4 6 9 2 3 1 18. Какой файл получится в результате применения алгоритма сортировки естественным слиянием после первого прохода? (Введите числа через пробел.)
Вопрос 4
В алгоритме внешней сортировки используется два вспомогательных файла и отдельно реализуются распределение и слияние. Определите характеристики такой сортировки.
Выберите один или несколько ответов:
Многопутевая
Двухпутевая
Однофазная
Двухфазная
Вопрос 5
Укажите сортировку, особенностью которой является то, что она работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями (например, при сортировке данных на жестком диске).
Выберите один ответ:
Сортировка слиянием
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
Промежуточный тест 13
Вопрос 1
Какой метод поиска представлен в следующем фрагменте?
REPEAT I:=I+1
UNTIL (A[I]=X) OR (I=N)
Выберите один ответ:
Последовательный
Двоичный
Восходящий
Нисходящий
Смешанный
Вопрос 2
Имеется двоичное дерево поиска, содержащее целые числа от 1 до 7. Каким будет результат нисходящего просмотра?
Выберите один ответ:
1, 3, 2, 5, 7, 6, 4
7, 6, 5, 4, 3, 2, 1
1, 2, 3, 4, 5, 6, 7
4, 2, 1, 3, 6, 5, 7
4, 2, 6, 1, 3, 5, 7
Вопрос 3
В каком случае двоичное дерево будет деревом поиска?
Выберите один ответ:
Если в одной части дерева хранятся значения, которые больше вершины, а в другой — те, что меньше
Если матрица достижимости для него будет бинарной
Если орграф такого дерева будет циклическим
Если орграф такого дерева будет ациклическим
Вопрос 4
Имеется неупорядоченный массив целых чисел из 8 элементов. Сколько операций сравнения потребуется для нахождения искомого ключа, если он находится в конце массива?
Выберите один ответ:
1
8
0
7
4
Вопрос 5
Имеется неупорядоченный массив целых чисел из 10 элементов. Сколько операций сравнения потребуется для установления факта отсутствия искомых данных в этом массиве?
Выберите один ответ:
9
0
1
10
5
Вопрос 6
Какой поиск не требует сортировки значений множества?
Выберите один ответ:
Бинарный (двоичный, дихотомический) поиск
Последовательный (линейный) поиск
Поиск с барьером
Поиск через слияние
Промежуточный тест 14
Вопрос 1
Какие действия предпринимаются для сохранения свойств красно-черного дерева, если при операции вставки вершины x элементы x и y оказались красными (y — родитель x, y — корень)?
Выберите один ответ:
x становится черным
y становится черным
Никакие действия не предпринимаются
x и y становятся черными
Вопрос 2
При вставке элемента в красно-черное дерево в случае возникновения «красно-красного» нарушения, когда «дядя» добавляемого узла — черный и при этом цепочка узлов образует прямую линию, потребуется
Выберите один ответ:
перекрасить вершины
перекрасить вершины и произвести левый поворот
перекрасить вершины и произвести правый поворот
произвести двойной поворот
Вопрос 3
При вставке элемента в красно-черное дерево в случае возникновения «красно-красного» нарушения, когда «дядя» добавляемого узла — черный и при этом цепочка узлов образует угол, потребуется
Выберите один ответ:
перекрасить вершины
перекрасить вершины и произвести левый поворот
перекрасить вершины и произвести правый поворот
произвести двойной поворот
Вопрос 4
Какие действия следует предпринять для сохранения свойств красно-черного дерева после операции вставки вершины x в следующей ситуации: A — родитель x, B — родитель A; B — черная вершина; A, C — красные; C — дядя x?
Выберите один ответ:
Никаких действий предпринимать не нужно
A и C сделать черными, B — красным
A сделать черными, x — красным
x сделать черным
Вопрос 5
Какие свойства могут нарушаться при вставке элемента в красно-черное дерево?
Выберите один или несколько ответов:
Каждый узел является красным или черным
Корень дерева является черным
Каждый лист дерева (NULL) является черным
У красного узла оба дочерних узла — черные
У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество черных узлов
Вопрос 6
Отметьте утверждения, справедливые для красно-черных деревьев.
Выберите один или несколько ответов:
Все листья черные
Если у красного родителя два сына, то их цвета черные
Количество черных вершин на пути от корня до листьев должно быть одинаковым
У черных вершин все дети красные
Красно-черные деревья сбалансированы
Высота поддеревьев различается не более чем на 1
Вопрос 7
Какими свойствами обладает красно-черное дерево?
Выберите один или несколько ответов:
Каждый лист дерева является черным
У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество черных узлов
У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество красных узлов
У черного узла оба дочерних узла — красные
Промежуточный тест 15
Вопрос 1
Пусть — неориентированный граф, где , .Число связных компонент данного графа равно
Вопрос 2
Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился двудольный граф?
Вопрос 3
Число полных трехвершинных подграфов в полном двудольном графе К6,7 равно
Вопрос 4
Граф G имеет 4 вершины, а граф H имеет 5 вершин. Сколько единиц будет в матрице смежности графа G H?
,
Вопрос 5
Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?
Выберите один ответ:
14
15
16
13
17
Вопрос 6
Граф G имеет 4 вершины, а граф H имеет 5 вершин. Сколько единиц будет в матрице смежности графа G H?
,
Вопрос 7
Сколько рёбер в полном графе с 20 вершинами?
Вопрос 8
Сколько имеется неизоморфных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?
Вопрос 9
В двудольном графе одна доля состоит из пяти вершин степени 2, а другая — из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?
Вопрос 10
В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?
Выберите один ответ:
7
14
18
21
Промежуточный тест 16
Вопрос 1
Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?
Вопрос 2
Какие из представленных графов являются эйлеровыми?
Выберите один ответ:
1, 2
1, 3
1, 4
2, 3
2, 4
Вопрос 3
Чему равно цикломатическое число графа?
Вопрос 4
Чему равно цикломатическое число графа?
Вопрос 5
Чему равно цикломатическое число графа?
Вопрос 6
Чему равно цикломатическое число графа?
Вопрос 7
В графе из n вершин остов содержит
Выберите один ответ:
n + 1 ребер
n – ¬1 ребер
n ребер
2n ребер
Промежуточный тест 17
Вопрос 1
Дано описание алгоритма поиска кратчайшего пути на графе: «Алгоритм находит кратчайший путь из данной вершины до остальных вершин. Строится множество S вершин, для которых кратчайшие пути от начальной вершины уже известны. На каждом шаге ко множеству S добавляется та из оставшихся вершин, расстояние до которой от начальной вершины меньше, чем для других оставшихся вершин». Укажите название алгоритма.
Выберите один ответ:
Алгоритм Дейкстры
Алгоритм Флойда
Волновой алгоритм
Алгоритм перебора с возвратом
Вопрос 2
От чего зависит асимптотика алгоритма Прима?
Выберите один или несколько ответов:
От способа хранения графа
От способа хранения вершин, не входящих в дерево
От способа модификации узлов графа
От способа изменения узлов графа
Вопрос 3
Дано описание алгоритма поиска кратчайшего пути на графе: «Алгоритм находит кратчайшее расстояние между двумя любыми вершинами графа на основании того факта, что всякий неэлементарный кратчайший путь состоит из других кратчайших путей». Укажите название алгоритма.
Выберите один ответ:
Алгоритм Дейкстры
Алгоритм Флойда
Волновой алгоритм
Алгоритм перебора с возвратом
Вопрос 4
Метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами называется
Выберите один ответ:
модульное программирование
динамическое программирование
комплексное программирование
программирование с отходом назад
жадное программирование
Вопрос 5
Алгоритм Прима применяется
Выберите один ответ:
для ориентированных графов
для неориентированных графов
для детерминированных графов
для взвешенных неориентированных графов
для взвешенных ориентированных графов
Промежуточный тест 18
Вопрос 1
На каждом шаге ветвления выбирается множество
Выберите один ответ:
с наибольшей оценкой
с наименьшей оценкой
с оптимальной оценкой
со средней оценкой
Вопрос 2
Задача коммивояжера относится
Выберите один ответ:
к целочисленному программированию
к аналитической геометрии
к анализу бесконечно малых величин
к евклидовой геометрии
Вопрос 3
Процесс ветвления можно представить в виде дерева, в котором
Выберите один ответ:
каждая вершина — это один маршрут
каждая вершина — это множество маршрутов
есть циклы
каждая вершина — это ребро в маршруте
Вопрос 4
Дана матрица стоимостей перевода системы из состояния в состояние.
1 2 3 4 5
1 10 15 7 10
2 5 10 15 20
3 8 12 20 7
4 14 8 6 15
5 10 3 25 6
Найдите самый дешевый способ провести систему по всем состояниям с возвращением в исходное состояние. Ответ запишите в виде 2-3-4-5-1-2.
Вопрос 5
Дана матрица стоимостей перевода системы из состояния в состояние.
1 2 3 4 5
1 10 8 25 10
2 1 10 15 20
3 8 9 20 7
4 14 5 24 15
5 10 8 25 6
Найдите самый дешевый способ провести систему по всем состояниям с возвращением в исходное состояние. Ответ запишите в виде 2-3-4-5-1-2.
Промежуточный тест 19
Вопрос 1
В полном графе со множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?
Вопрос 2
Что происходит с хроматическим числом графа при удалении ребра?
Выберите один ответ:
Увеличивается
Уменьшается
Уменьшается или не изменяется
Может увеличиться, уменьшиться или остаться прежним
Вопрос 3
Хроматическое число дерева равно
Вопрос 4
Хроматическое число полного 5-вершинного графа равно
Вопрос 5
Какие из приведенных ниже условий являются необходимыми и достаточными для того, чтобы граф имел хроматическое число 2?
Выберите один ответ:
Степени вершин не превосходят 2
Нет циклов нечетной длины
Каждая компонента связности — цепь
Каждая компонента связности — цикл четной длины или цепь
Вопрос 6
Хроматическое число полного двудольного графа К4,3 равно
Промежуточный тест 1
Вопрос 1
Алгоритм обрабатывает массив (см. рисунок). Входные данные алгоритма — k, t, n. От каких из перечисленныз входных данных зависит время работы алгоритма?
Выберите один ответ:
От k, t, n
От k и t
От t и n
От n
Не зависит от входных данных
Вопрос 2
Пусть X — задача из NP. Какое утверждение справедливо для задачи X?
Выберите один ответ:
X может быть неразрешима
Если X можно решить за полиномиальное время на ДМТ, то P = NP
Нет полиномиального алгоритма для X
X — NP-трудная задача
Если X — NP-трудная задача, то она NP-полная
Вопрос 3
Какова сложность алгоритма?
Выберите один ответ:
O(n)
O(k + n)
O(k(n – 1))
O(k)
Вопрос 4
Алгоритм нахождения минимального элемента массива был модифицирован. Теперь он ищет минимальный и максимальный элемент массива. В этом случае асимптотическая сложность алгоритма
Выберите один ответ:
не изменится
увеличится на порядок
уменьшится на порядок
уменьшится в два раза
Вопрос 5
Укажите два наилучших алгоритма по критерию трудоемкости.
Выберите один или несколько ответов:
Алгоритм с логарифмической скоростью роста
Алгоритм с линейной скоростью роста
Алгоритм с линейно-логарифмической скоростью роста
Алгоритм с квадратичной скоростью роста
Вопрос 6
Алгоритм некоторым образом обрабатывает массив (см. рисунок). Алгоритм состоит из двух вложенных циклов. Как асимптотическая сложность зависит от переменной n?
Выберите один ответ:
O(4 * n)
Не зависит от n
O(n)
O((i + j)n)
Вопрос 7
Что понимается под временной сложностью алгоритма?
Выберите один ответ:
Минимальное количество машинного кода для представления алгоритма в ЭВМ
Функция размера входных и выходных данных, равная минимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи данного размера
Максимальное количество машинного кода для представления алгоритма в ЭВМ
Нет го ответа
Вопрос 8
Рассмотрите программу ниже и определите её сложность.
void function(int n) {
int i, j, count=0;
for (i=n/2; i <= n; i++)
for (j = 1; j <= n; j = j*2)
count++;}
Выберите один ответ:
O(log n)
O(n²)
O(n² log n)
O(n log n)
Вопрос 9
Алгоритм F имеет оценку сложности O(n2), а алгоритм G — O(n). Тогда
Выберите один или несколько ответов:
F может быть быстрее G на любом входе
F может быть медленнее G на любом входе
F может быть таким, что для любого n он делает n2 операций на некотором входе размера n
G может быть таким, что для любого n он делает n2 операций на некотором входе размера n
Вопрос 10
Если f(n) = O(n), то какие оценки верны?
Выберите один или несколько ответов:
f(n) = O(10n)
f(n) = O(0.001n)
f(n) = O(n + 1000 / n)
f(n) = o(2n + 5)
f(n) = o(n2)
f(n) = o(0.001n3 + 1000)
f(n) = Θ(n + 10 / n)
f(n) = Θ(n)
Промежуточный тест 2
Вопрос 1
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n при n ≤ 2,
F(n) = F(n − 1) + 3 • F(n − 2) при n > 2.
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Вопрос 2
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 2 при n ≤ 2,
F(n) = F(n − 1) + 3 • F(n − 2) при n > 2.
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.
Вопрос 3
Задан алгоритм вычисления значения функции F(n), где n – натуральное число, который представлен следующими соотношениями:
F(1) = 1, F(2) = 1, F(n) = F(n – 1) * n − 2 * F(n – 2) при n > 2.
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Вопрос 4
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 2 при n ≤ 2,
F(n) = 2 • F(n − 1) + F(n − 2) при n > 2.
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.
Вопрос 5
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n при n ≤ 2,
F(n) = 3 • F(n − 1) − F(n − 2) при n > 2.
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Вопрос 6
Последовательность чисел трибоначчи задается рекуррентным соотношением:
F(1) = 0, F(2) = 1, F(3) = 1, F(n) = F(n – 3) + F(n – 2) + F(n–1) при n > 3, где n – натуральное число.
Чему равно девятое число в последовательности трибоначчи?
В ответе запишите только натуральное число.
Вопрос 7
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 3, F(n) = F(n − 1) * F(n − 2) + (n − 2) при n > 2.
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.
Вопрос 8
Представленный алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 3, F(n) = F(n – 1) * n + F(n–2) * (n – 1) при n > 2.
Каково значение функции F(5)?
В ответе запишите только натуральное число.
Вопрос 9
Последовательность чисел Люка задается рекуррентным соотношением:
F(1) = 2, F(2) = 1, F(n) = F(n – 2) + F(n – 1) при n > 2, где n – натуральное число.
Чему равно десятое число в последовательности Люка?
В ответе запишите только натуральное число.
Вопрос 10
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n при n ≤ 2,
F(n) = F(n − 1) • F(n − 2) при n > 2.
Чему равно значение функции F(6)?
В ответе запишите только натуральное число.
Промежуточный тест 3
Вопрос 1
Ниже на языке программирования C++ записаны две рекурсивные функции: F и G. Чему будет равно значение, вычисленное при выполнении вызова F(7)?
int F (int n)
{
if (n>2)
return F(n-1)+G(n-2);
else return 1;
}
int G(int n)
{
if(n>2)
return G(n-1)+F(n-2);
else return 1;
}
Вопрос 2
Формирование какой последовательности описывает рекурсивная функция Rec, код которой приведен ниже?
int Rec(int n) {
if (n<4) return n;
return Rec(Rec(n-3));
}
Выберите один ответ:
1, 2, 3, 4, 5, 6, 7, 8, 9, …
1, 2, 3, 1, 2, 3, 1, 2, 3, …
1, 2, 3, 3, 3, 3, 3, 3, 3, …
1, 2, 3, 3, 2, 1, 1, 2, 3, …
Вопрос 3
Ниже на языке программирования C++ записаны две рекурсивные функции: F и G. Чему будет равно значение, вычисленное при выполнении вызова G(6)?
int F (int n)
{
if (n>2)
return F(n-1)+G(n-2);
else return 1;
}
int G(int n)
{
if(n>2)
return G(n-1)+F(n-2);
else return n+1;
}
Вопрос 4
Формирование какой последовательности описывает рекурсивная функция Rec, код которой приведен ниже?
int Rec(int n) {
if (n<5) return n;
return Rec(n-1)+Rec(n%4);
}
Выберите один ответ:
1, 2, 3, 4, 1, 2, 3, 4, ...
1, 2, 3, 4, 5, 6, 7, 8, ...
1, 2, 3, 4, 5, 7, 10, 10, ...
1, 2, 3, 4, 6, 8, 10, 12, ...
Вопрос 5
Формирование какой последовательности описывает рекурсивная функция Rec, код которой приведен ниже?
int Rec(int n) {
if (n<4) return n;
return Rec(Rec(n-3));
}
Выберите один ответ:
1, 2, 3, 1, 2, 3, 1, 2, 3, ...
1, 2, 3, 4, 5, 6, 7, 8, 9, ...
1, 2, 3, 3, 2, 1, 1, 2, 3, ...
Нет го ответа
Промежуточный тест 4
Вопрос 1
Простыми типами данных в С++ являются
Выберите один ответ:
целые — int, вещественные — float или double, символьные — string
целые — int, вещественные — float или double, символьные — char
целые — bool, вещественные — float или double, символьные — string
целые — int, вещественные — float или real, символьные — char
Вопрос 2
Структура объявления переменных в С++ имеет вид
Выберите один ответ:
[=];< идент. 2>,…
[:=], < идент. 2>,…
[=], < идент. 2>,…
[==]; < идент. 2>,…
Вопрос 3
Какой из перечисленных типов данных не является типом данных в С++?
Выберите один ответ:
float
double
int
real
Вопрос 4
Назовите определение типа данных (выберите 2 варианта ответа).
Выберите один или несколько ответов:
Возможность ввода/вывода данных
Множество (диапазон) значений, которые могут принимать величины этого типа
Наименование библиотек для подключения функций
Операции и функции, которые можно применять к данным этого типа
Вопрос 5
Какое ключевое слово указывает на то, что целая переменная не может принимать отрицательные значения?
Выберите один ответ:
positive
long
unsigned
Другое
Нет такого зарезервированного слова
Промежуточный тест 5
Вопрос 1
Каков порядковый номер последнего элемента массива, если размер массива 19?
Выберите один ответ:
19
18
Порядковый номер определяется программистом
100
Вопрос 2
В какой из представленных строк выполняется обращение к седьмому элементу массива, если размер массива равен 10?
Выберите один ответ:
mas
mas(7)
mas[6]
mas[7]
Вопрос 3
Словосочетание «Hello world!» может быть сохранено в символьном массиве размером n элементов. Чему равно n?
Выберите один ответ:
12
10
13
11
Вопрос 4
Укажите строку, которая возвращает адрес первого элемента в массиве arr.
Выберите один ответ:
&arr
arr[1]
arr[0]
arr
Вопрос 5
В каком из вариантов ответов объявлен двумерный массив?
Выберите один ответ:
int array[20, 20]
array anarray[20][20]
int anarray[20][20]
char array[20]
Вопрос 6
Таблицы в языке программирования С++ бывают
Выберите один ответ:
только одномерными
только двумерными
только однострочными и двустрочными
одномерными и двумерными
Промежуточный тест 6
Вопрос 1
Определите основной недостаток использования связного представления данных (обращения к данным через указатели).
Выберите один ответ:
Размер структуры ограничивается только доступным объемом машинной памяти
При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей
На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память
Нет го ответа
Вопрос 2
Укажите зарезервированное ключевое слово для высвобождения выделенной памяти.
Выберите один ответ:
free
remove
delete
clear
Вопрос 3
Как освободить память от удаленного из списка элемента?
Выберите один ответ:
p=getnode
ptr(p)=nil
freenode(p)
p=lst
Вопрос 4
Определите характеристику динамической структуры данных (укажите 2 параметра).
Выберите один или несколько ответов:
Размерность структуры может меняться в процессе выполнения программы
Она не имеет имени
Она работает только с массивами
Она не требует дополнительной памяти
Вопрос 5
В чем заключается недостаток связного представления данных (обращения к данным через указатели)?
Выберите один ответ:
Размер структуры ограничивается только доступным объемом машинной памяти
При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей
Большая гибкость структуры
Доступ к элементам связной структуры может быть менее эффективным по времени
Вопрос 6
Укажите структуру, в которой доступ к элементам осуществляется в любой момент времени и к любому элементу с помощью индексов.
Выберите один ответ:
Множество
Массив
Очередь
Запись
Вопрос 7
Укажите достоинства связного представления данных (обращения к данным через указатели). (Выберите 2 показателя.)
Выберите один или несколько ответов:
При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей
Большая гибкость структуры
Доступ к элементам связной структуры может быть менее эффективным по времени
На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память
Вопрос 8
Какая структура является динамическими? (Укажите 2 параметра.)
Выберите один или несколько ответов:
Ей выделяется память в процессе выполнения программы
Она не имеет имени
Она работает только с массивами
Она не требует дополнительной памяти
Вопрос 9
Укажите зарезервированное ключевое слово для динамического выделения памяти.
Выберите один ответ:
new
value
create
malloc
Вопрос 10
В чем заключаются достоинства связного представления данных (обращения к данным через указатели)? (Выберите 2 показателя.)
Выберите один или несколько ответов:
Размер структуры ограничивается только доступным объемом машинной памяти
При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей
Доступ к элементам связной структуры может быть менее эффективным по времени
На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память
Промежуточный тест 7
Вопрос 1
Что позволяет делать процедура, показанная ниже?
Выберите один ответ:
Добавлять узел в начало двусвязного списка
Добавлять узел в конец двусвязного списка
Добавлять узел после заданного узла в двусвязном списке
Добавлять узел перед заданным узлом в двусвязном списке
Вопрос 2
Что можно объявить с помощью представленного ниже кода?
Выберите один ответ:
Односвязный список
Двусвязный список
Стек
Очередь
Дерево
Вопрос 3
Что можно объявить с помощью кода, представленного ниже?
Выберите один ответ:
Односвязный список
Двусвязный список
Стек
Очередь
Дерево
Вопрос 4
Что объявляется с помощью кода, представленного ниже?
Выберите один или несколько ответов:
Односвязный список
Двусвязный список
Стек
Очередь
Дерево
Вопрос 5
Что позволяет делать процедура, представленная ниже?
Выберите один ответ:
Добавлять узел в начало двусвязного списка
Добавлять узел в конец двусвязного списка
Добавлять узел после заданного узла в двусвязном списке
Добавлять узел перед заданным узлом в двусвязном списке
Вопрос 6
Что можно объявить с помощью кода, указанного ниже?
Выберите один или несколько ответов:
Односвязный список
Двусвязный список
Стек
Очередь
Дерево
Вопрос 7
С помощью кода можно объявить
Выберите один или несколько ответов:
односвязный список
двусвязный список
стек
очередь
дерево
Вопрос 8
Что позволяет делать процедура, показанная ниже?
Выберите один ответ:
Добавлять узел в начало списка
Добавлять узел в конец списка
Добавлять узел после заданного узла в списке
Добавлять узел перед заданным узлом в списке
Вопрос 9
Очередью называется
Выберите один ответ:
однородный набор величин одного и того же типа, идентифицируемых вычисляемым индексом
линейно упорядоченный набор следующих друг за другом компонент
набор именованных компонент разного типа, объединенных общим именем
множество элементов
Вопрос 10
С помощью какой структуры данных наиболее рационально реализовать очередь?
Выберите один ответ:
С помощью стека
С помощью списка
С помощью дека
С помощью массива
Вопрос 11
Процедура позволяет
Выберите один ответ:
добавлять узел в начало списка
добавлять узел в конец списка
добавлять узел после заданного узла в списке
добавлять узел перед заданным узлом в списке
Промежуточный тест 8
Вопрос 1
Какие структуры являются динамическими? (Укажите 2 вида.)
Выберите один или несколько ответов:
Однонаправленные (односвязные) списки
Циклические списки
Массивы
Структуры
Вопрос 2
Какое из приведенных утверждений ?
А. Указатели разных типов нельзя присваивать друг другу без операции приведения типа.
Б. Указатель, объявленный как void, может быть разыменован.
Выберите один ответ:
Только А
Только Б
Верны оба утверждения
Оба утверждения ложны
Вопрос 3
Динамической структурой данных является
Выберите один ответ:
очередь
запись
дерево
массив
Вопрос 4
К динамическим структурам относятся (выберите 2 вида):
Выберите один или несколько ответов:
двунаправленные (двусвязные) списки
стек
массивы
структуры
Вопрос 5
Структура данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов, называется
Выберите один ответ:
однонаправленные (односвязные) списки
дерево
стек
очередь
Промежуточный тест 9
Вопрос 1
Как вычисляется коэффициент заполнения для равномерно распределенной хэш-функции H: k -> {0,..., N-1}?
Выберите один ответ:
α = N/M
α = M/N
α = 1 + M/N
α = 1 + N/M
Вопрос 2
Если использовать универсальное семейство хэш-функций для хранения n ключей, то какова будет вероятность получить хотя бы одну коллизию при размере хэш-таблицы M = n2?
Выберите один ответ:
Не больше 2/3
Не больше 1/2
Меньше 1/M
Меньше 1/N
Вопрос 3
В предположении гипотезы простого равномерного хэширования чему равно среднее время безуспешного поиска ключа для хэш-функции H: k -> {0,..., N-1}?
Выберите один ответ:
Θ(M/N)
Θ(log M/N)
Θ(M * N)
Θ(M/N + 1)
Вопрос 4
В случае универсального хэширования чему равно среднее время успешного поиска ключа для хэш-функции H: k -> {0,..., N-1}, если k1, ..., kn — все ключи, присутствующие в хэш-таблице?
Выберите один ответ:
Θ(1)
Θ(M/N + 1)
Θ(M)
Θ(N)
Вопрос 5
Какая формула задает линейный способ просматривания ячеек хэш-таблицы?
Выберите один ответ:
h(k,j) = (h0(k) + j) mod m
h(k,j) = (h0(k) + j * h1(k)) mod m
h(k,j) = (h0(k) + j * h0(k)) mod m
h(k,j) = (h0(k) + k) mod m
Промежуточный тест 10
Вопрос 1
Укажите общие критерии оценки алгоритмов сортировки.
Выберите один или несколько ответов:
Вид алгоритма сортировки
Время работы в лучшем и худшем случаях
Реализация на конкретном языке программирования
Поведение алгоритма сортировки
Вопрос 2
Определите тип сортировки.
Выберите один ответ:
Пузырьковая
Сортировка отбором
Сортировка вставками
Сортировка Шелла
Вопрос 3
Какая процедура приведена ниже?
void Exchange (int i, int j, int *x) {
int tmp;
tmp=x[i];
x[i]=x[j];
x[j]=tmp;
}
Выберите один ответ:
Процедура упорядочения по убыванию
Процедура упорядочения по возрастанию
Процедура сортировки элементов
Процедура обмена двух элементов
Вопрос 4
Ниже представлен алгоритм. К какому типу сортировки он относится?
Выберите один ответ:
К пузырьковой сортировке
К сортировке отбором
К сортировке вставками
К сортировке Шелла
Вопрос 5
Как можно ускорить алгоритм сортировки «пузырьком»?
Выберите один ответ:
Добавить во внутренний цикл проверку на отсутствие перестановок
Добавить перестановку с шагом (increment)
Добавить во внешний цикл проверку на отсутствие перестановок
Добавить возможность сортировки по убыванию
Промежуточный тест 11
Вопрос 1
Дан массив с элементами (35,08,10,15,20,11,18,25,23,30,40). Какой массив будет получен после применения алгоритма Шелла с шагом 4 при сортировке по возрастанию? Последовательность запишите через запятую без пробелов.
Вопрос 2
Какие утверждения справедливы для медианного элемента массива?
Выберите один или несколько ответов:
Поиск медианы равносилен сортировке массива
Медианный элемент является идеальным с точки зрения выбора опорного элемента
Медианный элемент всегда находится в середине массива
Медиана — это среднее арифметическое всех элементов массива
Вопрос 3
При какой сортировке происходит быстрая перестановка далеких неупорядоченных пар значений (сортировка таких пар обычно требует большого количества перестановок, если используется сравнение только соседних элементов)?
Выберите один ответ:
При сортировке слиянием
При бинарной пирамидальной сортировке
При сортировке Хоара
При сортировке Шелла
Вопрос 4
Некоторый массив размером N был отсортирован за время, пропорциональное N1,27. По какому алгоритму выполнялась сортировка?
Выберите один ответ:
Хоара
Шелла
Перестановками
Отбором
Вставками
Вопрос 5
Дан массив элементов: 4, 7, 3, 8, 5, 6, 3, 7, 2, 6, 8. Укажите порядок элементов этого массива после выполнения второго прохода сортировки Хоара по неубыванию. Опорный элемент расположен на средней позиции.
Выберите один ответ:
4, 3, 3, 2, 5, 6, 7, 7, 8, 6, 8
2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8
3, 4, 5, 7, 8, 2, 3, 6, 6, 7, 8
3, 2, 4, 3, 5, 6, 6, 7, 7, 8, 8
Промежуточный тест 12
Вопрос 1
Какие утверждения справедливы для сортировки массивов методом слияния?
Выберите один или несколько ответов:
Сортировка основана на выделении и слиянии упорядоченных серий
Сортировка заканчивается, когда в массиве получена единственная серия
С каждым этапом сортировки в массиве образуются всё более длинные серии
Сортировка слиянием работает быстрее улучшенных методов
Вопрос 2
Дан файл 5 7 3 2 8 4 1. Какой файл получится при применении алгоритма сортировки простым слиянием после первого прохода? (Введите числа через пробел.)
Вопрос 3
Дан файл 3 2 17 7 8 9 1 4 6 9 2 3 1 18. Какой файл получится в результате применения алгоритма сортировки естественным слиянием после первого прохода? (Введите числа через пробел.)
Вопрос 4
В алгоритме внешней сортировки используется два вспомогательных файла и отдельно реализуются распределение и слияние. Определите характеристики такой сортировки.
Выберите один или несколько ответов:
Многопутевая
Двухпутевая
Однофазная
Двухфазная
Вопрос 5
Укажите сортировку, особенностью которой является то, что она работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями (например, при сортировке данных на жестком диске).
Выберите один ответ:
Сортировка слиянием
Бинарная пирамидальная сортировка
Сортировка Хоара
Сортировка Шелла
Промежуточный тест 13
Вопрос 1
Какой метод поиска представлен в следующем фрагменте?
REPEAT I:=I+1
UNTIL (A[I]=X) OR (I=N)
Выберите один ответ:
Последовательный
Двоичный
Восходящий
Нисходящий
Смешанный
Вопрос 2
Имеется двоичное дерево поиска, содержащее целые числа от 1 до 7. Каким будет результат нисходящего просмотра?
Выберите один ответ:
1, 3, 2, 5, 7, 6, 4
7, 6, 5, 4, 3, 2, 1
1, 2, 3, 4, 5, 6, 7
4, 2, 1, 3, 6, 5, 7
4, 2, 6, 1, 3, 5, 7
Вопрос 3
В каком случае двоичное дерево будет деревом поиска?
Выберите один ответ:
Если в одной части дерева хранятся значения, которые больше вершины, а в другой — те, что меньше
Если матрица достижимости для него будет бинарной
Если орграф такого дерева будет циклическим
Если орграф такого дерева будет ациклическим
Вопрос 4
Имеется неупорядоченный массив целых чисел из 8 элементов. Сколько операций сравнения потребуется для нахождения искомого ключа, если он находится в конце массива?
Выберите один ответ:
1
8
0
7
4
Вопрос 5
Имеется неупорядоченный массив целых чисел из 10 элементов. Сколько операций сравнения потребуется для установления факта отсутствия искомых данных в этом массиве?
Выберите один ответ:
9
0
1
10
5
Вопрос 6
Какой поиск не требует сортировки значений множества?
Выберите один ответ:
Бинарный (двоичный, дихотомический) поиск
Последовательный (линейный) поиск
Поиск с барьером
Поиск через слияние
Промежуточный тест 14
Вопрос 1
Какие действия предпринимаются для сохранения свойств красно-черного дерева, если при операции вставки вершины x элементы x и y оказались красными (y — родитель x, y — корень)?
Выберите один ответ:
x становится черным
y становится черным
Никакие действия не предпринимаются
x и y становятся черными
Вопрос 2
При вставке элемента в красно-черное дерево в случае возникновения «красно-красного» нарушения, когда «дядя» добавляемого узла — черный и при этом цепочка узлов образует прямую линию, потребуется
Выберите один ответ:
перекрасить вершины
перекрасить вершины и произвести левый поворот
перекрасить вершины и произвести правый поворот
произвести двойной поворот
Вопрос 3
При вставке элемента в красно-черное дерево в случае возникновения «красно-красного» нарушения, когда «дядя» добавляемого узла — черный и при этом цепочка узлов образует угол, потребуется
Выберите один ответ:
перекрасить вершины
перекрасить вершины и произвести левый поворот
перекрасить вершины и произвести правый поворот
произвести двойной поворот
Вопрос 4
Какие действия следует предпринять для сохранения свойств красно-черного дерева после операции вставки вершины x в следующей ситуации: A — родитель x, B — родитель A; B — черная вершина; A, C — красные; C — дядя x?
Выберите один ответ:
Никаких действий предпринимать не нужно
A и C сделать черными, B — красным
A сделать черными, x — красным
x сделать черным
Вопрос 5
Какие свойства могут нарушаться при вставке элемента в красно-черное дерево?
Выберите один или несколько ответов:
Каждый узел является красным или черным
Корень дерева является черным
Каждый лист дерева (NULL) является черным
У красного узла оба дочерних узла — черные
У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество черных узлов
Вопрос 6
Отметьте утверждения, справедливые для красно-черных деревьев.
Выберите один или несколько ответов:
Все листья черные
Если у красного родителя два сына, то их цвета черные
Количество черных вершин на пути от корня до листьев должно быть одинаковым
У черных вершин все дети красные
Красно-черные деревья сбалансированы
Высота поддеревьев различается не более чем на 1
Вопрос 7
Какими свойствами обладает красно-черное дерево?
Выберите один или несколько ответов:
Каждый лист дерева является черным
У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество черных узлов
У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество красных узлов
У черного узла оба дочерних узла — красные
Промежуточный тест 15
Вопрос 1
Пусть — неориентированный граф, где , .Число связных компонент данного графа равно
Вопрос 2
Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился двудольный граф?
Вопрос 3
Число полных трехвершинных подграфов в полном двудольном графе К6,7 равно
Вопрос 4
Граф G имеет 4 вершины, а граф H имеет 5 вершин. Сколько единиц будет в матрице смежности графа G H?
,
Вопрос 5
Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?
Выберите один ответ:
14
15
16
13
17
Вопрос 6
Граф G имеет 4 вершины, а граф H имеет 5 вершин. Сколько единиц будет в матрице смежности графа G H?
,
Вопрос 7
Сколько рёбер в полном графе с 20 вершинами?
Вопрос 8
Сколько имеется неизоморфных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?
Вопрос 9
В двудольном графе одна доля состоит из пяти вершин степени 2, а другая — из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?
Вопрос 10
В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?
Выберите один ответ:
7
14
18
21
Промежуточный тест 16
Вопрос 1
Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?
Вопрос 2
Какие из представленных графов являются эйлеровыми?
Выберите один ответ:
1, 2
1, 3
1, 4
2, 3
2, 4
Вопрос 3
Чему равно цикломатическое число графа?
Вопрос 4
Чему равно цикломатическое число графа?
Вопрос 5
Чему равно цикломатическое число графа?
Вопрос 6
Чему равно цикломатическое число графа?
Вопрос 7
В графе из n вершин остов содержит
Выберите один ответ:
n + 1 ребер
n – ¬1 ребер
n ребер
2n ребер
Промежуточный тест 17
Вопрос 1
Дано описание алгоритма поиска кратчайшего пути на графе: «Алгоритм находит кратчайший путь из данной вершины до остальных вершин. Строится множество S вершин, для которых кратчайшие пути от начальной вершины уже известны. На каждом шаге ко множеству S добавляется та из оставшихся вершин, расстояние до которой от начальной вершины меньше, чем для других оставшихся вершин». Укажите название алгоритма.
Выберите один ответ:
Алгоритм Дейкстры
Алгоритм Флойда
Волновой алгоритм
Алгоритм перебора с возвратом
Вопрос 2
От чего зависит асимптотика алгоритма Прима?
Выберите один или несколько ответов:
От способа хранения графа
От способа хранения вершин, не входящих в дерево
От способа модификации узлов графа
От способа изменения узлов графа
Вопрос 3
Дано описание алгоритма поиска кратчайшего пути на графе: «Алгоритм находит кратчайшее расстояние между двумя любыми вершинами графа на основании того факта, что всякий неэлементарный кратчайший путь состоит из других кратчайших путей». Укажите название алгоритма.
Выберите один ответ:
Алгоритм Дейкстры
Алгоритм Флойда
Волновой алгоритм
Алгоритм перебора с возвратом
Вопрос 4
Метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами называется
Выберите один ответ:
модульное программирование
динамическое программирование
комплексное программирование
программирование с отходом назад
жадное программирование
Вопрос 5
Алгоритм Прима применяется
Выберите один ответ:
для ориентированных графов
для неориентированных графов
для детерминированных графов
для взвешенных неориентированных графов
для взвешенных ориентированных графов
Промежуточный тест 18
Вопрос 1
На каждом шаге ветвления выбирается множество
Выберите один ответ:
с наибольшей оценкой
с наименьшей оценкой
с оптимальной оценкой
со средней оценкой
Вопрос 2
Задача коммивояжера относится
Выберите один ответ:
к целочисленному программированию
к аналитической геометрии
к анализу бесконечно малых величин
к евклидовой геометрии
Вопрос 3
Процесс ветвления можно представить в виде дерева, в котором
Выберите один ответ:
каждая вершина — это один маршрут
каждая вершина — это множество маршрутов
есть циклы
каждая вершина — это ребро в маршруте
Вопрос 4
Дана матрица стоимостей перевода системы из состояния в состояние.
1 2 3 4 5
1 10 15 7 10
2 5 10 15 20
3 8 12 20 7
4 14 8 6 15
5 10 3 25 6
Найдите самый дешевый способ провести систему по всем состояниям с возвращением в исходное состояние. Ответ запишите в виде 2-3-4-5-1-2.
Вопрос 5
Дана матрица стоимостей перевода системы из состояния в состояние.
1 2 3 4 5
1 10 8 25 10
2 1 10 15 20
3 8 9 20 7
4 14 5 24 15
5 10 8 25 6
Найдите самый дешевый способ провести систему по всем состояниям с возвращением в исходное состояние. Ответ запишите в виде 2-3-4-5-1-2.
Промежуточный тест 19
Вопрос 1
В полном графе со множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?
Вопрос 2
Что происходит с хроматическим числом графа при удалении ребра?
Выберите один ответ:
Увеличивается
Уменьшается
Уменьшается или не изменяется
Может увеличиться, уменьшиться или остаться прежним
Вопрос 3
Хроматическое число дерева равно
Вопрос 4
Хроматическое число полного 5-вершинного графа равно
Вопрос 5
Какие из приведенных ниже условий являются необходимыми и достаточными для того, чтобы граф имел хроматическое число 2?
Выберите один ответ:
Степени вершин не превосходят 2
Нет циклов нечетной длины
Каждая компонента связности — цепь
Каждая компонента связности — цикл четной длины или цепь
Вопрос 6
Хроматическое число полного двудольного графа К4,3 равно
