Структуры данных: стеки, очереди, списки, деревья: ЕГЭ по информатике

Структуры данных (стеки, очереди, списки, деревья) — это способы организации и хранения данных, определяющие порядок доступа к элементам. На ЕГЭ по информатике проверяется понимание принципов работы этих структур, умение анализировать алгоритмы с их использованием, а также применять их для решения…

Что нужно знать

Стек работает по принципу LIFO (последний пришёл — первый вышел): добавление и удаление элементов происходят с одного конца (вершины).
Очередь работает по принципу FIFO (первый пришёл — первый вышел): добавление в конец, удаление из начала.
Список — последовательность элементов, где каждый элемент содержит ссылку на следующий (односвязный) или на следующий и предыдущий (двусвязный); доступ к элементам последовательный.
Дерево — иерархическая структура, состоящая из узлов, связанных рёбрами; имеет корень, листья, родительские и дочерние узлы. Бинарное дерево — каждый узел имеет не более двух потомков.
Основные операции: для стека — push (добавить), pop (удалить), top (просмотреть); для очереди — enqueue (добавить), dequeue (удалить); для списка — вставка, удаление, поиск; для дерева — обходы (preorder, inorder…
Стек применяется для проверки сбалансированности скобок, вычисления постфиксных выражений, реализации рекурсии.

Термины и понятия

Стек: структура данных, работающая по принципу LIFO (Last In — First Out), где добавление и удаление элементов выполняются с одного конца…
Очередь: структура данных, работающая по принципу FIFO (First In — First Out), где элементы добавляются в конец, а удаляются из начала.
Список: структура данных, представляющая собой последовательность узлов, каждый из которых содержит данные и ссылку на следующий (и/или…
Дерево: иерархическая структура данных, состоящая из узлов, связанных рёбрами, с одним корневым узлом и не имеющая циклов.
Бинарное дерево: дерево, в котором каждый узел имеет не более двух дочерних узлов (левый и правый потомки).
Обход дерева: процесс посещения всех узлов дерева в определённом порядке (прямой/preorder, симметричный/inorder, обратный/postorder).
Push: операция добавления элемента в стек.
Pop: операция извлечения элемента из стека.

Частые ошибки

Путают принципы работы стека (LIFO) и очереди (FIFO), особенно при анализе последовательности операций.
Ошибаются при определении вершины стека после нескольких операций push/pop, забывая, что доступен только последний добавленный элемент.
Неправильно интерпретируют обходы дерева: путают прямой (preorder), симметричный (inorder) и обратный (postorder) обходы.
При работе со списками забывают, что доступ к элементу по индексу требует последовательного прохода, и путают с массивами.

Как пройти тему

В курсе «Информатика» тема «Структуры данных: стеки, очереди, списки, деревья» занимает 1 занятие по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Начать бесплатно Открыть курс

Другие темы раздела

← Предыдущая тема: Жадные алгоритмы. Перебор с возвратом
Следующая тема: Графы. Алгоритмы обхода графа (BFS, DFS)

Все темы: ЕГЭ по информатике