Arbeitsblatt Datenstrukturen mit Lösungen

Was ist der Hauptunterschied zwischen einem statischen und einem dynamischen Array?

1. AEin statisches Array erlaubt einen langsameren Indexzugriff
2. BEin dynamisches Array speichert seine Elemente in verketteten Knoten, damit es einzeln wachsen kann
3. CEin dynamisches Array kann wachsen, indem es in einen größeren Speicherblock umzieht
4. DEin statisches Array kann nur Zahlen speichern

Wie heißt die Stack-Operation, die ein Element oben hinzufügt?

1. APeek
2. BPush
3. CPop
4. DEnqueue

Was ist eine Kollision in einer Hashtabelle?

1. ADer Tabelle geht der Speicher aus
2. BEin Schlüssel lässt sich überhaupt nicht hashen
3. CZwei gleiche Schlüssel werden doppelt gespeichert
4. DZwei verschiedene Schlüssel werden auf denselben Index abgebildet

Welchen abstrakten Datentyp verwendet Dijkstras Algorithmus, um den nächsten zu verarbeitenden Knoten zu wählen?

1. AEine Menge ohne Ordnung
2. BEine FIFO-Queue
3. CEine Min-Prioritätswarteschlange
4. DEinen Stack

Was gilt für die Adjazenzmatrix eines ungerichteten Graphen?

1. ASie ist immer eine obere Dreiecksmatrix
2. BSie ist symmetrisch zur Hauptdiagonale
3. CIhre Hauptdiagonale enthält immer Einsen
4. DJede Zeile hat genau eine 1

Wie groß ist die Höhe eines binären Suchbaums mit n Knoten im schlechtesten Fall, wenn die Schlüssel in sortierter Reihenfolge eingefügt werden?

1. A√n
2. B1
3. Clog₂ n
4. Dn (er wird zu einer verketteten Liste)

Warum werden B-Bäume in Datenbanken und Dateisystemen verwendet?

1. ASie benötigen keine Rebalancierung
2. BIhr hoher Verzweigungsgrad hält den Baum flach und reduziert langsame Festplattenzugriffe
3. CSie benötigen weniger Speicher als jedes Array, sodass der gesamte Index immer in den Hauptspeicher passt
4. DSie speichern Daten unsortiert

Die Union-Find-Struktur (Disjoint Set) mit Union by Rank und Pfadkompression hat amortisierte Kosten pro Operation von:

1. AO(α(n)), der inversen Ackermann-Funktion, die praktisch konstant ist
2. BO(n)
3. CGenau O(log n)
4. DO(n²)