игра брюс 2048
Главная / Программирование / Структуры и алгоритмы компьютерной обработки данных / Тест 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
В вершину пирамиды помещен элемент. На какой позиции он остановится в результате спуска вниз? Нумерация элементов начинается с нуля
		files
		

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 2
В вершину пирамиды помещен элемент. На какой позиции он остановится в результате спуска вниз? Нумерация элементов начинается с нуля
		files
		

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 3
В вершину пирамиды помещен элемент. На какой позиции он остановится в результате спуска вниз? Нумерация элементов начинается с нуля
		files
		

Ответ:

 (1)

 (2)

 (3)

 (4)


Упражнение 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
		files
		

Ответ:

 (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
		files
		

Ответ:

 (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
		files
		

Ответ:

 (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) алгоритм перебора с возвратом 




Главная / Программирование / Структуры и алгоритмы компьютерной обработки данных / Тест 46