Главная / Программирование /
Структуры и алгоритмы компьютерной обработки данных / Тест 46
Структуры и алгоритмы компьютерной обработки данных - тест 46
Упражнение 1:
Номер 1
Укажите последовательности, которые являются бинарными пирамидами
Ответ:
 (1) 8, 4, 7, 3, 1, 5, 2, 2, 0 
 (2) 8, 7, 4, 3, 1, 5, 2, 2, 0 
 (3) 8, 5, 7, 4, 3, 3, 2, 2, 3 
 (4) 8, 5, 7, 4, 6, 3, 2, 2, 3 
Номер 2
Укажите последовательности, которые не являются бинарными пирамидами
Ответ:
 (1) 7, 5, 7, 4, 2, 6, 5, 3, 2 
 (2) 7, 5, 7, 4, 6, 2, 5, 3, 2 
 (3) 8, 6, 8, 3, 0, 7, 6, 1, 3 
 (4) 8, 6, 8, 3, 0, 7, 6, 1, 3, 1 
Номер 3
Укажите последовательности, которые являются бинарными пирамидами
Ответ:
 (1) 9, 6, 8, 3, 5, 7, 4, 2, 1, 4 
 (2) 9, 5, 8, 3, 4, 7, 4, 2, 1, 6 
 (3) 9, 6, 6, 2, 5, 8, 7, 0, 1, 3 
 (4) 9, 6, 8, 2, 5, 6, 7 0, 1, 3 
Упражнение 2:
Номер 1
В вершину пирамиды помещен элемент. На какой позиции он остановится в результате спуска вниз? Нумерация элементов начинается с нуля
Ответ:
 (1) 1 
 (2) 3 
 (3) 4 
 (4) 7 
Номер 2
В вершину пирамиды помещен элемент. На какой позиции он остановится в результате спуска вниз? Нумерация элементов начинается с нуля
Ответ:
 (1) 2 
 (2) 5 
 (3) 6 
 (4) 8 
Номер 3
В вершину пирамиды помещен элемент. На какой позиции он остановится в результате спуска вниз? Нумерация элементов начинается с нуля
Ответ:
 (1) 8 
 (2) 4 
 (3) 3 
 (4) 2 
Упражнение 3:
Номер 1
Дан массив элементов: 4, 7, 3, 8, 5, 6, 3, 7, 2, 6, 8. Укажите порядок элементов этого массива после выполнения первого прохода сортировки Хоара по невозрастанию. Опорный элемент расположен на средней позиции
Ответ:
 (1) 8, 8, 7, 7, 6, 6, 5, 4, 3, 3, 2 
 (2) 8, 7, 5, 4, 3, 6, 8, 7, 6, 3, 2 
 (3) 8, 7, 7, 8, 6, 5, 3, 3, 2, 6, 4 
 (4) 7, 4, 8, 3, 6, 5, 7, 3, 6, 2, 8 
Номер 2
Дан массив элементов: 4, 7, 3, 8, 5, 6, 3, 7, 2, 6, 8. Укажите порядок элементов этого массива после выполнения второго прохода сортировки Хоара по неубыванию. Опорный элемент расположен на средней позиции
Ответ:
 (1) 3, 2, 4, 3, 5, 6, 6, 7, 7, 8, 8 
 (2) 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8 
 (3) 4, 3, 3, 2, 5, 6, 7, 7, 8, 6, 8 
 (4) 3, 4, 5, 7, 8, 2, 3, 6, 6, 7, 8 
Номер 3
Дан массив элементов: 7, 9, 0, 3, 2, 4, 7, 6, 5, 2, 0. Укажите порядок элементов этого массива после выполнения второго прохода сортировки Хоара по невозрастанию. Опорный элемент расположен на средней позиции
Ответ:
 (1) 9, 7, 7, 6, 5, 4, 3, 2, 2, 0, 0 
 (2) 7, 9, 5, 6, 7, 4, 2, 3, 0, 2, 0 
 (3) 7, 9, 7, 6, 5, 4, 2, 3, 2, 0, 0 
 (4) 7, 9, 5, 6, 7, 4, 2, 3, 0, 2, 0 
Упражнение 4:
Номер 1
Дан массив элементов: 4, 7, 9, 0, 3, 2, 6, 8, 7. Укажите порядок элементов этого массива после выполнения одного прохода сортировки Шелла по неубыванию с шагом h=4
Ответ:
 (1) 4, 7, 0, 9, 2, 3, 6, 8, 7 
 (2) 3, 2, 6, 0, 4, 7, 9, 8, 7 
 (3) 0, 2, 3, 4, 6, 7, 7, 8, 9 
 (4) 0, 4, 7, 9, 2, 3, 6, 8, 7 
Номер 2
Дан массив элементов: 4, 7, 3, 0, 3, 2, 6, 8, 7, 2, 6, 4. Укажите порядок элементов этого массива после выполнения одного прохода сортировки Шелла по невозрастанию с шагом h=6
Ответ:
 (1) 7, 4, 3, 0, 3, 2, 8, 6, 7, 2, 6, 4 
 (2) 8, 7, 7, 6, 6, 4, 4, 3, 3, 2, 2, 0 
 (3) 8, 7, 6, 6, 4, 2, 7, 4, 3, 3, 2, 0 
 (4) 6, 8, 7, 2, 6, 4, 4, 7, 3, 0, 3, 2 
Номер 3
Дан массив элементов: 5, 0, 6, 4, 9, 7, 9, 2, 1, 0. Укажите порядок элементов этого массива после выполнения одного прохода сортировки Шелла по неубыванию с шагом h=5
Ответ:
 (1) 0, 4, 5, 6, 9, 0, 1, 2, 7, 9 
 (2) 0, 5, 4, 6, 7, 9, 2, 9, 0, 1 
 (3) 5, 0, 2, 1, 0, 7, 9, 6, 4, 9 
 (4) 5, 0, 0, 2, 1, 7, 9, 9, 6, 4 
