Wie hängen Suche, Einfügen und Löschen in einem BST von der Höhe h ab?

Sie kosten O(h). Ein balancierter Baum hat h = O(log n), eine Kette h = O(n). Erwartetes O(log n) benötigt Annahmen wie eine zufällige Einfügereihenfolge.

Welche Eigenschaften braucht eine Hashfunktion für Tabellensuchen?

Sie muss deterministisch sein und die erwarteten Schlüssel gut verteilen. Das Hashen eines Schlüssels fester Größe kann O(1) kosten; eine neue Zeichenkette mit L Zeichen zu hashen kostet meist O(L).

Warum kann eine doppelt verkettete Liste einen gegebenen Knoten in O(1) löschen?

Vorgänger- und Nachfolgerverweise verbinden seine Nachbarn direkt neu. Kopf und Ende werden bei Bedarf aktualisiert; eine Suche nach dem Vorgänger entfällt.

Was kostet der Aufbau eines Heaps von unten nach oben aus n Elementen?

O(n). Die meisten Knoten liegen nahe den Blättern und müssen nur wenig absinken; die Summe der Arbeit nach Knotenhöhe ist linear.

Ordne diese Wachstumsraten für n → ∞ von langsam nach schnell: n!, n, 1, n², log n, 2ⁿ, n log n.

Asymptotisch gilt: 1 < log n < n < n log n < n² < 2ⁿ < n!.

Welche Zugriffsregel und typischen Operationskosten hat eine Warteschlange?

FIFO: hinten einfügen, vorn entnehmen. Mit Kopf-/Endverweisen oder einem Ringpuffer fester Kapazität kosten beide O(1); das Verschieben eines Arrays macht die Entnahme O(n).

Wie vermeidet eine Warteschlange im Ringarray das Verschieben nach einer Entnahme?

Anfangs- und Endindex laufen modulo Kapazität um. Die Entnahme erhöht den Anfangsindex; freie Plätze lassen sich ohne Verschieben anderer Elemente wiederverwenden.

Wo liegen Elternknoten und Kinder von Knoten i in einem nullbasierten Heaparray der Länge n?

Elternknoten: ⌊(i−1)/2⌋ für i>0. Kinder: 2i+1 und 2i+2, sofern diese Indizes kleiner als n sind. Index 0 hat keinen Elternknoten.

Warum kostet ein Indexzugriff in einem Array fester Größe O(1)?

Gleich große Speicherplätze liegen zusammenhängend: Adresse(i) = Basis + i·Platzgröße. Dabei wird Adressarithmetik mit konstantem Zeitaufwand angenommen.

Was ist der Lastfaktor einer Hashtabelle, und warum kann sie ihre Größe ändern?

α = n/m: n gespeicherte Einträge und m Buckets oder Plätze. Das Überschreiten eines implementationsabhängigen Schwellenwerts kann Vergrößern und erneutes Hashen auslösen; 0,75 gilt nicht allgemein.

Welche erwarteten und schlechtesten Operationskosten hat eine Hashtabelle mit separater Verkettung?

Bei beschränkter Last, gut verteilten Hashwerten und konstanten Schlüsselkosten benötigen Suchen/Löschen erwartet O(1). Einfügen mit geometrischem Wachstum kostet erwartet amortisiert O(1). Eine Kette aus n kollidierenden Schlüsseln kann O(n) verursachen.

Was liefert eine Inorder-Traversierung eines BST mit verschiedenen Schlüsseln?

Alle Schlüssel streng aufsteigend; n Knoten werden in O(n) besucht.

Was kosten union/find mit Pfadkompression und Vereinigung nach Rang amortisiert?

O(α(n)) je Operation; α ist die inverse Ackermannfunktion, n die Elementzahl. Initialisieren kostet O(n). Die Schranke gilt für eine Folge, nicht als konstante Worst-Case-Kosten jeder einzelnen Ausführung.

