Sem II (Program I) - N9 Flashcards
Зачем используется стек при поиске в глубину?
Чтобы сохранять порядок узлов вдоль пути.
Wann gilt ein Binärbaum als sortiert?
Бинарное дерево считается отсортированным, если:
- Все узлы в левом поддереве узла меньше самого узла.
- Все узлы в правом поддереве узла больше самого узла.
Как вставить узел в отсортированное бинарное дерево?
Алгоритм решает на каждом узле, куда вставлять новый узел - слева или справа:
- Если значение меньше, проверить, есть ли место слева. Если да, вставить слева. В противном случае продолжить поиск в левом поддереве.
- Если значение больше, действовать аналогично с правой стороны.
- Если значение равно, узел не вставляется, и выводится сообщение об ошибке.
Was passiert, wenn der Baum leer ist?
Новый узел вставляется в качестве корня.
Was ist der Unterschied zwischen Preorder-, Inorder- und Postorder-Durchlauf in binären Bäumen?
Preorder: Корень → левое поддерево → правое поддерево
Inorder: левое поддерево → корень → правое поддерево
Postorder: левое поддерево → правое поддерево → корень
Wie wird ein Preorder-Durchlauf in Java implementiert?
public void preorder() {
rekPreorder(root);
}
private void rekPreorder(BinNode k) {
if (k != null) {
tuWas(k.inhalt);
rekPreorder(k.links);
rekPreorder(k.rechts);
}
}Welche Schritte sind beim Postorder-Durchlauf erforderlich?
- Обойти левое поддерево
- Обойти правое поддерево
- Посетить корень
Чем поиск в ширину (Levelorder) отличается от других обходов?
Поиск в ширину проходит дерево уровень за уровнем (слой за слоем), в то время как другие обходы являются рекурсивными и учитывают порядок корня и поддеревьев в зависимости от метода.
Wie könnte die Breitensuche in Java implementiert werden?
Поиск в ширину требует очереди для промежуточного хранения узлов текущего уровня:
- Вставить узлы текущего уровня в очередь.
- Последовательно вставлять дочерние узлы каждого узла в очередь.
- Повторять, пока не будут пройдены все уровни.
Welche praktische Anwendung hat die Breitensuche in Bäumen?
- Поиск в игровых деревьях (например, шахматы, шашки).
- Нахождение следующего игрового хода или выигрышной позиции за наименьшее количество ходов.
- Стратегии поиска с ограничением глубины для оптимизации.
Warum ist es wichtig, sich in der Breitensuche die Knoten einer Ebene zu merken?
Чтобы узлы могли быть пройдены в упорядоченном порядке (слева направо), их необходимо сохранить в очереди перед рассмотрением следующего уровня.
Wie wird ein Blattknoten aus einem sortierten Binärbaum entfernt?
- Найти узел, который нужно удалить.
- Удалить узел и установить указатель родительского узла в null.
Wozu wird die Datenstruktur Baum verwendet?
Деревья используются для отображения иерархических структур в наборах данных, например, деревья решений, деревья вывода и структуры баз данных.
Какой уровень доступа (видимости) к классу двоичных узлов вы порекомендуете?
Видимость класса должна быть ограничена (например, private или protected), чтобы избежать прямого доступа к данным узла и защитить структуру данных.
Как можно обойти дерево(3 варианта)?
Tiefensuche: Preorder, Inorder, Postorder
Breitensuche
Was ist der Unterschied zwischen Tiefen- und Breitensuche?
Поиск в глубину: Проходит по узлам вдоль одного пути до конца, прежде чем исследовать другие пути.
Поиск в ширину: Проходит по узлам уровень за уровнем.
Wie kann man Tiefen- und Breitensuche auf Bäumen in Java implementieren?
Поиск в глубину: Рекурсивная реализация, которая обращается к левому и правому поддеревьям.
Поиск в ширину: Использование очереди (Queue) для последовательного посещения узлов одного уровня
Легче ли вставить или удалить узел в отсортированном двоичном дереве?
Вставка обычно проще, так как требует только поиска правильной позиции. Удаление может быть сложнее, особенно когда удаляемый узел имеет два дочерних узла.
Blatt (Terminalknoten)
Knoten ohne Kinder
innerer Knoten
ein Knoten mit mind. einem Kind
Höhe (Tiefe) des Baumes
max. (Kanten-)Entfernung von Wurzel bis zum Blatt
Tiefe (Level) eines Knoten
seine Entfernung zur Wurzel (Tiefe der Wurzel = 0)
Binärbaum
Baum, bei dem jeder Knoten max. zwei Kindknoten hat
Was ist eine Wrapper-Klasse?
Класс-обертка служит для преобразования простых типов данных в объекты.
Welche Wrapper-Klassen bietet das Paket java.lang?
Классы Integer, Float, Double, Byte, Short, Long и Void.
Wie wandelt man einen String in einen int mit einer Wrapper-Klasse um?
String s1 = "100"; int i = Integer.parseInt(s1);
Как упаковать простые типы данных в объект-обертку?
Mit dem new-Operator: Integer i1 = new Integer(1);
Mit der Methode valueOf(): Integer i2 = Integer.valueOf(2);
Как распаковать значение объекта-обертки?
Mit Methoden wie intValue(), floatValue(), doubleValue() usw.
~~~
Integer i1 = Integer.valueOf(10);
int wert = i1.intValue();
~~~
Warum sind Wrapper-Objekte unveränderlich?
Классы-обертки объявлены как final, поэтому значение объекта не может быть изменено напрямую. Изменения требуют создания нового объекта.
~~~
Integer io = Integer.valueOf(12);
int wert = io.intValue();
io = Integer.valueOf(wert + 1);
~~~
Что такое автоупаковка и автораспаковка?
Автоупаковка: Автоматическое преобразование простого типа данных в объект-обертку.
Пример: Integer i = 10;
Автораспаковка: Автоматическая распаковка объекта-обертки в простой тип данных.
Пример: int wert = i;
**Как работает интерфейс Comparable<T> в классах-обертках?**</T>
Все числовые классы-обертки (например, Integer, Float), а также Character и Boolean реализуют интерфейс Comparable. Он позволяет сравнивать объекты с помощью метода compareTo().
~~~
Integer i1 = Integer.valueOf(10);
Integer i2 = Integer.valueOf(20);
int result = i1.compareTo(i2); // -1, потому что 10 < 20
~~~
Какие преимущества имеет автоупаковка/автораспаковка?
Это позволяет обращаться с простыми типами данных как с объектами, что облегчает их использование в методах, ожидающих ссылки в качестве параметров.
Почему простые типы данных быстрее, чем классы-обертки?
Прямая адресация: при использовании простых типов данных процессор может напрямую обращаться к памяти.
Прямая поддержка: операции, такие как сложение и умножение, напрямую поддерживаются процессором, в то время как объекты-обертки требуют дополнительных ссылок.
Как преобразовать значение типа double в объект Double?
С помощью автоупаковки: Double dObj = 2.1;
Как преобразовать объект Double в значение типа double?
С помощью автораспаковки: double d = dObj;
Что такое автоупаковка?
Автоматическое преобразование примитивного типа в соответствующий объект-обертку.
Что такое автораспаковка?
Автоматическое преобразование объекта-обертки в соответствующий примитивный тип.
Каковы преимущества и недостатки автоупаковки?
Преимущества: Повышает читаемость и уменьшает шаблонный код.
Недостатки: Может привести к проблемам с производительностью, так как используются объекты вместо примитивных типов.
Каковы преимущества и недостатки автораспаковки?
Преимущества: Повышает читаемость и уменьшает шаблонный код.
Недостатки: Может привести к проблемам с производительностью, так как используются объекты вместо примитивных типов.
Что такое обобщенный класс?
Класс, который **определяется с одним или несколькими параметрами типа (например, <T>), что делает тип данных гибким.**</T>
Как выглядит объявление обобщенного класса?
public class Punkt<T> {
private T x;
private T y;
public Punkt(T x, T y) {
this.x = x;
this.y = y;
}
}Как можно создать экземпляры обобщенного класса с разными типами?
Punkt<Integer> p1 = new Punkt<>(1, 2); Punkt<Double> p2 = new Punkt<>(1.0, 2.0); Punkt<Float> p3 = new Punkt<>(1.0f, 2.0f);
В чем преимущество обобщенных классов?
Гибкость при использовании различных типов и избежание преобразований типов.
Что такое “параметризованные классы”?
Экземпляр обобщенного класса, для которого указан конкретный тип, например Punkt<Integer> или Punkt<Double>.</Double></Integer>
Почему простые типы вроде int нельзя использовать напрямую как параметры типа?
Обобщенные классы принимают только ссылочные типы, например Integer, Double, так как примитивные типы не являются объектами.
Что такое обобщенный метод?
Метод, который имеет собственный параметр типа, например:
public static <T> void swap(Punkt<T> p1, Punkt<T> p2) {
T tempX = p1.getX();
p1.setX(p2.getX());
p2.setX(tempX);
}
Чем отличаются обобщенные методы экземпляра от обобщенных методов класса?Чем отличаются обобщенные методы экземпляра от обобщенных методов класса?
Методы экземпляра используют параметр типа класса, в то время как методы класса объявляют собственные параметры типа.
Что такое “ограниченные параметры типа”?
Параметры типа, которые ограничены определенными классами или интерфейсами
~~~
public class PunktGen<T> { ... }</T>
~~~
Почему ограничение типов имеет смысл?
Это позволяет использовать специфические функциональные возможности, например, сравнение числовых значений через equals().
