Semesterwoche 11 Flashcards
Auf welchem Konzept basiert die LinkedList?
Konzept der verketteten Listen
Auf welchem Konzept basiert die ArrayList?
Konzept der wachsenden Arrays
Wie und an welchem Beispiel gibt man den konstanten Aufwand an?
O(1) z.B. zurückgeben eines Elements in einem Array
Wie und an welchem Beispiel gibt man den logarithmischen Aufwand an?
O(log n) z.B. Baumsuche
Wie und an welchem Beispiel gibt man den linearen Aufwand an?
O(n) z.B. Suche in einer Liste
Wann gibt man den Aufwand (n*log n) an?
z.B. bei guten Sotierverfahren
Wie und an welchem Beispiel gibt man den quadratischen Aufwand an?
O(n^2) z.B bei einfachen Sortierverfahren
Wie und an welchem Beispiel gibt man den exponentiellen Aufwand an?
O(2^n) z.B. beim Erzeugen der Potenzmenge
Wie komplex ist das Einfügen in eine Liste (LinkedList/ArrayList)?
O(n)
Wie komplex ist der Zugriff auf ein Element in einer Liste (LinkedList/ArrayList)?
LinkedList: O(n)
ArrayList: O(1)
Bei der Implementation einer Menge als Liste, wie komplex ist das Einfügen?
O(n)
In welche Datenstruktur kann man sortierbare Elemente einpflegen?
MIt einem Suchbaum
Womit kann man kategorisierbare Elemente implementieren?
Mit einem Hash-Verfahren
Wie ist ein binärer Suchbaum aufgebaut?
- Jeder Knoten hat maximal zwei Nachfolger
- im linken Teilbaum sind alle Elemente kleiner als der Knoten
- im rechten Teilbaum sind alle Elemente größer als der Knoten
Wie viele Blätter hat ein voller Binärbaum?
2^h
