Файловый архив студентов. Файловый архив студентов.
1261 вуз, 4605 предмет.
/ Регистрация
FAQ Обратная связь Вопросы и предложения
Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Витебский государственный университет им. П. М. Машерова
Предмет:
[НЕСОРТИРОВАННОЕ]
Файл:
MU_dlya_RGR.doc
Скачиваний:
5
Добавлен:
21.11.2018
Размер:
317.95 Кб
Скачать
☆
►Содержание►

3

Министерство образования Республики Беларусь

УО «Полоцкий государственный университет»

Кафедра технологий программирования

С.В.Кухта

Методические указания

к выполнению РГР по курсу

«СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ»

для студентов заочной формы обучения

специальности 1–40 01 01 «Программное обеспечение нформационных технологий»

Новополоцк 2011

Введение

Цели расчетно-графической работы:

  • - формирование практических навыков организации и использования при решении задач динамических структур данных;

  • изучение наиболее распространенных алгоритмов решения задач с использованием сложных структур данных.

В контрольной работе требуется выполнить 4 задачи. Задачи выбираются согласно правил, изложенных в разделе 2.

Для проектирования программ разрешается использовать любой язык программирования высокого уровня. Но все структуры данных должны быть созданы с использованием простейших типов данных языка в «ручном» режиме, запрещается использовать встроенные в язык или среду программирования средства. Операции их обработки, например, помещения элемента в стек, извлечения из него, полностью должны быть реализованы студентом.

  1. Правила оформления

Соблюдение всех правил оформления является обязательным!

Работа оформляется только на компьютере и распечатывается затем на листах формата А4 и подшивается в папку.

Пояснительная записка к РГР оформляется в среде текстового процессора Microsoft Word. Представляется на лис­тах белой бумаги формата А4 со следующими параметрами страницы: левое поле – 30 мм, правое поле – 15 мм, верхнее и нижнее 20 мм. Шрифт – Times New Roman, размер 14 пт, междустрочный интервал – множитель 1,1. Абзацный отступ – 1,25 см.

Решение задач оформляется с применением стилей заголовков, списков, таблиц, формул, рисунков, с выделением шрифтом важных мест в тексте. В описание решения задачи должны быть вставлены блок-схемы алгоритмов, иллюстрации, поясняющие основные моменты обработки структур данных, копии экранов программы, поясняющие основные этапы решения. В приложении должны прилагаться листинги основных модулей программы.

Структура пояснительной записки к контрольной работе:

Титульный лист

Содержание

1. Задача № 1

1.1. Постановка задачи и ее анализ

1.2. Описание структур данных

1.3. Проектирование программы

1.4. Результаты отладки и тестирования

2. Задача № 2

…

Список использованных источников

Приложения

В конце РГР приводится полный список литературы, которая была использована при выполнении всех заданий контрольной работы. Список составляется в алфавитном порядке по фамилиям авторов с указанием их инициалов. Далее указывается полное название книги, место и год издания, количество страниц. При использовании источников сети Интернет указывается полный адрес Web-сайта и гипертекстового документа. Список литературы должен содержать только названия тех источников, которые действительно были использованы при изучении.

Вмнсте с РГР следует представить диск с файлами программ.

Работа должна быть представлена на кафедру технологий программирования для проверки не позже указанного 14 декабря. В случае, если работа не допущена к защите, студент в этой же папке, не извлекая при этом из нее листы с ошибками, должен исправить все отмеченные ошибки и недочеты и представить ее на повторное рецензирование.

2. Варианты заданий для ргр

Номер варианта V определяется по правилу:

V = n mod 90 + 1,

где n – две последние цифры номера зачетной книжки.

Вариант

Задача № 1

Задача № 2

Задача № 3

Задача № 4

Вариант

Задача № 1

Задача № 2

Задача № 3

Задача № 4

Вариант

Задача № 1

Задача № 2

Задача № 3

Задача № 4

1.12

2.31

3.20

4.2

1.73

2.58

3.11

4.31

1.64

2.10

3.27

4.38

1.33

2.61

3.26

4.3

1.7

2.50

3.25

4.19

1.16

2.47

3.22

4.1

1.58

2.65

3.33

4.9

1.62

2.54

3.33

4.18

1.17

2.49

3.3

4.27

1.75

2.14

3.27

4.19

1.72

2.21

3.40

4.17

1.1

2.65

3.28

4.32

1.54

2.32

3.7

4.45

1.37

2.55

3.45

4.7

1.26

2.57

3.18

4.5

1.59

2.64

3.34

4.14

1.67

2.30

3.31

4.4

1.6

2.57

3.16

4.28

1.53

2.69

3.8

4.28

1.34

2.26

3.13

4.39

1.63

2.25

3.31

4.10

1.67

2.1

3.19

4.23

1.68

2.18

3.6

4.27

1.49

2.52

3.39

4.12

1.11

2.33

3.23

4.8

1.23

2.44

3.14

4.35

1.64

2.47

3.32

4.8

1.32

2.24

3.36

4.44

1.35

2.56

3.6

4.10

1.27

2.53

3.41

4.6

1.60

2.70

3.32

4.24

1.24

2.13

3.44

4.36

1.22

2.38

3.29

4.11

1.10

2.43

3.35

4.1

1.69

2.34

3.8

4.11

1.21

2.59

3.13

4.33

1.61

2.40

3.1

4.23

1.2

2.45

3.15

4.37

1.57

2.70

3.39

4.3

1.59

2.6

3.18

4.43

1.36

2.2

3.20

4.15

1.45

2.27

3.17

4.7

1.9

2.54

3.43

4.17

1.18

2.23

3.5

4.38

1.66

2.56

3.29

4.37

1.52

2.48

3.9

4.22

1.37

2.46

3.26

4.18

1.44

2.3

3.28

4.34

1.8

2.53

3.35

4.40

1.13

2.51

3.44

4.30

1.20

2.36

3.7

4.42

1.72

2.15

3.34

4.42

1.76

2.18

3.38

4.43

1.3

2.37

3.45

4.12

1.31

2.68

3.24

4.13

1.46

2.5

3.22

4.24

1.38

2.12

3.37

4.4

1.53

2.7

3.17

4.41

1.70

2.51

3.21

4.41

1.43

2.60

3.4

4.32

1.30

2.67

3.25

4.45

1.14

2.63

3.4

4.36

1.77

2.55

3.42

4.2

1.74

2.59

3.2

4.16

1.23

2.22

3.42

4.39

1.42

2.4

3.12

4.31

1.38

2.16

3.43

4.5

1.25

2.70

3.14

4.35

1.65

2.11

3.6

4.20

1.60

2.42

3.10

4.25

1.47

2.34

3.38

4.9

1.19

