Arbeitsblatt Datenstrukturen mit Lösungen

Was wird bei der Darstellung eines Graphen als Adjazenzliste für jeden Knoten gespeichert?

1. ADer kürzeste Weg zu jedem anderen Knoten
2. BEine Liste seiner Nachbarknoten
3. CEine Zeile aus V booleschen Werten
4. DDie Gesamtzahl der Kanten im Graphen

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

1. AStack
2. BPrioritätswarteschlange
3. CQueue
4. DHashtabelle

Was kennzeichnet einen Binärbaum?

1. ADer Baum hat genau zwei Ebenen
2. BJeder Knoten speichert eine Binärzahl
3. CJeder Knoten hat genau zwei Kindknoten
4. DJeder Knoten hat höchstens zwei Kindknoten

Die Schlüssel 50, 30, 70, 20, 40 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt. Was ist das linke Kind von 30?

1. A70
2. B50
3. C40
4. D20

Wie lange dauert die Suche nach einem Wort der Länge L in einem Trie mit festem Alphabet?

1. AO(L × n)
2. BO(n), wobei n die Anzahl der Wörter ist
3. CO(L), unabhängig davon, wie viele Wörter gespeichert sind
4. DO(log n), wobei n die Anzahl der Wörter ist

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. A1
2. B√n
3. Clog₂ n
4. Dn (er wird zu einer verketteten Liste)

In einem Ringpuffer kann front == rear entweder leer oder voll bedeuten. Wie unterscheidet man das üblicherweise?

1. AEinen separaten Elementzähler führen oder immer einen Platz frei lassen
2. BFront und rear in derselben Variablen speichern
3. CDen Puffer immer leeren, wenn front gleich rear ist, sodass der Zustand leer ist
4. DDie Puffergröße zu einer Zweierpotenz machen

Die Zeitkomplexität von decrease-key in einem binären Heap (bei bekannter Position des Elements) beträgt:

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