игра брюс 2048
Главная / Программирование / Программирование / Тест 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  



Главная / Программирование / Программирование / Тест 111