Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Порядок выполнения работы. 1. Ознакомится с общими методическими указаниями и с описаниями данной работы






    1. Ознакомится с общими методическими указаниями и с описаниями данной работы. Ознакомиться по литературе с основными понятиями обработки ИМ, алгоритмами поиска и требованиями к ним.

    2. Изучить блок-схему, реализующую бинарный поиск в ИМ (Приложение 6).

    3. Каждому студенту взять из таблицы (лабораторная работа № 5) массив из n ключей {K1, K2, …, Kn} и набор значений аргумента поиска Z.

    4. Из данного массива ключей {K1, K2, …, Kn} получить массив {К1’, К2’, …, Кj’} путем исключения дублирующих значений ключей.

    5. Записать элементы массива {К1’, К2’, …, Кj’} в порядке возрастания их значений. Провести поиск в полученном массиве вручную, используя лишь одно (любое) из данных значений аргумента поиска (см. пример).

    6. Провести сортировку массива {К1’, К2’, …, Кj’} любым из ранее изученных методов.

    7. Провести поиск в отсортированном массиве на ЭВМ, задавая по очереди все данные значения аргумента поиска.

    8. Построить бинарное дерево поиска в отсортированном массиве для всех значений аргумента поиска. Оценить число сравнений при поиске.

    Содержание отчета.

    1. Краткое изложение целей и задач лабораторной работы, задачи поиска в ИМ и рассматриваемого метода поиска.

    2. Схема алгоритма бинарного поиска.

    3. Массив {К1’, К2’, …, Кj’} и результаты поиска вручную.

    4. Результаты сортировки и поиска в отсортированном массиве на ЭВМ (распечатка с комментариями).

    5. Бинарное дерево поиска в отсортированном массиве для всех значений аргумента поиска. Оценка числа сравнений при поиске.

    6. Сравнительный анализ методов последовательного и бинарного поиска.

    Контрольные вопросы.

    1. Что такое отношение упорядочения?

    2. Что такое бинарное дерево?

    3. Что такое оптимальное бинарное дерево?

    4. Как определяется высота дерева?

    5. Каково возможное минимальное и максимальное число сравнений при удачном поиске? Как оценить среднее число сравнений?

    6. Почему при бинарном поиске в исходном массиве не допускается одинаковые значения ключей?

    7. В чем заключается разница между первичным и вторичным ключами? Для каких целей используется каждый из них? Приведите примеры их использования.

    Литература.

    1. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. Т.3: Пер. с англ. – М.: Мир, 1978. – 843с.

    2. Флорес И. Структуры и управление данными: Пер. с англ. – М.: Статистика, 1982. – 317с.

    3. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов: Пер. с англ. – М.: Мир, 1981. – 366с.

     

     

    Содержание

    1. Основные понятия сортировки и поиска........................................................................................ 3

    1.1. Сортировка....................................................................................................................................... 3

    1.2. Поиск................................................................................................................................................ 9

    2. Методические указания к выполнению лабораторных работ..................................................... 11

    2.1. Лабораторная работа № 1.............................................................................................................. 11

    2.2. Лабораторная работа № 2.............................................................................................................. 15

    2.3. Лабораторная работа № 3.............................................................................................................. 17

    2.4. Лабораторная работа № 4.............................................................................................................. 20

    2.5. Лабораторная работа № 5.............................................................................................................. 27

    2.6. Лабораторная работа № 6.............................................................................................................. 30

    3. Литература......................................................................................................................................... 33

    Приложение 1. Сортировка методом “пузырька”............................................................................. 35

    Приложение 2. Сортировка методом подсчета................................................................................. 36

    Приложение 3. Сортировка методом вставок................................................................................... 37

    Приложение 4. Сортировка методом Шелла..................................................................................... 38

    Приложение 5. Бинарный поиск........................................................................................................ 39

    Приложение 6. Последовательный поиск......................................................................................... 40

     







    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.