Sem II (Program I) - N8

Question 1

Что такое структура данных?

Answer 1

Структура данных – это упорядочивание и/или связывание данных для их эффективного управления. Примером является массив.

Question 2

Welche Nachteile haben Arrays als Datenstruktur?

Answer 2

Массивы статические (фиксированного размера), негибкие (доступ только через индексы), а вставка или удаление элементов в середине требует копирования элементов.

Question 3

Wie unterscheiden sich dynamische Datenstrukturen von statischen?

Answer 3

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

Question 4

Welche Bestandteile hat eine Liste als dynamische Datenstruktur?

Answer 4

Список состоит из двух классов: класса для определения узла и класса для определения самого списка.

Question 5

Was enthält ein Knoten(узел) in einer Liste?

Answer 5

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

Question 6

Welche Vorteile bietet eine doppelt verkettete Liste?

Answer 6

Он позволяет осуществлять обход в обоих направлениях.

Question 7

Welche Nachteile hat eine doppelt verkettete Liste?

Answer 7

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

Question 8

Wie wird ein einfacher Knoten in Java definiert?

Answer 8

Посредством рекурсивного объявления класса с полями для данных (data) и следующего узла (next).

Question 9

Welche Zugriffsmodifikatoren können für die Attribute eines Knotens verwendet werden?

Answer 9

Public: Kein Schutz.
Private: Zugriff über Getter und Setter.
Default: Schutz innerhalb des Pakets.
Elementklasse: Knoten als Teil der Listenklasse definiert.

Question 10

Какие методы обычны в классе узла?

Answer 10

Getter (getData, getNext) und Setter (setData, setNext) für Attribute.

Question 11

Was ist die Aufgabe der Listen-Klasse?

Answer 11

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

Question 12

Wie wird eine doppelt verkettete Liste in Java implementiert?

Answer 12

Durch Hinzufügen eines zusätzlichen Zeigers (prev) in der Knotenklasse.

Question 13

Was sind geschachtelte Klassen und wie unterscheiden sie sich von Vererbung?

Answer 13

Вложенные классы - это классы, определенные внутри других классов. Они не имеют отношения к наследованию, хотя могут нормально наследоваться от внешних классов.

Question 14

Welche Sichtbarkeitsmodifikatoren können geschachtelte Klassen haben?

Answer 14

Geschachtelte Klassen können private, protected, default oder public sein.

Question 15

Welche Einschränkungen gelten für Elementklassen?

Answer 15

Elementklassen dürfen keine statischen Elemente enthalten, außer Konstanten (static final).

Question 16

Wie wird eine Instanz einer inneren Klasse erstellt?

Answer 16

Outer.Inner obj = outerObj.new Inner();

Question 17

Was ist das LIFO-Prinzip bei einem Stack?

Answer 17

По принципу Last-In-First-Out (LIFO) первым удаляется последний добавленный элемент.

Question 18

Welche Operationen bietet ein Stack an?

Answer 18

push: Fügt ein Element oben hinzu.
pop: Entfernt das oberste Element und gibt es zurück.
top (peek): Gibt das oberste Element zurück, ohne es zu entfernen.

Question 19

Wie wird ein Stack als Array implementiert?

Answer 19

private int[] stack;
private int count;

Question 20

Wie wird ein Stack als Liste implementiert?

Answer 20

class Stack {
    private Node top = null;
}

Question 21

Welche Vorteile bieten innere Klassen?

Answer 21

- Lokale Definitionen für Hilfsklassen.
- Verbergen von Implementierungsdetails.
- Flexibler Mechanismus für GUI-Programmierung, z. B. Event-Handler.

Question 22

Welche Nachteile haben innere Klassen?

Answer 22

- Unübersichtliche Klassenstruktur.
- Komplexe Vererbung.
- Abhängigkeit von der äußeren Klasse erschwert die Objekterzeugung.

Question 23

Wie wird die Länge einer verketteten Liste bestimmt?

Answer 23

Путем итерации по списку и подсчета узлов до достижения null.

Question 24

Was sind die Vorteile von Arrays im Vergleich zu Listen?

Answer 24

- Быстрый доступ к элементам по индексу (сложность O(1)).
- Эффективное добавление элементов в конец.

Question 25

**Wie implementiert man eine Methode, um ein Element an einer bestimmten Position in eine Liste einzufügen?**

Answer 25

**Путем прохождения списка до нужной позиции и корректировки указателей предыдущего и нового узла (Node).**

Question 26

**Что происходит при удалении элемента из связанного списка?**

Answer 26

**-** Поиск элемента. **-** Корректировка указателей для удаления элемента из цепочки.

Question 27

**Что такое Node в связанном списке и какие атрибуты он имеет?**

Answer 27

**data:** хранимые данные. **next:** ссылка на следующий узел.

Question 28

**Was ist der Unterschied zwischen einer Liste und einem Array?**

Answer 28

**Liste:** **-** Динамический, размер может быть изменен во время выполнения. **-** Добавление и удаление элементов происходит без перемещения (сложность O(1)). **Array:** **-** Прямой доступ к элементам очень быстрый (O(1)). **-** Эффективен при добавлении элементов в конец.

Question 29

**Wie ist ein Baum definiert?**

Answer 29

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

Question 30

**Was ist ein Blatt in der Baum-Terminologie?**

Answer 30

