Sem II (Program I) - N8 Flashcards
Что такое структура данных?
Структура данных – это упорядочивание и/или связывание данных для их эффективного управления. Примером является массив.
Welche Nachteile haben Arrays als Datenstruktur?
Массивы статические (фиксированного размера), негибкие (доступ только через индексы), а вставка или удаление элементов в середине требует копирования элементов.
Wie unterscheiden sich dynamische Datenstrukturen von statischen?
Динамические структуры данных могут расти во время выполнения, но требуют выделения памяти во время выполнения.
Welche Bestandteile hat eine Liste als dynamische Datenstruktur?
Список состоит из двух классов: класса для определения узла и класса для определения самого списка.
Was enthält ein Knoten(узел) in einer Liste?
Узел содержит данные (например, число) и указатели, либо только на последующий элемент (одностороннее связывание), либо дополнительно на предыдущий элемент (двустороннее связывание).
Welche Vorteile bietet eine doppelt verkettete Liste?
Он позволяет осуществлять обход в обоих направлениях.
Welche Nachteile hat eine doppelt verkettete Liste?
Он требует больше места для хранения и более сложных методов, так как при манипуляциях со списком необходимо корректировать оба указателя.
Wie wird ein einfacher Knoten in Java definiert?
Посредством рекурсивного объявления класса с полями для данных (data) и следующего узла (next).
Welche Zugriffsmodifikatoren können für die Attribute eines Knotens verwendet werden?
Public: Kein Schutz.
Private: Zugriff über Getter und Setter.
Default: Schutz innerhalb des Pakets.
Elementklasse: Knoten als Teil der Listenklasse definiert.
Какие методы обычны в классе узла?
Getter (getData, getNext) und Setter (setData, setNext) für Attribute.
Was ist die Aufgabe der Listen-Klasse?
Он определяет методы для работы с узлами, такие как добавление, удаление и обход, и позволяет моделировать различные типы списков.
Wie wird eine doppelt verkettete Liste in Java implementiert?
Durch Hinzufügen eines zusätzlichen Zeigers (prev) in der Knotenklasse.
Was sind geschachtelte Klassen und wie unterscheiden sie sich von Vererbung?
Вложенные классы - это классы, определенные внутри других классов. Они не имеют отношения к наследованию, хотя могут нормально наследоваться от внешних классов.
Welche Sichtbarkeitsmodifikatoren können geschachtelte Klassen haben?
Geschachtelte Klassen können private, protected, default oder public sein.
Welche Einschränkungen gelten für Elementklassen?
Elementklassen dürfen keine statischen Elemente enthalten, außer Konstanten (static final).
Wie wird eine Instanz einer inneren Klasse erstellt?
Outer.Inner obj = outerObj.new Inner();
Was ist das LIFO-Prinzip bei einem Stack?
По принципу Last-In-First-Out (LIFO) первым удаляется последний добавленный элемент.
Welche Operationen bietet ein Stack an?
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.
Wie wird ein Stack als Array implementiert?
private int[] stack; private int count;
Wie wird ein Stack als Liste implementiert?
class Stack {
private Node top = null;
}Welche Vorteile bieten innere Klassen?
- Lokale Definitionen für Hilfsklassen.
- Verbergen von Implementierungsdetails.
- Flexibler Mechanismus für GUI-Programmierung, z. B. Event-Handler.
Welche Nachteile haben innere Klassen?
- Unübersichtliche Klassenstruktur.
- Komplexe Vererbung.
- Abhängigkeit von der äußeren Klasse erschwert die Objekterzeugung.
Wie wird die Länge einer verketteten Liste bestimmt?
Путем итерации по списку и подсчета узлов до достижения null.
Was sind die Vorteile von Arrays im Vergleich zu Listen?
- Быстрый доступ к элементам по индексу (сложность O(1)).
- Эффективное добавление элементов в конец.
Wie implementiert man eine Methode, um ein Element an einer bestimmten Position in eine Liste einzufügen?
Путем прохождения списка до нужной позиции и корректировки указателей предыдущего и нового узла (Node).
Что происходит при удалении элемента из связанного списка?
- Поиск элемента.
- Корректировка указателей для удаления элемента из цепочки.
Что такое Node в связанном списке и какие атрибуты он имеет?
data: хранимые данные.
next: ссылка на следующий узел.
Was ist der Unterschied zwischen einer Liste und einem Array?
Liste:
- Динамический, размер может быть изменен во время выполнения.
- Добавление и удаление элементов происходит без перемещения (сложность O(1)).
Array:
- Прямой доступ к элементам очень быстрый (O(1)).
- Эффективен при добавлении элементов в конец.
Wie ist ein Baum definiert?
- Корень без родительского узла.
- Каждый узел, кроме корня, имеет ровно один родительский узел.
- Существует ровно один путь от корня к любому другому узлу (без циклов).
Was ist ein Blatt in der Baum-Terminologie?
Лист (терминальный узел) – это узел без дочерних узлов.
Wie wird die Tiefe und Höhe eines Baumes definiert?
Tiefe eines Knotens: Abstand von der Wurzel zum Knoten.
Höhe des Baumes: Maximale Entfernung von der Wurzel bis zu einem Blatt
Was ist ein Binärbaum?
Ein Binärbaum ist ein Baum, bei dem jeder Knoten höchstens zwei Kindknoten hat (linker und rechter Teilbaum).
Welche Eigenschaften hat ein vollständiger Binärbaum?
- Ein vollständiger Binärbaum mit Höhe ( n ) besitzt:
—- ( 2^n ) Blätter.
—- Insgesamt ( 2^{n+1} - 1 ) Knoten.
In welchen Anwendungsfällen werden Bäume genutzt?
- Деревья принятия решений в играх и искусственном интеллекте.
- Деревья вывода при компиляции для проверки синтаксиса.
- Организация доступа к данным в базах данных (например, отсортированное и сбалансированное бинарное дерево).
Was sind die Effizienzvorteile von sortierten, ausbalancierten Bäumen?
- Effiziente Realisierung von Grundoperationen:
—- Suchen: ( O(\log_2(n)) )
—- Einfügen und Löschen: ( O(\log_2(n)) )
Wie wird ein Binärbaum in Java implementiert?
public class BinNode {
int data;
BinNode left, right;
BinNode(int d) {
data = d;
left = right = null;
}
}Welche Zugriffsmodifikatoren sind für die BinNode-Datenfelder sinnvoll?
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.
Что такое бинарное дерево?
Бинарное дерево - это структура данных, в которой каждый узел имеет максимально два дочерних узла: левый и правый.
Wie kann ein Binärbaum in Java initialisiert werden?
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);
Как работает алгоритм подсчета узлов бинарного дерева?
- Если дерево пустое, количество узлов равно 0.
- В противном случае: количество узлов = 1 + количество узлов в левом поддереве + количество узлов в правом поддереве.
Wie lautet die Java-Implementierung zum Zählen der Knoten eines Binärbaums?
private int countNodes(BinNode k) {
if (k == null) return 0;
return 1 + countNodes(k.left) + countNodes(k.right);
}
public int countNodes() {
return countNodes(root);
}Wie wird die Tiefe eines Binärbaums berechnet?
- Если дерево пустое или является листовым узлом, глубина равна 0.
- В противном случае: глубина = 1 + max(глубина левого поддерева, глубина правого поддерева
Wie lautet die Java-Implementierung zur Berechnung der Tiefe eines Binärbaums?
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);
}Was ist die Serialisierung eines Binärbaums?
Preorder: (Wurzel (linker Teilbaum) (rechter Teilbaum))
Beispiel für Baum mit Wurzel 1: ((((6)4(7))2(5))1(3)).
Что понимается под обходом бинарного дерева?
Обход означает посещение каждого узла в дереве по крайней мере один раз. Это необходимо для таких операций, как подсчет узлов, вычисление глубины дерева или поиск узлов с определенным значением.
Что такое поиск в глубину (прямой обход) в бинарном дереве?
- Посетить корень.
- Обойти левое поддерево.
- Обойти правое поддерево
Какие еще существуют стратегии обхода?
Inorder: (linker Teilbaum) Wurzel (rechter Teilbaum)
Postorder: (linker Teilbaum)(rechter Teilbaum) Wurzel
Wie funktioniert der Algorithmus für die Breitensuche in einem Binärbaum in Java?
1) Корень добавляется в очередь.
2) Пока очередь не пуста:
- Удаляется первый элемент.
- Выполняется нужное действие (например, вывод данных).
- Левый и правый дочерние узлы текущего узла добавляются в очередь.
Какая структура данных используется для поиска в ширину?
Eine Warteschlange.
Wie funktioniert die nicht-rekursive Tiefensuche in einem Binärbaum?
1) Поместить корень на стек.
2) Пока стек не пуст:
- Взять верхний узел со стека (pop).
- Выполнить нужное действие.
- Поместить дочерние узлы узла (сначала правый, затем левый) на стек.