Was kosten Einfügen, Entfernen der Wurzel und Nachsehen an der Wurzel eines binären Heaps?

O(log n), O(log n) beziehungsweise O(1), sofern keine Arraygrößenänderung nötig ist. Eine solche kann O(n) kosten.

Welche Antworten kann ein Bloomfilter geben, der nur Einfügungen erlaubt?

Negativ bedeutet: Das Element wurde nicht eingefügt. Positiv bedeutet: Es könnte eingefügt worden sein. Hashwerte setzen Bits in einem Bitarray; falsch positive Ergebnisse sind möglich, falsch negative bei intaktem Zustand nicht.

Was bedeutet f(n) ∈ O(g(n)) für nichtnegative Funktionen f und g?

Es gibt Konstanten c > 0 und n₀ ≥ 0, sodass f(n) ≤ c·g(n) für alle n ≥ n₀ gilt.

Welche Besuchsreihenfolgen haben Präorder-, Inorder- und Postorder-Traversierung eines Binärbaums?

Präorder: Knoten → links → rechts. Inorder: links → Knoten → rechts. Postorder: links → rechts → Knoten.

Welche zwei Eigenschaften definieren einen binären Min-Heap?

Alle Ebenen sind voll, außer gegebenenfalls der letzten, die von links gefüllt wird. Jeder Elternschlüssel ist höchstens so groß wie die Schlüssel seiner Kinder. Die Wurzel enthält daher ein Minimum.

Worin unterscheiden sich O, Ω und Θ?

Sie bezeichnen asymptotische obere, untere beziehungsweise beidseitig enge Schranken. Sie beschreiben eine festgelegte Kostenfunktion; O bedeutet nicht automatisch „schlechtester Fall“.

Wie funktioniert ein Stapel, und wann kosten seine Operationen O(1)?

LIFO: Das zuletzt abgelegte Element wird zuerst entnommen. Am Kopf einer verketteten Liste kosten Ablegen, Entnehmen und Nachsehen O(1); eine Arrayvergrößerung kann eine einzelne Ablage O(n) kosten lassen.

Wie unterscheiden sich lineares und quadratisches Sondieren bei offener Adressierung?

Die Einträge bleiben im Array. Bei Tabellengröße m und Startindex h werden (h+i) mod m beziehungsweise (h+c₁i+c₂i²) mod m geprüft. Quadratisches Sondieren benötigt geeignete Parameter.

Welche Farbregeln halten einen Rot-Schwarz-Suchbaum balanciert?

Knoten sind rot oder schwarz; Wurzel und NIL-Blätter sind schwarz. Rote Knoten haben keine roten Kinder. Jeder Pfad von einem Knoten zu einem untergeordneten NIL-Blatt enthält gleich viele schwarze Knoten. Damit ist die Höhe O(log n).

Wie löst separate Verkettung Hashkollisionen?

Jeder Bucket enthält eine Sammlung von Einträgen mit diesem Bucketindex, oft eine verkettete Liste. Verschiedene Schlüssel im selben Bucket bleiben getrennte Einträge.

Welche Ordnungsinvariante definiert einen binären Suchbaum (BST) mit verschiedenen Schlüsseln?

An jedem Knoten sind alle Schlüssel im linken Teilbaum kleiner und alle im rechten größer. Die Regel gilt rekursiv.

Wie besucht eine Traversierung nach Ebenen einen Binärbaum?

Eine FIFO-Warteschlange verarbeitet jeweils eine Tiefenebene. Das linke Kind wird vor dem rechten eingereiht, damit die Reihenfolge von links nach rechts entsteht.

Vergleiche Einfügen am Anfang und Indexzugriff bei einfach verketteter Liste und dynamischem Array.

Liste: Einfügen am Anfang O(1), Indexzugriff O(n). Array: Einfügen am Anfang O(n), Indexzugriff O(1); beim Einfügen vorn werden Elemente verschoben.

Was ist ein Trie, und wann kostet die Suche nach einem Schlüssel mit L Zeichen O(L)?

