Сортировка массива
5.1. Количество
арифметический операций алгоритма
сортировки выбором последовательности
элементов
в худшем случае есть:
а)
+б)
в)
,
где
г)
5.2. Количество
арифметический операций алгоритма
сортировки включением последовательности
элементов
в худшем случае есть:
а)
+б)
в) , где
г)
5.3. Количество арифметический операций алгоритма сортировки обменами (пузырьковая сортировка) последовательности элементов в худшем случае есть:
а)
+б)
в) , где
г)
5.4. Количество арифметический операций алгоритма Шейкерной сортировки последовательности элементов в худшем случае есть:
а)
+б)
в) , где
г)
5.5. Количество арифметический операций алгоритма сортировки Хоара (быстрая сортировка) последовательности элементов в худшем случае есть:
а)
+б)
в) , где
г)
5.6. Количество арифметический операций алгоритма сортировки слиянием последовательности элементов в худшем случае есть:
+а)
б)
в) , где
г)
Поиск элемента
6.1. Обозначим через l размерность задачи. Чему равна трудоемкость алгоритма бинарного поиска элемента в упорядоченном массиве (дихотомия)
а)
+б)
,
в)
,
где
г) ,
+д)
,
е)
,
6.2. Обозначим через l размерность задачи. Чему равна трудоемкость алгоритма поиска элемента среди элементов произвольного массива .
а)
+б) ,
в) ,
г)
,
д) нет правильного варианта ответа
6.3. Обозначим через l размерность задачи. Чему равна трудоемкость алгоритма построения бинарного поискового дерева из чисел.
а)
б) ,
+в) ,
г)
,
д) ,
е) нет правильного варианта ответа
6.4. Обозначим через l размерность задачи. Чему равна трудоемкость алгоритма поиска наибольшего элемента в упорядоченном массиве .
+а)
+б)
,
- константа
в) ,
г) ,
д) нет правильного варианта ответа
6.5. Обозначим через l размерность задачи. Задана последовательность из чисел . Чему равна трудоемкость алгоритма, который по заданной последовательности строит бинарное поисковое дерево, а затем осуществляет поиск в нем некоторого элемента .
а)
б) ,
в) ,
+г) ,
д)
,
е) нет правильного варианта ответа
6.6. Обозначим через l размерность задачи. Задан массив и элемент . Определить трудоемкость алгоритма: для выполнения поиска элемента в массиве сначала выполняется сортировка массива «включением», а затем используется алгоритм дихотомического поиска.
а)
,
где
б)
,
где
+в)
,
где
г)
д) другое
6.7. Обозначим через l размерность задачи. Задан массив и элемент . Определить трудоемкость алгоритма: для выполнения поиска элемента в массиве сначала выполняется сортировка массива «выбором», а затем используется алгоритм дихотомического поиска.
а)
+б)
,
где
+в) , где
г)
,
где
д) другое
6.8. Обозначим через l размерность задачи. Задан массив и элемент . Определить трудоемкость алгоритма: для выполнения поиска элемента в массиве сначала выполняется сортировка массива «обменами» (пузырьковая сортировка), затем используется алгоритм дихотомического поиска.
а) , где
б) , где
+в) , где
+г) , где
д) другое
6.9. Обозначим через l размерность задачи. Задан массив и элемент . Определить трудоемкость алгоритма: для выполнения поиска элемента в массиве сначала выполняется сортировка массива «слиянием», а затем используется алгоритм дихотомического поиска.
а)
+б) , где
+в) , где
+г)
,
д) другое
6.10. Обозначим через l размерность задачи. Задан массив и элемент . Определить трудоемкость алгоритма: для выполнения поиска элемента в массиве сначала выполняется сортировка Хоара, затем используется алгоритм дихотомического поиска.
а)
+б) , где
+в) ,
г) , где
д) другое