Ответы на тесты / РОСДИСТАНТ / Алгоритмы и структуры данных / 168 вопросов / Тесты 1-19 + Итоговый тест (Решение → 7066)

В файле собраны ответы к тестам из курса РОСДИСТАНТ / Алгоритмы и структуры данных (Тесты 1-19 + Итоговый тест).

Результаты сдачи представлены на скринах.

После покупки Вы получите файл, где будет 168 вопросов с ответами. Верный ответ выделен по тексту.

В демо-файлах представлены скрины с результатами тестирования, а также пример, как выделены ответы.

Все набрано в Word, можно искать с помощью поиска.

Ниже список вопросов, которые представлены в файле.

Также Вы можете заказать решение тестов и других работ у меня на странице по ссылке:

Промежуточный тест 1

Вопрос 1

Рассмотрите программу ниже и определите её сложность.

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)

Вопрос 2

Что понимается под временной сложностью алгоритма?

Выберите один ответ:

Минимальное количество машинного кода для представления алгоритма в ЭВМ

Функция размера входных и выходных данных, равная минимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи данного размера

Максимальное количество машинного кода для представления алгоритма в ЭВМ

Нет го ответа

Вопрос 3

Алгоритм некоторым образом обрабатывает массив (см. рисунок). Алгоритм состоит из двух вложенных циклов. Как асимптотическая сложность зависит от переменной n?

Выберите один ответ:

O(4 * n)

Не зависит от n

O(n)

O((i + j)n)

Вопрос 4

Укажите два наилучших алгоритма по критерию трудоемкости.

Выберите один или несколько ответов:

Алгоритм с логарифмической скоростью роста

Алгоритм с линейной скоростью роста

Алгоритм с линейно-логарифмической скоростью роста

Алгоритм с квадратичной скоростью роста

Вопрос 5

Алгоритм F имеет оценку сложности O(n2), а алгоритм G — O(n). Тогда

Выберите один или несколько ответов:

F может быть быстрее G на любом входе

F может быть медленнее G на любом входе

F может быть таким, что для любого n он делает n2 операций на некотором входе размера n

G может быть таким, что для любого n он делает n2 операций на некотором входе размера n

Вопрос 6

Пусть X — задача из NP. Какое утверждение справедливо для задачи X?

Выберите один ответ:

X может быть неразрешима

Если X можно решить за полиномиальное время на ДМТ, то P = NP

Нет полиномиального алгоритма для X

X — NP-трудная задача

Если X — NP-трудная задача, то она NP-полная

Вопрос 7

Алгоритм обрабатывает массив (см. рисунок). Входные данные алгоритма — k, t, n. От каких из перечисленныз входных данных зависит время работы алгоритма?

Выберите один ответ:

От k, t, n

От k и t

От t и n

От n

Не зависит от входных данных

Вопрос 8

Какова сложность алгоритма?

Выберите один ответ:

O(n)

O(k + n)

O(k(n – 1))

O(k)

Вопрос 9

Если 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)

Вопрос 10

Алгоритм нахождения минимального элемента массива был модифицирован. Теперь он ищет минимальный и максимальный элемент массива. В этом случае асимптотическая сложность алгоритма

Выберите один ответ:

не изменится

увеличится на порядок

уменьшится на порядок

уменьшится в два раза

Промежуточный тест 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(1) = 1, F(2) = 3, F(n) = F(n − 1) * F(n − 2) + (n − 2) при n > 2.

Чему равно значение функции F(5)?

В ответе запишите только натуральное число.

Вопрос 3

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = 2 при n ≤ 2,

F(n) = 2 • F(n − 1) + F(n − 2) при n > 2.

Чему равно значение функции F(5)?

В ответе запишите только натуральное число.

Вопрос 4

Задан алгоритм вычисления значения функции F(n), где n – натуральное число, который представлен следующими соотношениями:

F(1) = 1, F(2) = 1, F(n) = F(n – 1) * n − 2 * F(n – 2) при n > 2.

Чему равно значение функции F(6)?

В ответе запишите только натуральное число.

Вопрос 5

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = n при n ≤ 2,

F(n) = F(n − 1) • F(n − 2) при n > 2.

Чему равно значение функции F(6)?

В ответе запишите только натуральное число.

Вопрос 6

Последовательность чисел Люка задается рекуррентным соотношением:

F(1) = 2, F(2) = 1, F(n) = F(n – 2) + F(n – 1) при n > 2, где n – натуральное число.

Чему равно десятое число в последовательности Люка?

В ответе запишите только натуральное число.

Вопрос 7

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = 2 при n ≤ 2,

F(n) = F(n − 1) + 3 • F(n − 2) при n > 2.

Чему равно значение функции F(5)?

В ответе запишите только натуральное число.

Вопрос 8

Последовательность чисел трибоначчи задается рекуррентным соотношением:

F(1) = 0, F(2) = 1, F(3) = 1, F(n) = F(n – 3) + F(n – 2) + F(n–1) при n > 3, где n – натуральное число.

Чему равно девятое число в последовательности трибоначчи?

В ответе запишите только натуральное число.

Вопрос 9

Представленный алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(1) = 1, F(2) = 3, F(n) = F(n – 1) * n + F(n–2) * (n – 1) при n > 2.

Каково значение функции F(5)?

В ответе запишите только натуральное число.

Вопрос 10

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = n при n ≤ 2,

F(n) = 3 • F(n − 1) − F(n − 2) при n > 2.

Чему равно значение функции F(6)?

В ответе запишите только натуральное число.

Промежуточный тест 3

Вопрос 1

Формирование какой последовательности описывает рекурсивная функция 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, …

Вопрос 2

Формирование какой последовательности описывает рекурсивная функция 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, ...

Нет го ответа

Вопрос 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

Ниже на языке программирования 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;

}

Вопрос 5

Формирование какой последовательности описывает рекурсивная функция 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, ...

Промежуточный тест 4

Вопрос 1

Простыми типами данных в С++ являются

Выберите один ответ:

целые — int, вещественные — float или double, символьные — string

целые — int, вещественные — float или double, символьные — char

целые — bool, вещественные — float или double, символьные — string

целые — int, вещественные — float или real, символьные — char

Вопрос 2

Какой из перечисленных типов данных не является типом данных в С++?

Выберите один ответ:

float

double

int

real

Вопрос 3

Назовите определение типа данных (выберите 2 варианта ответа).

Выберите один или несколько ответов:

Возможность ввода/вывода данных

Множество (диапазон) значений, которые могут принимать величины этого типа

Наименование библиотек для подключения функций

Операции и функции, которые можно применять к данным этого типа

Вопрос 4

Какое ключевое слово указывает на то, что целая переменная не может принимать отрицательные значения?

Выберите один ответ:

positive

long

unsigned

Другое

Нет такого зарезервированного слова

Вопрос 5

Структура объявления переменных в С++ имеет вид

Выберите один ответ:

[=];< идент. 2>,…

[:=], < идент. 2>,…

[=], < идент. 2>,…

[==]; < идент. 2>,…

Промежуточный тест 5

Вопрос 1

Укажите строку, которая возвращает адрес первого элемента в массиве arr.

Выберите один ответ:

&arr

arr[1]

arr[0]

arr

Вопрос 2

В каком из вариантов ответов объявлен двумерный массив?

Выберите один ответ:

int array[20, 20]

array anarray[20][20]

int anarray[20][20]

char array[20]

Вопрос 3

Словосочетание «Hello world!» может быть сохранено в символьном массиве размером n элементов. Чему равно n?

Выберите один ответ:

12

10

13

11

Вопрос 4

Каков порядковый номер последнего элемента массива, если размер массива 19?

Выберите один ответ:

19

18

Порядковый номер определяется программистом

100

Вопрос 5

В какой из представленных строк выполняется обращение к седьмому элементу массива, если размер массива равен 10?

Выберите один ответ:

mas

mas(7)

mas[6]

mas[7]

Вопрос 6

Таблицы в языке программирования С++ бывают

Выберите один ответ:

только одномерными

только двумерными

только однострочными и двустрочными

одномерными и двумерными

Промежуточный тест 6

Вопрос 1

В чем заключается недостаток связного представления данных (обращения к данным через указатели)?

Выберите один ответ:

Размер структуры ограничивается только доступным объемом машинной памяти

При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей

Большая гибкость структуры

Доступ к элементам связной структуры может быть менее эффективным по времени

Вопрос 2

Укажите зарезервированное ключевое слово для динамического выделения памяти.

Выберите один ответ:

new

value

create

malloc

Вопрос 3

Определите основной недостаток использования связного представления данных (обращения к данным через указатели).

Выберите один ответ:

Размер структуры ограничивается только доступным объемом машинной памяти

При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей

На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память

Нет го ответа

Вопрос 4

Как освободить память от удаленного из списка элемента?

Выберите один ответ:

p=getnode

ptr(p)=nil

freenode(p)

p=lst

Вопрос 5

Укажите структуру, в которой доступ к элементам осуществляется в любой момент времени и к любому элементу с помощью индексов.

Выберите один ответ:

Множество

Массив

Очередь

Запись

Вопрос 6

Укажите достоинства связного представления данных (обращения к данным через указатели). (Выберите 2 показателя.)

Выберите один или несколько ответов:

При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей

Большая гибкость структуры

