Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

M_P_DS > Sem II (Program I) - N8 > Flashcards

Sem II (Program I) - N8 Flashcards

1
Q

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

A

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

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

Welche Nachteile haben Arrays als Datenstruktur?

A

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

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

Wie unterscheiden sich dynamische Datenstrukturen von statischen?

A

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

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

Welche Bestandteile hat eine Liste als dynamische Datenstruktur?

A

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

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

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

A

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

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

Welche Vorteile bietet eine doppelt verkettete Liste?

A

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

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

Welche Nachteile hat eine doppelt verkettete Liste?

A

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

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

Wie wird ein einfacher Knoten in Java definiert?

A

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

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

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

A

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

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

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

A

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

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

Was ist die Aufgabe der Listen-Klasse?

A

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

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

Wie wird eine doppelt verkettete Liste in Java implementiert?

A

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

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

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

A

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

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

Welche Sichtbarkeitsmodifikatoren können geschachtelte Klassen haben?

A

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

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

Welche Einschränkungen gelten für Elementklassen?

A

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

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

Wie wird eine Instanz einer inneren Klasse erstellt?

A 
Outer.Inner obj = outerObj.new Inner();
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Was ist das LIFO-Prinzip bei einem Stack?

A

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

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

Welche Operationen bietet ein Stack an?

A

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.

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

Wie wird ein Stack als Array implementiert?

A 
private int[] stack;
private int count;
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Wie wird ein Stack als Liste implementiert?

A 
class Stack {
    private Node top = null;
}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Welche Vorteile bieten innere Klassen?

A

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

22
Q

Welche Nachteile haben innere Klassen?

A

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

23
Q

Wie wird die Länge einer verketteten Liste bestimmt?

A

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

24
Q

Was sind die Vorteile von Arrays im Vergleich zu Listen?

A

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

25
Q

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

A

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

26
Q

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

A

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

27
Q

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

A

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

28
Q

Was ist der Unterschied zwischen einer Liste und einem Array?

A

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

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

29
Q

Wie ist ein Baum definiert?

A

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

30
Q

Was ist ein Blatt in der Baum-Terminologie?

A

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

31
Q

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

A

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

32
Q

Was ist ein Binärbaum?

A

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

33
Q

Welche Eigenschaften hat ein vollständiger Binärbaum?

A

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

34
Q

In welchen Anwendungsfällen werden Bäume genutzt?

A

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

35
Q

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

A

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

36
Q

Wie wird ein Binärbaum in Java implementiert?

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

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

A

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.

38
Q

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

A

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

39
Q

Wie kann ein Binärbaum in Java initialisiert werden?

A

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);
~~~

40
Q

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

A

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

41
Q

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

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

Wie wird die Tiefe eines Binärbaums berechnet?

A

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

43
Q

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

A 
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);
}
44
Q

Was ist die Serialisierung eines Binärbaums?

A

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

45
Q

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

A

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

46
Q

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

A

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

47
Q

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

A

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

48
Q

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

A

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

49
Q

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

A

Eine Warteschlange.

50
Q

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

A

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

M_P_DS (62 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions