Sem II (Program I) - N9 Flashcards

1
Q

Зачем используется стек при поиске в глубину?

A

Чтобы сохранять порядок узлов вдоль пути.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Wann gilt ein Binärbaum als sortiert?

A

Бинарное дерево считается отсортированным, если:
- Все узлы в левом поддереве узла меньше самого узла.
- Все узлы в правом поддереве узла больше самого узла.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Как вставить узел в отсортированное бинарное дерево?

A

Алгоритм решает на каждом узле, куда вставлять новый узел - слева или справа:

- Если значение меньше, проверить, есть ли место слева. Если да, вставить слева. В противном случае продолжить поиск в левом поддереве.
- Если значение больше, действовать аналогично с правой стороны.
- Если значение равно, узел не вставляется, и выводится сообщение об ошибке.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Was passiert, wenn der Baum leer ist?

A

Новый узел вставляется в качестве корня.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Was ist der Unterschied zwischen Preorder-, Inorder- und Postorder-Durchlauf in binären Bäumen?

A

Preorder: Корень → левое поддерево → правое поддерево
Inorder: левое поддерево → корень → правое поддерево
Postorder: левое поддерево → правое поддерево → корень

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Wie wird ein Preorder-Durchlauf in Java implementiert?

A
public void preorder() {    
    rekPreorder(root); 
}

