Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Способы обхода бинарного дерева: нисходящий, восходящий, смешанный. ⇐ ПредыдущаяСтр 3 из 3
Нисходящий – от корневой вершины вниз к листьям. Восходящий – от листьев вверх к корню. Смешанный – от самого левого листа дерева через корень к самому правому листу. Поиск минимальной длины ветви дерева.(?) Сбалансированные деревья. Показатель сбалансированности. AVL-деревья. Дерево, для каждого узла которого высота 2-х его поддеревьев различается не более чем на 1. Узлы: левоперевешивающие(самый длинный путь по левому поддереву на 1 больше чем по правому), правоперевешивающие, сбалансированные. Виды балансировки деревьев. Балансировка через массив. Операции балансировки: однократный правый(RR), однократный левый(LL), двукратный лево-правый(LR), двукратный право-левый(RL) повороты узлов. Красно-черные деревья. Каждый узел дерева окрашен либо в красный, либо в черный, причем: каждый нулевой узел – черный, корневой – черный, у красного дети черные, всякий путь от корня к произвольной вершине имеет одинаковое кол-во черных узлов. Приложения деревьев. Дерево Хаффмана. Бинарная куча. Проверка основного свойства кучи. Массив, обладающий определенными свойствами упорядоченности. По массиву строится дерево причем для всех i родитель >= потомкам. Проверка основного свойства кучи осуществляется с помощью процедуры heapify(проверяет, если дети >родителя –меняет местами). Бинарная куча. Определение родительской и дочерних вершин. Для каждого элемента массива можно определить левую и правую вершины, кроме листьев, и наоборот, для всех, кроме корня можно определить родителя. Бинарная куча. Алгоритм построения кучи из произвольного массива. buildheap(последовательно вызывает heapify для всех элементов, в порядке убывания номера). Бинарная куча. Извлечение наибольшего элемента. Оценка сложности Extractmax(извлекает максимальный элемент не нарушая основного св-ва). Бинарная куча. Добавление элемента. insertheap – добавляет новый элемент не нарушая основного свойства. Обзор куч: левосторонние, биномиальные, фибоначевы, тонкие и др. Оценка сложности(?) Биномиальная - это набор биномиальных деревьев, узлам которых приписаны элементы взвешенного множества в соответствии с кучеобразным порядком, при котором вес элемента, приписанного узлу, не превосходит весов элементов, приписанных его потомкам.
Название рассматриваемых куч связано с использованием чисел Фибоначчи при анализе трудоемкости выполнения операций. Хэш-таблицы. Понятие, назначение и принцип организации. Сочетание массивов и списков, структура для хранения и получения динамических данных. Работа с одним большим множеством сводится к работе с массивом небольших множеств. Алгоритмы вычисления хэш-функции. Преобразовывает ключи в адреса таблицы. 40. Хэш-таблицы. Прямая адресация в хэш-таблицах. Необходимо построить для каждого адреса таблицы H связный список элементов, ключи которых отображаются на этот адрес. Хэш-таблицы. Коллизии. Построение цепочек. Ситуация когда для различных ключей, получается одно и то же хеш-значение. Разрешается с помощью цепочек. Элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список. 42. Хэш-таблицы. Открытая адресация в хэш-таблицах. Способы вычисления последовательности испробованных мест при открытой адресации (линейный, квадратичный). Хеш-списков нет, все записи хранятся в самой хеш-таблице, каждая ячейка хранит либо значение динамического множества, либо NULL. Хэш-таблицы. Основные свойства и эффективность. Основной параметр, от которого зависит время выполнения – коэффициент заполнения(число хранимых эл-тов/размер массива). Задача поиска подстрок, простейший алгоритм.(?) Задача поиска подстрок. Алгоритм Хорспула. Алгоритм Карпа-Рабина.(?) Задача поиска подстрок. Алгоритм Бойера-Мура. Алгоритм Кнута-Морриса-Пратта(?)
|
|||||
Последнее изменение этой страницы: 2017-02-07; просмотров: 161; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.17.28.48 (0.006 с.) |