Упражнение 5:
Номер 1
В алгоритме внешней сортировки используется три вспомогательных файла и отдельно реализуются распределение и слияние. Определите характеристики такой сортировки
Ответ:
 (1) однофазная 
 (2) двухфазная 
 (3) двухпутевая 
 (4) многопутевая 
Номер 2
В алгоритме внешней сортировки используется два вспомогательных файла и совмещены распределение и слияние. Определите характеристики такой сортировки
Ответ:
 (1) однофазная 
 (2) двухфазная 
 (3) двухпутевая 
 (4) многопутевая 
Номер 3
В алгоритме внешней сортировки используется два вспомогательных файла и отдельно реализуются распределение и слияние. Определите характеристики такой сортировки
Ответ:
 (1) однофазная 
 (2) двухфазная 
 (3) двухпутевая 
 (4) многопутевая 
Упражнение 6:
Номер 1
Во входном файле дан массив чисел:
5 6 9 3 2 3 4 5 4 7 8 6 0
Выполните первое распределение входных данных по двум вспомогательным файлам f1
и f2
, используя сортировку по неубыванию естественным слиянием
Ответ:
 (1) f1: 5 6 9 3 4 7 8 6 f2: 2 3 4 5 0 
 (2) f1: 5 6 9 2 3 4 5 6 f2: 3 4 7 8 0 
 (3) f1: 5 6 2 3 4 7 0 f2: 9 3 4 5 8 6 
 (4) f1: 5 6 9 4, 5 4 0 f2: 3 2 3 7 8 6 
Номер 2
После распределения по двум файлам были получены данные (серии разделены апострофом)
f1: 3 7 2 8 5 9 1 3 f2: 6 9 3 5 7 7
Выполните слияние этих результатов в один файл согласно алгоритму простой сортировки по неубыванию
Ответ:
 (1) 3 7 6 9 2 8 3 5 5 9 7 7 1 3
 
 (2) 3 7 2 8 6 9 3 5 5 9 1 3 7 7
 
 (3) 3 7 2 8 5 9 1 3 6 9 3 5 7 7
 
 (4) 3 6 7 9 2 3 5 8 5 7 7 9 1 3
 
Номер 3
Во входном файле дан массив чисел:
5 6 9 3 2 3 4 5 4 7 8 6 0
Выполните первое распределение входных данных по двум вспомогательным файлам f1
и f2
, используя сортировку по невозрастанию естественным слиянием
Ответ:
 (1) f1: 5 6 2 3 4 7 0 f2: 9 3 4 5 8 6 
 (2) f1: 9 8 7 6 6 5 5 f2: 4 4 3 3 2 0 
 (3) f1: 5 9 3 2 4 7 f2: 6 3 5, 4 8 6 0 
 (4) f1: 9 6 5 4 3 3 2 f2: 8 7 6 5 4 0 
Упражнение 7:
Номер 1
Укажите порядок вершин при обходе графа в ширину, начиная с вершины 1
Ответ:
 (1) 1 2 5 7 3 4 6 8 
 (2) 1 2 3 4 5 6 7 8 
 (3) 1 2 7 3 5 8 4 6 
 (4) 1 2 4 5 7 3 6 8 
Номер 2
Укажите порядок вершин при обходе графа в глубину, начиная с вершины 1
Ответ:
 (1) 1 2 4 5 7 3 6 8 
 (2) 1 2 3 4 6 5 7 8 
 (3) 1 2 3 4 6 4 5 1 7 8 
 (4) 1 2 3 4 5 6 7 8 
Номер 3
Укажите порядок вершин при обходе графа в ширину, начиная с вершины 5
Ответ:
 (1) 5 1 4 7 2 3 6 8 
 (2) 5 1 7 8 4 3 6 2 
 (3) 5 1 7 8 2 4 3 6 
 (4) 5 1 4 7 8 2 3 6 
Упражнение 8:
Номер 1
Дано описание алгоритма поиска кратчайшего пути на графе. "Алгоритм находит кратчайший путь из данной вершины до остальных вершин. Построим множество S
вершин, для которых кратчайшие пути от начальной вершины уже известны. На каждом шаге к множеству S
добавляется та из оставшихся вершин, расстояние до которой от начальной вершины меньше, чем для других оставшихся вершин." Укажите название алгоритма
Ответ:
 (1) алгоритм Дейкстры 
 (2) алгоритм Флойда 
 (3) волновой алгоритм 
 (4) алгоритм перебора с возвратом 
Номер 2
Дано описание алгоритма поиска кратчайшего пути на графе. "Алгоритм находит кратчайшее расстояние между двумя любыми вершинами графа на основании факта о том, что всякий неэлементарный кратчайший путь состоит из других кратчайших путей." Укажите название алгоритма
Ответ:
 (1) алгоритм Дейкстры 
 (2) алгоритм Флойда 
 (3) волновой алгоритм 
 (4) алгоритм перебора с возвратом 
Номер 3
Дано описание алгоритма поиска кратчайшего пути на графе. "Алгоритм находит оптимальное решение задачи о кратчайшем пути на графе методом проб и ошибок (попробуем сходить в эту сторону: не получится – вернемся и попробуем в другую)." Укажите название алгоритма
Ответ:
 (1) алгоритм Дейкстры 
 (2) алгоритм Флойда 
 (3) волновой алгоритм 
 (4) алгоритм перебора с возвратом