Arbeitsblatt Datenstrukturen mit Lösungen

Was speichert eine Map (Dictionary)?

1. ANach Größe sortierte Werte
2. BPaare gleicher Schlüssel
3. CSchlüssel-Wert-Paare mit eindeutigen Schlüsseln
4. DNur Werte in Einfügereihenfolge

Die Tiefe eines Knotens in einem Baum ist:

1. ADie Anzahl der Kanten von diesem Knoten bis zum tiefsten Blatt
2. BDie Anzahl der Kindknoten dieses Knotens
3. CDie Anzahl der Knoten in seinem Teilbaum
4. DDie Anzahl der Kanten von der Wurzel bis zu diesem Knoten

Was ist ein Zyklus in einem Graphen?

1. AEin Knoten ohne Kanten
2. BEin Pfad, der jeden Knoten besucht
3. CEine Kante mit dem Gewicht null
4. DEin Pfad, der am selben Knoten beginnt und endet

Was kostet das Einfügen eines Elements in der Mitte eines Arrays mit n Elementen?

1. AO(n²), weil jedes Element n-mal verschoben wird
2. BO(log n), wegen der binären Suche
3. CO(n), weil die nachfolgenden Elemente verschoben werden müssen
4. DO(1), weil der Index bekannt ist

Eine In-Order-Traversierung eines binären Suchbaums besucht die Schlüssel in:

1. AImmer absteigender Reihenfolge
2. BAufsteigend sortierter Reihenfolge
3. CEinfügereihenfolge
4. DEbenenweiser Reihenfolge (Level-Order)

Wo liegt in einem binären Heap, der in einem Array ab Index 0 gespeichert ist, der Elternknoten des Knotens mit Index i?

1. ABei Index 2i + 1
2. BBei Index i − 1
3. CBei Index ⌊(i − 1) / 2⌋
4. DBei Index ⌊i / 2⌋ + 1

Welche Datenstruktur ermöglicht einen LRU-Cache (least recently used) mit get und put in O(1)?

1. ANur ein Stack
2. BNur ein binärer Suchbaum
3. CEine Hashmap kombiniert mit einer doppelt verketteten Liste
4. DEin einzelnes sortiertes Array

Welche Regel müssen Hash und Gleichheit befolgen, damit eine Hashtabelle korrekt funktioniert?

1. AGleiche Hashwerte bedeuten gleiche Schlüssel
2. BHashwerte müssen Primzahlen sein
3. CVerschiedene Schlüssel müssen verschiedene Hashwerte haben
4. DGleiche Schlüssel müssen gleiche Hashwerte haben