Ответы на вопросы по языкам программирования. Вопросы к экзамену. Инф Вопросы для подготовки к экзамену (3 курс) Метод нисходящего проектирования программы
 Скачать 0.64 Mb.
|
empty[править]boolean empty(): return head == tail push[править]function push(x : T): if (size() != n) elements[tail] = x tail = (tail + 1) % n pop[править]T pop(): if (empty()) return null x = elements[head] head = (head + 1) % n return x size[править]int size() if head > tail return n - head + tail else return tail - head Из-за того что нам не нужно снова выделять память, каждая операция выполняется за O(1)O(1) времени. Плюсы: проста в разработке, по сравнению с реализацией на списке есть незначительная экономия памяти. Минусы: количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива), при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив. Древовидная структура представления данных. Древовидная структура, древовидная диаграмма или древовидная модель-это способ представления иерархической природы структуры в графической форме. Он называется "древовидной структурой", потому что классическое представление напоминает дерево, хотя диаграмма, как правило, перевернута вверх ногами по сравнению с биологическим деревом, с "стволом" вверху и "листьями" внизу. Древовидная структура является концептуальной и проявляется в нескольких формах. Для обсуждения древовидных структур в конкретных областях см. Дерево (структура данных) для информатики; в той мере, в какой это относится к теории графов, см. Дерево (теория графов) или дерево (теория множеств). Другие соответствующие статьи перечислены ниже. Элементы дерева называются "узлами". Линии, соединяющие элементы, называются "ветвями". Узлы без дочерних элементов называются конечными узлами, "конечными узлами" или "листьями". Каждая конечная древовидная структура имеет элемент, который не имеет превосходства. Этот элемент называется "корневым" или корневым узлом. Корень-это начальный узел. Но обратное неверно: бесконечные древовидные структуры могут иметь или не иметь корневого узла. Названия связей между узлами моделируют терминологию родства семейных отношений. Гендерно нейтральные имена "родитель" и "ребенок" в значительной степени вытеснили более старую терминологию "отец" и "сын". Термин "дядя" по-прежнему широко используется для других узлов на том же уровне, что и родительский, хотя иногда его заменяют гендерно нейтральными терминами, такими как "оммер"[1]. "Родитель" узла-это узел на одну ступень выше в иерархии (т. е. ближе к корневому узлу) и расположенный на той же ветви. Узлы "Брат" ("брат" или "сестра") совместно используют один и тот же родительский узел. "Дяди" узла (иногда "оммеры") являются братьями и сестрами родителя этого узла. Узел, подключенный ко всем узлам более низкого уровня, называется "предком". Подключенные узлы нижнего уровня являются "потомками" узла-предка. В приведенном примере "энциклопедия" является родителем "науки" и "культуры", ее детей. "Искусство" и "ремесло" - это братья и сестры и дети "культуры", которая является их родителем и, следовательно, одним из их предков. Кроме того, "энциклопедия", как корень дерева, является прародителем "науки", "культуры", "искусства" и "ремесла". Наконец, "наука", "искусство" и "ремесло", как листья, не являются предками ни одного другого узла. Древовидная структура может изобразить всех видов таксономических знаний, таких как семейные деревья, биологическое эволюционное дерево, на дерево эволюции языковой семьи, на грамматическую структуру языка (ключ пример с → НП ВП, смысл в предложении словосочетания и фразы команды, каждая, в свою очередь, наличие других компонентов, другие компоненты), как веб-страницы являются логически упорядоченные на веб-сайте, математические деревьев целыми наборами, и так далее. Оксфордский словарь английского языка фиксирует использование терминов "древовидная структура" и "древовидная диаграмма" с 1965 года в Аспектах теории синтаксиса Ноама Хомского[2]. В древовидной структуре существует один и только один путь из любой точки в любую другую точку. Информатика широко использует древовидные структуры (см. Дерево (структура данных) и телекоммуникации). Формальное определение см. в разделе Теория множеств, а обобщение, в котором дочерние элементы не обязательно являются преемниками, см. в разделе Порядок префиксов. Алгоритмы построения и просмотра деревьев. |