Datenstrukturen und Abstrakte Datentypen

Question 1

Was ist eine Datenstruktur?

Answer 1

Eine Datenstruktur ist eine Art Daten zu organisieren, um sie effizient zu nutzen.
•Essentiell um schnelle und performante Algorithmen zu schreiben.

Question 2

Was ist ein Abstrakter Datentyp?

Answer 2

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.

Question 3

Ordne den Abstrakten Datentypen mindestens eine Datenstruktur zu:
•List
•Queue
•Map

Answer 3

List: Dynamic Array, Linked List

Queue: Link List, Array oder Stack based Queue

Map: Tree Map, Hash Map / Table

Question 4

Was ist ein statisches Array?

Answer 4

Ein statisches Array ist ein Kontainer mit fixer Größe n und indizierbaren Elementen von [0, n-1]

Question 5

Wofür werden Arrays benutzt?

Answer 5

• 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

Question 6

Worin unterscheiden sich Dynamic Arrays zu statischen?

Answer 6

Sie sind in iherer Größe flexibel, das heißt sie können wachsen und schrumpfen.

Question 7

Wie werden Dynamische Arrays in manchen Sprachen noch bezeichnet?

Answer 7

Array List oder Vector

Question 8

Wie funktioniert ein dynamisches Array

Answer 8

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.

Question 9

Welche Bestandteile hat eine Linked List

Answer 9

• 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

Question 10

Worin unterscheidet sich eine doppelt verkettete List zu einer einfach verketteten Liste?

Answer 10

Die doppelt verkettete Liste besitzt pro Node 2 Pointer und kann somit auch Rückwärts traversiert werden.

Question 11

Was ist ein Traverser Pointer?

Answer 11

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.

Question 12

Was ist ein Stack?

Answer 12

Der Stack ist eine linerare Datenstrucktur mit einem Ende. Es wird ein Stapel aus der realen Welt damit modelliert.

Question 13

Was sind die zwei Hauptoperationen eines Stacks?

Answer 13

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)

Question 14

Was ist eine Queue?

Answer 14

Eine Queue ist eine lineare Datenstruktur, die eine Warteschlange der realen Welt darstellt.

Question 15

Was sind die Hauptoperationen einer Queue?

Answer 15

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)

Question 16

Was ist eine Priority Queue?

Answer 16

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

Question 17

Was ist ein Heap?

Answer 17

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)

Question 18

Was versteht man unter der Heap Property / Heap Invariant?

Answer 18

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)

Question 19

Woran unterscheidet sich ein binary Heap zu einem normalen Heap?

Answer 19

Beim binary Heap hat jede Parent Node maximal 2 Child Nodes.

Question 20

Was ist ein Binary Search Tree?

Answer 20

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

Question 21

Was ist eine Hash Table?

Answer 21

Eine Datenstruktur die mapping von Schlüsseln zu Werten implementiert.
Meistens werden die Schlüssel durch eine Technik namens Hashing erstellt

Question 22

Was ist eine Hashing Funktion und welchen Sinn erfüllt sie?

Answer 22

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.

Question 23

Was ist eine Hash Kollision?

Answer 23

Wenn zwei Objekte den selben Hashwert haben, deren Daten aber unterschiedlich sind, spricht man von einer Hash Kollision.