Программная инженерия Нижний Новгород 017 Лабораторный

5. Критерии оценивания выполнения лабораторной работы 
Лабораторная работа считается сданной при выполнении минимального набора 
требований: 

---

 
104 

Реализованы просматриваемая, упорядоченная, хеш-таблица (с одним способом 
разрешения коллизий), таблицы на основе деревьев поиска. Эффективность поиска 
в лучшем, худшем и среднем случаях соответствует теоретическим оценкам. 

Для рассматриваемой прикладной задачи реализованы 4-5 операций для обработки 
результатов экзаменационной сессии и 2-3 графические формы вывода. 
В более полном варианте выполнения лабораторной работы реализованы два варианта 
разрешения коллизий в хеш-таблице, реализован класс таблиц на основе сбалансированного 
дерева.
6. Вопросы и задания для самоконтроля 

Приведите примеры прикладных задач, при решении которых могут быть 
использованы таблицы. 

Какие дополнительные операции могут быть полезны при обработке результатов 
экзаменационной сессии? 

Для разных способов организации таблиц приведите примеры задач, в которых эти 
способы являются наиболее эффективными? 

Какова трудоемкость алгоритма сортировки вставками, алгоритма сортировки 
слиянием, метода быстрой сортировки? 

В чем различие сбалансированных и идеально сбалансированных деревьев поиска? 

Почему при реализации таблиц не используются идеально сбалансированные 
деревья поиска? 

Какие рекомендации следует учитывать при выборе хэш-функций? 

Какие существуют методы разрешения коллизий? Укажите их сильные и слабые 
стороны. 
Литература 
1. Топп У., Форд У. Структуры данных в С++. - М. Бином, 1999 
2. Мейн М., Савитч У. Структуры данных и другие объекты в С++. - М.: Издательский дом 
“Вильямс”, 2003 
3. Скиена С.С. Алгоритмы. Руководство по разработке. – СПб.: БХВ-Петербург, 2013 
4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.- МЦМО, 1999 
5. Вирт Н. Алгоритмы+структуры данных=программы. – М.: Мир, 1985. 
6. Себеста Р. У. Основные концепции языков программирования. - М.: Издательский дом 
“Вильямс”, 2001. 
7. Танненбаум Э. Современные операционные системы. - СПб.: Питер, 2002.