САОД, семестр 1

Темы выносимые на зачет в 1 семестре:

Абстрактный тип данных

1.1. Типы, структуры данных и АТД

1.2. Время выполнения программы

1.3. Асимптотическое соотношение

1.4. О - символика

1.5. О и W - обозначения

1.6. Ограниченность показателя функции роста

1.7. Анализ программы на псевдоязыке

Абстрактный тип данных в списках

2.1. Реализация АТД. Линейный список

2.2. Сравнение последовательного и связанного распределения

Структура данных на основе линейных списков

3.1. Стек, очередь, дек

3.2. Реализация стека, дека и очереди на основе ЛСС (Линейного связанного списка)

3.3. Реализация Дека

Не линейная структура данных

4.1. АТД дерево

4.2. Порядок узлов

4.3. Прямой, обратный и симметричный обход

4.4. Помеченные деревья или деревья выражений

4.5. Префиксные коды. Код Хаффмана.

Сортировки

5.1. Классификация алгоритма сортировки

5.2. Постановка, задача сортировки

5.3. Методы сортировок

5.4. Типы сортировок

5.5. Критерии оценки сортировок

5.6. Простые схемы сортировок

5.7. Простая вставка

5.8. Алгоритм Шелла

5.9. Быстрая сортировка Хоару

5.10. Оценка эффективности быстрой сортировки

5.11. Пирамидальная сортировка. Выбор из дерева

5.12. Сортировка подсчетом

5.13. Распределяющий подсчет

Класс сортировок слиянием

6.1. ЕДС - единственное двухпутевое слияние

6.2. ФДС - фиксированное двухпутевое слияние

7. Хеширование: открытое и закрытое. Оценка эффективности и трудоемкости. Коллизии и методы их разрешения при закрытом хешировании.