Ein Präfixbaum speichert Schlüssel entlang von Zeichenpfaden; Markierungen kennzeichnen vollständige Schlüssel. Die Suche kostet O(L), wenn jeder Übergang zum nächsten Zeichen O(1) kostet.

Was tun find und union in einer Struktur für disjunkte Mengen?

find(x) liefert den Repräsentanten der Menge von x. union(x,y) vereinigt ihre Mengen, falls sie verschieden sind; sind sie schon gleich, bleibt die Partition unverändert.

Wie unterscheiden sich Pfadkompression, Vereinigung nach Rang und Vereinigung nach Größe?

Pfadkompression leitet besuchte Knoten zur Wurzel um. Nach Rang wird die rangniedrigere Wurzel unter die ranghöhere gehängt; nach Größe die kleinere Menge unter die größere. Der Rang muss nicht der aktuellen Höhe entsprechen.

Was kostet das Anhängen an ein dynamisches Array amortisiert, wenn seine Kapazität jeweils verdoppelt wird?

O(1) je Anhängen. Eine Größenänderung kann O(n) kosten, aber n Anhängeoperationen ab einem leeren Array kosten insgesamt O(n).

Wie wird ein Links-Rechts-Ungleichgewicht nach einer AVL-Einfügung behoben?

Zuerst das linke Kind nach links drehen, dann den unausgeglichenen Knoten nach rechts.

Was ist die AVL-Balancebedingung?

An jedem Knoten gilt Höhe(links) − Höhe(rechts) ∈ {−1, 0, 1}. Zusätzlich gilt die BST-Ordnungsinvariante.

Datenstrukturen, Komplexitätsanalyse (Big-O) und Kernalgorithmen

Wiederholung auf Bachelor-Niveau mit grundlegenden Programmierkenntnissen als Voraussetzung: 32 Lernkarten zu Arrays, Listen, Hashing, Bäumen, Heaps, Tries, Union–Find, Bloomfiltern und Komplexität.