Доступ к элементам связной структуры может быть менее эффективным по времени

На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память

Вопрос 7

Какая структура является динамическими? (Укажите 2 параметра.)

Выберите один или несколько ответов:

Ей выделяется память в процессе выполнения программы

Она не имеет имени

Она работает только с массивами

Она не требует дополнительной памяти

Вопрос 8

Определите характеристику динамической структуры данных (укажите 2 параметра).

Выберите один или несколько ответов:

Размерность структуры может меняться в процессе выполнения программы

Она не имеет имени

Она работает только с массивами

Она не требует дополнительной памяти

Вопрос 9

В чем заключаются достоинства связного представления данных (обращения к данным через указатели)? (Выберите 2 показателя.)

Выберите один или несколько ответов:

Размер структуры ограничивается только доступным объемом машинной памяти

При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей

Доступ к элементам связной структуры может быть менее эффективным по времени

На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память

Вопрос 10

Укажите зарезервированное ключевое слово для высвобождения выделенной памяти.

Выберите один ответ:

free

remove

delete

clear

Промежуточный тест 7

Вопрос 1

Процедура позволяет

Выберите один ответ:

добавлять узел в начало списка

добавлять узел в конец списка

добавлять узел после заданного узла в списке

добавлять узел перед заданным узлом в списке

Вопрос 2

Что можно объявить с помощью представленного ниже кода?

Выберите один ответ:

Односвязный список

Двусвязный список

Стек

Очередь

Дерево

Вопрос 3

Что позволяет делать процедура, представленная ниже?

Выберите один ответ:

Добавлять узел в начало двусвязного списка

Добавлять узел в конец двусвязного списка

Добавлять узел после заданного узла в двусвязном списке

Добавлять узел перед заданным узлом в двусвязном списке

Вопрос 4

Что позволяет делать процедура, показанная ниже?

Выберите один ответ:

Добавлять узел в начало двусвязного списка

Добавлять узел в конец двусвязного списка

Добавлять узел после заданного узла в двусвязном списке

Добавлять узел перед заданным узлом в двусвязном списке

Вопрос 5

Очередью называется

Выберите один ответ:

однородный набор величин одного и того же типа, идентифицируемых вычисляемым индексом

линейно упорядоченный набор следующих друг за другом компонент

набор именованных компонент разного типа, объединенных общим именем

множество элементов

Вопрос 6

Что можно объявить с помощью кода, представленного ниже?

Выберите один ответ:

Односвязный список

Двусвязный список

Стек

Очередь

Дерево

Вопрос 7

Что объявляется с помощью кода, представленного ниже?

Выберите один или несколько ответов:

Односвязный список

Двусвязный список

Стек

Очередь

Дерево

Вопрос 8

Что можно объявить с помощью кода, указанного ниже?

Выберите один или несколько ответов:

Односвязный список

Двусвязный список

Стек

Очередь

Дерево

Вопрос 9

Что позволяет делать процедура, показанная ниже?

Выберите один ответ:

Добавлять узел в начало списка

Добавлять узел в конец списка

Добавлять узел после заданного узла в списке

Добавлять узел перед заданным узлом в списке

Вопрос 10

С помощью кода можно объявить

Выберите один или несколько ответов:

односвязный список

двусвязный список

стек

очередь

дерево

Вопрос 11

С помощью какой структуры данных наиболее рационально реализовать очередь?

Выберите один ответ:

С помощью стека

С помощью списка

С помощью дека

С помощью массива

Промежуточный тест 8

Вопрос 1

Структура данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов, называется

Выберите один ответ:

однонаправленные (односвязные) списки

дерево

стек

очередь

Вопрос 2

Динамической структурой данных является

Выберите один ответ:

очередь

запись

дерево

массив

Вопрос 3

Какие структуры являются динамическими? (Укажите 2 вида.)

Выберите один или несколько ответов:

Однонаправленные (односвязные) списки

Циклические списки

Массивы

Структуры

Вопрос 4

Какое из приведенных утверждений ?

А. Указатели разных типов нельзя присваивать друг другу без операции приведения типа.

Б. Указатель, объявленный как void, может быть разыменован.

Выберите один ответ:

Только А

Только Б

Верны оба утверждения

Оба утверждения ложны

Вопрос 5

К динамическим структурам относятся (выберите 2 вида):

Выберите один или несколько ответов:

двунаправленные (двусвязные) списки

стек

массивы

структуры

Промежуточный тест 9

Вопрос 1

Как вычисляется коэффициент заполнения для равномерно распределенной хэш-функции H: k -> {0,..., N-1}?

Выберите один ответ:

α = N/M

α = M/N

α = 1 + M/N

α = 1 + N/M

Вопрос 2

Какая формула задает линейный способ просматривания ячеек хэш-таблицы?

Выберите один ответ:

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

Вопрос 3

В предположении гипотезы простого равномерного хэширования чему равно среднее время безуспешного поиска ключа для хэш-функции H: k -> {0,..., N-1}?

Выберите один ответ:

Θ(M/N)

Θ(log M/N)

Θ(M * N)

Θ(M/N + 1)

Вопрос 4

Если использовать универсальное семейство хэш-функций для хранения n ключей, то какова будет вероятность получить хотя бы одну коллизию при размере хэш-таблицы M = n2?

Выберите один ответ:

Не больше 2/3

Не больше 1/2

Меньше 1/M

Меньше 1/N

Вопрос 5

В случае универсального хэширования чему равно среднее время успешного поиска ключа для хэш-функции H: k -> {0,..., N-1}, если k1, ..., kn — все ключи, присутствующие в хэш-таблице?

Выберите один ответ:

Θ(1)

Θ(M/N + 1)

Θ(M)

Θ(N)

Промежуточный тест 10

Вопрос 1

Как можно ускорить алгоритм сортировки «пузырьком»?

Выберите один ответ:

Добавить во внутренний цикл проверку на отсутствие перестановок

Добавить перестановку с шагом (increment)

Добавить во внешний цикл проверку на отсутствие перестановок

Добавить возможность сортировки по убыванию

Вопрос 2

Укажите общие критерии оценки алгоритмов сортировки.

Выберите один или несколько ответов:

Вид алгоритма сортировки

Время работы в лучшем и худшем случаях

Реализация на конкретном языке программирования

Поведение алгоритма сортировки

Вопрос 3

Какая процедура приведена ниже?

void Exchange (int i, int j, int *x) {

int tmp;

tmp=x[i];

x[i]=x[j];

x[j]=tmp;

}

Выберите один ответ:

Процедура упорядочения по убыванию

Процедура упорядочения по возрастанию

Процедура сортировки элементов

Процедура обмена двух элементов

Вопрос 4

Определите тип сортировки.

Выберите один ответ:

Пузырьковая

Сортировка отбором

Сортировка вставками

Сортировка Шелла

Вопрос 5

Ниже представлен алгоритм. К какому типу сортировки он относится?

Выберите один ответ:

К пузырьковой сортировке

К сортировке отбором

К сортировке вставками

К сортировке Шелла

Промежуточный тест 11

Вопрос 1

Какие утверждения справедливы для медианного элемента массива?

Выберите один или несколько ответов:

Поиск медианы равносилен сортировке массива

Медианный элемент является идеальным с точки зрения выбора опорного элемента

Медианный элемент всегда находится в середине массива

Медиана — это среднее арифметическое всех элементов массива

Вопрос 2

Некоторый массив размером N был отсортирован за время, пропорциональное N1,27. По какому алгоритму выполнялась сортировка?

Выберите один ответ:

Хоара

Шелла

Перестановками

Отбором

Вставками

Вопрос 3

При какой сортировке происходит быстрая перестановка далеких неупорядоченных пар значений (сортировка таких пар обычно требует большого количества перестановок, если используется сравнение только соседних элементов)?

Выберите один ответ:

При сортировке слиянием

При бинарной пирамидальной сортировке

При сортировке Хоара

При сортировке Шелла

Вопрос 4

Дан массив элементов: 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

Вопрос 5

Дан массив с элементами (35,08,10,15,20,11,18,25,23,30,40). Какой массив будет получен после применения алгоритма Шелла с шагом 4 при сортировке по возрастанию? Последовательность запишите через запятую без пробелов.

Промежуточный тест 12

Вопрос 1

Укажите сортировку, особенностью которой является то, что она работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями (например, при сортировке данных на жестком диске).

Выберите один ответ:

Сортировка слиянием

Бинарная пирамидальная сортировка

Сортировка Хоара

Сортировка Шелла

Вопрос 2

В алгоритме внешней сортировки используется два вспомогательных файла и отдельно реализуются распределение и слияние. Определите характеристики такой сортировки.

Выберите один или несколько ответов:

Многопутевая

Двухпутевая

Однофазная

Двухфазная

Вопрос 3

Дан файл 3 2 17 7 8 9 1 4 6 9 2 3 1 18. Какой файл получится в результате применения алгоритма сортировки естественным слиянием после первого прохода? (Введите числа через пробел.)

Вопрос 4

Какие утверждения справедливы для сортировки массивов методом слияния?

Выберите один или несколько ответов:

Сортировка основана на выделении и слиянии упорядоченных серий

Сортировка заканчивается, когда в массиве получена единственная серия

С каждым этапом сортировки в массиве образуются всё более длинные серии

Сортировка слиянием работает быстрее улучшенных методов