2.28

3.3

4.30

1.29

2.63

3.36

4.44

1.71

2.29

3.19

4.34

1.65

2.39

3.21

4.13

1.68

2.9

3.16

4.20

1.15

2.61

3.37

4.29

1.41

2.58

3.30

4.21

1.51

2.17

3.24

4.40

1.55

2.8

3.11

4.25

1.40

2.64

3.2

4.14

1.51

2.41

3.10

4.21

1.48

2.71

3.15

4.33

1.4

2.60

3.40

4.22

1.50

2.62

3.12

4.26

1.63

2.35

3.23

4.16

1.39

2.19

3.1

4.29

1.28

2.66

3.41

4.6

1.56

2.62

3.9

4.26

1.5

2.20

3.30

4.15

Задача № 1. Разработать программу с реализацией линейных списков

    1. Слияние k упорядоченных однонаправленных списков с сохранением характера упорядоченности

    2. Написать программу передвижения элемента двунаправленного списка на n позиций вперед и назад

    3. Написать программу передвижения элемента однонаправленного списка на n позиций вперед и назад

    4. Удалить n-ый элемент из двунаправленного списка

    5. Удалить n-ый элемент из однонаправленного списка

    6. Создать список содержащий элементы общие для двух двунаправленных списков

    7. Упорядочить элементы в двунаправленном списке по возрастанию

    8. Упорядочить элементы в однонаправленном списке по возрастанию

    9. Удалить каждый второй элемент двунаправленного списка

    10. Удалить каждый второй элемент однонаправленного списка

    11. Удалить каждый третий элемент двунаправленного списка

    12. Удалить каждый третий элемент однонаправленного списка

    13. Дан кольцевой список, содержащий 20 фамилий игроков футбольной команды. Разбить игроков на 2 группы по 10 человек. Во вторую группу попадает каждый 12-й человек.

    14. Проверить, являются ли элементы списка членами арифметической прогрессии. Если являются – вывести шаг прогрессии, если нет – сообщение об этом.

    15. Поменять местами i-ую и j-ую строки разреженной матрицы, реализованной посредством динамического списка.

    16. Пусть А и B – две разреженные матрицы, реализованные посредством динамических списков. Размерность матрицы В по обоим измерениям не должна превосходить размерность матрицы А. Проверить, является ли матрица В частью матрицы А и определить координаты верхнего левого угла в матрице А, откуда начинается совпадение с матрицей В. Если матрица А не содержит в себе матрицы В – вернуть пару (–1,–1).

    17. Умножить на вектор разреженную матрицу, реализованную посредством динамических списков.

    18. Поменять местами i-ую и j-ую строки нижнетреугольной матрицы.

    19. Поменять местами i-ый и j-ый столбец верхнетреугольной матрицы.

    20. Транспонировать верхнетреугольную матрицу.

    21. Даны 2 кольцевых списка, содержащие фамилии спортсменов 2-х фехтовальных команд. Произвести жеребьевку. В первой команде выбирается каждый n-й игрок, а во второй – каждый m-й.

    22. Даны 2 кольцевых списка, содержащие фамилии участников лотереи и наименования призов. Выиграет N человек (каждый К-й). Число для пересчета призов – t.

    23. Даны 2 кольцевых списка, содержащих фамилии учащихся и номера экзаменационных билетов. Число пересчета для билетов – Е, для учащихся – К. Определить номера билетов, вытащенных учащимися.

    24. Элементы однонаправленного списка – вещественные числа. Описать процедуру или функцию, которая: a) вычисляет среднее арифметическое всех элементов списка; b) удаляет из списка элементы со значением меньшим среднего арифметического.

    25. Элементы упорядоченного по убыванию списка – вещественные числа. Описать процедуру или функцию, которая: a) вычисляет среднее арифметическое всех элементов списка; b) добавляет в список элемент со значением, вычисленным в предыдущей процедуре (функции), без нарушения упорядоченности.

    26. Проверить является ли кольцевой список палиндромом.

    27. Удалить из непустого списка L один элемент после каждого вхождения заданного элемента E, если такой есть и он отличен от E. Элементы списка – записи с полями: номер паспорта, ФИО, год рождения, пол. Список реализовать посредством массива.

    28. Удалить из непустого кольцевого списка L один элемент после каждого вхождения заданного элемента E, если такой есть и он отличен от E. Считать, что последний элемент является соседом первого. Элементы списка – записи с полями: номер паспорта, ФИО, год рождения, пол. Список реализовать посредством указателей.

    29. Заменить каждый элемент списка, состоящий из символов, на предыдущий символ алфавита.

    30. Проверить является ли линейный однонаправленный список палиндромом.

    31. Определить функцию, которая возвращает первый элемент, входящий в оба списка, в противном случае – сообщение об этом.

    32. Написать программу для циклического сдвига двунаправленного списка вправо на заданное число элементов. Например: список [6, 5, 4, 3, 2, 1], циклически сдвинутый вправо на 2 элемента, преобразуется в список [2, 1, 6, 5, 4, 3].

    33. Написать программу для перевода списка арабских чисел (от 1 до 10) в список римских чисел. Например: список [1, 2, 3] преобразуется в список [“I”, “II”, “III”].

    34. Написать программу для циклического сдвига однонаправленного списка вправо на заданное число элементов. Например: список [6, 5, 4, 3, 2, 1], циклически сдвинутый вправо на 2 элемента, преобразуется в список [2, 1, 6, 5, 4, 3].

    35. Составить программу генерации списка ста случайных двухбуквенных слов из больших латинских букв (A..Z – коды 65..90). Разработать функцию расчета числа элементов списка, содержащих заданную букву. Все операции со списком реализовать подпрограммами.

    36. Создать двусвязный список, содержащий не менее двух элементов. Продублировать в списке все элементы с нечетными номерами за исключением отрицательных значений (новые элементы добавлять перед существующими элементами с такими же значениями). Операции со списком реализовать подпрограммами.

    37. В списке хранится информация о студентах: фамилия, группа, пол, оценка по математике. Удалить из списка информацию о студентах мужского пола, имеющих оценку ниже 4 баллов. Операции со списком реализовать подпрограммами.

    38. Ввести натуральное число N. Создать два упорядоченных двусвязных списка из N элементов. Построить третий список, который содержит без повторений элементы, одновременно содержащиеся в обоих списках. Операции со списком реализовать подпрограммами.

    39. После поступления в университет в линейном списке хранится информация о студентах: фамилия, что окончил (школа, лицей, колледж), какой иностранный язык изучал. Составить программу, формирующую списки студентов, окончивших лицеи, отдельно по каждому иностранному языку. Операции со списком реализовать подпрограммами.

    40. Создать кольцевой список вещественных чисел. Заменить в нем каждый элемент, начиная с начального, на его среднее арифметическое с предыдущим и последующим элементом. Операции со списком реализовать подпрограммами.

    41. Дана вещественная матрица nm. Организовать линейный список строк матрицы, упорядоченных по невозрастанию значений наибольших элементов строк. Операции со списком реализовать подпрограммами.

    42. Линейный список записей содержит шестизначные номера телефонов и информацию о сумме задолженности абонента данного телефона. Записи об одном абоненте могут повторяться. Программа должна выводить суммарную задолженность абонента по введенному номеру телефона. Операции со списком реализовать подпрограммами.

    43. Составить программу, которая подсчитывает количество элементов списка, оканчивающиеся цифрой «1», меняет местами первый и последний из таких элементы. Все операции со списком реализовать подпрограммами.

    44. При поступлении на музыкально-педагогический факультет на абитуриентов собираются сведения: фамилия, музыкальный инструмент. Для поступления необходимо сдать экзамен по специальности. Составить списки для данного экзамена в зависимости от музыкального инструмента. Все операции со списком реализовать подпрограммами.

    45. Имеются 3 списка, содержащие целые числа. Объединить эти списки в один список без повторений элементов, расположив элементы сначала 1-го списка, потом 2-го и т.д..

    46. Ввести натуральное N. Ввести N строк и занести их в двусвязный список L. Отсортировать L методом вставок, используя при сортировке только присваивания указателей (не строк). Все операции со списком реализовать подпрограммами.

    47. Пусть дан линейный список. После каждого нулевого элемента добавить предшествующую ему часть списка.

    48. Сформировать кольцевой линейный список целых чисел. Требуется переставить элементы списка так, чтобы в начале шла группа элементов, больших того элемента, который в исходном списке располагался на первом месте, затем – сам этот элемент, далее – группа элементов, меньших или равных ему.

    49. С помощью однонаправленных списков реализовать обработку многочлена от переменной х произвольной степени с целыми коэффициентами. Причем, его одночлены могут быть и не упорядочены по степеням х, а одночлены одной степени могут повторяться. Возможный пример: –8х4–74х+7х4+5–2х3. Требуется привести подобные члены в этом многочлене и упорядочить по убыванию степеней х.

    50. Создать однонаправленный список, содержащий слова предложения, введенного с клавиатуры. Затем преобразовать список, оставив в нем только слова, длина которых меньше 5.

    51. Создать односвязный список, хранящий целые числа. Переставить в обратном порядке элементы между первым и последним вхождением заданного элемента Е, если Е входит в список не менее двух раз.

    52. Составить программу, которая формирует однонаправленный список L, включив в него по одному разу элементы, которые входят в один из списков L1 и L2, но в то же время не входят в другой. Списки реализовать массивами.

    53. Составить программу, которая формирует двунаправленный список L, включив в него по одному разу элементы, которые входят в один из списков L1 и L2, но в то же время не входят в другой. Списки реализовать через указатели.

    54. Удалить из односвязного списка элементы, встречающиеся ровно два раза. Список реализовать массивами.

    55. Удалить из односвязного списка элементы, встречающиеся ровно два раза. Список реализовать через указатели.

    56. Написать программу, позволяющую ввести последовательность натуральных чисел и создать из нее двунаправленный список. Длина последовательности n. Обеспечить с помощью списка вычисление суммы и произведения вида  x1*xn + x2*xn-1 + ... + xn*x1

    57. Написать программу, позволяющую ввести последовательность натуральных чисел и создать из нее кольцевой список. Длина последовательности n. Обеспечить с помощью списка вычисление суммы и произведения вида  (x1+xn)*(x2+xn-1)* ... *(xn+x1)

    58. Реализовать логическую функцию simm (s, i, j), проверяющую, является ли симметричной часть двунаправленного списка s, начинающаяся i-м и заканчивающаяся j-м элементами. Функцию применить для списка записей с полями: номер паспорта, ФИО, год рождения, пол. Список реализовать посредством указателей.

    59. Реализовать логическую функцию simm (s, i, j), проверяющую, является ли симметричной часть линейного списка s, начинающаяся i-м и заканчивающаяся j-м элементами. Функцию применить для списка чисел. Список реализовать посредством массива.

    60. Даны две разреженные квадратные матрицы A и B порядка n. Получить матрицу C = A+B. Для представления разреженной матрицы использовать двусвязный циклический список. Каждое звено списка состоит из пяти полей: номер строки ненулевого элемента; номер столбца ненулевого элемента; значение элемента; ссылка на предыдущий ненулевой элемент в этой же строке; ссылка на предыдущий ненулевой элемент в этом же столбце. Каждая строка (и столбец) имеют заглавное звено, соответствующее ссылочное поле которого содержит ссылку на последний ненулевой элемент в строке (в столбце).

    61. Написать библиотеку функций для работы со свободными матрицами. Матрицы представлять в виде ди­намически выделяемых массивов. Предусмотреть следующие операции для работы с матрица­ми: создание/удаление матрицы, ввод/вывод, добавление/удаление столбца, добавление/удаление строки, установка/получение элемента матрицы, выделение подматрицы.

    62. Написать библиотеку функций для работы с множествами. Множества представлять в ви­де неупорядоченных двусвязных списков. Предусмотреть следующие операции для работы с множествами: создание/удаление, ввод/вывод, проверка вхождения, объединение, пересечение, разность.

    63. Написать библиотеку функций для работы с множествами. Множества представлять в ви­де упорядоченных односвязных списков. Предусмотреть следующие операции для работы с множествами: создание/удаление, ввод/вывод, проверка вхождения, объединение, пересечение, разность.

    64. Написать библиотеку функций для работы с многочленами одной переменной. Отображе­ния представлять в виде неупорядоченных массивов пар («степень», «коэффициент»). Преду­смотреть следующие операции для работы с многочленами: создание/удаление, ввод/вывод, нахождение значения, сложение, вычитание, умножение, деление.

    65. Написать библиотеку функций для работы с многочленами одной переменной. Отображе­ния представлять в виде упорядоченных по степени массивов пар («степень», «коэффици­ент»). Предусмотреть следующие операции для работы с многочленами: создание/удаление, ввод/вывод, нахождение значения, сложение, вычитание, умножение, деление.

    66. Написать библиотеку функций для работы с многочленами одной переменной. Отображе­ния представлять в виде неупорядоченных односвязных списков пар («степень», «коэффици­ент»). Предусмотреть следующие операции для работы с многочленами: создание/удаление, ввод/вывод, нахождение значения, сложение, вычитание, умножение, деление.

    67. Написать библиотеку функций для работы с многочленами одной переменной. Отображения представлять в виде упорядоченных по степени односвязных списков пар («степень», «коэффи­циент»). Предусмотреть следующие операции для работы с многочленами: создание/удаление, ввод/вывод, нахождение значения, сложение, вычитание, умножение, деление.

    68. Написать библиотеку функций для работы с многочленами одной переменной. Отображе­ния представлять в виде неупорядоченных двусвязных списков пар («степень», «коэффици­ент»). Предусмотреть следующие операции для работы с многочленами: создание/удаление, ввод/вывод, нахождение значения, сложение, вычитание, умножение, деление.

    69. Написать библиотеку функций для работы с многочленами одной переменной. Отображения представлять в виде упорядоченных по степени двусвязных списков пар («степень», «коэффи­циент»). Предусмотреть следующие операции для работы с многочленами: создание/удаление, ввод/вывод, нахождение значения, сложение, вычитание, умножение, деление.

    70. Написать библиотеку функций для работы с целыми числами сколь угодно большой дли­ны. Отображения представлять в виде односвязных списков цифр. Предусмотреть следующие операции для работы с числами: создание/удаление, ввод/вывод, сложение, вычитание, умно­жение, деление.

    71. Написать библиотеку функций для работы с целыми числами сколь угодно большой длины. Отображения представлять в виде двусвязных списков цифр. Предусмотреть следующие опера­ции для работы с числами: создание/удаление, ввод/вывод, сложение, вычитание, умножение, деление.

    72. Написать библиотеку функций для работы с множествами отрезков числовой прямой. Мно­жества представлять в виде неупорядоченных односвязных списков, который содержат края отрезков. Предусмотреть следующие операции для работы с множествами: создание/удаление, ввод/вывод, объединение, пересечение, разность.

    73. Написать библиотеку функций для работы с множествами отрезков числовой прямой. Мно­жества представлять в виде упорядоченных по первой точке односвязных списков, который содержат края отрезков. Предусмотреть следующие операции для работы с множествами: со­здание/удаление, ввод/вывод, объединение, пересечение, разность.

    74. Написать библиотеку функций для работы с множествами отрезков числовой прямой. Мно­жества представлять в виде неупорядоченных двусвязных списков, который содержат края отрезков. Предусмотреть следующие операции для работы с множествами: создание/удаление, ввод/вывод, объединение, пересечение, разность.

    75. Написать библиотеку функций для работы с множествами отрезков числовой прямой. Мно­жества представлять в виде упорядоченных по первой точке двусвязных списков, который со­держат края отрезков. Предусмотреть следующие операции для работы с множествами: созда­ние/удаление, ввод/вывод, объединение, пересечение, разность.

    76. Написать библиотеку функций для работы с текстом. Текст представлять в виде односвязного списка, который содержит отдельные строки. Предусмотреть следующие операции для работы с текстом: создание/удаление, ввод/вывод, поиск, удаление/вставка символов, удале­ние/вставка строк, конкатенация, вырезка части текста.

    77. Написать библиотеку функций для работы с текстом. Текст представлять в виде двусвязного списка, который содержит отдельные строки. Предусмотреть следующие операции для работы с текстом: создание/удаление, ввод/вывод, поиск, удаление/вставка символов, удаление/вставка строк, вставка одного текста внутрь другого, склейка/расзделение строк.

