Лекция 32. Решение задач на динамические структуры данных

Упражнения

Вопросы

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

1. С чем связана популярность использования деревьев в программировании?

2. Можно ли список отнести к деревьям? Ответ обоснуйте.

3. Какие данные содержат адресные поля элемента бинарного дерева?

4. Может ли бинарное дерево быть строгим и неполным? Ответ обоснуйте.

5. Может ли бинарное дерево быть нестрогим и полным? Ответ обоснуйте.

6. Каким может быть почти сбалансированное бинарное дерево: полным, неполным, строгим, нестрогим? Ответ обоснуйте.

7. Куда может быть добавлен элемент в бинарное дерево в зависимости от его вида (полное, неполное, строгое, нестрогое)? Вид дерева при этом должен сохраниться.

8. Куда может быть добавлен элемент в сбалансированное бинарное дерево? Вид дерева при этом должен сохраниться.

9. Чем отличаются, с точки зрения реализации алгоритма, прямой, симметричный и обратный обходы бинарного дерева?

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

2. Найдите количество четных элементов бинарного дерева. Укажите эти элементы и их уровни.

3. Найдите сумму элементов сбалансированного дерева, находящихся на уровне k.

4. Оператор мобильной связи организовал базу данных абонентов, содержащую сведения о телефонах, их владельцах и используемых тарифах, в виде бинарного дерева. Составьте программу, которая:

· обеспечивает начальное формирование базы данных в виде бинарного дерева;

· производит вывод всей базы данных;

· производит поиск владельца по номеру телефона;

· выводит наиболее востребованный тариф (по наибольшему числу абонентов).

Литература

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

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

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

4. Топп Уильям, Форд Уильям. Структуры данных в С++. Пер. с англ. - М.: БИНОМ, 2000. – 816 с.

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

Краткая аннотация лекции.

В лекции рассматриваются определения, способы объявления, инициализация и особенности использования при решении задач циклических списков, деков, красно-черных деревьев, приводятся примеры решения задач на обработку кольцевых списков, деков, красно-черных деревьев.

Цель лекции: изучить алгоритмы и приемы работы с динамическими структурами данных, научиться решать задачи с использованием динамических структур данных и алгоритмов работы с ними на языке C++.

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