Вопрос 5

Дан файл 5 7 3 2 8 4 1. Какой файл получится при применении алгоритма сортировки простым слиянием после первого прохода? (Введите числа через пробел.)

Промежуточный тест 13

Вопрос 1

Имеется неупорядоченный массив целых чисел из 8 элементов. Сколько операций сравнения потребуется для нахождения искомого ключа, если он находится в конце массива?

Выберите один ответ:

1

8

0

7

4

Вопрос 2

Имеется неупорядоченный массив целых чисел из 10 элементов. Сколько операций сравнения потребуется для установления факта отсутствия искомых данных в этом массиве?

Выберите один ответ:

9

0

1

10

5

Вопрос 3

Имеется двоичное дерево поиска, содержащее целые числа от 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

Вопрос 4

В каком случае двоичное дерево будет деревом поиска?

Выберите один ответ:

Если в одной части дерева хранятся значения, которые больше вершины, а в другой — те, что меньше

Если матрица достижимости для него будет бинарной

Если орграф такого дерева будет циклическим

Если орграф такого дерева будет ациклическим

Вопрос 5

Какой метод поиска представлен в следующем фрагменте?

REPEAT I:=I+1

UNTIL (A[I]=X) OR (I=N)

Выберите один ответ:

Последовательный

Двоичный

Восходящий

Нисходящий

Смешанный

Вопрос 6

Какой поиск не требует сортировки значений множества?

Выберите один ответ:

Бинарный (двоичный, дихотомический) поиск

Последовательный (линейный) поиск

Поиск с барьером

Поиск через слияние

Промежуточный тест 14

Вопрос 1

Какие действия следует предпринять для сохранения свойств красно-черного дерева после операции вставки вершины x в следующей ситуации: A — родитель x, B — родитель A; B — черная вершина; A, C — красные; C — дядя x?

Выберите один ответ:

Никаких действий предпринимать не нужно

A и C сделать черными, B — красным

A сделать черными, x — красным

x сделать черным

Вопрос 2

Какие действия предпринимаются для сохранения свойств красно-черного дерева, если при операции вставки вершины x элементы x и y оказались красными (y — родитель x, y — корень)?

Выберите один ответ:

x становится черным

y становится черным

Никакие действия не предпринимаются

x и y становятся черными

Вопрос 3

Отметьте утверждения, справедливые для красно-черных деревьев.

Выберите один или несколько ответов:

Все листья черные

Если у красного родителя два сына, то их цвета черные

Количество черных вершин на пути от корня до листьев должно быть одинаковым

У черных вершин все дети красные

Красно-черные деревья сбалансированы

Высота поддеревьев различается не более чем на 1

Вопрос 4

Какими свойствами обладает красно-черное дерево?

Выберите один или несколько ответов:

Каждый лист дерева является черным

У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество черных узлов

У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество красных узлов

У черного узла оба дочерних узла — красные

Вопрос 5

Какие свойства могут нарушаться при вставке элемента в красно-черное дерево?

Выберите один или несколько ответов:

Каждый узел является красным или черным

Корень дерева является черным

Каждый лист дерева (NULL) является черным

У красного узла оба дочерних узла — черные

У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество черных узлов

Вопрос 6

При вставке элемента в красно-черное дерево в случае возникновения «красно-красного» нарушения, когда «дядя» добавляемого узла — черный и при этом цепочка узлов образует угол, потребуется

Выберите один ответ:

перекрасить вершины

перекрасить вершины и произвести левый поворот

перекрасить вершины и произвести правый поворот

произвести двойной поворот

Вопрос 7

При вставке элемента в красно-черное дерево в случае возникновения «красно-красного» нарушения, когда «дядя» добавляемого узла — черный и при этом цепочка узлов образует прямую линию, потребуется

Выберите один ответ:

перекрасить вершины

перекрасить вершины и произвести левый поворот

перекрасить вершины и произвести правый поворот

произвести двойной поворот

Промежуточный тест 15

Вопрос 1

Сколько рёбер в полном графе с 20 вершинами?

Вопрос 2

Число полных трехвершинных подграфов в полном двудольном графе К6,7 равно

Вопрос 3

Граф G имеет 4 вершины, а граф H имеет 5 вершин. Сколько единиц будет в матрице смежности графа G H?

,

Вопрос 4

Пусть — неориентированный граф, где , .Число связных компонент данного графа равно

Вопрос 5

Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?

Выберите один ответ:

14

15

16

13

17

Вопрос 6

В двудольном графе одна доля состоит из пяти вершин степени 2, а другая — из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?

Вопрос 7

Сколько имеется неизоморфных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?

Вопрос 8

Граф G имеет 4 вершины, а граф H имеет 5 вершин. Сколько единиц будет в матрице смежности графа G H?

,

Вопрос 9

В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?

Выберите один ответ:

7

14

18

21

Вопрос 10

Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился двудольный граф?

Промежуточный тест 16

Вопрос 1

Чему равно цикломатическое число графа?

Вопрос 2

Какие из представленных графов являются эйлеровыми?

Выберите один ответ:

1, 2

1, 3

1, 4

2, 3

2, 4

Вопрос 3

Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?

Вопрос 4

Чему равно цикломатическое число графа?

Вопрос 5

В графе из n вершин остов содержит

Выберите один ответ:

n + 1 ребер

n – ¬1 ребер

n ребер

2n ребер

Вопрос 6

Чему равно цикломатическое число графа?

Вопрос 7

Чему равно цикломатическое число графа?

Промежуточный тест 17

Вопрос 1

Алгоритм Прима применяется

Выберите один ответ:

для ориентированных графов

для неориентированных графов

для детерминированных графов

для взвешенных неориентированных графов

для взвешенных ориентированных графов

Вопрос 2

От чего зависит асимптотика алгоритма Прима?

Выберите один или несколько ответов:

От способа хранения графа

От способа хранения вершин, не входящих в дерево

От способа модификации узлов графа

От способа изменения узлов графа

Вопрос 3

Метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами называется

Выберите один ответ:

модульное программирование

динамическое программирование

комплексное программирование

программирование с отходом назад

жадное программирование

Вопрос 4

Дано описание алгоритма поиска кратчайшего пути на графе: «Алгоритм находит кратчайшее расстояние между двумя любыми вершинами графа на основании того факта, что всякий неэлементарный кратчайший путь состоит из других кратчайших путей». Укажите название алгоритма.

Выберите один ответ:

Алгоритм Дейкстры

Алгоритм Флойда

Волновой алгоритм

Алгоритм перебора с возвратом

Вопрос 5

Дано описание алгоритма поиска кратчайшего пути на графе: «Алгоритм находит кратчайший путь из данной вершины до остальных вершин. Строится множество S вершин, для которых кратчайшие пути от начальной вершины уже известны. На каждом шаге ко множеству S добавляется та из оставшихся вершин, расстояние до которой от начальной вершины меньше, чем для других оставшихся вершин». Укажите название алгоритма.

Выберите один ответ:

Алгоритм Дейкстры

Алгоритм Флойда

Волновой алгоритм

Алгоритм перебора с возвратом

Промежуточный тест 18

Вопрос 1

Процесс ветвления можно представить в виде дерева, в котором

Выберите один ответ:

каждая вершина — это один маршрут

каждая вершина — это множество маршрутов

есть циклы

каждая вершина — это ребро в маршруте

Вопрос 2

Дана матрица стоимостей перевода системы из состояния в состояние.

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.

Вопрос 3

Задача коммивояжера относится

Выберите один ответ:

к целочисленному программированию

к аналитической геометрии

к анализу бесконечно малых величин

к евклидовой геометрии

Вопрос 4

На каждом шаге ветвления выбирается множество

Выберите один ответ:

с наибольшей оценкой

с наименьшей оценкой

с оптимальной оценкой

со средней оценкой

Вопрос 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

Хроматическое число полного двудольного графа К4,3 равно

Вопрос 2

Что происходит с хроматическим числом графа при удалении ребра?

Выберите один ответ:

Увеличивается

Уменьшается

Уменьшается или не изменяется

Может увеличиться, уменьшиться или остаться прежним

Вопрос 3

Хроматическое число дерева равно

Вопрос 4

Хроматическое число полного 5-вершинного графа равно

Вопрос 5

Какие из приведенных ниже условий являются необходимыми и достаточными для того, чтобы граф имел хроматическое число 2?

Выберите один ответ:

Степени вершин не превосходят 2

Нет циклов нечетной длины

Каждая компонента связности — цепь

Каждая компонента связности — цикл четной длины или цепь

Вопрос 6

В полном графе со множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?

Итоговый тест

Вопрос 1

Как осуществить вставку (Insert(k)) ключа k в таблицу T, реализованную фильтром Блюма?

Выберите один ответ:

Вычислить хэш-коды h1(k), ..., hs(k), после чего в получившиеся индексы ячеек булева массива T записать значение True

Вычислить сумму ∑hi(k) и записать в таблицу T в ячейку с получившимся индексом значение True

По хэш-функции h(k) определить булево значение и вставить его в индекс таблицы T

Вычислить хэш-коды h1(k), ..., hs(k), после чего в соответствующие значения записать ключ k

Вопрос 2

Какие высказывания относятся к рекурсивному определению дерева?

Выберите один или несколько ответов:

Дерево может быть пустым