Задача № 2. Разработать программу с реализацией стека, очереди или хеш-таблицы

    1. Слияние k упорядоченных стеков с сохранением характера упорядоченности

    2. Удалить каждый третий элемент стека

    3. Удалить каждый третий элемент очереди

    4. Удалить каждый второй элемент стека

    5. Удалить каждый второй элемент очереди

    6. Удалить наименьший элемент стека

    7. Удалить наибольший элемент очереди

    8. Удалить n-ый элемент стека

    9. Удалить n-ый элемент очереди

    10. Проверить, являются ли одинаковыми два стека М1 и М2, один из которых реализован посредством массивов, другой – посредством динамических указателей.

    11. Проверить, являются ли одинаковыми две очереди М1 и М2, реализованных посредством кольцевых массивов.

    12. Проверить, являются ли одинаковыми две открытых хеш-таблицы М1 и М2 (хеш функция h(k)= k mod n, где k – элемент, n – количество строк таблицы).

    13. Проверить, являются ли одинаковыми две закрытых хеш-таблицы М1 и М2 (хеш функция h(k)= k mod n, где k – элемент, n – количество строк таблицы). Количество столбцов хеш-таблицы – 3.

    14. Проверить, являются ли элементы стека, реализованного массивом, членами арифметической прогрессии. Если являются – вывести шаг прогрессии, если нет – сообщение об этом.

    15. Проверить, являются ли элементы стека, реализованного динамическими указателями, членами арифметической прогрессии. Если являются – вывести шаг прогрессии, если нет – сообщение об этом.

    16. Создать текстовый файл, содержащий текстовую и числовую информацию. Используя стек, создать другой текстовый файл, в котором числа были бы записаны в обратном порядке.

    17. Проверить, являются ли элементы очереди, реализованной циклическим массивом, членами арифметической прогрессии. Если являются – вывести шаг прогрессии, если нет – сообщение об этом.

    18. Проверить, являются ли элементы очереди, реализованной динамическими указателями, членами арифметической прогрессии. Если являются – вывести шаг прогрессии, если нет – сообщение об этом.

    19. Пусть в очереди хранится следующая информация: наименование процесса, его приоритет, время выполнения. Упорядочить процессы очереди по возрастанию приоритета и убыванию времени выполнения.

    20. Элементы стека – вещественные числа. Описать процедуру или функцию, которая: a) вычисляет среднее арифметическое всех элементов стека; b) удаляет из стека элементы со значением меньшим среднего арифметического.

    21. Создать процедуры или функции, реализующие методы работы с хеш-таблицей: инициализация, добавление элемента, удаление элемента, поиск. Кроме того, при заполнении хеш-таблицы выше заданного уровня размер хеш-таблицы должен автоматически увеличиваться.

    22. С использованием стеков разработать программу перевода инфиксного выражения в постфиксную форму. В выражении могут применяться переменные, целые и вещественные числа, знаки арифметических операций, стандартные математические функции, скобки.

    23. С использованием стеков разработать программу перевода инфиксного выражения в префиксную форму. В выражении могут применяться переменные, целые и вещественные числа, знаки арифметических операций, стандартные математические функции, скобки.

    24. Удалить элементы очереди В, повторяющиеся в очереди А несколько раз.

    25. Заменить каждый элемент стека, состоящий из символов, на следующий символ алфавита.

    26. Удалить из стека L один элемент после каждого вхождения заданного элемента E, если такой есть и он отличен от E. Элементы стека – записи с полями: номер паспорта, ФИО, год рождения, пол. Стек реализовать посредством массива.

    27. Удалить из стека L один элемент после каждого вхождения заданного элемента E, если такой есть и он отличен от E. Элементы стека – записи с полями: номер паспорта, ФИО, год рождения, пол. Стек реализовать посредством динамических указателей.

    28. Удалить из стека элементы со значением, попадающим в заданный диапазон.

    29. Определить функцию, которая возвращает первый элемент, входящий в оба стека, в противном случае – сообщение об этом.

    30. Написать программу для циклического сдвига очереди вправо на заданное число элементов. Например: очередь [6, 5, 4, 3, 2, 1], циклически сдвинутая вправо на 2 элемента, преобразуется в очередь [2, 1, 6, 5, 4, 3].

    31. Даны три стека, наполненные натуральными числами и четвертый стек пустой. В четвертый стек поместить три числа, являющиеся максимальными числами в первом, втором и третьем стеке. В четвертом стеке числа расположить в порядке неубывания, а в первых трех стеках порядок расположения оставшихся чисел оставить прежним.

    32. Реализовать логическую функцию simm (s, i, j), проверяющую, является ли симметричной часть дека s, начинающаяся i-м и заканчивающаяся j-м элементами. Функцию применить для дека записей с полями: номер паспорта, ФИО, год рождения, пол.

    33. Реализовать логическую функцию simm (s, i, j), удаляющую из очереди с приоритетами s элементы с приоритетами, начинающающимися i-м и заканчивающиеся j-м значениями. Функцию применить для очереди, хранящей следующую информацию: номер паспорта, ФИО, год рождения, пол. Приоритет расчитывается по следующему правилу: если возраст более 60 лет и пол – женский, то приоритет наивысший; для мужчин в возрасте менее 50 лет наименьший; для всех остальных – (возраст) mod 41.

    34. Даны три открытых хеш-таблицы (хеш функция h(k)= k mod n, где k – элемент, n – количество строк таблицы), наполненные натуральными числами. В четвертую таблицу поместить для каждого сегмента числа, являющиеся максимальными числами в нем.

    35. Даны три закрытых хеш-таблицы (хеш функция h(k)= k mod n, где k – элемент, n – количество сегментов), наполненные натуральными числами. В четвертую таблицу поместить для каждого сегмента числа, являющиеся максимальными числами в ней. Учесть при этом возможные коллизии в исходных таблицах.

    36. Преобразовать хеш-таблицу в бинарное дерево (хеш функция h(k)= k mod n, где k – элемент, n – количество строк таблицы).

    37. Преобразовать бинарное дерево в хеш-таблицу (хеш функция h(k)= k mod n, где k – элемент, n – количество строк таблицы).

    38. Реализовать в виде программы заданный набор операций (принадлежность, объединение, разность, пересечение) с использованием управляющей структуры данных – хеш-таблицы (хеш функция h(k)= k mod n, где k – элемент, n – количество строк таблицы).

    39. Найти максимальный элемент числового множества с использованием управляющей структуры данных – хеш-таблицы (хеш-функция методом умножения (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.233)).

    40. Напишите программу, удаляющую из стека его медиану. Медианой  стека из N элементов называется элемент, значение которого меньше (или равно) половины N элементов и больше (или равно) другой половины. Например, медиана стека 16 22 99 95 18 87 10 есть 18.

    41. Дана последовательность символов, оканчивающаяся точкой. Используя двунаправленный список, переставить в обратном порядке все символы между первым и последним вхождениями заданного символа.

    42. Элементы упорядоченного по убыванию стека – вещественные числа. Описать процедуру или функцию, которая: a) вычисляет среднее арифметическое всех элементов стека; b) добавляет в стек элемент со значением, вычисленным в предыдущей процедуре (функции), без нарушения упорядоченности.

    43. Типизированный файл хранит каталог книг в библиотеке. Составить программу, формирующую структуру данных стек для книг А.С.Пушкина, хранящихся в библиотеке, по возрастанию года издания. Операции со стеком реализовать подпрограммами.

    44. Написать библиотеку функций для работы с целыми числами сколь угодно большой дли­ны. Отображения представлять в виде односвязных стеков цифр. Предусмотреть следующие операции для работы с числами: создание/удаление, ввод/вывод, сложение, вычитание, умно­жение, деление.

    45. Написать библиотеку функций для работы с целыми числами сколь угодно большой дли­ны. Отображения представлять в виде деков цифр. Предусмотреть следующие операции для работы с числами: создание/удаление, ввод/вывод, сложение, вычитание, умно­жение, деление.

    46. Написать библиотеку функций для работы с целыми числами сколь угодно большой дли­ны. Отображения представлять в виде очередей цифр. Предусмотреть следующие операции для работы с числами: создание/удаление, ввод/вывод, сложение, вычитание, умно­жение, деление.

    47. Написать программу, позволяющую ввести последовательность натуральных чисел и создать из нее дек. Длина последовательности n. Обеспечить вычисление суммы и произведения вида  x1*xn + x2*xn-1 + ... + xn*x1

    48. Написать программу, позволяющую ввести последовательность натуральных чисел и создать из нее очередь. Длина последовательности n. Обеспечить вычисление суммы и произведения вида  (x1+xn)*(x2+xn-1)* ... *(xn+x1)

    49. Используя структуру данных «Очередь» реализовать телефонную книгу. Составить программу, формирующую отдельные очереди абонентов, чьи телефонные номера начинаются с одинаковых двух цифр. Операции с очередью реализовать подпрограммами.

    50. Реализовать очередь с приоритетами. Каждый новый элемент попадает в очередь с неким приоритетом. Если его приритет выше всех уже имевшихся элементов очереди, он попадает сразу в начало очереди. Если в очереди есть элементы с таким же приоритетом, как у него, он помещается сразу за последним из имевшихся с тем же приоритетом.

    51. Составить программу генерации очереди ста случайных двухбуквенных слов из малых латинских букв (a..z – коды 97..122). Разработать процедурe обмена местами заданного (номером) и первого элементов очереди. Все операции с очередью реализовать подпрограммами.

    52. Разработать программу, которая объединяет содержимое двух числовых стеков по следующему правилу: из первого стека берутся только элементы, стоящие на четных местах, и помещаются на позицию с номером на единицу больше; из второго стека берутся только отрицательные элементы и помещаются на позиции с нечетными номерами. Если в первом стеке не окажется необходимого количества элементов, то в результирующий стек записать в оставшиеся позиции «1», если во втором – то «2». Все операции со стеком реализовать подпрограммами.

    53. Имеются 3 закрытых хеш-таблицы, содержащие целые числа. Используется хеш-функция i mod 8, где i – число. Объединить эти хеш-таблицы в одну без повторений элементов, расположив элементы сначала 1-й таблицы, потом 2-й и т.д..

    54. Имеются 3 открытых хеш-таблицы, содержащие целые числа. Используется хеш-функция i mod 8, где i – число. Объединить эти хеш-таблицы в одну без повторений элементов, расположив элементы сначала 1-й таблицы, потом 2-й и т.д..

    55. Дан файл целых чисел. Создать стек, содержащий длины всех серий исходного файла. Серией называется набор последовательно расположенных одинаковых элементов, длиной серии – количество этих элементов. Например, для исходного файла с элементами 1, 5, 5, 5, 4, 4, 5 содержимое стека должно быть следующим: 1, 3, 2, 1.

    56. В стеке хранится информация о станках: наименование станка, время простоя в месяц, время работы в месяц. Составить программу, определяющую общее время простоя на заводе, и удаляющую из стека информацию о станках, не имеющих простоя.

    57. Создать список А целых чисел. Занести в очередь В порядковые номера отрицательных элементов списка А, а затем удалить из нее минимальный элемент. Операции со списком и очередью реализовать подпрограммами.

    58. Дан текстовый файл, содержащий даты в формате «день/месяц/год», причем под день и месяц отводится по две позиции, а под год – четыре (например, «16/04/2001»). Сформировать очередь, содержащую весенние даты, упорядоченные только по месяцу и числу.

    59. Создать стек из целых чисел. Преобразовать стек, оставив в нем из группы подряд идущих одинаковых элементов только один.

    60. Создать два стека S1 и S2 из целых чисел. Сформировать стек S, включив в него по одному разу элементы, которые входят в стек S1, но не входят в стек S2.

    61. Дан текстовый файл. Подсчитать число появлений в нем каждой строчной (то есть маленькой) русской буквы и создать очередь, элементы которой имеют вид «<буква>–<число ее появлений>» (например, «а–25»). Буквы, отсутствующие в тексте, в очередь не включать.

    62. Создать стек, хранящий целые числа. Переставить в обратном порядке элементы между первым и последним вхождением заданного элемента Е, если Е входит в стек не менее двух раз.

    63. Удалить из стека элементы, лежащие в заданном диапазоне, посчитать их среднее арифметическое. Все операции со стеком реализовать подпрограммами.

    64. Удалить из очереди элементы, лежащие в заданном диапазоне, посчитать их среднее арифметическое. Все операции с очередью реализовать подпрограммами.

    65. Используя стек, преобразовать десятичное вещественное число в систему счисления с заданным основанием.

    66. В файле WORK содержатся результаты работы цеха за день. Элемент файла включает: шифр изделия (8-символьный код), наименование изделия, количество (штук). Построить открытую хеш-таблицу, содержащую результаты работы за день, считая ключом шифр изделия. Элемент таблицы имеет ту же структуру, что и элемент файла. Содержащаяся в файле информация с равными ключами должна быть помещена в таблицу один раз с общим количеством штук изделия.

    67. В файле WORK содержатся результаты работы цеха за день. Элемент файла включает: шифр изделия (8-символьный код), наименование изделия, количество (штук). Построить закрытую хеш-таблицу (7 сегментов, 4 столбца), содержащую результаты работы за день, считая ключом шифр изделия. Элемент таблицы имеет ту же структуру, что и элемент файла. Содержащаяся в файле информация с равными ключами должна быть помещена в таблицу один раз с общим количеством штук изделия.

    68. В спортивных соревнованиях участвуют n команд. В файле SPORT содержатся прогнозы результатов соревнований. Каждый прогноз включает номер команды, занявшей первое место, номер команды, занявшей последнее место, номера команд, входящих в первую тройку сильнейших команд. Построить открытую хеш-таблицу, содержащую проценты голосов, отданных командам-претендентам на первое место, командам-претендентам на последнее место и проценты голосов, отданных командам-претендентам на первую тройку.

    69. В спортивных соревнованиях участвуют n команд. В файле SPORT содержатся прогнозы результатов соревнований. Каждый прогноз включает номер команды, занявшей первое место, номер команды, занявшей последнее место, номера команд, входящих в первую тройку сильнейших команд. Построить закрытую хеш-таблицу (5 сегментов, 3 столбца), содержащую проценты голосов, отданных командам-претендентам на первое место, командам-претендентам на последнее место и проценты голосов, отданных командам-претендентам на первую тройку.

    70. Написать библиотеку функций для работы с множествами отрезков числовой прямой. Мно­жества представлять в виде упорядоченных по первой точке стеков, который со­держат края отрезков. Предусмотреть следующие операции для работы с множествами: созда­ние/удаление, ввод/вывод, объединение, пересечение, разность.

    71. Написать библиотеку функций для работы с множествами отрезков числовой прямой. Мно­жества представлять в виде упорядоченных по первой точке деков, который со­держат края отрезков. Предусмотреть следующие операции для работы с множествами: созда­ние/удаление, ввод/вывод, объединение, пересечение, разность.

