Опорный конспект лекций

Упражнения

Вопросы

Набор для практики

1. Чем обусловлено использование алгоритмов внешних сортировок?

2. Как расходуется ОЗУ при использовании различных алгоритмов внешних сортировок?

3. Каким слиянием, простым или естественным, эффективнее объединять два упорядоченных по общему ключу файла? Ответ обоснуйте.

4. Какие еще факторы, кроме числа фаз и путей, следует учитывать при анализе эффективности алгоритмов внешних сортировок?

5. Как определить, какому алгоритму внешних сортировок отдать предпочтение при решении задачи?

1. На основании приведенной в лекции функции реализуйте программу, в которой выполняется алгоритм внешней сортировки двухпутевым двухфазным простым слиянием.

2. На основании приведенной в лекции функции реализуйте программу, в которой выполняется алгоритм внешней сортировки двухпутевым двухфазным естественным слиянием.

3. Дан полный перечень всех стран, который включает в себя: название, континент, столицу, площадь, численность населения. Указать сведения о государствах заданного континента в порядке возрастания численности населения. Использовать двухпутевое однофазное простое слияние.

4. Даны сведения о химических веществах, которые включает в себя: класс вещества, название вещества, молекулярная масса вещества. Упорядочить по возрастанию молекулярных масс все вещества указанного класса. Использовать двухпутевое двухфазное естественное сбалансированное слияние.

5. В файле хранится последовательность русских слов. Упорядочить ее в алфавитном порядке. Использовать внешнюю сортировку. Учесть, что порядок кодов букв русского алфавита не соответствует порядку букв в алфавите.

Литература

1. Ахо А., Хопкрофт Дж., Ульман Д. Структуры данных и алгоритмы. Уч. пособие. — М.: Вильямс, 2000. – 384с.

2. Кнут Д.Э. Искусство программирования. Том 3. Сортировка и поиск, 3-е изд.: Пер. с англ.: Уч. пос. – М.: Вильямс, 2000. – 832 с.

3. Кормен Т., Леверсон Ч.., Ртвест Р. Алгоритмы. Построение и анализ. — М.: МЦНМО, 1999. – 960 с.

4. Подбельский, В.В. Программирование на языке Си: учеб. пособие / В.В. Подбельский, С.С. Фомин. – М.: Финансы и статистика, 2004. – 600 с.

5. Подбельский, В.В. Язык Си++: учеб. пособие / В.В. Подбельский. – М.: Финансы и статистика, 2005. – 560 с.

6. Сэджвик Р. Фундаментальные алгоритмы на С++. Части 1-4. Анализ, структуры данных, сортировка, поиск. — М.: Диасофт, 2001. – 687 с.

7. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учебное пособие. - М.: Финансы и статистика, 2004. – 464 с.

Лекция № 1.

Лекция № 2.

=

Дата добавления: 2014-01-04