Главная / Программирование /
Программирование / Тест 111
Программирование - тест 111
Упражнение 1:
Номер 1
К массиву a
длины 64 применяется
восходящая схема двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти — массива b
такого же размера. В каком из этих массивов мы получим результат после
окончательного шага слияния, т.е. будет ли вызвана
функция copyArray
, чтобы
скопировать результат из вспомогательного массива
b
в массив a
?
Ответ:
 (1)
Результат будет в массиве a
, функция
copyArray
вызвана не будет.
 
 (2)
Результат будет в массиве b
, будет вызвана функция
copyArray
.
 
Номер 2
К массиву a
длины 50 применяется
восходящая схема двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти — массива b
такого же размера. В каком из этих массивов мы получим результат после
окончательного шага слияния, т.е. будет ли вызвана
функция copyArray
, чтобы
скопировать результат из вспомогательного массива
b
в массив a
?
Ответ:
 (1)
Результат будет в массиве a
, функция
copyArray
вызвана не будет.
 
 (2)
Результат будет в массиве b
, будет вызвана функция
copyArray
.
 
Упражнение 2:
Номер 1
К массиву a
длины 28 применяется
восходящая схема двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти — массива b
такого же размера. В каком из этих массивов мы получим результат после
окончательного шага слияния, т.е. будет ли вызвана
функция copyArray
, чтобы
скопировать результат из вспомогательного массива
b
в массив a
?
Ответ:
 (1)
Результат будет в массиве a
, функция
copyArray
вызвана не будет.
 
 (2)
Результат будет в массиве b
, будет вызвана функция
copyArray
.
 
Номер 2
К массиву a
длины 30 применяется
восходящая схема двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти.
В процессе выполнения алгоритма многократно
вызывается функция merge
слияния двух упорядоченных
массивов длины n
и m
. Каковы
длины массивов, которые сливаются при самом последнем вызове
функции merge
?
Ответ:
 (1)
n=15
, m=15
 
 (2)
n=16
, m=14
 
 (3)
n=24
, m=16
 
 (4)
n=24
, m=15
 
 (5)
n=16
, m=15
 
 (6)
n=15
, m=14
 
Упражнение 3:
Номер 1
К массиву a
длины 12 применяется
восходящая схема двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти.
В процессе выполнения алгоритма многократно
вызывается функция merge
слияния двух упорядоченных
массивов длины n
и m
. Каковы
длины массивов, которые сливаются при самом последнем вызове
функции merge
?
Ответ:
 (1)
n=6
, m=6
 
 (2)
n=8
, m=4
 
 (3)
n=10
, m=2
 
 (4)
n=8
, m=6
 
 (5)
n=6
, m=4
 
 (6)
n=10
, m=4
 
Номер 2
К массиву a
длины 20 применяется
восходящая схема двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти.
В процессе выполнения алгоритма многократно
вызывается функция merge
слияния двух упорядоченных
массивов длины n
и m
. Каковы
длины массивов, которые сливаются при самом последнем вызове
функции merge
?
Ответ:
 (1)
n=10
, m=10
 
 (2)
n=12
, m=8
 
 (3)
n=16
, m=4
 
 (4)
n=10
, m=8
 
 (5)
n=12
, m=4
 
 (6)
n=16
, m=10
 
Упражнение 4:
Номер 1
К массиву a
длины 10 применяется восходящая схема
двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти
такого же размера. Сколько раз будет вызвана
функция слияния двух упорядоченных массивов merge
?
Ответ:
 (1)
5 раз
 
 (2)
8 раз
 
 (3)
9 раз
 
 (4)
10 раз
 
 (5)
11 раз
 
Номер 2
К массиву a
длины 12 применяется восходящая схема
двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти
такого же размера. Сколько раз будет вызвана
функция слияния двух упорядоченных массивов merge
?
Ответ:
 (1)
8 раз
 
 (2)
9 раз
 
 (3)
10 раз
 
 (4)
11 раз
 
Упражнение 5:
Номер 1
К массиву a
длины 11 применяется восходящая схема
двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти
такого же размера. Сколько раз будет вызвана
функция слияния двух упорядоченных массивов merge
?
Ответ:
 (1)
6 раз
 
 (2)
8 раз
 
 (3)
10 раз
 
 (4)
11 раз
 
Номер 2
В алгоритме сортировки слиянием "In Place Merge Sort",
не использующем дополнительной памяти,
применяется функция mergeBlocks
слияния двух упорядоченных блоков, т.е. подмассивов длины
m
и n
, реализованная рекурсивно.
За какое время работает эта функция?
Ответ:
 (1)
t=O(n+m)
 
 (2)
t=O((n+m)log2(n+m))
 
 (3)
t=O((n+m)log22(n+m))
 
 (4)
t=O((n)log2(m))
 
 (5)
t=O((m)log2(n))
 
Упражнение 6:
Номер 2
В алгоритме сортировки слиянием "In Place Merge Sort",
не использующем дополнительной памяти, применяется
функция mergeBlocks
слияния двух упорядоченных блоков, т.е. подмассивов длины
m
и n
, реализованная рекурсивно.
Пусть сумма длин блоков m+n=1000
. Какой может быть
максимальная суммарная длина блоков при рекурсивном вызове
функции mergeBlocks
на первом шаге?
Ответ:
 (1)
250
 
 (2)
500
 
 (3)
750
 
 (4)
1000
 
 (5)
1500
 
Номер 2
В алгоритме сортировки слиянием "In Place Merge Sort",
не использующем дополнительной памяти, применяется
функция mergeBlocks
слияния двух упорядоченных блоков, т.е. подмассивов длины
m
и n
, реализованная рекурсивно.
Пусть сумма длин блоков m+n=512
.
При реализации функции mergeBlocks
вызывается функция перестановки двух блоков
swapBlocks
. Какой может быть
максимальная суммарная длина блоков переставляемых блоков?
Ответ:
 (1)
192
 
 (2)
256
 
 (3)
384
 
 (4)
128
 
 (5)
512