Страницу Назад
Поискать другие аналоги этой работы
400 Лабораторные работы №1-5 по дисциплине "Структуры и алгоритмы обработки данных". Вариант №07.ID: 175287Дата закачки: 27 Ноября 2016 Продавец: teacher-sib (Напишите, если есть вопросы) Посмотреть другие работы этого продавца Тип работы: Работа Лабораторная Сдано в учебном заведении: ДО СИБГУТИ Описание: Лабораторная работа №1 1. Разработать процедуры сортировки массива целых чисел методом прямого выбора, методом пузырьковой сортировки и методом шейкерной сортировки (язык программирования Паскаль или Си). 2. Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве. 3. Во время сортировки предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками. 4. Составить таблицу следующего вида (данные получить экспериментально) для n= 100, 200, 300, 400, 500. (n – количество элементов в массиве) Метод N количество элементов в массиве С для упорядоченного массива М для упорядоченного массива С для случайного массива М для случайного массива Время сортировки при N=5000 Прямой выбор 100 4950 297 4950 297 0.000000…. 200 19900 597 19900 597 300 44850 897 44850 897 400 7980 1197 7980 1197 500 124750 1497 124750 1497 Пузырьковая 100 4950 0 4950 7143 1.540000… 200 19900 0 19900 29127 300 44850 0 44850 64989 400 79800 0 79800 119892 500 124750 0 124750 185673 Шейкерная 100 99 0 3501 7601 1.270000… 200 199 0 13409 29346 300 299 0 31991 70440 400 399 0 51258 112353 500 499 0 83356 187617 5. Проанализировать полученные результаты. Какой из методов самый быстрый? Самый медленный? Как сложность зависит от начальной отсортированности? Лабораторная работа №2 1. Разработать процедуры сортировки массива целых чисел методом Шелла, методом пирамидальной сортировки и методом Хоара (язык программирования Паскаль или Си). 2. Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве. 3. Во время сортировки предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками. 4. Составить таблицу следующего вида (данные получить экспериментально) для n= 100, 200, 300, 400, 500. (n – количество элементов в массиве) Метод N количество элементов в массиве С для упорядоченного массива М для упорядоченного массива С для случайного массива М для случайного массива Метод Шелла 100 629 1211 649 1231 200 1994 3174 2096 3276 300 4402 6182 4572 6352 400 8790 11168 8288 10666 500 12493 15471 13321 16299 Пирамидальная сортировка 100 1434 1073 1473 1086 200 3501 2362 3489 2358 300 5712 3699 5775 3720 400 8139 5108 8193 5126 500 10623 6536 10485 6490 Метод Хоара 100 1460 1213 1202 898 200 2453 1899 2299 1992 300 3220 2534 3026 2146 400 5557 5110 5465 4923 500 6412 5317 6894 6278 5. Проанализировать полученные результаты. Какой из методов самый быстрый? Самый медленный? Как сложность зависит от начальной отсортированности? Сравните трудоемкости методов быстрой сортировки и трудоемкости методов с квадратичной трудоемкости (использовать результаты лабораторной работы №1) Лабораторная работа №3 Порядок выполнения работы: 1. Разработать процедуры сортировки последовательности целых чисел методом прямого слияния и методом цифровой сортировки (язык программирования Паскаль или Си). 2. Во время сортировки предусмотреть подсчет количества пересылок элементов в очередь и сравнений (М и С), сравнить их с теоретическими оценками. 3. Составить таблицу следующего вида (данные получить экспериментально) для n= 100, 200, 300, 400, 500. (n – количество элементов в массиве) Метод N количество элементов в массиве С для упорядоченного массива М для упорядоченного массива С для случайного массива М для случайного массива Слияние 100 667 767 723 823 200 1532 1732 1647 1847 300 2472 2772 2646 2946 400 3460 3860 3693 4093 500 4486 4986 4777 5277 Цифровая сортировка 100 2970 372 2970 372 200 5684 558 5684 558 300 9108 530 9108 730 400 11484 930 11484 930 500 15147 1104 15147 1104 4. Проанализировать полученные результаты. (Какой из методов самый быстрый? Самый медленный? Как сложность зависит от начальной отсортированности?) Лабораторная работа №4 Написать программу «Телефонный справочник», которая обрабатывает данные об абонентах телефонной станции. Каждый абонент имеет имя, адрес, телефонный номер. В программе описать массив абонентов (назовем его справочник). В справочнике должно быть не менее 20 элементов, которые заполняются либо программно, либо считываются из файла. С помощью индексов и фильтров выбрать абонентов, которые имеют имя и адрес в заданном диапазоне. Результаты работы программы: 1. Пункты главного меню. 2. Вывод базы данных на экран: 3. Ввод верхней и нижней границ поиска: 4. Результаты поиска по имени: 5. Результаты поиска по адресу Лабораторная работа №5 1. Построить хэш-таблицу методом линейных проб для слов заданного текста. Текст находится в некотором файле (примерно 200 слов). Экспериментально определить минимально необходимый объем хэш-таблицы и число коллизий при построении. 2. Построить хэш-таблицу методом квадратичных проб для слов заданного текста. Файл с текстом должен быть тот же, что и п.1. Экспериментально определить минимально необходимый объем хэш-таблицы и число коллизий при построении. 3. Заполнить следующую таблицу полученными данными. Проанализировать результаты. (Какой метод требует большего объема памяти? Для какого из методов меньшее число коллизий?) Комментарии: Лабораторные работы выполнены в Pascal Уважаемый слушатель, дистанционного обучения, Оценена Ваша работа по предмету: "Структуры и алгоритмы обработки данных" Вид работы: Лабораторная работа 5 Оценка: Зачет Дата оценки: 21.11.2016 Рецензия:Уважаемый С* Размер файла: 71,7 Кбайт Фаил: 
(.rar)
------------------- Обратите внимание, что преподаватели часто переставляют варианты и меняют исходные данные! Если вы хотите, чтобы работа точно соответствовала, смотрите исходные данные. Если их нет, обратитесь к продавцу или к нам в тех. поддержку. Имейте ввиду, что согласно гарантии возврата средств, мы не возвращаем деньги если вариант окажется не тот. -------------------
Коментариев: 0 |
||||
Есть вопросы? Посмотри часто задаваемые вопросы и ответы на них. Опять не то? Мы можем помочь сделать! |
||||
Вход в аккаунт:
Страницу Назад
Cодержание / Структуры и алгоритмы обработки данных / Лабораторные работы №1-5 по дисциплине "Структуры и алгоритмы обработки данных". Вариант №07.