Задача № 3. Разработать программу с реализацией дерева указанного вида

3.1. Реализовать в виде программы заданный набор операций (поиск, объединение, разность, пересечение) с использованием управляющей структуры данных – двоичного дерева (дерева двоичного поиска).

3.2. Реализовать в виде программы заданный набор операций (поиск, объединение, разность, пересечение) с использованием управляющей структуры данных – АВЛ-дерева.

3.3. Реализовать в виде программы заданный набор операций (поиск, объединение, разность, пересечение) с использованием управляющей структуры данных – 2-3-дерева.

3.4. Обход бинарного дерева по уровням: сначала корень, затем все вершины на уровень ниже и т.д.

3.5. Реализовать в виде программы заданный набор операций (поиск, объединение, разность, пересечение) с использованием управляющей структуры данных – красно-черное дерево.

3.6. Реализовать в виде программы заданный набор операций (поиск, объединение, разность, пересечение) с использованием управляющей структуры данных – B-дерево порядка k=3.

3.7. Построить дерево по математическому выражению для проверки его правильности. В выражении могут применяться переменные, целые и вещественные числа, знаки арифметических операций, стандартные математические функции, скобки.

3.8. Вывести бинарное дерево в виде строки так, что если A – отец, а B, C – сыновья, то строка имеет вид ((B)(A)(C)).