Level: basic
Languages: de → de
Cards: 32
Markdown: Datenstrukturen, Komplexitätsanalyse (Big-O) und Kernalgorithmen (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Wie hängen Suche, Einfügen und Löschen in einem BST von der Höhe h ab?	Sie kosten O(h). Ein balancierter Baum hat h = O(log n), eine Kette h = O(n). Erwartetes O(log n) benötigt Annahmen wie eine zufällige Einfügereihenfolge.
2	Welche Eigenschaften braucht eine Hashfunktion für Tabellensuchen?	Sie muss deterministisch sein und die erwarteten Schlüssel gut verteilen. Das Hashen eines Schlüssels fester Größe kann O(1) kosten; eine neue Zeichenkette mit L Zeichen zu hashen kostet meist O(L).
3	Warum kann eine doppelt verkettete Liste einen gegebenen Knoten in O(1) löschen?	Vorgänger- und Nachfolgerverweise verbinden seine Nachbarn direkt neu. Kopf und Ende werden bei Bedarf aktualisiert; eine Suche nach dem Vorgänger entfällt.
4	Was kostet der Aufbau eines Heaps von unten nach oben aus n Elementen?	O(n). Die meisten Knoten liegen nahe den Blättern und müssen nur wenig absinken; die Summe der Arbeit nach Knotenhöhe ist linear.
5	Ordne diese Wachstumsraten für n → ∞ von langsam nach schnell: n!, n, 1, n², log n, 2ⁿ, n log n.	Asymptotisch gilt: 1 < log n < n < n log n < n² < 2ⁿ < n!.
6	Welche Zugriffsregel und typischen Operationskosten hat eine Warteschlange?	FIFO: hinten einfügen, vorn entnehmen. Mit Kopf-/Endverweisen oder einem Ringpuffer fester Kapazität kosten beide O(1); das Verschieben eines Arrays macht die Entnahme O(n).
7	Wie vermeidet eine Warteschlange im Ringarray das Verschieben nach einer Entnahme?	Anfangs- und Endindex laufen modulo Kapazität um. Die Entnahme erhöht den Anfangsindex; freie Plätze lassen sich ohne Verschieben anderer Elemente wiederverwenden.
8	Wo liegen Elternknoten und Kinder von Knoten i in einem nullbasierten Heaparray der Länge n?	Elternknoten: ⌊(i−1)/2⌋ für i>0. Kinder: 2i+1 und 2i+2, sofern diese Indizes kleiner als n sind. Index 0 hat keinen Elternknoten.
9	Warum kostet ein Indexzugriff in einem Array fester Größe O(1)?	Gleich große Speicherplätze liegen zusammenhängend: Adresse(i) = Basis + i·Platzgröße. Dabei wird Adressarithmetik mit konstantem Zeitaufwand angenommen.
10	Was ist der Lastfaktor einer Hashtabelle, und warum kann sie ihre Größe ändern?	α = n/m: n gespeicherte Einträge und m Buckets oder Plätze. Das Überschreiten eines implementationsabhängigen Schwellenwerts kann Vergrößern und erneutes Hashen auslösen; 0,75 gilt nicht allgemein.
11	Welche erwarteten und schlechtesten Operationskosten hat eine Hashtabelle mit separater Verkettung?	Bei beschränkter Last, gut verteilten Hashwerten und konstanten Schlüsselkosten benötigen Suchen/Löschen erwartet O(1). Einfügen mit geometrischem Wachstum kostet erwartet amortisiert O(1). Eine Kette aus n kollidierenden Schlüsseln kann O(n) verursachen.
12	Was liefert eine Inorder-Traversierung eines BST mit verschiedenen Schlüsseln?	Alle Schlüssel streng aufsteigend; n Knoten werden in O(n) besucht.
13	Was kosten union/find mit Pfadkompression und Vereinigung nach Rang amortisiert?	O(α(n)) je Operation; α ist die inverse Ackermannfunktion, n die Elementzahl. Initialisieren kostet O(n). Die Schranke gilt für eine Folge, nicht als konstante Worst-Case-Kosten jeder einzelnen Ausführung.
14	Was kosten Einfügen, Entfernen der Wurzel und Nachsehen an der Wurzel eines binären Heaps?	O(log n), O(log n) beziehungsweise O(1), sofern keine Arraygrößenänderung nötig ist. Eine solche kann O(n) kosten.
15	Welche Antworten kann ein Bloomfilter geben, der nur Einfügungen erlaubt?	Negativ bedeutet: Das Element wurde nicht eingefügt. Positiv bedeutet: Es könnte eingefügt worden sein. Hashwerte setzen Bits in einem Bitarray; falsch positive Ergebnisse sind möglich, falsch negative bei intaktem Zustand nicht.
16	Was bedeutet f(n) ∈ O(g(n)) für nichtnegative Funktionen f und g?	Es gibt Konstanten c > 0 und n₀ ≥ 0, sodass f(n) ≤ c·g(n) für alle n ≥ n₀ gilt.
17	Welche Besuchsreihenfolgen haben Präorder-, Inorder- und Postorder-Traversierung eines Binärbaums?	Präorder: Knoten → links → rechts. Inorder: links → Knoten → rechts. Postorder: links → rechts → Knoten.
18	Welche zwei Eigenschaften definieren einen binären Min-Heap?	Alle Ebenen sind voll, außer gegebenenfalls der letzten, die von links gefüllt wird. Jeder Elternschlüssel ist höchstens so groß wie die Schlüssel seiner Kinder. Die Wurzel enthält daher ein Minimum.
19	Worin unterscheiden sich O, Ω und Θ?	Sie bezeichnen asymptotische obere, untere beziehungsweise beidseitig enge Schranken. Sie beschreiben eine festgelegte Kostenfunktion; O bedeutet nicht automatisch „schlechtester Fall“.
20	Wie funktioniert ein Stapel, und wann kosten seine Operationen O(1)?	LIFO: Das zuletzt abgelegte Element wird zuerst entnommen. Am Kopf einer verketteten Liste kosten Ablegen, Entnehmen und Nachsehen O(1); eine Arrayvergrößerung kann eine einzelne Ablage O(n) kosten lassen.
21	Wie unterscheiden sich lineares und quadratisches Sondieren bei offener Adressierung?	Die Einträge bleiben im Array. Bei Tabellengröße m und Startindex h werden (h+i) mod m beziehungsweise (h+c₁i+c₂i²) mod m geprüft. Quadratisches Sondieren benötigt geeignete Parameter.
22	Welche Farbregeln halten einen Rot-Schwarz-Suchbaum balanciert?	Knoten sind rot oder schwarz; Wurzel und NIL-Blätter sind schwarz. Rote Knoten haben keine roten Kinder. Jeder Pfad von einem Knoten zu einem untergeordneten NIL-Blatt enthält gleich viele schwarze Knoten. Damit ist die Höhe O(log n).
23	Wie löst separate Verkettung Hashkollisionen?	Jeder Bucket enthält eine Sammlung von Einträgen mit diesem Bucketindex, oft eine verkettete Liste. Verschiedene Schlüssel im selben Bucket bleiben getrennte Einträge.
24	Welche Ordnungsinvariante definiert einen binären Suchbaum (BST) mit verschiedenen Schlüsseln?	An jedem Knoten sind alle Schlüssel im linken Teilbaum kleiner und alle im rechten größer. Die Regel gilt rekursiv.
25	Wie besucht eine Traversierung nach Ebenen einen Binärbaum?	Eine FIFO-Warteschlange verarbeitet jeweils eine Tiefenebene. Das linke Kind wird vor dem rechten eingereiht, damit die Reihenfolge von links nach rechts entsteht.
26	Vergleiche Einfügen am Anfang und Indexzugriff bei einfach verketteter Liste und dynamischem Array.	Liste: Einfügen am Anfang O(1), Indexzugriff O(n). Array: Einfügen am Anfang O(n), Indexzugriff O(1); beim Einfügen vorn werden Elemente verschoben.
27	Was ist ein Trie, und wann kostet die Suche nach einem Schlüssel mit L Zeichen O(L)?	Ein Präfixbaum speichert Schlüssel entlang von Zeichenpfaden; Markierungen kennzeichnen vollständige Schlüssel. Die Suche kostet O(L), wenn jeder Übergang zum nächsten Zeichen O(1) kostet.
28	Was tun find und union in einer Struktur für disjunkte Mengen?	find(x) liefert den Repräsentanten der Menge von x. union(x,y) vereinigt ihre Mengen, falls sie verschieden sind; sind sie schon gleich, bleibt die Partition unverändert.
29	Wie unterscheiden sich Pfadkompression, Vereinigung nach Rang und Vereinigung nach Größe?	Pfadkompression leitet besuchte Knoten zur Wurzel um. Nach Rang wird die rangniedrigere Wurzel unter die ranghöhere gehängt; nach Größe die kleinere Menge unter die größere. Der Rang muss nicht der aktuellen Höhe entsprechen.
30	Was kostet das Anhängen an ein dynamisches Array amortisiert, wenn seine Kapazität jeweils verdoppelt wird?	O(1) je Anhängen. Eine Größenänderung kann O(n) kosten, aber n Anhängeoperationen ab einem leeren Array kosten insgesamt O(n).
31	Wie wird ein Links-Rechts-Ungleichgewicht nach einer AVL-Einfügung behoben?	Zuerst das linke Kind nach links drehen, dann den unausgeglichenen Knoten nach rechts.
32	Was ist die AVL-Balancebedingung?	An jedem Knoten gilt Höhe(links) − Höhe(rechts) ∈ {−1, 0, 1}. Zusätzlich gilt die BST-Ordnungsinvariante.