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

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

Номер 1

Массив a размера 4 содержит
элементы 4, 3, 2, 1 в указанном порядке.
К нему применяется алгоритм пузырьковой сортировки,
использующий сравнение элементов с помощью функции compare
и обмен элементов с помощью функции swap.
Сколько раз будет вызвана функция swap?

Ответ:

6

Номер 2

Массив a размера 4 содержит
элементы 4, 2, 1, 3 в указанном порядке.
К нему применяется алгоритм пузырьковой сортировки,
использующий сравнение элементов с помощью функции compare
и обмен элементов с помощью функции swap.
Сколько раз будет вызвана функция swap?

Ответ:

4

Номер 3

Массив a размера 4 содержит
элементы 4, 1, 3, 2 в указанном порядке.
К нему применяется алгоритм пузырьковой сортировки,
использующий сравнение элементов с помощью функции compare
и обмен элементов с помощью функции swap.
Сколько раз будет вызвана функция swap?

Ответ:

4

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

Номер 1

Алгоритм пузырьковой сортировки упорядочивает массив
из 10 тысяч элементов примерно за 1 секунду. За какое примерно
время тот же алгоритм упорядочит массив из 100 тысяч элементов?

Ответ:

(1) 10 секунд

(2) 100 секунд

(3) 1000 секунд

(4) 10000 секунд

(5) 2 секунды

Номер 2

Алгоритм пузырьковой сортировки упорядочивает массив
из 10 тысяч элементов примерно за 1 секунду. За какое примерно
время тот же алгоритм упорядочит массив из миллиона элементов?

Ответ:

(1) За 1 минуту 40 секунд

(2) Около 17 минут

(3) Около 2 часов 47 минут

(4) Около 57 минут

(5) Около 37 минут

Номер 3

Алгоритм пузырьковой сортировки упорядочивает массив
из 100 тысяч элементов примерно за 1 минуту. За какое примерно
время тот же алгоритм упорядочит массив из 10 тысяч элементов?

Ответ:

(1) За 0.6 секунды

(2) За 6 секунд

(3) За 30 секунд

(4) За 0.6 секунды

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

Номер 1

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

Ответ:

(1) 4 раза

(2) 5 раз

(3) 6 раз

(4) 7 раз

(5) 8 раз

Номер 2

Массив длины 5 содержит элементы
5, 4, 1, 2, 3 в указанном порядке.
К нему применяется
алгоритм сортировки методом прямого выбора,
использующий сравнение элементов с помощью функции compare
и обмен элементов с помощью функции swap.
Сколько раз будет вызвана функция swap?

Ответ:

(1) 2 раза

(2) 3 раза

(3) 4 раза

(4) 5 раз

Номер 3

Массив длины 5 содержит элементы
2, 1, 5, 4, 3 в указанном порядке.
К нему применяется
алгоритм сортировки методом прямого выбора,
использующий сравнение элементов с помощью функции compare
и обмен элементов с помощью функции swap.
Сколько раз будет вызвана функция swap?

Ответ:

(1) 2 раза

(2) 3 раза

(3) 4 раза

(4) 5 раз

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

Номер 1

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

Ответ:

(1) Пузырьковая сортировка.

(2) Сортировка методом прямого выбора.

Номер 2

Для конкретного массива длины 1000 применяются
алгоритмы пузырьковой сортировки и сортировки
методом прямого выбора. Какой из этих двух
алгоритмов работает быстрее?

Ответ:

(1) Пузырьковая сортировка.

(2) Сортировка методом прямого выбора.

(3) Возможны оба варианта в зависимости от содержания массива (для каких-то массивов быстрее пузырьковая сортировка, для других - сортировка прямым выбором).

Номер 3

Для конкретного массива длины 1000 применяются
алгоритмы пузырьковой сортировки и сортировки
методом прямого выбора.
Оба алгоритма используют сравнение элементов
с помощью функции compare
и обмен элементов с помощью функции swap.
Какой из этих алгоритмов вызывает функцию swap
большее число раз? (Имеется в виду нестрогое сравнение.)

Ответ:

(1) Пузырьковая сортировка всегда вызывает функцию swap не меньшее число раз, чем сортировка прямым выбором.

(2) Сортировка прямым выбором всегда вызывает функцию swap не меньшее число раз, чем пузырьковая сортировка.

(3) Возможны оба варианта в зависимости от содержания массива (для каких-то массивов пузырьковая сортировка вызывает функцию swap большее число раз, для других массивов - сортировка прямым выбором).

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

Номер 1

В турнире участвуют 4 баскетбольные команды,
все матчи проводятся последовательно
в одном зале. По результатам турнира команды должны быть упорядочены в
соответствии с их силой. В зависимости от исхода матчей турнир может
завершиться раньше или позже; для всякого расписания турнира
можно определить максимально возможное количество матчей.
Приведите оценку снизу максимального количества матчей
для всех возможных расписаний турниров 4 команд.

Ответ:

(1) 4 матча

(2) 5 матчей

(3) 6 матчей

(4) 3 матча

Номер 2

Есть 4 монеты, известно, что все они имеют различные веса.
Веса двух монет можно сравнить, используя весы-коромысло.
Какое минимальное количество взвешиваний во всех случаях достаточно,
чтобы упорядочить монеты по возрастанию их веса?

Ответ:

(1) 4 взвешивания

(2) 5 взвешиваний

(3) 6 взвешиваний

(4) 3 взвешивания

(5) 2 взвешивания

Номер 3

Есть 6 монет, известно, что все они имеют различные веса.
Веса двух монет можно сравнить, используя весы-коромысло.
Требуется упорядочить монеты по возрастанию их веса.
Можно ли придумать такой алгоритм сортировки монет по весу,
при котором в любом случае будет сделано не больше 9 взвешиваний?

Ответ:

(1) Можно.

(2) Нельзя.

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