Lesson_2 Datenstrukturen Flashcards
Was ist ein Datentyp?
Ein Datentyp beschreibt den Wertebereich, den Variablen annehmen können, und die darauf anwendbaren Operationen.
Was sind primitive Datentypen und wie unterscheiden sie sich?
- bool: 1 Byte, Wertebereich: 0 oder 1
- char: 1 Byte, Wertebereich: -128 bis 127
- int: 8 Byte, Wertebereich: ca. -9x10^18 bis 9x10^18
- unsigned int: 8 Byte, Wertebereich: 0 bis ca. 18x10^18
- float: 4 Byte, Wertebereich: ca. -3,4x10^38 bis 3,4x10^38
- double: 8 Byte, Wertebereich: ca. -1,7x10^308 bis 1,7x10^308
- long double: 10 Byte
Was ist eine Datenstruktur?
Eine Datenstruktur fasst gleiche oder unterschiedliche Datentypen nach bestimmten Konstruktionsprinzipien zusammen. Beispiele sind Arrays, Listen, Bäume.
Nenne Beispiele für häufig verwendete Datenstrukturen.
- Arrays,
- verkettete Listen,
- Bäume,
- Graphen,
- Stacks,
- Queues.
Was ist ein Array?
Ein Array ist eine Sammlung von Elementen desselben Datentyps, die in zusammenhängenden Speicherplätzen mit fixer größe abgelegt werden. Der Zugriff auf ein Element erfolgt über den Index.
Was sind die Vor- und Nachteile von Arrays?
Antwort:
- Vorteile: Schneller Zugriff auf Elemente mittels Index, effizienter Speicherverbrauch
- Nachteile: Feste Größe, umständlich beim Einfügen und Löschen von Elementen
Welche Zeitkomplexität hat das Einfügen in ein Array?
Das Einfügen eines Elements in ein Array hat im Worst Case eine Zeitkomplexität von O(n), da im schlimmsten Fall alle Elemente verschoben werden müssen.
Was ist die binäre Suche?
Die **binäre Suche **ist ein Algorithmus zum Suchen eines Elements in einem sortierten Array. Sie halbiert das Suchfeld in jedem Schritt und hat eine Zeitkomplexität von O(log n).
Wie funktioniert die binäre Suche? (Schritte detailliert)
Antwort:
1. Starte in der Mitte des Arrays.
2. Vergleiche das mittlere Element mit dem gesuchten Wert.
3. Falls der Wert kleiner ist, suche im linken Teil weiter, andernfalls im rechten.
4. Wiederhole den Vorgang, bis das Element gefunden wird oder das Suchfeld leer ist.
Welche Zeitkomplexität hat die binäre Suche?
Die binäre Suche hat eine Zeitkomplexität von O(log n) im Worst Case.
Was ist eine verkettete Liste?
Eine verkettete Liste ist eine dynamische Datenstruktur, bei der jedes Element einen Verweis auf das nächste Element enthält. Dies ermöglicht flexibles Einfügen und Löschen von Elementen.
Wie funktioniert das Einfügen in eine verkettete Liste?
Beim Einfügen wird ein neuer Knoten erstellt, dessen Verweis auf den nächsten Knoten zeigt. Der Vorgängerknoten wird so umgeleitet, dass er auf den neuen Knoten verweist.
Was sind die Vor- und Nachteile von verketteten Listen?
Antwort:
- Vorteile: Effizientes Einfügen und Löschen von Elementen
- Nachteile: Langsamer Zugriff, da jedes Element sequentiell durchsucht werden muss
Was ist eine doppelt verkettete Liste?
Eine doppelt verkettete Liste ist eine verkettete Liste, bei der jeder Knoten zusätzlich zum Verweis auf den nächsten Knoten auch einen Verweis auf den vorherigen Knoten hat. Dadurch ist Vor- und Rückwärtsnavigation möglich.
Wie funktioniert das Löschen in einer doppelt verketteten Liste?
Beim Löschen eines Knotens werden die Verweise des vorherigen und des nachfolgenden Knotens so angepasst, dass der gelöschte Knoten übersprungen wird. Dies kann in konstanter Zeit O(1) geschehen.
