Arbeitsblatt Datenstrukturen mit Lösungen

Was ist in einem ungerichteten Graphen der Grad eines Knotens?

1. ADie Länge des längsten Pfades, der von ihm ausgeht
2. BSeine Position in der Adjazenzliste
3. CDie Anzahl der Knoten im Graphen
4. DDie Anzahl der mit ihm verbundenen Kanten

Was enthält in einer einfach verketteten Liste der next-Zeiger des letzten Knotens?

1. ADie Anzahl der Knoten in der Liste
2. BNull (keinen Knoten)
3. CDie Adresse des vorherigen Knotens
4. DDie Adresse des ersten Knotens

Was ist eine Deque (double-ended queue)?

1. AEine Queue, die nur hinten das Entfernen erlaubt
2. BEine nach Priorität sortierte Queue
3. CEine Struktur, die Einfügen und Entfernen an beiden Enden erlaubt
4. DZwei getrennte Queues, die sich ein Array teilen

Ein Straßennetz hat 100,000 Kreuzungen, die jeweils mit etwa 4 anderen verbunden sind. Welche Darstellung ist am besten geeignet?

1. AEin binärer Heap der Kanten
2. BAdjazenzliste
3. CEin einziges sortiertes Array der Knoten
4. DAdjazenzmatrix

Wie viele Knoten hat ein perfekter Binärbaum der Höhe h, wenn die Höhe in Kanten gezählt wird?

1. Ah²
2. B2h + 1
3. C2^h+1 − 1
4. D2^h

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 i − 1
2. BBei Index 2i + 1
3. CBei Index ⌊i / 2⌋ + 1
4. DBei Index ⌊(i − 1) / 2⌋

Welche Eigenschaft muss ein Rot-Schwarz-Baum erfüllen?

1. AJeder Knoten muss rot sein
2. BRote Knoten müssen rote Kindknoten haben, sodass rote Knoten immer ununterbrochene Ketten bis zu den Blättern bilden
3. CJeder Pfad von einem Knoten zu seinen Nachfahren-Blättern enthält gleich viele schwarze Knoten
4. DDie Wurzel muss rot sein

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

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