private void rekPreorder(BinNode k) {
    if (k != null) {
        tuWas(k.inhalt);  
        rekPreorder(k.links);  
        rekPreorder(k.rechts);  
    } 
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Welche Schritte sind beim Postorder-Durchlauf erforderlich?

A

- Обойти левое поддерево
- Обойти правое поддерево
- Посетить корень

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Чем поиск в ширину (Levelorder) отличается от других обходов?

A

Поиск в ширину проходит дерево уровень за уровнем (слой за слоем), в то время как другие обходы являются рекурсивными и учитывают порядок корня и поддеревьев в зависимости от метода.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Wie könnte die Breitensuche in Java implementiert werden?

A

Поиск в ширину требует очереди для промежуточного хранения узлов текущего уровня:
- Вставить узлы текущего уровня в очередь.
- Последовательно вставлять дочерние узлы каждого узла в очередь.
- Повторять, пока не будут пройдены все уровни.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Welche praktische Anwendung hat die Breitensuche in Bäumen?

A

- Поиск в игровых деревьях (например, шахматы, шашки).
- Нахождение следующего игрового хода или выигрышной позиции за наименьшее количество ходов.
- Стратегии поиска с ограничением глубины для оптимизации.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Warum ist es wichtig, sich in der Breitensuche die Knoten einer Ebene zu merken?

A

Чтобы узлы могли быть пройдены в упорядоченном порядке (слева направо), их необходимо сохранить в очереди перед рассмотрением следующего уровня.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Wie wird ein Blattknoten aus einem sortierten Binärbaum entfernt?

A

- Найти узел, который нужно удалить.
- Удалить узел и установить указатель родительского узла в null.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Wozu wird die Datenstruktur Baum verwendet?

A

Деревья используются для отображения иерархических структур в наборах данных, например, деревья решений, деревья вывода и структуры баз данных.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Какой уровень доступа (видимости) к классу двоичных узлов вы порекомендуете?

A

Видимость класса должна быть ограничена (например, private или protected), чтобы избежать прямого доступа к данным узла и защитить структуру данных.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Как можно обойти дерево(3 варианта)?

A

Tiefensuche: Preorder, Inorder, Postorder
Breitensuche

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Was ist der Unterschied zwischen Tiefen- und Breitensuche?

A

Поиск в глубину: Проходит по узлам вдоль одного пути до конца, прежде чем исследовать другие пути.
Поиск в ширину: Проходит по узлам уровень за уровнем.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Wie kann man Tiefen- und Breitensuche auf Bäumen in Java implementieren?

A

Поиск в глубину: Рекурсивная реализация, которая обращается к левому и правому поддеревьям.
Поиск в ширину: Использование очереди (Queue) для последовательного посещения узлов одного уровня

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Легче ли вставить или удалить узел в отсортированном двоичном дереве?

A

Вставка обычно проще, так как требует только поиска правильной позиции. Удаление может быть сложнее, особенно когда удаляемый узел имеет два дочерних узла.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Blatt (Terminalknoten)

A

Knoten ohne Kinder

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

innerer Knoten

A

ein Knoten mit mind. einem Kind

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Höhe (Tiefe) des Baumes

A

max. (Kanten-)Entfernung von Wurzel bis zum Blatt

22
Q

Tiefe (Level) eines Knoten

A

seine Entfernung zur Wurzel (Tiefe der Wurzel = 0)

23
Q

Binärbaum

A

Baum, bei dem jeder Knoten max. zwei Kindknoten hat

25
**Was ist eine Wrapper-Klasse?**
Класс-обертка служит для **преобразования простых типов данных в объекты.**
26
**Welche Wrapper-Klassen bietet das Paket java.lang?**
Классы **Integer, Float, Double, Byte, Short, Long и Void.**
27
**Wie wandelt man einen String in einen int mit einer Wrapper-Klasse um?**
``` String s1 = "100"; int i = Integer.parseInt(s1); ```
28
**Как упаковать простые типы данных в объект-обертку?**
**Mit dem new-Operator:** Integer i1 = new Integer(1); **Mit der Methode valueOf():** Integer i2 = Integer.valueOf(2);
29
**Как распаковать значение объекта-обертки?**
Mit Methoden wie intValue(), floatValue(), doubleValue() usw. ``` Integer i1 = Integer.valueOf(10); int wert = i1.intValue(); ```
30
**Warum sind Wrapper-Objekte unveränderlich?**
Классы-обертки объявлены как final, поэтому значение объекта не может быть изменено напрямую. Изменения требуют создания нового объекта. ``` Integer io = Integer.valueOf(12); int wert = io.intValue(); io = Integer.valueOf(wert + 1); ```
31
**Что такое автоупаковка и автораспаковка?**
**Автоупаковка:** Автоматическое преобразование простого типа данных в объект-обертку. **Пример:** Integer i = 10; **Автораспаковка:** Автоматическая распаковка объекта-обертки в простой тип данных. **Пример:** int wert = i;
32
**Как работает интерфейс Comparable в классах-обертках?**
Все числовые классы-обертки (например, **Integer, Float**), а также **Character и Boolean реализуют интерфейс Comparable**. Он позволяет **сравнивать объекты с помощью метода compareTo().** ``` Integer i1 = Integer.valueOf(10); Integer i2 = Integer.valueOf(20); int result = i1.compareTo(i2); // -1, потому что 10 < 20 ```
33
**Какие преимущества имеет автоупаковка/автораспаковка?**
Это **позволяет обращаться с простыми типами данных как с объектами, что облегчает их использование в методах, ожидающих ссылки в качестве параметров.**
34
**Почему простые типы данных быстрее, чем классы-обертки?**
**Прямая адресация:** при использовании простых типов данных процессор может напрямую обращаться к памяти. **Прямая поддержка:** операции, такие как сложение и умножение, напрямую поддерживаются процессором, в то время как объекты-обертки требуют дополнительных ссылок.
35
**Как преобразовать значение типа double в объект Double?**
**С помощью автоупаковки:** Double dObj = 2.1;
36
**Как преобразовать объект Double в значение типа double?**
**С помощью автораспаковки:** double d = dObj;
37
**Что такое автоупаковка?**
Автоматическое преобразование примитивного типа в соответствующий объект-обертку.
38
**Что такое автораспаковка?**
Автоматическое преобразование объекта-обертки в соответствующий примитивный тип.
39
**Каковы преимущества и недостатки автоупаковки?**
**Преимущества:** Повышает читаемость и уменьшает шаблонный код. **Недостатки:** Может привести к проблемам с производительностью, так как используются объекты вместо примитивных типов.
40
**Каковы преимущества и недостатки автораспаковки?**
**Преимущества:** Повышает читаемость и уменьшает шаблонный код. **Недостатки:** Может привести к проблемам с производительностью, так как используются объекты вместо примитивных типов.
41
**Что такое обобщенный класс?**
Класс, который **определяется с одним или несколькими параметрами типа (например, ), что делает тип данных гибким.**
42
**Как выглядит объявление обобщенного класса?**
``` public class Punkt { private T x; private T y; public Punkt(T x, T y) { this.x = x; this.y = y; } } ```
43
**Как можно создать экземпляры обобщенного класса с разными типами?**
``` Punkt p1 = new Punkt<>(1, 2); Punkt p2 = new Punkt<>(1.0, 2.0); Punkt p3 = new Punkt<>(1.0f, 2.0f); ```
44
**В чем преимущество обобщенных классов?**
Гибкость при использовании различных типов и избежание преобразований типов.
45
**Что такое "параметризованные классы"?**
Экземпляр обобщенного класса, для которого указан конкретный тип, например Punkt или Punkt.
46
**Почему простые типы вроде int нельзя использовать напрямую как параметры типа?**
**Обобщенные классы принимают только ссылочные типы, например Integer, Double, так как примитивные типы не являются объектами.**
47
**Что такое обобщенный метод?**
**Метод, который имеет собственный параметр типа**, например: ``` public static void swap(Punkt p1, Punkt p2) { T tempX = p1.getX(); p1.setX(p2.getX()); p2.setX(tempX); } ```
48
**Чем отличаются обобщенные методы экземпляра от обобщенных методов класса?Чем отличаются обобщенные методы экземпляра от обобщенных методов класса?**
**Методы экземпляра используют параметр типа класса, в то время как методы класса объявляют собственные параметры типа.**
49
**Что такое "ограниченные параметры типа"?**
Параметры типа, которые **ограничены определенными классами или интерфейсами** ``` public class PunktGen { ... } ```
50
**Почему ограничение типов имеет смысл?**
Это **позволяет использовать специфические функциональные возможности, например, сравнение числовых значений через equals().**