Datenstrukturen und Abstrakte Datentypen Flashcards
Was ist eine Datenstruktur?
Eine Datenstruktur ist eine Art Daten zu organisieren, um sie effizient zu nutzen.
•Essentiell um schnelle und performante Algorithmen zu schreiben.
Was ist ein Abstrakter Datentyp?
Eine Abstraktion einer Datenstruktur, die ein Interface bereitstellt, an die sich die Datenstruktur halten muss.
Es wird nicht vorgegeben, wie oder in welcher Sprache etwas implementiert werden muss.
Ordne den Abstrakten Datentypen mindestens eine Datenstruktur zu:
•List
•Queue
•Map
List: Dynamic Array, Linked List
Queue: Link List, Array oder Stack based Queue
Map: Tree Map, Hash Map / Table
Was ist ein statisches Array?
Ein statisches Array ist ein Kontainer mit fixer Größe n und indizierbaren Elementen von [0, n-1]
Wofür werden Arrays benutzt?
- Ablegen und Aufrufen von sequenziellen Daten
- Vorübergehendes Speichern von Objekten
- Als Buffer füt IO Operationen
- Lookup tables und inversive lookup tables
- Um mehrere Werte einer Funktion zu returnen
Worin unterscheiden sich Dynamic Arrays zu statischen?
Sie sind in iherer Größe flexibel, das heißt sie können wachsen und schrumpfen.
Wie werden Dynamische Arrays in manchen Sprachen noch bezeichnet?
Array List oder Vector
Wie funktioniert ein dynamisches Array
1) Array mit intialer Größe wird erstellt
2) Elemente werden hinzugefügt
3) Sobald Kapazität überschritten wird, wird ein neues Array erstellt (z.B. doppelt so groß) als das ursprüngliche. Die Werte werden dann hineinkopiert.
Welche Bestandteile hat eine Linked List
- Head: der erste Knoten in einer LL
- Tail: der letzte Knoten in einer LL
- Pointer: Referenz auf einen anderen Node
- Node: ein Objekt, das Daten und je nach Typ der Liste einen oder mehrere Pointer beinhaltet
Worin unterscheidet sich eine doppelt verkettete List zu einer einfach verketteten Liste?
Die doppelt verkettete Liste besitzt pro Node 2 Pointer und kann somit auch Rückwärts traversiert werden.
Was ist ein Traverser Pointer?
Ein Traverser Pointer wird erzeugt um den Pointer eines Elemements vorrübergehend zu speichern. So können dann Elemente der Liste hinzugefügt oder entfernt werden.
Was ist ein Stack?
Der Stack ist eine linerare Datenstrucktur mit einem Ende. Es wird ein Stapel aus der realen Welt damit modelliert.
Was sind die zwei Hauptoperationen eines Stacks?
Push: Das hinzufügen eines Objekts auf den Stapel
Pop: Das Entfernen eines Objekts vom Stapel
Die Operationen verfahren nach dem LIFO Prinzip (last in, first out)
Was ist eine Queue?
Eine Queue ist eine lineare Datenstruktur, die eine Warteschlange der realen Welt darstellt.
Was sind die Hauptoperationen einer Queue?
Enqueue: Ein Element wird hinten an die Reihe gehängt
Dequeue: Ein Element wird vorne von der Reihe entfernt
Die Operationen basieren auf den FIFO-Prinzip (first in, first out)
Was ist eine Priority Queue?
Ein Abstrakter Datentyp, basierend auf einer Queue, nur das hinzukommt, dass die Elemente darin eine Priorität besitzen. Nach dieser Priorität werden die Elemente dann wieder entfernt
> Funktioniert nur mit Elementen die sich vergleichen lassen
Was ist ein Heap?
Ein Heap ist eine auf Bäumen basierte Datenstruktur. Jedes darin abgelegte Element besitzt einen Schlüssel, der die Priorität festlegt.
Durch die Priorität wird die Position eines Elements im Heap festgelegt.
Operationen basieren auf dem HIFO-Prinzip (high in, first out)
Was versteht man unter der Heap Property / Heap Invariant?
Abhängig davon, ob es sich um einen Min oder Max Heap handelt, ist die Parent Node eines Elements immer gleich oder größer (Max Heap), bzw. gleich oder kleiner (Min Heap)
Woran unterscheidet sich ein binary Heap zu einem normalen Heap?
Beim binary Heap hat jede Parent Node maximal 2 Child Nodes.
Was ist ein Binary Search Tree?
Bei der abstrakten Datenstruktur Binary Search Tree, handelt es sich um eine binäre Baumstruktur, mit der besonderheit, dass die linke Child Node immer kleiner und die rechte Child Node immer größer, als die Parent Node.
left node < parent node < right node
Was ist eine Hash Table?
Eine Datenstruktur die mapping von Schlüsseln zu Werten implementiert.
Meistens werden die Schlüssel durch eine Technik namens Hashing erstellt
Was ist eine Hashing Funktion und welchen Sinn erfüllt sie?
Eine Hashing Funtkion errechnet einen Schlüssel mittels den Werten eines Objekts.
Mittels dem so erstellten Schlüssel kann daher leicht die Ungleichheit zweier Objekte festgestellt werden, ohne die eigentlichen Werte zu betrachten, außer beide Hashwerte sind gleich.
Es gilt mit der Hashfunktion möglichst Hash Kollisionen zu vermeiden.
Was ist eine Hash Kollision?
Wenn zwei Objekte den selben Hashwert haben, deren Daten aber unterschiedlich sind, spricht man von einer Hash Kollision.
