- •Лабораторная работа №1 «Семафоры и синхронизация процессов»
- •Теоретические сведения
- •Алгоритмы
- •Тестовый пример
- •Контрольные вопросы
- •Варианты заданий
- •Содержание отчёта
- •Приложение 1 Пример работы программы
- •Приложение 2. Код программы
- •Содержание
- •1. Теоретические сведения 1
- •Лабораторная работа №2 «Интерпретатор командного языка (кя) операционной системы»
- •1.Теоретические сведения
- •2.Алгоритм
- •3.Тестовый пример
- •4.Контрольные вопросы
- •5.Варианты заданий:
- •6. Содержание отчета
- •Приложение.
- •1. Теоретические сведения 27
- •1. Теоретические сведения 11
- •Лабораторная работа №3 «Алгоритмы последовательного поиска в таблице записи данных»
- •1. Теоретические сведения
- •2. Алгоритмы поиска
- •3. Тестовый пример
- •4. Контрольные вопросы
- •5. Варианты заданий
- •6. Содержание отчёта
- •Приложение
- •Литература
- •Содержание
- •1. Теоретические сведения 17
- •Лабораторная работа №4 «Пирамидальная сортировка»
- •Теоретические сведения
- •Алгоритм
- •Тестовый пример
- •Контрольные вопросы
- •Варианты заданий
- •Содержание отчёта
- •Приложение 1. Код программы
- •Приложение 2. Пример работы программы
- •Литература
- •Содержание
- •1. Теоретические сведения 28
Тестовый пример
Дано: Распределённое множество K ключей: “3,7,2,1,8,17,97,75,63,46,14,59,12,77,76,70,18,20,49,26,52,71,39,99,98,41,37,54,58”.
Задание: Требуется упорядочить последовательность множество K ключей в порядке убывания. Для упорядочивания необходимо воспользоваться пирамидальной сортировкой Р. Флойда. Для работы программы необходимо скопировать код из Приложения 1 в любой компилятор С++, ввести множество ключей в соответствии с вариантом, указанном в табл. 1, затем нажать и отпустить клавишу Enter.
Результат:
Результат работы программы приведёт в Приложении 2:
{99,98,97,77,76,75,71,70,63,59,58,54,52,49,46,41,39,37,26,20,18,17,14,12,8,7,3,2,1}
Контрольные вопросы
При каком условии массив ключей называют пирамидой?
В каком случае образуется иерархия ключей так, что наибольший ключ оказывается «на вершине пирамиды»?
Какое условие в исходном массиве выполняется автоматически для ℓ = [N/2] ?
Почему выполняется данное условие?
Как можно преобразовать массив, изменяя лишь поддерево с корнем в узле ℓ?
Варианты заданий
Номер варианта |
Множество ключей |
1 |
65,3,7,67,12,3,5,32,56,22,43,56,65,87,78,56,56,34,34,22,23,11,32,68 |
2 |
2,4,66,43,22,19,8,33,49,78,56,23,90,77,78,99,4,33,327,39,87,88 |
3 |
23,1,18,11,2,67,33,19,26,41,88,50,64,73,48,2,5,14,18,33,45,90,4 |
4 |
2,16,5,8,4,55,24,66,78,324,89,669,74,1,34,45,77,89,48,326,6,43,5 |
5 |
76,2,43,27,11,17,54,32,777,78,26,3,93,40,54,32,27,88,5,23,87,12,12 |
6 |
6,7,6,35,54,2,9,7,4,33,55,338,8,9,234,33,26,48,29,37,84,95,90,73,3 |
7 |
9,5,1,7,5,3,6,2,4,8,4,2,77,85,33,27,89,64,2,32,456,67,88,53,2,5,67,2 |
8 |
11,51,3,12,25,56,83,1,,11,23,4,27,84,92,7,77,54,38,71,5,8,9,32,12,9 |
9 |
43,1,45,11,17,23,4,887,65,32,24,68,89,29,61,45,3,2,87,9,6,24,4,8 |
10 |
23,62,3,32,38,34,11,2,46,18,9,33,51,92,38,46,3,22,234,0,5,3,3,56 |
11 |
23,43,67,76,2,2,114,6,1,82,800,34,2,1,44,66,82,17,5,6,8,7,64,123,81 |
12 |
3,8,364,52,34,14,15,66,42,433,66,7,14,32,577,86,542,4,3,7,4,6,5 |
13 |
43,4,17,3,79,9,5,332,5,667,75,32,411,43,67,56,65,12,72,65,7,9,1 |
14 |
90,45,2,12,4,90,8,43,2335,553,25,243,2,45,32,455,22,9,2,5,3,4,2 |
15 |
643,2,55,563,2,25,552,543,2,55,563,2,25,552,5345,25,4,5,6,1,2,3,0 |
16 |
23,5,11,663,69,0,334,48,92,73,81,77,53,3,22,46,6,73,75,78,4,8,9 |
17 |
5,67,3,88,82,0,93 84,67,39,17,38,99,8,13,15,3,2,23,7,72,3,78,9,8 |
18 |
45,3,22,11,10,3,23,45,66,89,32,0,26,33,145,32,213,56,7,21,7,13,6,78 |
19 |
10,8,5,45,2442,13,55,774,1,7,3,2,8,90,53,34,42,345,225,3,59,12,7 |
20 |
1,2,3,4,6,3,33,8,9,65,33,123,56,27,81,93,85,42,22,53,1,5,47,6,35,41 |