Дерево — это вершина и связанное с ней конечное число поддеревьев

Дерево всегда содержит хотя бы одну корневую вершину

Дерево — это вершина и связанное с ней единственное поддерево

Вопрос 3

Алгоритм нахождения максимального элемента массива имеет сложность

Выберите один ответ:

O(n)

O(n2)

O(lnn)

(logn)

Вопрос 4

Преобразование значения переменной к новому типу, которое происходит автоматически, по правилам, заложенным в языке программирования, называют

Выберите один ответ:

явное приведение типа

неявное приведение типа

прямая рекурсия

косвенная (взаимная) рекурсия

Вопрос 5

Какие существуют метрики, отображающие эффективность алгоритма?

Выберите один ответ:

Процессорное время, память

Надежность, масштабируемость

Адаптивность

Простота реализации

Вопрос 6

Какая сортировка является одной из разновидностей быстрых сортировок и основана на упорядочивании подмножеств массива относительно опорных элементов?

Выберите один ответ:

Сортировка слиянием

Сортировка деревом

Сортировка Хоара

Сортировка Шелла

Вопрос 7

Пусть определен тип данных переменной. Тогда известной является информация

Выберите один ответ:

о начальном значении

о конечном значении

о количестве обращений к данным

о точности возможных значений

Вопрос 8

Какие утверждения справедливы для представления графа с помощью матрицы смежности?

Выберите один или несколько ответов:

В этом представлении используются двумерные массивы

Данное представление рекомендуется использовать для графов с фиксированным числом вершин

Данное представление имеет простую программную реализацию

Данное представление позволяет легко изменять набор вершин в графе

Вопрос 9

Какой из представленных на рисунке графов является полным?

Выберите один ответ:

1

2

3

4

Вопрос 10

Граф, который может быть изображен на плоскости так, что все пересечения ребер являются его вершинами, — это

Выберите один ответ:

дерево

плоский граф

лес

полный граф

Вопрос 11

Какое значение возвращает рекурсивная функция Rec(108,72), код которой приведен ниже?

int Rec(int n,int k) {

if (n%k==0) return k;

return Rec(k,n%k);

}

Выберите один ответ:

36

72

12

1

Вопрос 12

Дан массив с элементами (35, 08, 10, 15, 20, 11, 07, 25, 23, 30, 40). Какой массив будет получен после первого шага применения алгоритма Хоара при сортировке по возрастанию, если в качестве опорного элемента выбран средний элемент?

Запишите последовательность через запятую без пробелов.

Вопрос 13

Укажите все достоинства последовательного (линейного) поиска.

Выберите один или несколько ответов:

Может работать в потоковом режиме при непосредственном получении данных из любого источника

Не требует дополнительного анализа функций

Осуществляет просмотр всего массива в худшем случае

Применяется для малого числа элементов

Вопрос 14

Последовательность элементов сортировки, которая упорядочена по ключу, называется

Выберите один ответ:

распределение

слияние

серия (упорядоченный отрезок)

длина серии

Вопрос 15

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(1) = 5, F(2) = 5, F(n) = 5 • F(n − 1) − 4 • F(n − 2) при n > 2.

Чему равно значение функции F(13)?

В ответе запишите только натуральное число.

Вопрос 16

Какое утверждение ?

Выберите один ответ:

В остаточной сети могут быть только те ребра, которые были в исходной сети

В остаточной сети могут появиться новые ребра

В остаточной сети могут появиться новые вершины и ребра, соединяющие их со старыми вершинами

Все утверждения неверны

Вопрос 17

Дана матрица смежности неориентированного графа G(V, E). Укажите порядок обхода графа в глубину со стартовой вершины 4.

Выберите один ответ:

4213657

4213567

4321567

4312567

Вопрос 18

Выберите один ответ:

1

2

3

4

5

Вопрос 19

Какой поиск не требует дополнительной памяти?

Выберите один ответ:

Бинарный (двоичный, дихотомический) поиск

Последовательный (линейный) поиск

Поиск с барьером

Поиск через слияние

Вопрос 20

Ниже на языке программирования C++ записан рекурсивный алгоритм F.Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

void F(int n){

if (n>0){

std::cout <<n;

F(n-3);

F(n/3);

}

}

Вопрос 21

Какие правила обхода дерева являются основными

Выберите один или несколько ответов:

Обход в прямом порядке

Обход в обратном порядке

Симметричный обход

Круговой обход

Вопрос 22

Задача дискретной оптимизации характеризуется тем, что

Выберите один или несколько ответов:

множество её допустимых решений невыпукло

множество её допустимых решений представляет собой выпуклый многогранник

для двух близких точек функции так же близки

не удается естественным образом ввести понятие окрестности

Вопрос 23

Сортировка, в которой отдельно реализуется две фазы: распределение и слияние, называется

Выберите один ответ:

двухфазная сортировка

однофазная сортировка

двухпутевое слияние

многопутевое слияние

Вопрос 24

В чём отличительная особенность динамических объектов?

Выберите один ответ:

Они порождаются непосредственно перед выполнением программы

Они возникают уже в процессе выполнения программы

Они задаются в процессе выполнения программы

Они передаются из другой программы

Вопрос 25

Последовательность чисел Падована задается рекуррентным соотношением:

F(1) = 1, F(2) = 1, F(3) = 1, F(n) = F(n – 3) + F(n – 2) при n > 3, где n — натуральное число.

Чему равно десятое число в последовательности Падована?

В ответе запишите только натуральное число.

Вопрос 26

Что необходимо сделать при реализации структуры приближенное множество (Lossy Map) с помощью двух Блюм-фильтров (использованных для множеств-прообразов 0 и 1), чтобы избежать ситуации, когда при запросе Get(k) оба Блюм-фильтра вернули 1?

Выберите один ответ:

Такие значения признаются ложноположительными срабатываниями, их количество всегда невелико

На образованном такими значениями множестве C изготовить два более мелких Блюм-фильтра для множеств-прообразов 0 и 1, затем продолжить создание иерархии таких множеств, пока они не перестанут пересекаться

Признать такие значения равными 0

Удалить все такие значения из множества

Вопрос 27

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = n при n ≤ 2,

F(n) = F(n − 1) + 2 • F(n − 2) при n > 2.

Чему равно значение функции F(6)?

В ответе запишите только натуральное число.

Вопрос 28

Рекурсия использует

Выберите один ответ:

создание подпрограммы самой себя

копирование подпрограммы самой себя

удаление подпрограммой самой себя

обращение подпрограммы к самой себе

Вопрос 29

В каком из представленных случаев можно утверждать, что путь, соединяющий вершины x и y в BFS-дереве, является кратчайшим путем между ними в графе?

Выберите один ответ:

x и y — любые вершины

x и y находятся в дереве на одинаковом расстоянии от корня

x — корень дерева

Вершина x является предком вершины y в BFS-дереве

Вопрос 30

Алгоритм некоторым образом обрабатывает массив:

Алгоритм состоит из трёх вложенных циклов. Какая асимптотическая оценка сложности лучше подходит для данного алгоритма?

Выберите один ответ:

O(n)

O(n^3)

O(sinn)

O(logn)

Вопрос 31

Если T — время работы алгоритма, N — размер входных данных, что отображает функция maxT(I) для N(I) = N?

Выберите один ответ:

Время работы алгоритма в худшем случае для конкретного входа I

Время работы алгоритма в лучшем случае при рассмотрении всех входов I размера N

Время работы алгоритма в худшем случае при рассмотрении всех входов I размера N

Время работы алгоритма в среднем случае для конкретного входа I

Вопрос 32

Как называется один из параметров трудоемкости алгоритма, который характеризуется тем, что сортировка не меняет взаимного расположения равных элементов?

Выберите один ответ:

Алгоритм сортировки

Время сортировки

Устойчивость сортировки

Ключ сортировки

Вопрос 33

Любой граф, изоморфный плоскому, называется

Выберите один ответ:

кратный

симметрический

хроматический

планарный

Вопрос 34

Для оценки сложности алгоритмов, как правило, используется

Выберите один ответ:

сложность алгоритма в наилучшем случае

реальная сложность

асимптотическая сложность

сложность в худшем случае

сложность в среднем

Вопрос 35

Какая из заданных сортировок является внешней?

Выберите один ответ:

Многофазная сортировка

Бинарная пирамидальная сортировка

Сортировка Хоара

Сортировка Шелла

Вопрос 36

Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр этого дерева?

Вопрос 37

Какие действия включает операция вставки (Insert(x)) в двоичном дереве поиска?

Выберите один или несколько ответов:

Осуществляется поиск ключа x в дереве

Если поиск завершился неудачей, создается новая вершина w с ключом x

Если поиск завершился удачей, создается новая вершина w с ключом x

Вершина w объявляется левым сыном v, если key(v) > key(w)

Вершина w объявляется правым сыном v, если key(v) < key(w)

Вопрос 38

Атрибут (или несколько атрибутов), по значению которого определяется порядок элементов во множестве, называется

Выберите один ответ:

алгоритм сортировки

время сортировки

устойчивость сортировки

ключ сортировки

Вопрос 39

Связный неориентированный граф, не содержащий циклов, петель и кратных ребер, — это

Выберите один ответ:

плоский граф

дерево

лес

полный граф

Вопрос 40

