ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Рекомендации к выполнению работы.

Функция main() может содержать цикл, например, с постусловием, внутри которого может происходить опрос клавиатуры и выполнение вставки в очередь (стек) или извлечение, в зависимости от нажатой клавиши.

Контрольные вопросы.

1. Что представляет собой очередь?

2. Что представляет собой стек?

3. Какие известны виды очередей?

4. На основе каких структур данных могут организовываться стеки?

5. Какие операции допустимы для очередей?

6. Какие операции допустимы для стеков?

7. Какой характер имеет операция удаления для очередей и стеков?

8. Какими свойствами обладают очереди?

9. Каким недостатком обладает простая очередь? Каков способ борьбы с этим недостатком?

10. Чем отличается циклическая очередь от простой?

11. Чем отличается стек на основе массива от стека на основе связного списка?

12. Чем отличается приоритетная очередь от простой?

13. Чем отличается стек на основе связного списка от собственно связного списка?

14. К каким структурам данных относятся очереди и стеки?

15. Что такое уровни представления структур данных?

16. Пояснить различие между логическим и физическим уровнями представления структур данных на примере очередей или стеков.

17. Каковы области применения очередей и стеков?

18. Что представляет собой дек?

Лабораторная работа №5

Связные списки

Подготовка к работе. По указанной литературе и конспекту лекций повторить тему «Связные списки».

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

Задание.

1. Для организации односвязного списка определить структурный тип, содержащий указатель на свой тип и поля, использованные в работе №2.

2. Определить функции вставки нового звена в односвязный линейный список, удаления звена из списка, просмотра содержимого списка.

3. В функции main() создать заглавное звено списка и проверить работу функций вставки, удаления и просмотра. В функции просмотра предусмотреть вывод адресов каждого звена списка. Сделать выводы.

4. Преобразовать односвязный список в двусвязный. Внести соответствующие изменения в функции работы со списком. Проверить работу функций.

5. Преобразовать линейный список в кольцевой. Внести необходимые изменения в функции работы со списком. Проверить работу функций. Сделать выводы.

Сохранить файл с тестом программы для последующих работ.

Рекомендации к выполнению работы.

Функция main() может содержать цикл, похожий на тот, который использован в работе №4. В этом случае вызов функций вставки, удаления и просмотра списка будет выполняться аналогично вызову соответствующих функций для очереди или стека.

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

Контрольные вопросы.

1. Что представляют собой списки?

2. К каким классификационным группам структур данных относятся списки?

3. Какие существуют разновидности списков?

4. В чем состоит отличие несвязного списка от массива?

5. В чем состоит отличие связного списка от массива?

6. В чем состоит отличие линейного списка от кольцевого?

7. В чем заключаются недостатки односвязного списка?

8. В чем состоит отличие односвязного списка от двусвязного?

9. Какие операции применяются для связных списков?

10. В чем отличие считывания информации из списка от считывания из очереди или стека?

11. Особенности операций вставки и удаления для связных списков.

12. В чем отличие операции вставки в двусвязный список от вставки в односвязный список?

13. В чем отличие операции удаления из двусвязного списка от удаления из односвязного списка?

14. В чем заключаются особенности работы с кольцевыми списками?

15. Что означает понятие «динамическая структура данных»?

16. Какой тип должно иметь звено связного списка? Почему?

17. Что обязательно должно содержать звено связного списка?

18. В чем состоит отличие звена двусвязного списка от звена односвязного списка?

19. В чем состоит отличие связного списка от стека, организованного в виде связного списка?

Лабораторная работа №6

Сортировка массивов

Подготовка к работе. По указанной литературе и конспекту лекций повторить тему «Сортировка».

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

Задание.

1. Определить массив, элементы которого будут упорядочиваться. Тип массива выбрать по таблице №1 – массив №1.

2. Разработать функцию сортировки массива методами, выбранными по таблице 3 в соответствии с вариантом.

Таблица 3

№	Алгоритмы сортировки	№	Алгоритмы сортировки
	1). Пузырьковая; 2). Быстрая.		1). Быстрая; 2). Отбором.
	1). Отбором; 2). Шелла.		1). Шелла; 2). Вставками.
	1). Вставками; 2). Быстрая.		1). Пузырьковая; 2). Отбором.
	1). Пузырьковая; 2). Шелла.		1). Быстрая; 2). Пузырьковая.
	1). Отбором; 2). Быстрая.		1). Шелла; 2). Отбором.
	1). Вставками; 2). Шелла.		1). Вставками; 2). Пузырьковая.
	1). Отбором; 2). Пузырьковая.		1). Быстрая; 2). Вставками.
	1). Пузырьковая; 2). Вставками.		1). Шелла; 2). Пузырьковая.

3. Любым способом заполнить элементы массива значениями.

4. Выполнить сортировку массива первым алгоритмом и проконтролировать ее результат. Проверить все варианты исходного заполнения массива: случайным образом, отсортированного в обратном порядке, отсортированного в требуемом порядке. Убедиться в правильности сортировки во всех случаях. Сделать выводы.

5. Повторить пункты 3 и 4 для второго алгоритма сортировки.

Сохранить файл с тестом программы для последующих работ.