3.9. Написать библиотеку функций для работы с множествами отрезков числовой прямой. Мно­жества представлять в виде упорядоченных по первой точке бинарных деревьев поиска, кото­рый содержат края отрезков. Предусмотреть следующие операции для работы с множествами: создание/удаление, ввод/вывод, объединение, пересечение, разность.

3.9. Вершины бинарного дерева – вещественные числа. Описать процедуру или функцию, которая: a) вычисляет среднее арифметическое всех вершин дерева; b) добавляет в дерево вершину со значением, вычисленным в предыдущей процедуре (функции).

3.10. Вершины 2-3–дерева – вещественные числа. Описать процедуру или функцию, которая: a) вычисляет среднее арифметическое всех вершин дерева; b) добавляет в дерево вершину со значением, вычисленным в предыдущей процедуре (функции).

3.11. Вершины 2-3–дерева – вещественные числа. Описать процедуру или функцию, которая: a) вычисляет среднее арифметическое всех вершин дерева; b) удаляет из дерева вершины со значением меньшим среднего арифметического.

3.12. Вершины АВЛ–дерева – вещественные числа. Описать процедуру или функцию, которая: a) вычисляет среднее арифметическое всех вершин дерева; b) удаляет из дерева вершины со значением меньшим среднего арифметического.