Ниже на языке программирования C++ записаны две рекурсивные функции: F и G. Чему будет равно значение, вычисленное при выполнении вызова F(6)?

int F (int n)

{

if (n>2)

return F(n-1)+G(n-1);

else return n;

}

int G(int n){

if (n>2)

return G(n-1)+F(n-2;

else return 3-n;

}

Промежуточный тест 1

Вопрос 1

Рассмотрите программу ниже и определите её сложность.

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)

Вопрос 2

Что понимается под временной сложностью алгоритма?

Выберите один ответ:

Минимальное количество машинного кода для представления алгоритма в ЭВМ

Функция размера входных и выходных данных, равная минимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи данного размера

Максимальное количество машинного кода для представления алгоритма в ЭВМ

Нет го ответа

Вопрос 3

Алгоритм некоторым образом обрабатывает массив (см. рисунок). Алгоритм состоит из двух вложенных циклов. Как асимптотическая сложность зависит от переменной n?

Выберите один ответ:

O(4 * n)

Не зависит от n

O(n)

O((i + j)n)

Вопрос 4

Укажите два наилучших алгоритма по критерию трудоемкости.

Выберите один или несколько ответов:

Алгоритм с логарифмической скоростью роста

Алгоритм с линейной скоростью роста

Алгоритм с линейно-логарифмической скоростью роста

Алгоритм с квадратичной скоростью роста

Вопрос 5

Алгоритм F имеет оценку сложности O(n2), а алгоритм G — O(n). Тогда

Выберите один или несколько ответов:

F может быть быстрее G на любом входе

F может быть медленнее G на любом входе

F может быть таким, что для любого n он делает n2 операций на некотором входе размера n

G может быть таким, что для любого n он делает n2 операций на некотором входе размера n

Вопрос 6

Пусть X — задача из NP. Какое утверждение справедливо для задачи X?

Выберите один ответ:

X может быть неразрешима

Если X можно решить за полиномиальное время на ДМТ, то P = NP

Нет полиномиального алгоритма для X

X — NP-трудная задача

Если X — NP-трудная задача, то она NP-полная

Вопрос 7

Алгоритм обрабатывает массив (см. рисунок). Входные данные алгоритма — k, t, n. От каких из перечисленныз входных данных зависит время работы алгоритма?

Выберите один ответ:

От k, t, n

От k и t

От t и n

От n

Не зависит от входных данных

Вопрос 8

Какова сложность алгоритма?

Выберите один ответ:

O(n)

O(k + n)

O(k(n – 1))

O(k)

Вопрос 9

Если 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)

Вопрос 10

Алгоритм нахождения минимального элемента массива был модифицирован. Теперь он ищет минимальный и максимальный элемент массива. В этом случае асимптотическая сложность алгоритма

Выберите один ответ:

не изменится

увеличится на порядок

уменьшится на порядок

уменьшится в два раза

Промежуточный тест 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(1) = 1, F(2) = 3, F(n) = F(n − 1) * F(n − 2) + (n − 2) при n > 2.

Чему равно значение функции F(5)?

В ответе запишите только натуральное число.

Вопрос 3

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = 2 при n ≤ 2,

F(n) = 2 • F(n − 1) + F(n − 2) при n > 2.

Чему равно значение функции F(5)?

В ответе запишите только натуральное число.

Вопрос 4

Задан алгоритм вычисления значения функции F(n), где n – натуральное число, который представлен следующими соотношениями:

F(1) = 1, F(2) = 1, F(n) = F(n – 1) * n − 2 * F(n – 2) при n > 2.

Чему равно значение функции F(6)?

В ответе запишите только натуральное число.

Вопрос 5

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = n при n ≤ 2,

F(n) = F(n − 1) • F(n − 2) при n > 2.

Чему равно значение функции F(6)?

В ответе запишите только натуральное число.

Вопрос 6

Последовательность чисел Люка задается рекуррентным соотношением:

F(1) = 2, F(2) = 1, F(n) = F(n – 2) + F(n – 1) при n > 2, где n – натуральное число.

Чему равно десятое число в последовательности Люка?

В ответе запишите только натуральное число.

Вопрос 7

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = 2 при n ≤ 2,

F(n) = F(n − 1) + 3 • F(n − 2) при n > 2.

Чему равно значение функции F(5)?

В ответе запишите только натуральное число.

Вопрос 8

Последовательность чисел трибоначчи задается рекуррентным соотношением:

F(1) = 0, F(2) = 1, F(3) = 1, F(n) = F(n – 3) + F(n – 2) + F(n–1) при n > 3, где n – натуральное число.

Чему равно девятое число в последовательности трибоначчи?

В ответе запишите только натуральное число.

Вопрос 9

Представленный алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(1) = 1, F(2) = 3, F(n) = F(n – 1) * n + F(n–2) * (n – 1) при n > 2.

Каково значение функции F(5)?

В ответе запишите только натуральное число.

Вопрос 10

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = n при n ≤ 2,

F(n) = 3 • F(n − 1) − F(n − 2) при n > 2.

Чему равно значение функции F(6)?

В ответе запишите только натуральное число.

Промежуточный тест 3

Вопрос 1

Формирование какой последовательности описывает рекурсивная функция 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, …

Вопрос 2

Формирование какой последовательности описывает рекурсивная функция 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, ...

Нет го ответа

Вопрос 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

Ниже на языке программирования 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;

}

Вопрос 5

Формирование какой последовательности описывает рекурсивная функция 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, ...

Промежуточный тест 4

Вопрос 1

Простыми типами данных в С++ являются

Выберите один ответ:

целые — int, вещественные — float или double, символьные — string

целые — int, вещественные — float или double, символьные — char

целые — bool, вещественные — float или double, символьные — string

целые — int, вещественные — float или real, символьные — char

Вопрос 2

Какой из перечисленных типов данных не является типом данных в С++?

Выберите один ответ:

float

double

int

real

Вопрос 3

Назовите определение типа данных (выберите 2 варианта ответа).

Выберите один или несколько ответов:

Возможность ввода/вывода данных

Множество (диапазон) значений, которые могут принимать величины этого типа

Наименование библиотек для подключения функций

Операции и функции, которые можно применять к данным этого типа

Вопрос 4

Какое ключевое слово указывает на то, что целая переменная не может принимать отрицательные значения?

Выберите один ответ:

positive

long

unsigned

Другое

Нет такого зарезервированного слова

Вопрос 5

Структура объявления переменных в С++ имеет вид

Выберите один ответ:

[=];< идент. 2>,…

[:=], < идент. 2>,…

[=], < идент. 2>,…

[==]; < идент. 2>,…

Промежуточный тест 5

Вопрос 1

Укажите строку, которая возвращает адрес первого элемента в массиве arr.

Выберите один ответ:

&arr

arr[1]

arr[0]

arr

Вопрос 2

В каком из вариантов ответов объявлен двумерный массив?

Выберите один ответ:

int array[20, 20]

array anarray[20][20]

int anarray[20][20]

char array[20]

Вопрос 3

Словосочетание «Hello world!» может быть сохранено в символьном массиве размером n элементов. Чему равно n?

Выберите один ответ:

12

10

13

11

Вопрос 4

Каков порядковый номер последнего элемента массива, если размер массива 19?

Выберите один ответ:

19

18

Порядковый номер определяется программистом

100

Вопрос 5

В какой из представленных строк выполняется обращение к седьмому элементу массива, если размер массива равен 10?

Выберите один ответ:

mas

mas(7)

mas[6]

mas[7]

Вопрос 6

Таблицы в языке программирования С++ бывают

Выберите один ответ:

только одномерными

только двумерными

только однострочными и двустрочными

одномерными и двумерными

Промежуточный тест 6

Вопрос 1

В чем заключается недостаток связного представления данных (обращения к данным через указатели)?

Выберите один ответ:

Размер структуры ограничивается только доступным объемом машинной памяти

При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей

Большая гибкость структуры

Доступ к элементам связной структуры может быть менее эффективным по времени

Вопрос 2

Укажите зарезервированное ключевое слово для динамического выделения памяти.

Выберите один ответ:

new

value

create

malloc

Вопрос 3

Определите основной недостаток использования связного представления данных (обращения к данным через указатели).

Выберите один ответ:

Размер структуры ограничивается только доступным объемом машинной памяти

При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей

На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память

Нет го ответа

Вопрос 4

Как освободить память от удаленного из списка элемента?

Выберите один ответ:

p=getnode

ptr(p)=nil

freenode(p)

p=lst

Вопрос 5

Укажите структуру, в которой доступ к элементам осуществляется в любой момент времени и к любому элементу с помощью индексов.

Выберите один ответ:

Множество

Массив

Очередь

Запись

Вопрос 6

Укажите достоинства связного представления данных (обращения к данным через указатели). (Выберите 2 показателя.)

Выберите один или несколько ответов:

При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей

Большая гибкость структуры

Доступ к элементам связной структуры может быть менее эффективным по времени

На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память

Вопрос 7

Какая структура является динамическими? (Укажите 2 параметра.)

Выберите один или несколько ответов:

Ей выделяется память в процессе выполнения программы

Она не имеет имени

Она работает только с массивами

Она не требует дополнительной памяти

Вопрос 8

Определите характеристику динамической структуры данных (укажите 2 параметра).

Выберите один или несколько ответов:

Размерность структуры может меняться в процессе выполнения программы

