Datenstrukturen Flashcards
Datenstrukturen, Blockchain, Abstrakte Datentypen
Was sind Datenstrukturen? Gib ein Beispiel
1
- Queues
- FIFO (First In, First Out)
- Durckaufträge sequenziell in Warteschlange abgelegt und in Reihenfolge abgearbeitet
Was ist Enqueue?
1
- Element wird Warteschlange hinzugefügt
Was ist Dequeue?
1
- Element wird Warteschlange entnommen
Wo findet man Warteschlangen?
1
- Drucker
- Kundenservice-Hotline
- Verkehr
- Aufzüge
- Fast-Food-Bestellungen
- Ticket-Schalter
Was ist ein Heap?
1
- gleicht einem Baum
- Hierarchisch
- HIFO (Highest In, First Out)
- Schlüssel - Priorität
Was ist FIFO?
1
- First In, First Out
- Zuerst eingelagertes Element wird zuerst verarbeitet
Was ist LIFO?
1
- Last In, First Out
- zuletzt eingelagertes Element wird zuerst verarbeitet (zB Stack)
Was ist HIFO?
1
- Highest In, First Out
- Element mit höchstem Wert wird zuerst entnommen
Was ist LOFO?
1
- Lowest In, First Out
- Element mit niedrigstem Wert wird entnommen (Gegenteil von HIFO)
Was ist FEFO?
1
- First Expired, First Out
- Elemente mit frühestem Ablaufdatum werden zuerst verarbeitet
Was sind Max-Heaps?
1
- Wurzelelement: immer höchste Priorität
- Kinderknoten: kleinere Priorität als Eltern
Was sind Min-Heaps?
1
- Wurzelknoten: kleinste Priorität
- Kinderknoten: höhere Priorität als Eltern
Welche Funktionalitäten hat ein Heap?
1
- Insert()
- Remove()
- ExtractMin(): Auslesen, gibt Element mit geringster Priorität zurück
Was ist ein binärer Heap?
1
- Baumstruktur, bei dem Eltern nur genau zwei Kinder haben können
Was ist ein Stack?
1
- Stapelspeicher
- LIFO (Last-In, First-Out)
- auch: Kellerspeicher
Wo werden Stacks verwendet?
1
- Mikroprozessoren
- hardwarenahes Verwalten von Information ermöglicht
Welche Funktionen haben Stacks?
1
- Push: Neues Element auf Stack abgelegt
- Pop: Oberstes Element aus Stack entnommen
- Peek: oberstes Element wird ausgegeben, ohne aus Speicher entfernt zu werden
Was sind Graphen?
1
- Menge aus Knoten (Elementen E) und Kanten (K)
Was ist ein Multigraph?
1
- erlaubt mehrere Kanten zwischen zwei Knoten (zB bei Modellierung von Straßennetzen)
Was sind ungerichtete Graphen?
1
- Graph ohne direkte Richtung
Was sind gerichtete Graphen?
1
- Kanten gehen in eine Richtung
- zB Straßennetz mit Einbahnstraßen
Was sind ungewichtete Graphen?
1
- keine zusätzlichen Werte an Kanten
- Kanten = gleichwertig
Was sind gewichtete Kanten?
1
- jede Kante besitzt Gewicht (numerischer Wert)
- Gewicht: Entfernung, Kosten, Kapazitäten, Wahrscheinlichkeiten
Wie kann das Internet als Graph abgebildet werden?
1
- Knoten: Netzwerk
- Kanten: Netzverbindung
Wie kann ein ÖPNV-Netz als Graph abgebildet werden?
1
- Knoten: Haltestellen
- Kante: Verbindung
Wie kann ein Freundschaftsnetzwerk als Graph dargestellt werden?
1
- Knoten: Person
- Kante: Freundschaft
Was ist die Hauptmotivation von Blockchains?
2
- Transaktionen zwischen Partnern
- ohne zentrale Instanz
- vertrauenswürdig, transparent, manipulationssicher
- Nachteile einer zentralen Speicherung
Was sind die Nachteile einer zentralen Speicherung von Daten?
2
- Ausfall eines Servers o. zentralen Instanz
- Datenmissbrauch
- Hackerangriffe
Was sind die Nachteile von Blockchains? (optional)
2
- hohe Transaktionskosten
- langsame Transaktionsgeschwindigkeiten
- hoher Energieverbrauch (wegen Pow Konsensmechanismus)
Wie funktioniert eine Blockchain? Erkläre kurz
2
- Daten in langer, verknüpfter Kette abgelegt
- von jedem einsehbar
- dezentral auf Computern/Servern vieler Nutzer
- Konsensverfahren (zB PoW)
Was ist ein Nonce?
2
- Ziffernkette
- nur für einmaligen Einsatz gewählt
Was ist Proof of Work?
2
- Konsens-Algorithmus
- Validierung von Transaktionen
Was sind abstrakte Datentypen?
3
- Grundlage für weiterführende Konzepte wie Objekte und Klassen
- Definition gemeinsamer Eigenschaften für mehrere Datenstrukturen
Was ist ein Objekt?
3
- Zusammenschluss von Informationen
- Instanz
- Attribute und Funktionen
Was sind Klassen?
3
- Definition d. Attribute und Funktionen
- Beziehungen möglich
- Ober- Unterklassen
Was ist Generalisierung?
3
- Vererbung
- Sichtweise in andere Richtung (von Unterklasse zu Oberklasse)
Was ist eine abstrakte Klasse?
3
- Instanzlose Klassen
- kann Unterklassen haben
- zB Auto, dann müssen Instanzen in Unterklassen liegen (zB Sportwage, Limousine, etc)
Was ist multiple Vererbung?
3
- Klassen mit mehreren Oberklassen
- Risiko: versch. Klassen mit untersch. Eigenschaften - hohes Risiko von Widersprüchen in Definitionen
Was ist Polymorphie?
3
- Implementierte Objekte können versch. Datentypen weiterverarbeiten
- je nach Datentyp: unterschiedliche Implementierungen
Welche Arten von Polymorphismus gibt es?
3
- AdHoc-Polymorphismus
- Inklusion-Polymorphismus
Was ist AdHoc-Polymorphie?
3
- Methoden- oder Operatorüberladung
- zur Kompilierzeit (statisch)
Was ist Inklusion-Polymorphismus?
3
- erlaubt Vererbung und Methodenüberschreibung
- Zur Laufzeit (dynamisch)
Was sind die Vorteile von Polymorphismus?
3
- Nutzung allgemeiner Schnittstellen (unabhängig von konkreter Implementierung)
- Funktionalität in Oberklassen definiert und in Unterklassen angepasst
