Программирование

Упражнение 1:

Номер 1

Дан массив длины n, требуется циклически
сдвинуть его элементы вправо на одну позицию. Какое минимальное
число операций копирования выполняется в любом алгоритме,
решающем данную задачу? Имеются в виду операции копирования
одного элемента массива в другой, элемента массива в простую
переменную, одной простой переменной в другую.

Ответ:

(1) Минимум n операций.

(2) Минимум n+1 операция.

(3) Минимум 3n операций.

(4) Минимум n-1 операций.

(5) Минимум 2n операций.

Номер 2

Дан массив длины 11, требуется циклически
сдвинуть его элементы вправо на 3 позиции. Какое минимальное
число операций копирования выполняется в любом алгоритме,
решающем данную задачу? Имеются в виду операции копирования
одного элемента массива в другой, элемента массива в простую
переменную, одной простой переменной в другую.

Ответ:

(1) Минимум 11 операций.

(2) Минимум 12 операций.

(3) Минимум 33 операции.

(4) Минимум 22 операции.

(5) Минимум 10 операции.

Упражнение 2:

Номер 1

Дан массив длины 12, требуется циклически
сдвинуть его элементы влево на 5 позиций. Какое минимальное
число операций копирования выполняется в любом алгоритме,
решающем данную задачу? Имеются в виду операции копирования
одного элемента массива в другой, элемента массива в простую
переменную, одной простой переменной в другую.

Ответ:

(1) Минимум 12 операций.

(2) Минимум 13 операций.

(3) Минимум 36 операции.

(4) Минимум 11 операции.

(5) Минимум 24 операции.

Номер 2

Дан массив длины 21, требуется циклически
сдвинуть его элементы вправо на 6 позиций.
Существует ли алгоритм, который решает эту задачу,
выполняя 22 операции копирования?
Имеются в виду операции копирования
одного элемента массива в другой, элемента массива в простую
переменную, одной простой переменной в другую.

Ответ:

(1) Да.

(2) Нет.

Упражнение 3:

Номер 1

Дан массив длины 26, требуется циклически
сдвинуть его элементы вправо на 6 позиций.
Существует ли алгоритм, который решает эту задачу,
выполняя 28 операций копирования?
Имеются в виду операции копирования
одного элемента массива в другой, элемента массива в простую
переменную, одной простой переменной в другую.

Ответ:

(1) Да.

(2) Нет.

Номер 2

Дан массив длины 15, требуется циклически
сдвинуть его элементы вправо на 6 позиций.
Существует ли алгоритм, который решает эту задачу,
выполняя 18 операций копирования?
Имеются в виду операции копирования
одного элемента массива в другой, элемента массива в простую
переменную, одной простой переменной в другую.

Ответ:

(1) Да.

(2) Нет.

Упражнение 4:

Номер 1

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

Ответ:

(1) t = O(n)

(2) t = O(n log₂n)

(3) t = O(n²)

(4) t = O(n³)

(5) t = O(2ⁿ)

(6) t = O(log₂n)

Номер 2

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

Ответ:

(1) t = O(n)

(2) t = O(n log₂n)

(3) t = O(n²)

(4) t = O(n³)

(5) t = O(log₂n)

Упражнение 5:

Номер 1

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

Ответ:

(1) t = O(n)

(2) t = O(n log₂n)

(3) t = O(n²)

(4) t = O(n³)

(5) t = O(log₂n)

Номер 2

На 3 вакансии имеется 10 претендентов.
Сколько способов выбора возможно?

Ответ:

120

Упражнение 6:

Номер 1

Из восьми человек надо выбрать четверых.
Сколько способов выбора возможно?

Ответ:

70

Номер 2

При вычислении (x+y)⁷
раскрываются скобки и приводятся подобные члены.
Чему будет равен коэффициент при
x³y⁴?

Ответ:

35

Программирование - тест 121