Она не имеет имени

Она работает только с массивами

Она не требует дополнительной памяти

Вопрос 9

В чем заключаются достоинства связного представления данных (обращения к данным через указатели)? (Выберите 2 показателя.)

Выберите один или несколько ответов:

Размер структуры ограничивается только доступным объемом машинной памяти

При изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей

Доступ к элементам связной структуры может быть менее эффективным по времени

На поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память

Вопрос 10

Укажите зарезервированное ключевое слово для высвобождения выделенной памяти.

Выберите один ответ:

free

remove

delete

clear

Промежуточный тест 7

Вопрос 1

Процедура позволяет

Выберите один ответ:

добавлять узел в начало списка

добавлять узел в конец списка

добавлять узел после заданного узла в списке

добавлять узел перед заданным узлом в списке

Вопрос 2

Что можно объявить с помощью представленного ниже кода?

Выберите один ответ:

Односвязный список

Двусвязный список

Стек

Очередь

Дерево

Вопрос 3

Что позволяет делать процедура, представленная ниже?

Выберите один ответ:

Добавлять узел в начало двусвязного списка

Добавлять узел в конец двусвязного списка

Добавлять узел после заданного узла в двусвязном списке

Добавлять узел перед заданным узлом в двусвязном списке

Вопрос 4

Что позволяет делать процедура, показанная ниже?

Выберите один ответ:

Добавлять узел в начало двусвязного списка

Добавлять узел в конец двусвязного списка

Добавлять узел после заданного узла в двусвязном списке

Добавлять узел перед заданным узлом в двусвязном списке

Вопрос 5

Очередью называется

Выберите один ответ:

однородный набор величин одного и того же типа, идентифицируемых вычисляемым индексом

линейно упорядоченный набор следующих друг за другом компонент

набор именованных компонент разного типа, объединенных общим именем

множество элементов

Вопрос 6

Что можно объявить с помощью кода, представленного ниже?

Выберите один ответ:

Односвязный список

Двусвязный список

Стек

Очередь

Дерево

Вопрос 7

Что объявляется с помощью кода, представленного ниже?

Выберите один или несколько ответов:

Односвязный список

Двусвязный список

Стек

Очередь

Дерево

Вопрос 8

Что можно объявить с помощью кода, указанного ниже?

Выберите один или несколько ответов:

Односвязный список

Двусвязный список

Стек

Очередь

Дерево

Вопрос 9

Что позволяет делать процедура, показанная ниже?

Выберите один ответ:

Добавлять узел в начало списка

Добавлять узел в конец списка

Добавлять узел после заданного узла в списке

Добавлять узел перед заданным узлом в списке

Вопрос 10

С помощью кода можно объявить

Выберите один или несколько ответов:

односвязный список

двусвязный список

стек

очередь

дерево

Вопрос 11

С помощью какой структуры данных наиболее рационально реализовать очередь?

Выберите один ответ:

С помощью стека

С помощью списка

С помощью дека

С помощью массива

Промежуточный тест 8

Вопрос 1

Структура данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов, называется

Выберите один ответ:

однонаправленные (односвязные) списки

дерево

стек

очередь

Вопрос 2

Динамической структурой данных является

Выберите один ответ:

очередь

запись

дерево

массив

Вопрос 3

Какие структуры являются динамическими? (Укажите 2 вида.)

Выберите один или несколько ответов:

Однонаправленные (односвязные) списки

Циклические списки

Массивы

Структуры

Вопрос 4

Какое из приведенных утверждений ?

А. Указатели разных типов нельзя присваивать друг другу без операции приведения типа.

Б. Указатель, объявленный как void, может быть разыменован.

Выберите один ответ:

Только А

Только Б

Верны оба утверждения

Оба утверждения ложны

Вопрос 5

К динамическим структурам относятся (выберите 2 вида):

Выберите один или несколько ответов:

двунаправленные (двусвязные) списки

стек

массивы

структуры

Промежуточный тест 9

Вопрос 1

Как вычисляется коэффициент заполнения для равномерно распределенной хэш-функции H: k -> {0,..., N-1}?

Выберите один ответ:

α = N/M

α = M/N

α = 1 + M/N

α = 1 + N/M

Вопрос 2

Какая формула задает линейный способ просматривания ячеек хэш-таблицы?

Выберите один ответ:

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

Вопрос 3

В предположении гипотезы простого равномерного хэширования чему равно среднее время безуспешного поиска ключа для хэш-функции H: k -> {0,..., N-1}?

Выберите один ответ:

Θ(M/N)

Θ(log M/N)

Θ(M * N)

Θ(M/N + 1)

Вопрос 4

Если использовать универсальное семейство хэш-функций для хранения n ключей, то какова будет вероятность получить хотя бы одну коллизию при размере хэш-таблицы M = n2?

Выберите один ответ:

Не больше 2/3

Не больше 1/2

Меньше 1/M

Меньше 1/N

Вопрос 5

В случае универсального хэширования чему равно среднее время успешного поиска ключа для хэш-функции H: k -> {0,..., N-1}, если k1, ..., kn — все ключи, присутствующие в хэш-таблице?

Выберите один ответ:

Θ(1)

Θ(M/N + 1)

Θ(M)

Θ(N)

Промежуточный тест 10

Вопрос 1

Как можно ускорить алгоритм сортировки «пузырьком»?

Выберите один ответ:

Добавить во внутренний цикл проверку на отсутствие перестановок

Добавить перестановку с шагом (increment)

Добавить во внешний цикл проверку на отсутствие перестановок

Добавить возможность сортировки по убыванию

Вопрос 2

Укажите общие критерии оценки алгоритмов сортировки.

Выберите один или несколько ответов:

Вид алгоритма сортировки

Время работы в лучшем и худшем случаях

Реализация на конкретном языке программирования

Поведение алгоритма сортировки

Вопрос 3

Какая процедура приведена ниже?

void Exchange (int i, int j, int *x) {

int tmp;

tmp=x[i];

x[i]=x[j];

x[j]=tmp;

}

Выберите один ответ:

Процедура упорядочения по убыванию

Процедура упорядочения по возрастанию

Процедура сортировки элементов

Процедура обмена двух элементов

Вопрос 4

Определите тип сортировки.

Выберите один ответ:

Пузырьковая

Сортировка отбором

Сортировка вставками

Сортировка Шелла

Вопрос 5

Ниже представлен алгоритм. К какому типу сортировки он относится?

Выберите один ответ:

К пузырьковой сортировке

К сортировке отбором

К сортировке вставками

К сортировке Шелла

Промежуточный тест 11

Вопрос 1

Какие утверждения справедливы для медианного элемента массива?

Выберите один или несколько ответов:

Поиск медианы равносилен сортировке массива

Медианный элемент является идеальным с точки зрения выбора опорного элемента

Медианный элемент всегда находится в середине массива

Медиана — это среднее арифметическое всех элементов массива

Вопрос 2

Некоторый массив размером N был отсортирован за время, пропорциональное N1,27. По какому алгоритму выполнялась сортировка?

Выберите один ответ:

Хоара

Шелла

Перестановками

Отбором

Вставками

Вопрос 3

При какой сортировке происходит быстрая перестановка далеких неупорядоченных пар значений (сортировка таких пар обычно требует большого количества перестановок, если используется сравнение только соседних элементов)?

Выберите один ответ:

При сортировке слиянием

При бинарной пирамидальной сортировке

При сортировке Хоара

При сортировке Шелла

Вопрос 4

Дан массив элементов: 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

Вопрос 5

Дан массив с элементами (35,08,10,15,20,11,18,25,23,30,40). Какой массив будет получен после применения алгоритма Шелла с шагом 4 при сортировке по возрастанию? Последовательность запишите через запятую без пробелов.

Промежуточный тест 12

Вопрос 1

Укажите сортировку, особенностью которой является то, что она работает с элементами массива преимущественно последовательно, благодаря чему именно этот алгоритм используется при сортировке в системах с различными аппаратными ограничениями (например, при сортировке данных на жестком диске).

Выберите один ответ:

Сортировка слиянием

Бинарная пирамидальная сортировка

Сортировка Хоара

Сортировка Шелла

Вопрос 2

В алгоритме внешней сортировки используется два вспомогательных файла и отдельно реализуются распределение и слияние. Определите характеристики такой сортировки.

Выберите один или несколько ответов:

Многопутевая

Двухпутевая

Однофазная

Двухфазная

Вопрос 3

Дан файл 3 2 17 7 8 9 1 4 6 9 2 3 1 18. Какой файл получится в результате применения алгоритма сортировки естественным слиянием после первого прохода? (Введите числа через пробел.)

Вопрос 4

Какие утверждения справедливы для сортировки массивов методом слияния?

Выберите один или несколько ответов:

Сортировка основана на выделении и слиянии упорядоченных серий

Сортировка заканчивается, когда в массиве получена единственная серия

С каждым этапом сортировки в массиве образуются всё более длинные серии

Сортировка слиянием работает быстрее улучшенных методов

Вопрос 5

Дан файл 5 7 3 2 8 4 1. Какой файл получится при применении алгоритма сортировки простым слиянием после первого прохода? (Введите числа через пробел.)

Промежуточный тест 13

Вопрос 1

Имеется неупорядоченный массив целых чисел из 8 элементов. Сколько операций сравнения потребуется для нахождения искомого ключа, если он находится в конце массива?