3.13. Вершины АВЛ–дерева – вещественные числа. Описать процедуру или функцию, которая: a) вычисляет среднее арифметическое всех вершин дерева; b) добавляет в дерево вершину со значением, вычисленным в предыдущей процедуре (функции).

3.14. Записи вершин АВЛ–дерева – вещественные числа. Описать процедуру, которая удаляет все вершины со значением в указанном диапазоне.

3.15. Записи вершин 2-3–дерева – вещественные числа. Описать процедуру, которая удаляет все вершины со значением в указанном диапазоне.

3.16. Записи вершин бинарного дерева – вещественные числа. Описать процедуру, которая удаляет все вершины с отрицательными записями.

3.17. Записи вершин бинарного дерева – вещественные числа. Описать процедуру или функцию, которая: a) находит максимальное или минимальное значение записей вершин непустого дерева; b) печатает записи из всех листьев дерева.

3.18. Записи вершин АВЛ–дерева – вещественные числа. Описать процедуру, которая печатает записи вершин из всех листьев дерева.

3.19. Описать процедуру ЕQUAL(T1,T2), проверяющую на равенство АВЛ–деревья Т1 и Т2 (деревья равны, если ключи и записи вершин одного дерева равны соответственно ключам и записям другого дерева).

3.20. Описать процедуру ЕQUAL(T1,T2), проверяющую на равенство 2-3–деревья Т1 и Т2 (деревья равны, если ключи и записи вершин одного дерева равны соответственно ключам и записям другого дерева).

