Контрольная Информатика (структурные алгоритмы и обработка данных ), вариант 23, лабораторные работы, номер: 200103

"СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ
Лабораторная работа № 1
Анализ сложности алгоритмов

Содержание
1. Цель работы 3
2. Вариант задания 3
3. Программа 3
4. Расчет теоретических пространственной и временной сложностей алгоритма 4
5. Выводы 5
Список литературы 6

2. Вариант задания
Используя память, пропорциональную n, хранить массив целых чисел A, содержащий n элементов.
Элементы массива A могут принимать случайные значения от ((n div 2) - 1) до (n div 2).
Разработать алгоритм, который осуществляет заполнение массива A, и по выбору пользователя выполняет одну из двух функций:
? все значения элементов кратные 10 уменьшить на один порядок, теоретическая временная сложность O(n);
? подсчитать количество элементов с отрицательными значениями, теоретическая временная сложность O(1).

Список литературы

1. Матьяш В.А., Фомин А.В., Щекин С.В. Структуры и алгоритмы обработки данных. Методические указания к выполнению лабораторных работ – СПб, ГУАП, 2003. – 44 с.
2. Ключарев А.А., Матьяш В.А., Щекин С.В. Структуры и алгоритмы обработки данных. Учебное пособие. – СПб.: ГУАП, 2003. – 172 с., ил.
3. Bjarne Stroustrup. The C+ + Programming Language/Third Edition – New Jersey: AT&T Labs Murray Hill , 1997. – 912 pp.


СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ
Лабораторная работа № 4
Хеширование данных

Содержание
1. Цель работы 3
2. Вариант задания 3
3. Описание хеш-функции 3
4. Результаты анализа хеш-функции 4
5. Программа 7
6. Выводы 11
Список литературы 13


2. Вариант задания
Составить хеш-функцию со следующими характеристиками:
? формат ключа цAAAAц
? количество сегментов 3000
? метод хеширования Квадратичное опробование
и проанализировать ее. При необходимости доработать хеш-функцию. Используя полученную хеш-функцию разработать на языке программирования высокого уровня программу, которая должна выполнять следующие функции:
создавать хеш-таблицу;
добавлять элементы в хеш-таблицу;
просматривать хеш-таблицу;
искать элементы в хеш-таблице;
удалять элементы из хеш-таблицы.


Список литературы

1. Матьяш В.А., Фомин А.В., Щекин С.В. Структуры и алгоритмы обработки данных. Методические указания к выполнению лабораторных работ – СПб, ГУАП, 2003. – 44 с.
2. Ключарев А.А., Матьяш В.А., Щекин С.В. Структуры и алгоритмы обработки данных. Учебное пособие. – СПб.: ГУАП, 2003. – 172 с., ил.
3. Bjarne Stroustrup. The C+ + Programming Language/Third Edition – New Jersey: AT&T Labs Murray Hill , 1997. – 912 pp.


СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ
Лабораторная работа № 6
Деревья поиска

Содержание
1. Цель работы 3
2. Вариант задания 3
3. Программа 3
4. Выводы 10
Список литературы 11

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

Список литературы

1. Матьяш В.А., Фомин А.В., Щекин С.В. Структуры и алгоритмы обработки данных. Методические указания к выполнению лабораторных работ – СПб, ГУАП, 2003. – 44 с.
2. Ключарев А.А., Матьяш В.А., Щекин С.В. Структуры и алгоритмы обработки данных. Учебное пособие. – СПб.: ГУАП, 2003. – 172 с., ил.
3. Bjarne Stroustrup. The C+ + Programming Language/Third Edition – New Jersey: AT&T Labs Murray Hill , 1997. – 912 pp.
"