Выберите один ответ:

1

8

0

7

4

Вопрос 2

Имеется неупорядоченный массив целых чисел из 10 элементов. Сколько операций сравнения потребуется для установления факта отсутствия искомых данных в этом массиве?

Выберите один ответ:

9

0

1

10

5

Вопрос 3

Имеется двоичное дерево поиска, содержащее целые числа от 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

Вопрос 4

В каком случае двоичное дерево будет деревом поиска?

Выберите один ответ:

Если в одной части дерева хранятся значения, которые больше вершины, а в другой — те, что меньше

Если матрица достижимости для него будет бинарной

Если орграф такого дерева будет циклическим

Если орграф такого дерева будет ациклическим

Вопрос 5

Какой метод поиска представлен в следующем фрагменте?

REPEAT I:=I+1

UNTIL (A[I]=X) OR (I=N)

Выберите один ответ:

Последовательный

Двоичный

Восходящий

Нисходящий

Смешанный

Вопрос 6

Какой поиск не требует сортировки значений множества?

Выберите один ответ:

Бинарный (двоичный, дихотомический) поиск

Последовательный (линейный) поиск

Поиск с барьером

Поиск через слияние

Промежуточный тест 14

Вопрос 1

Какие действия следует предпринять для сохранения свойств красно-черного дерева после операции вставки вершины x в следующей ситуации: A — родитель x, B — родитель A; B — черная вершина; A, C — красные; C — дядя x?

Выберите один ответ:

Никаких действий предпринимать не нужно

A и C сделать черными, B — красным

A сделать черными, x — красным

x сделать черным

Вопрос 2

Какие действия предпринимаются для сохранения свойств красно-черного дерева, если при операции вставки вершины x элементы x и y оказались красными (y — родитель x, y — корень)?

Выберите один ответ:

x становится черным

y становится черным

Никакие действия не предпринимаются

x и y становятся черными

Вопрос 3

Отметьте утверждения, справедливые для красно-черных деревьев.

Выберите один или несколько ответов:

Все листья черные

Если у красного родителя два сына, то их цвета черные

Количество черных вершин на пути от корня до листьев должно быть одинаковым

У черных вершин все дети красные

Красно-черные деревья сбалансированы

Высота поддеревьев различается не более чем на 1

Вопрос 4

Какими свойствами обладает красно-черное дерево?

Выберите один или несколько ответов:

Каждый лист дерева является черным

У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество черных узлов

У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество красных узлов

У черного узла оба дочерних узла — красные

Вопрос 5

Какие свойства могут нарушаться при вставке элемента в красно-черное дерево?

Выберите один или несколько ответов:

Каждый узел является красным или черным

Корень дерева является черным

Каждый лист дерева (NULL) является черным

У красного узла оба дочерних узла — черные

У любого узла все пути от него до листьев, являющихся его потомками, содержат одинаковое количество черных узлов

Вопрос 6

При вставке элемента в красно-черное дерево в случае возникновения «красно-красного» нарушения, когда «дядя» добавляемого узла — черный и при этом цепочка узлов образует угол, потребуется

Выберите один ответ:

перекрасить вершины

перекрасить вершины и произвести левый поворот

перекрасить вершины и произвести правый поворот

произвести двойной поворот

Вопрос 7

При вставке элемента в красно-черное дерево в случае возникновения «красно-красного» нарушения, когда «дядя» добавляемого узла — черный и при этом цепочка узлов образует прямую линию, потребуется

Выберите один ответ:

перекрасить вершины

перекрасить вершины и произвести левый поворот

перекрасить вершины и произвести правый поворот

произвести двойной поворот

Промежуточный тест 15

Вопрос 1

Сколько рёбер в полном графе с 20 вершинами?

Вопрос 2

Число полных трехвершинных подграфов в полном двудольном графе К6,7 равно

Вопрос 3

Граф G имеет 4 вершины, а граф H имеет 5 вершин. Сколько единиц будет в матрице смежности графа G H?

,

Вопрос 4

Пусть — неориентированный граф, где , .Число связных компонент данного графа равно

Вопрос 5

Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?

Выберите один ответ:

14

15

16

13

17

Вопрос 6

В двудольном графе одна доля состоит из пяти вершин степени 2, а другая — из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?

Вопрос 7

Сколько имеется неизоморфных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?

Вопрос 8

Граф G имеет 4 вершины, а граф H имеет 5 вершин. Сколько единиц будет в матрице смежности графа G H?

,

Вопрос 9

В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?

Выберите один ответ:

7

14

18

21

Вопрос 10

Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился двудольный граф?

Промежуточный тест 16

Вопрос 1

Чему равно цикломатическое число графа?

Вопрос 2

Какие из представленных графов являются эйлеровыми?

Выберите один ответ:

1, 2

1, 3

1, 4

2, 3

2, 4

Вопрос 3

Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?

Вопрос 4

Чему равно цикломатическое число графа?

Вопрос 5

В графе из n вершин остов содержит

Выберите один ответ:

n + 1 ребер

n – ¬1 ребер

n ребер

2n ребер

Вопрос 6

Чему равно цикломатическое число графа?

Вопрос 7

Чему равно цикломатическое число графа?

Промежуточный тест 17

Вопрос 1

Алгоритм Прима применяется

Выберите один ответ:

для ориентированных графов

для неориентированных графов

для детерминированных графов

для взвешенных неориентированных графов

для взвешенных ориентированных графов

Вопрос 2

От чего зависит асимптотика алгоритма Прима?

Выберите один или несколько ответов:

От способа хранения графа

От способа хранения вершин, не входящих в дерево

От способа модификации узлов графа

От способа изменения узлов графа

Вопрос 3

Метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами называется

Выберите один ответ:

модульное программирование

динамическое программирование

комплексное программирование

программирование с отходом назад

жадное программирование

Вопрос 4

Дано описание алгоритма поиска кратчайшего пути на графе: «Алгоритм находит кратчайшее расстояние между двумя любыми вершинами графа на основании того факта, что всякий неэлементарный кратчайший путь состоит из других кратчайших путей». Укажите название алгоритма.

Выберите один ответ:

Алгоритм Дейкстры

Алгоритм Флойда

Волновой алгоритм

Алгоритм перебора с возвратом

Вопрос 5

Дано описание алгоритма поиска кратчайшего пути на графе: «Алгоритм находит кратчайший путь из данной вершины до остальных вершин. Строится множество S вершин, для которых кратчайшие пути от начальной вершины уже известны. На каждом шаге ко множеству S добавляется та из оставшихся вершин, расстояние до которой от начальной вершины меньше, чем для других оставшихся вершин». Укажите название алгоритма.

Выберите один ответ:

Алгоритм Дейкстры

Алгоритм Флойда

Волновой алгоритм

Алгоритм перебора с возвратом

Промежуточный тест 18

Вопрос 1

Процесс ветвления можно представить в виде дерева, в котором

Выберите один ответ:

каждая вершина — это один маршрут

каждая вершина — это множество маршрутов

есть циклы

каждая вершина — это ребро в маршруте

Вопрос 2

Дана матрица стоимостей перевода системы из состояния в состояние.

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.

Вопрос 3

Задача коммивояжера относится

Выберите один ответ:

к целочисленному программированию

к аналитической геометрии

к анализу бесконечно малых величин

к евклидовой геометрии

Вопрос 4

На каждом шаге ветвления выбирается множество

Выберите один ответ:

с наибольшей оценкой

с наименьшей оценкой

с оптимальной оценкой

со средней оценкой

Вопрос 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

Хроматическое число полного двудольного графа К4,3 равно

Вопрос 2

Что происходит с хроматическим числом графа при удалении ребра?

Выберите один ответ:

Увеличивается

Уменьшается

Уменьшается или не изменяется

Может увеличиться, уменьшиться или остаться прежним

Вопрос 3

Хроматическое число дерева равно

Вопрос 4

Хроматическое число полного 5-вершинного графа равно

Вопрос 5

Какие из приведенных ниже условий являются необходимыми и достаточными для того, чтобы граф имел хроматическое число 2?

Выберите один ответ:

Степени вершин не превосходят 2

Нет циклов нечетной длины

Каждая компонента связности — цепь

Каждая компонента связности — цикл четной длины или цепь

Вопрос 6

В полном графе со множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?

Итоговый тест

Вопрос 1

Как осуществить вставку (Insert(k)) ключа k в таблицу T, реализованную фильтром Блюма?

Выберите один ответ:

Вычислить хэш-коды h1(k), ..., hs(k), после чего в получившиеся индексы ячеек булева массива T записать значение True

Вычислить сумму ∑hi(k) и записать в таблицу T в ячейку с получившимся индексом значение True

По хэш-функции h(k) определить булево значение и вставить его в индекс таблицы T

Вычислить хэш-коды h1(k), ..., hs(k), после чего в соответствующие значения записать ключ k

Вопрос 2

Какие высказывания относятся к рекурсивному определению дерева?

Выберите один или несколько ответов:

Дерево может быть пустым

Дерево — это вершина и связанное с ней конечное число поддеревьев

Дерево всегда содержит хотя бы одну корневую вершину

Дерево — это вершина и связанное с ней единственное поддерево

Вопрос 3

Алгоритм нахождения максимального элемента массива имеет сложность

Выберите один ответ:

O(n)

O(n2)

O(lnn)

(logn)

Вопрос 4

Преобразование значения переменной к новому типу, которое происходит автоматически, по правилам, заложенным в языке программирования, называют

Выберите один ответ:

явное приведение типа

неявное приведение типа

прямая рекурсия

косвенная (взаимная) рекурсия

Вопрос 5

Какие существуют метрики, отображающие эффективность алгоритма?

Выберите один ответ:

Процессорное время, память

Надежность, масштабируемость

Адаптивность

Простота реализации

Вопрос 6

Какая сортировка является одной из разновидностей быстрых сортировок и основана на упорядочивании подмножеств массива относительно опорных элементов?

Выберите один ответ:

Сортировка слиянием

Сортировка деревом

Сортировка Хоара

Сортировка Шелла

Вопрос 7

Пусть определен тип данных переменной. Тогда известной является информация

Выберите один ответ:

о начальном значении

о конечном значении

о количестве обращений к данным

о точности возможных значений

Вопрос 8

Какие утверждения справедливы для представления графа с помощью матрицы смежности?

Выберите один или несколько ответов:

В этом представлении используются двумерные массивы

Данное представление рекомендуется использовать для графов с фиксированным числом вершин

Данное представление имеет простую программную реализацию

Данное представление позволяет легко изменять набор вершин в графе

Вопрос 9

Какой из представленных на рисунке графов является полным?

Выберите один ответ:

1

2

3

4

Вопрос 10

Граф, который может быть изображен на плоскости так, что все пересечения ребер являются его вершинами, — это

Выберите один ответ:

дерево

плоский граф

лес

полный граф

Вопрос 11

Какое значение возвращает рекурсивная функция Rec(108,72), код которой приведен ниже?

int Rec(int n,int k) {

if (n%k==0) return k;

return Rec(k,n%k);

}

Выберите один ответ:

36

72

12

1

Вопрос 12

Дан массив с элементами (35, 08, 10, 15, 20, 11, 07, 25, 23, 30, 40). Какой массив будет получен после первого шага применения алгоритма Хоара при сортировке по возрастанию, если в качестве опорного элемента выбран средний элемент?

Запишите последовательность через запятую без пробелов.

Вопрос 13

Укажите все достоинства последовательного (линейного) поиска.

Выберите один или несколько ответов:

Может работать в потоковом режиме при непосредственном получении данных из любого источника

Не требует дополнительного анализа функций

Осуществляет просмотр всего массива в худшем случае

Применяется для малого числа элементов

Вопрос 14

Последовательность элементов сортировки, которая упорядочена по ключу, называется

Выберите один ответ:

распределение

слияние

серия (упорядоченный отрезок)

длина серии

Вопрос 15

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(1) = 5, F(2) = 5, F(n) = 5 • F(n − 1) − 4 • F(n − 2) при n > 2.

Чему равно значение функции F(13)?

В ответе запишите только натуральное число.

Вопрос 16

Какое утверждение ?

Выберите один ответ:

В остаточной сети могут быть только те ребра, которые были в исходной сети

В остаточной сети могут появиться новые ребра

В остаточной сети могут появиться новые вершины и ребра, соединяющие их со старыми вершинами

Все утверждения неверны

Вопрос 17

Дана матрица смежности неориентированного графа G(V, E). Укажите порядок обхода графа в глубину со стартовой вершины 4.

Выберите один ответ:

4213657

4213567

4321567

4312567

Вопрос 18

Выберите один ответ:

1

2

3

4

5

Вопрос 19

Какой поиск не требует дополнительной памяти?

Выберите один ответ:

Бинарный (двоичный, дихотомический) поиск

Последовательный (линейный) поиск

Поиск с барьером

Поиск через слияние

Вопрос 20

Ниже на языке программирования C++ записан рекурсивный алгоритм F.Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

void F(int n){

if (n>0){

std::cout <<n;

F(n-3);

F(n/3);

}

}

Вопрос 21

Какие правила обхода дерева являются основными

Выберите один или несколько ответов:

Обход в прямом порядке

Обход в обратном порядке

Симметричный обход

Круговой обход

Вопрос 22

Задача дискретной оптимизации характеризуется тем, что

Выберите один или несколько ответов:

множество её допустимых решений невыпукло

множество её допустимых решений представляет собой выпуклый многогранник

для двух близких точек функции так же близки

не удается естественным образом ввести понятие окрестности

Вопрос 23

Сортировка, в которой отдельно реализуется две фазы: распределение и слияние, называется

Выберите один ответ:

двухфазная сортировка

однофазная сортировка

двухпутевое слияние

многопутевое слияние

Вопрос 24

В чём отличительная особенность динамических объектов?

Выберите один ответ:

Они порождаются непосредственно перед выполнением программы

Они возникают уже в процессе выполнения программы

Они задаются в процессе выполнения программы

Они передаются из другой программы

Вопрос 25

Последовательность чисел Падована задается рекуррентным соотношением:

F(1) = 1, F(2) = 1, F(3) = 1, F(n) = F(n – 3) + F(n – 2) при n > 3, где n — натуральное число.

Чему равно десятое число в последовательности Падована?

В ответе запишите только натуральное число.

Вопрос 26

Что необходимо сделать при реализации структуры приближенное множество (Lossy Map) с помощью двух Блюм-фильтров (использованных для множеств-прообразов 0 и 1), чтобы избежать ситуации, когда при запросе Get(k) оба Блюм-фильтра вернули 1?

Выберите один ответ:

Такие значения признаются ложноположительными срабатываниями, их количество всегда невелико

На образованном такими значениями множестве C изготовить два более мелких Блюм-фильтра для множеств-прообразов 0 и 1, затем продолжить создание иерархии таких множеств, пока они не перестанут пересекаться

Признать такие значения равными 0

Удалить все такие значения из множества

Вопрос 27

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = n при n ≤ 2,

F(n) = F(n − 1) + 2 • F(n − 2) при n > 2.

Чему равно значение функции F(6)?

В ответе запишите только натуральное число.

Вопрос 28

Рекурсия использует

Выберите один ответ:

создание подпрограммы самой себя

копирование подпрограммы самой себя

удаление подпрограммой самой себя

обращение подпрограммы к самой себе

Вопрос 29

В каком из представленных случаев можно утверждать, что путь, соединяющий вершины x и y в BFS-дереве, является кратчайшим путем между ними в графе?

Выберите один ответ:

x и y — любые вершины

x и y находятся в дереве на одинаковом расстоянии от корня

x — корень дерева

Вершина x является предком вершины y в BFS-дереве

Вопрос 30

Алгоритм некоторым образом обрабатывает массив:

Алгоритм состоит из трёх вложенных циклов. Какая асимптотическая оценка сложности лучше подходит для данного алгоритма?

Выберите один ответ:

O(n)

O(n^3)

O(sinn)

O(logn)

Вопрос 31

Если T — время работы алгоритма, N — размер входных данных, что отображает функция maxT(I) для N(I) = N?

Выберите один ответ:

Время работы алгоритма в худшем случае для конкретного входа I

Время работы алгоритма в лучшем случае при рассмотрении всех входов I размера N

Время работы алгоритма в худшем случае при рассмотрении всех входов I размера N

Время работы алгоритма в среднем случае для конкретного входа I

Вопрос 32

Как называется один из параметров трудоемкости алгоритма, который характеризуется тем, что сортировка не меняет взаимного расположения равных элементов?

Выберите один ответ:

Алгоритм сортировки

Время сортировки

Устойчивость сортировки

Ключ сортировки

Вопрос 33

Любой граф, изоморфный плоскому, называется

Выберите один ответ:

кратный

симметрический

хроматический

планарный

Вопрос 34

Для оценки сложности алгоритмов, как правило, используется

Выберите один ответ:

сложность алгоритма в наилучшем случае

реальная сложность

асимптотическая сложность

сложность в худшем случае

сложность в среднем

Вопрос 35

Какая из заданных сортировок является внешней?

Выберите один ответ:

Многофазная сортировка

Бинарная пирамидальная сортировка

Сортировка Хоара

Сортировка Шелла

Вопрос 36

Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр этого дерева?

Вопрос 37

Какие действия включает операция вставки (Insert(x)) в двоичном дереве поиска?

Выберите один или несколько ответов:

Осуществляется поиск ключа x в дереве

Если поиск завершился неудачей, создается новая вершина w с ключом x

Если поиск завершился удачей, создается новая вершина w с ключом x

Вершина w объявляется левым сыном v, если key(v) > key(w)

Вершина w объявляется правым сыном v, если key(v) < key(w)

Вопрос 38

Атрибут (или несколько атрибутов), по значению которого определяется порядок элементов во множестве, называется

Выберите один ответ:

алгоритм сортировки

время сортировки

устойчивость сортировки

ключ сортировки

Вопрос 39

Связный неориентированный граф, не содержащий циклов, петель и кратных ребер, — это

Выберите один ответ:

плоский граф

дерево

лес

полный граф

Вопрос 40

Ниже на языке программирования C++ записаны две рекурсивные функции: F и G. Чему будет равно значение, вычисленное при выполнении вызова F(6)?

int F (int n)

{

if (n>2)

return F(n-1)+G(n-1);

else return n;

}

int G(int n){

if (n>2)

return G(n-1)+F(n-2;

else return 3-n;

}