Лист (терминальный узел) – **это узел без дочерних узлов.**

Question 31

**Wie wird die Tiefe und Höhe eines Baumes definiert?**

Answer 31

**Tiefe eines Knotens:** Abstand von der Wurzel zum Knoten. **Höhe des Baumes:** Maximale Entfernung von der Wurzel bis zu einem Blatt

Question 32

**Was ist ein Binärbaum?**

Answer 32

Ein Binärbaum ist ein Baum, **bei dem jeder Knoten höchstens zwei Kindknoten hat** (**linker** und **rechter Teilbaum**).

Question 33

**Welche Eigenschaften hat ein vollständiger Binärbaum?**

Answer 33

**-** Ein vollständiger Binärbaum mit Höhe ( n ) besitzt: **----** ( 2^n ) Blätter. **----** Insgesamt ( 2^{n+1} - 1 ) Knoten.

Question 34

**In welchen Anwendungsfällen werden Bäume genutzt?**

Answer 34

**-** Деревья принятия решений в играх и искусственном интеллекте. **-** Деревья вывода при компиляции для проверки синтаксиса. **-** Организация доступа к данным в базах данных (например, отсортированное и сбалансированное бинарное дерево).

Question 35

**Was sind die Effizienzvorteile von sortierten, ausbalancierten Bäumen?**

Answer 35

**-** Effiziente Realisierung von Grundoperationen: **----** Suchen: ( O(\log_2(n)) ) **----** Einfügen und Löschen: ( O(\log_2(n)) )

Question 36

**Wie wird ein Binärbaum in Java implementiert?**

Answer 36

``` public class BinNode { int data; BinNode left, right; BinNode(int d) { data = d; left = right = null; } } ```

Question 37

**Welche Zugriffsmodifikatoren sind für die BinNode-Datenfelder sinnvoll?**

Answer 37

**public:** Keine Schutzmechanismen. **private:** Zugriff über Getter/Setter, aber langsamer. **default:** Schutz auf Paketebene, effizienter Zugriff. **Als innere Klasse in der Baum-Klasse für spezifischen Zugriffsschutz.**

Question 38

**Что такое бинарное дерево?**

Answer 38

Бинарное дерево - это структура данных, в которой **каждый узел имеет максимально два дочерних узла: левый и правый.**

Question 39

**Wie kann ein Binärbaum in Java initialisiert werden?**

Answer 39

Mit der Klasse **BinTree und Knoten der Klasse BinNode. Beispiel:** ``` BinNode k1 = new BinNode(6); BinNode k2 = new BinNode(7); BinNode m1 = new BinNode(4, k1, k2); BinTree baum = new BinTree(m1); ```

Question 40

**Как работает алгоритм подсчета узлов бинарного дерева?**

Answer 40

**-** Если дерево пустое, количество узлов равно 0. **-** В противном случае: количество узлов = 1 + количество узлов в левом поддереве + количество узлов в правом поддереве.

Question 41

**Wie lautet die Java-Implementierung zum Zählen der Knoten eines Binärbaums?**

Answer 41

``` private int countNodes(BinNode k) { if (k == null) return 0; return 1 + countNodes(k.left) + countNodes(k.right); } public int countNodes() { return countNodes(root); } ```

Question 42

**Wie wird die Tiefe eines Binärbaums berechnet?**

Answer 42

**-** Если дерево пустое или является листовым узлом, глубина равна 0. **-** В противном случае: глубина = 1 + max(глубина левого поддерева, глубина правого поддерева

Question 43

**Wie lautet die Java-Implementierung zur Berechnung der Tiefe eines Binärbaums?**

Answer 43

``` private int calculateDepth(BinNode k) { if (k == null || (k.left == null && k.right == null)) return 0; return 1 + Math.max(calculateDepth(k.left), calculateDepth(k.right)); } public int calculateDepth() { return calculateDepth(root); } ```

Question 44

**Was ist die Serialisierung eines Binärbaums?**

Answer 44

**Preorder:** (Wurzel (linker Teilbaum) (rechter Teilbaum)) **Beispiel** für Baum mit Wurzel 1: ((((6)4(7))2(5))1(3)).

Question 45

**Что понимается под обходом бинарного дерева?**

Answer 45

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

Question 46

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

Answer 46

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

Question 47

**Какие еще существуют стратегии обхода?**

Answer 47

**Inorder:** (linker Teilbaum) Wurzel (rechter Teilbaum) **Postorder:** (linker Teilbaum)(rechter Teilbaum) Wurzel

Question 48

**Wie funktioniert der Algorithmus für die Breitensuche in einem Binärbaum in Java?**

Answer 48

**1)** Корень добавляется в очередь. **2)** Пока очередь не пуста: **-** Удаляется первый элемент. **-** Выполняется нужное действие (например, вывод данных). **-** Левый и правый дочерние узлы текущего узла добавляются в очередь.

Question 49

**Какая структура данных используется для поиска в ширину?**

Answer 49

**Eine Warteschlange.**

Question 50

**Wie funktioniert die nicht-rekursive Tiefensuche in einem Binärbaum?**

Answer 50

**1)** Поместить корень на стек. **2)** Пока стек не пуст: **-** Взять верхний узел со стека (pop). **-** Выполнить нужное действие. **-** Поместить дочерние узлы узла (сначала правый, затем левый) на стек.