3.21. Описать процедуру ЕQUAL(T1,T2), проверяющую на равенство бинарные деревья Т1 и Т2 (деревья равны, если ключи и записи вершин одного дерева равны соответственно ключам и записям другого дерева).

3.22. Описать процедуру, удаляет все листья АВЛ–дерева, попадающие в заданный диапазон значений.

3.23. Описать процедуру, которая удаляет все листья 2-3–дерева, попадающие в заданный диапазон значений.

3.24. Описать процедуру, которая удаляет все листья бинарного дерева, попадающие в заданный диапазон значений.

3.25. Реализовать в виде программы заданный набор операций (принадлежность, поиск, объединение, разность, пересечение) с использованием управляющей структуры данных – B-дерево порядка k=4.

3.26. Определить функцию для проверки упорядоченности бинарного дерева.

3.27. Организовать бинарное дерево для вычисления биномиальных коэффицииентов, используя треугольник Паскаля:

Программа должна для заданного номера уровня n вывести значения всех коэффициентов.

3.28. Подсчитать число узлов на k-ом уровне бинарного дерева. Корень считать узлом 1-го уровня.

3.29. Построить Trie-дерево. Подсчитать количество слов, начинающихся с заданной последовательности символов.

3.30. Дан текстовый файл, состоящий из слов, разделенных пробелами. Построить Trie-дерево, которое содержит перевернутые слова из файла. Найти все слова, имеющие заданное окончание.

3.31. Построить Trie-дерево. Подсчитать количество слов, содержащих заданную букву.

3.32. Построить Trie-дерево. Подсчитать количество слов, содержащих заданное количество согласных букв.

3.33. Построить Trie-дерево. Вывести все формы данного слова, содержащиеся в дереве. Формой слова считается некоторое другое слово, отличающееся от заданного не более чем на n последних символов. n вводит пользователь.

3.34. Построить Trie-дерево. Удалить из него все слова, которые содержат указанную подстроку.

3.35. Для заданного Trie-дерева построить Trie-дерево, в котором все слова расположены в обратном порядке.

3.36. Из Trie-дерева удалить все слова четной длины.

3.37. Посчитать в Trie-дереве количество слов, оканчивающихся на согласную букву.

3.38. Выполнить операцию объединения двух АВЛ-деревьев. Под объединением понимается дерево, содержащее вершины обоих деревьев дерева (без дублирования).

3.39. Выполнить операцию объединения двух 2–3-деревьев. Под объединением понимается дерево, содержащее вершины обоих деревьев дерева (без дублирования).

3.40. Выполнить операцию пересечения двух АВЛ-деревьев. Под пересечением понимается дерево, содержащее вершины первого дерева, входящие и во второе.

3.41. Выполнить операцию пересечения двух 2–3-деревьев. Под пересечением понимается дерево, содержащее вершины первого дерева, входящие и во второе.

3.42. Выполнить операцию разности двух АВЛ-деревьев. Под разностью понимается дерево, содержащее вершины первого дерева, не входящие во второе.

3.43. Напишите программу, которая вводит арифметическое выражение, состоящее из констант и арифметических операций, стандартных математических функций и строит для него бинарное дерево. Осуществив прохождение дерева, выдайте префиксную, инфиксную и постфиксную формы выражения.

3.44. Придумайте строку из 30 символови и закодируйте ее с помощью алгоритма Хаффмана.

3.45. Написать библиотеку функций для работы с множествами. Множества представлять в виде бинарных деревьев поиска. Предусмотреть следующие операции для работы с множествами: создание/удаление, ввод/вывод, проверка вхождения, объединение, пересечение, разность, ге­нерация множества подмножеств.

Задача № 4. Разработать программу, реализующую указанный алгоритм сортировки или поиска в одномерном массиве или файле. Графы

4.1. Алгоритм лексикографической сортировки последовательности цепочек одинаковой длины

4.2. Алгоритм лексикографической сортировки последовательности цепочек различной длины

4.3. Сортировка деревом

4.4. Поиск медианы массива

4.5. Поиск k-статистики массива

4.6. Сортировка Шелла

4.7. Параллельная сортировка Бэтчера

4.8. Внешняя сортировка прямым слиянием

4.9. Внешняя сортировка естественным слиянием

4.10. Внешняя сортировка сбалансированным трехпутевым слиянием

