Задания итогового теста:
Тема: Динамическое выделение памяти, списки, стеки, очереди, обратная польская запись.
- Автоматическое, статическое, динамическое выделение памяти (С++). Примитивные и объектные типы (Java). Динамические массивы. Связные списки: одно/двунаправленные, линейные/циклические. (Язык С++/Java)
Примерные вопросы:
Запишите необходимые объявления (типов и переменных) для создания в программе на языке C++/Java одно/двунаправленного списка …
Нарисуйте схему линейного/циклического одно/двунаправленного списка, содержащего следующие числа …
Приведите пример описания автоматической (локальной) переменной / описания, выделения, и освобождения динамически-выделяемой памяти.
Запишите оператор создания динамического массива …
- Стеки/очереди, АТД.
Упрощение выражений использующих АТД Стек, Очередь.
Например, top(pop(push(push(newstack,20),3))) -> top(push(newstack,20)) -> 20.
Свойства стеков, очередей. Например, в стек помещены числа 10, 9, 3, 5, 4, 2, 1. Какой максимальной длины можно извлечь из стека некоторую возрастающую последовательность чисел (имеется в виду последовательность извлеченных из стека чисел).
Небольшая программа, использующая стеки / очереди. (Например, прочитать 10 чисел, четные записать в очередь).
- Обратная польская запись.
Перевести выражение в обратную польскую запись / из обратной польской в инфиксную. (вручную, без компьютера).
Посчитать выражение в обратной польской записи.
Деревья
- Проанализируйте дерево, изображенное на рисунке. Укажите следующие узлы дерева.
- Корень дерева.
- Родительские узлы.
- Дочерние узлы.
- Братья.
- Предки узла ….
- Потомки узла ….
- Листья.
- Чему равна высота дерева, изображенного на рисунке?
- Проанализируйте бинарные деревья, изображенные на рисунке. Какое из них является идеально- сбалансированным, сбалансированным (AVL)?
- Рассчитайте факторы балансировки для каждой вершины дерева.
- Укажите порядок прямого, симметричного и обратного обхода бинарного дерева, представленного на рисунке.
- Последовательно добавьте в двоичное дерево следующие элементы: …