Grundlegende Datenstrukturen Flashcards
Nenne beide Varianten zur Realisierung von linearen Listen
- Sequenziell
- Verkettet
Nenne Vorteile der Sequenziellen Realisierung von linearen Listen
schneller Zugriff
Nenne Nachteile der Sequenziellen Realisierung von linearen Listen
langsames Einfügen
Wie implementiert man eine Queue sequenziell?
Nenne Vorteile der verketteten Realisierung von linearen Listen
schnelles Einfügen
Nenne Nachteile der verketteten Realisierung von linearen Listen
langsamer Zugriff, höherer
Speicherbedarf
Lineare Listen: Sequenzielle Speicherung
Komplexität Zugriff
O(1)
direkt über Index p: L.element[p]
Lineare Listen: Sequenzielle Speicherung
Komplexität Suchen
O(N)
durchlaufe die Liste bis x gefunden wurde
Lineare Listen: Sequenzielle Speicherung
Komplexität Einfügen
O(N)
verschiebe Elemente p+1,…,n um eine Position nach hinten
Lineare Listen: Sequenzielle Speicherung
Komplexität Entfernen
O(N)
verschiebe Elemente p+1,…,n um eine Position nach vorne
Lineare Listen: Sequenzielle Speicherung
Komplexität Verketten
O(N)
füge die Elemente von Liste 2 hinter Liste 1 ein
Lineare Listen: (Doppelt-)verkettete Speicherung
Komplexität Zugriff
O(N) [O(1)]
durchlaufe die Liste bis Position p
[ ] : falls pos-Zeiger bereits an Position p
Lineare Listen: (Doppelt-)verkettete Speicherung
Komplexität Suchen
O(N)
durchlaufe die Liste bis x gefunden wurde
Lineare Listen: (Doppelt-)verkettete Speicherung
Komplexität Einfügen
O(N) [O(1)]
erzeuge neues Element, ‚verbiege‘ Zeiger
[ ] : falls pos-Zeiger bereits an Position p
Lineare Listen: (Doppelt-)verkettete Speicherung
Komplexität Entfernen
O(N) [O(1)]
verbiege‘ Zeiger, lösche das Element
[ ] : falls pos-Zeiger bereits an Position p
Lineare Listen: (Doppelt-)verkettete Speicherung
Komplexität Verketten
O(1)
next-Zeiger des letzten Elements der Liste 1 zeigt
auf erstes Element der Liste 2
Doppelt-verkettete Listen
Wie löst man das Problem, dass ein spezieller Code für das Einfügen und Löschen am Listenanfang / -ende
notwendig ist?
Man nutzt einen Wächter vor dem Listenkopf
Nenn Elementare Datentypen
- Integer
- Real
- Boolean
- Char
Nenn strukturierte Datentypen
- Array
- Record/Struct
- Enum
- Union
Welche wichtigen Methoden definiert ein Stack?
- head
- push
- pop
Auf welche Weisen kann man einen Stapel implementieren?
Sequenziell oder verkettet
Wie kann man wohlgeormte Klammerausdrücke mit einem Algorithmus, welcher einen Stapel benutzt erkennen?
- für jede offene Klammer packt man den Index auf den Stapel und für jede schließende löscht man das oberste Element
- Ist der Stapel am Ende leer, ist der Ausdruck wohlgeformt
Welche wichtigen Methoden definiert eine Queue?
- head
- enqueue
- dequeue
Wie lautet die Nomenklatur für eine lineare Liste?
L = 〈a1, a2, a3, …, an〉
leere Liste: 〈〉
Nenn Grundoperationen einer linearen Liste
Nenn weiterführende Operationen einer linearen Liste
Wie wird eine Lineare Liste verkettet implementiert?
Wie wird eine Lineare Liste doppelt verkettet implementiert?
Was ist die Höhe eines Baumes?
Anzahl an Ebenen unter der Wurzel (max. Höhe eines Teilbaums)
Was ist die Tiefe eines Knotens?
Anzahl der Kanten von k bis zur Wurzel
Was ist das Niveau/die Ebene eines Baumes?
Wie viele Knoten hat ein vollständiger Binärbaum auf Ebene i?
2^i
Wie viele Blätter hat ein vollständiger Binärbaum?
2^h
Wie viele Knoten hat ein vollständiger Binärbaum?
Laufzeit zur Speicherung von |K| Knoten in einem Binärbaum der Höhe
Wie stellt man einen binären Baum dar?
Wie stellt man einen Baum mit unbeschränktem Grad dar?
