Arbeitsblatt Datenstrukturen mit Lösungen

Wie werden die Elemente eines Arrays im Speicher abgelegt?

1. AIn einem Baum aus Speicherseiten
2. BIn einem zusammenhängenden Block, eins nach dem anderen
3. CAn zufälligen, per Hash gewählten Stellen
4. DVerstreut, über Zeiger verbunden

Was ist der Füllgrad (Load Factor) einer Hashtabelle?

1. ADie Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
2. BDie Anzahl der Buckets geteilt durch die durchschnittliche Länge der gespeicherten Schlüssel
3. CDie Zeit, um die Tabelle von der Festplatte zu laden
4. DDie Anzahl der bisherigen Kollisionen

Welche Datenstruktur wird für eine Level-Order-Traversierung eines Baums verwendet?

1. APrioritätswarteschlange
2. BStack
3. CQueue
4. DHashtabelle

Was gilt für die Adjazenzmatrix eines ungerichteten Graphen?

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

Mit welcher Datenstruktur prüft man, ob die Klammern in "{[()]}" ausgeglichen sind?

1. AMit einer Hashtabelle
2. BMit einem Stack
3. CMit einer Queue
4. DMit einem binären Suchbaum

Ein Binärbaum hat die Wurzel 1 mit linkem Kind 2 und rechtem Kind 3; Knoten 2 hat die Kinder 4 (links) und 5 (rechts). Wie lautet die Post-Order-Traversierung?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D5 4 3 2 1

Wie hoch sind ohne Union by Rank und Pfadkompression die Kosten eines einzelnen find im schlechtesten Fall in einer Union-Find-Struktur mit n Elementen?

1. AO(1)
2. BO(n)
3. CO(α(n))
4. DO(log n)

Ein Bloom-Filter kann die Frage „Ist dieses Element in der Menge?“ beantworten mit:

1. AImmer exakten Antworten
2. BMöglichen falsch-positiven, aber keinen falsch-negativen Ergebnissen
3. CMöglichen falsch-negativen, aber keinen falsch-positiven Ergebnissen
4. DAntworten nur für Zahlen