Контрольные вопросы.

1. Что такое «сортировка»?

2. Сколько существует групп алгоритмов сортировки?

3. Сколько существует алгоритмов сортировки?

4. По каким признакам характеризуются алгоритмы сортировки?

5. Что нужно учитывать при выборе алгоритма сортировки?

6. Какой алгоритм сортировки считается самым простым?

7. Какой алгоритм сортировки считается самым эффективным?

8. Что означает понятие «скорость сортировки»?

9. В чем заключается метод пузырьковой сортировки?

10. В чем заключается метод сортировки отбором?

11. В чем заключается метод сортировки вставками?

12. В чем заключается метод сортировки разделением?

13. В чем заключается метод быстрой сортировки?

14. В чем заключается метод сортировки Шелла?

15. В чем заключается метод сортировки Бэтчера?

16. Как зависит скорость сортировки от размера структуры данных для разных алгоритмов?

17. Почему метод Бэтчера называется параллельным?

Лабораторная работа №7

Сортировка списков

Подготовка к работе. По указанной литературе и конспекту лекций повторить тему «Сортировка», «Списки».

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

Задание.

1. Разработать функции сортировки списков методами, выбранными по таблице 4 в соответствии с вариантом.

Таблица 4

№	Алгоритмы сортировки	№	Алгоритмы сортировки
	Линейный односвязный список, содержащий целые числа. 1). Отбором с процедурами вставки и удаления; 2). Вставками.		Кольцевой двусвязный список, содержащий символы. 1). Пузырьковая с заменой указателей; 2). Отбором с процедурами вставки и удаления.
	Кольцевой односвязный список, содержащий символы. 1). Вставками; 2). Отбором с заменой указателей.		Кольцевой односвязный список, содержащий данные типа float. 1). Пузырьковая с заменой указателей; 2). Вставками.
	Линейный односвязный список, содержащий данные типа float. 1). Пузырьковая с процедурами вставки и удаления; 2). Отбором с заменой указателей.		Кольцевой двусвязный список, содержащий целые числа. 1). Отбором с процедурами вставки и удаления; 2). Пузырьковая с переносом данных.
	Линейный двусвязный список, содержащий целые числа. 1). Вставками; 2). Пузырьковая с переносом данных.		Линейный односвязный список, содержащий данные типа double. 1). Пузырьковая c процедурами вставки и удаления; 2). Отбором c процедурами вставки и удаления.
	Линейный двусвязный список, содержащий символы. 1). Вставками; 2). Пузырьковая с заменой указателей.		Линейный двусвязный список, содержащий данные типа double. 1). Вставками; 2). Пузырьковая c процедурами вставки и удаления.
	Линейный односвязный список, содержащий символы. 1). Отбором с заменой указателей; 2). Пузырьковая с переносом данных.		Кольцевой односвязный список, содержащий данные типа double. 1). Отбором с заменой указателей; 2). Вставками.
	Кольцевой односвязный список, содержащий целые числа. 1). Пузырьковая с переносом данных; 2). Вставками.		Кольцевой двусвязный список, содержащий данные типа double. 1). Вставками; 2). Пузырьковая с заменой указателей.
	Линейный двусвязный список, содержащий данные типа float. 1). Отбором с заменой указателей; 2). Пузырьковая с заменой указателей.		Кольцевой двусвязный список, содержащий данные типа float. 1). Вставками; 2). Отбором с заменой указателей.

2. Ввести информацию в элементы списка.

3. Выполнить сортировку списка первым алгоритмом и проконтролировать ее результат. Проверить все варианты исходного заполнения списка: случайным образом, отсортированного в обратном порядке, отсортированного в требуемом порядке. Убедиться в правильности сортировки во всех случаях. Сделать выводы.

4. Повторить пункты 2 и 3 для второго алгоритма сортировки. Для ввода данных в существующие элементы списка может потребоваться соответствующая функция (редактирования элемента). Ее необходимо разработать самостоятельно.

Сохранить файл с тестом программы для последующих работ.

Контрольные вопросы.

1. Что такое «сортировка»?

2. Сколько существует алгоритмов сортировки?

3. Сколько существует групп алгоритмов сортировки?

4. Чем сортировка списка отличается от сортировки массива?

5. Что нужно учитывать при выборе алгоритма сортировки?

6. По каким признакам характеризуются алгоритмы сортировки?

7. Какой алгоритм сортировки считается самым эффективным?

8. Какой алгоритм сортировки считается самым простым?

9. В чем заключается метод сортировки вставками?

10. В чем заключается метод сортировки отбором?

11. В чем заключается метод пузырьковой сортировки?

12. В чем заключается пузырьковая сортировка списка с использованием процедур вставки в список и удаления?

13. В чем заключается пузырьковая сортировка списка с переносом данных между звеньями?

14. В чем заключается пузырьковая сортировка списка с заменой значений указателей?

15. В чем заключается сортировка списка отбором с использованием процедур вставки в список и удаления?

16. В чем заключается сортировка списка отбором с заменой значений указателей?

17. В чем заключается метод сортировки списка вставками?

18. Что означают термины «внешняя сортировка» и «внутренняя сортировка»?

Лабораторная работа №8