4.11. В ООН имеется полный перечень всех стран, который включает в себя: название, континент, столицу, площадь, численность населения, государственный строй. Вывести названия и столицы государств в порядке убывания плотности населения. Применить многопутевое двухфазное естественное сбалансированное слиянеие.

4.12. Алгоритм Рабина-Карпа поиска подстроки в строке (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.761)

4.13. Алгоритм Кнута-Морриса-Пратта поиска подстроки в строке (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.771)

4.14. Алгоритм Бойера-Мура поиска подстроки в строке (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.777)

4.15. Слияние k упорядоченных массивов

4.16. Модификация алгоритма быстрой сортировки на основе разбиения с помощью медианы трех элементов (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.171)

4.17. Алгоритм сортировки подсчетом (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.175)

4.18. Алгоритм цифровой сортировки (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.177)

4.19. Алгоритм сортировки вычерпыванием (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.180)

4.20. Алгоритм поиска Randomized-Select (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.188)

4.21. Алгоритм поиска наибольшей общей подпоследовательности (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.318)

4.22. В ООН имеется полный перечень всех стран, который включает в себя: название, континент, столицу, площадь, численность населения, государственный строй. Упорядочить по названиям столиц сведения о государствах с площадью меньше заданной. Применить трехфазную внешнюю сортировку.

4.23. Алгоритм сортировки подсчетом (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.224, файл djvu)

4.24. Алгоритм поразрядной сортировки (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.226, файл djvu)

4.25. Алгоритм карманнной сортировки (книга Т.Кормена, Ч.Лейзера. Алгоритмы. Построение и анализ. Стр.230, файл djvu)

4.26. Алгоритм сортировки посредством вставок и слияния (книга Д.Кнут. Искусство Программирование. Том 3. Сортировка и Поиск. Стр.204, файл djvu)

4.27. Алгоритм сортировки бинарным слиянием Хана-Линя (книга Д.Кнут. Искусство Программирование. Том 3. Сортировка и Поиск. Стр.221, файл djvu)

4.28. Алгоритм многофазного слияния (книга Д.Кнут. Искусство Программирование. Том 3. Сортировка и Поиск. Стр.287, файл djvu)

4.29. Сортировка методом многофазного слияния с использованием «горизонтального» распределения (книга Д.Кнут. Искусство Программирование. Том 3. Сортировка и Поиск. Стр.287, файл djvu)

4.30. Сортировка методом каскадного слияния со специальным распределением (книга Д.Кнут. Искусство Программирование. Том 3. Сортировка и Поиск. Стр.312, файл djvu)

4.31. Написать функцию sort(x), упорядочивающую по неубыванию двоичные числа массива х методом поразрядной сортировки: все числа упорядочить по цифре в самом старшем разряде. Массив просматривается от начала (ищется число с 1 в заданном разряде) и конца (ищется число с 0 в заданном разряде) к середине и выбирается пара чисел для обмена. В результате массив разбивается на две части с 0 и 1 в старших разрядах, к каждой из которых применяется сортировка по цифре в разряде правее (при равенстве этих цифр сохранять упорядоченность по цифре в старшем разряде); и так далее до самого младшего разряда. В основе алгоритма поразрядной сортировки лежит абстрактная операция извлечения цифры в заданном разряде.

4.32. Дано n чисел. Упорядочить их по неубыванию методом фон Неймана: упорядочить пары соседних чисел (А1 и А2, А3 и А4 и т.д.); взять по две соседние упорядоченные пары и слить их в упорядоченные четверки; затем каждые две соседние четверки слить в упорядоченные восьмерки и т.д.

4.33. Написать программу поразрядной сортировки двузначных десятичных чисел с использованием очередей. Очереди представляют собой бункеры для хранения чисел (всего 10 бункеров). При сортировке выполняются два прохода по последовательности чисел для обработки сначала по позициям единиц, а затем десятков. В первом проходе числа из исходного массива распределяются в бункеры по позициям единиц. Затем выбираются из бункеров в порядке от 0 до 9 снова в массив. Во втором проходе числа из массива распределяются в бункеры по позициям десятков. После второго выбора из бункеров последовательность становится упорядоченной.

4.34. Выполнить обход в ширину неориентрованного графа, начиная с заданной вершины. Способ представления графа – матрица смежности.

4.35. Выполнить обход в ширину неориентрованного графа, начиная с заданной вершины. Способ представления графа – матрица инциденций.

4.36. Выполнить обход в ширину ориентрованного графа, начиная с заданной вершины. Способ представления графа – список смежности.

4.37. Выполнить обход в глубину ориентрованного графа, начиная с заданной вершины. Способ представления графа – матрица смежности.

4.38. Выполнить обход в глубину ориентрованного графа, начиная с заданной вершины. Способ представления графа – матрица инциденций.

4.39. Выполнить обход в глубину неориентрованного графа, начиная с заданной вершины. Способ представления графа – список смежности.

4.40. Написать библиотеку функций для работы с ориентированными графами. Графы представ­лять в виде матрицы смежности. Предусмотреть следующие операции для работы с графами: создание/удаление графа, ввод/вывод, добавление/удаление ребра, добавление/удаление вер­шины, объединение/разбиение графа.

4.41. Написать библиотеку функций для работы с неориентированными графами. Графы пред­ставлять в виде матрицы смежности. Предусмотреть следующие операции для работы с гра­фами: создание/удаление графа, ввод/вывод, добавление/удаление ребра, добавление/удаление вершины, объединение/разбиение графа.

4.42. Написать библиотеку функций для работы с ориентированными графами. Графы представ­лять в виде матрицы инцидентности. Предусмотреть следующие операции для работы с гра­фами: создание/удаление графа, ввод/вывод, добавление/удаление ребра, добавление/удаление вершины, объединение/разбиение графа.

4.43. Написать библиотеку функций для работы с неориентированными графами. Графы пред­ставлять в виде матрицы инцидентности. Предусмотреть следующие операции для работы с графами: создание/удаление графа, ввод/вывод, добавление/удаление ребра, добавление/удаление вершины, объединение/разбиение графа.

4.44. Написать библиотеку функций для работы с ориентированными графами. Графы представ­лять в виде динамического списка связности. Предусмотреть следующие операции для работы с гра­фами: создание/удаление графа, ввод/вывод, добавление/удаление ребра, добавление/удаление вершины, объединение/разбиение графа.

4.45. Написать библиотеку функций для работы с неориентированными графами. Графы представ­лять в виде динамического списка связности. Предусмотреть следующие операции для работы с гра­фами: создание/удаление графа, ввод/вывод, добавление/удаление ребра, добавление/удаление вершины, объединение/разбиение графа.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
Помощь Обратная связь Вопросы и предложения Пользовательское соглашение Политика конфиденциальности