|
Читайте также: |
1. Создание коллекции «Вектор» выполняется в соответствии с технологией реализации коллекций, изложенной в разделе 1. Для АТД «Вектор» разрабатываются формат АТД и шаблонный класс – контейнер.
2. Для тестирования разработанного класса – контейнера разрабатываются две программы: программа тестирования отдельных операций через меню, и программа тестирования эффективности алгоритмов сортировки.
3. При реализации сортировок рекомендуется использовать алгоритмы, приведённые в приложении 2.
4. Тестирование отдельных операций через меню выполняется на коллекциях небольшого размера (до 20 элементов). Размер коллекции и тип данных хранящихся в ней, задаётся с клавиатуры перед началом тестирования. До и после выполнения операций сортировки необходимо вывести на экран содержимое коллекции.
5. Перед тестированием трудоёмкости сортировок задаются тип и размер коллекции, вид набора данных (упорядоченный или случайный). Размер коллекции может задаваться в пределах от 10 до 100 000 элементов. Полученная трудоёмкость (количество операций сравнения и операций обменов, выполненных в процессе сортировки) выводится на экран. При тестировании алгоритмов сортировки исследуются варианты худшего и среднего случаев работы алгоритмов. Сравнительное тестирование эффективности алгоритмов проводится на базе сортировки одного и того же набора данных.
Контрольные вопросы и упражнения.
1. Что понимается под средним и худшим случаем работы алгоритма? Приведите примеры.
2. Дайте краткую характеристику алгоритмов сортировки, имеющих трудоёмкость O(n 2 ).
3. Дайте краткую характеристику алгоритмов сортировки, c трудоёмкостью O(n log 2 n).
4. Какие методы выбора опорного элемента используются в алгоритме быстрой сортировки?
5. Постройте дерево выбора, размещенное в массиве, для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
6. Постройте пирамиду, размещенную в массиве, для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
7. Приведите схему сортировки Шелла для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
8. Приведите схему пирамидальной сортировки для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
9. Приведите схему быстрой сортировки для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
10. Приведите схему нисходящей сортировки слиянием для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
11. Приведите схему восходящей сортировки слиянием для значений в массиве: 5 23 2 6 8 2 78 1 9 12.
12. Приведите схему десятичной MSD-сортировки для значений в массиве: 3285 0023 1459 6346 8453 2000 1578 0341 0009 1245.
13. Приведите схему десятичной LSD-сортировки для значений в массиве: 3285 0023 1459 6346 8453 2000 1578 0341 0009 1245.
3. Лабораторная работа «Коллекция данных - список».
Цели работы: Освоение технологии реализации позиционных, линейных коллекций на примере АТД «Список». Освоение методики тестирования трудоёмкости реализации коллекций.
Список представляет позиционно–ориентированную, линейную последовательность с доступом к элементам по номеру позиции или по значению. Элемент списка хранит значение объекта, включённого в список. Номера элементов в списке задаются в линейном порядке, начиная со значения 0 или 1. У списка есть первый и последний элементы. У всех остальных элементов есть единственный предшествующий элемент (предшественник) и последующий элемент (преемник). Список имеет начало (голову), фиксирующую первый элемент, и конец (хвост), фиксирующий последний элемент.
Над списком и его элементами можно выполнять вставку, удаление, изменение значений элементов в произвольных позициях, поиск заданных значений, последовательный обход элементов списка.
Элементы списка вместе с операциями над ними образуют абстрактный тип данных.
Дата добавления: 2015-11-04; просмотров: 77 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Задание к лабораторной работе | | | Структуры списков |