# 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.

- **Canonical URL:** https://flashcards.world/flashcards/sets/e384343c-8885-470c-aeaf-bf32d26dcce8/
- **Markdown URL:** https://flashcards.world/flashcards/sets/e384343c-8885-470c-aeaf-bf32d26dcce8.md
- **Level:** basic
- **Languages:** de → de
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 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. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/e384343c-8885-470c-aeaf-bf32d26dcce8/).