Arbeitsblatt Datenstrukturen mit Lösungen

Welche Datenstruktur arbeitet nach dem Prinzip „last in, first out“ (LIFO)?

1. AWarteschlange (Queue)
2. BHashtabelle
3. CStapel (Stack)
4. DVerkettete Liste

Was ist die Wurzel eines Baums?

1. ADer Knoten mit dem größten Wert
2. BDer oberste Knoten ohne Elternknoten
3. CEin beliebiger Knoten in der Mitte
4. DEin Knoten ohne Kindknoten

Welche Datenstruktur eignet sich am besten für die „Rückgängig“-Funktion (Undo) in einem Texteditor?

1. AWarteschlange (Queue)
2. BStapel (Stack)
3. CHash-Set
4. DGraph

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

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

Wie wird ein neues Element in einen binären Heap eingefügt?

1. AIn die Wurzel setzen und nach unten wandern lassen
2. BAn der sortierten Position einfügen, indem alle größeren Elemente um eine Stelle nach rechts verschoben werden
3. CAns Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
4. DDen ganzen Heap von Grund auf neu aufbauen

Wozu dient ein Sentinel-Knoten (Dummy-Knoten) in einer verketteten Liste?

1. AUm zu verhindern, dass die Liste über eine feste Höchstzahl von Knoten hinauswächst
2. BEr hält die Liste sortiert
3. CEr vereinfacht den Code, weil Sonderfälle am Kopf oder Ende wegfallen
4. DEr speichert die Anzahl der Elemente

Wie kannst du mit O(1) zusätzlichem Speicher erkennen, ob eine einfach verkettete Liste einen Zyklus enthält?

1. AEinen Zeiger um einen Schritt und einen anderen um zwei Schritte bewegen und prüfen, ob sie sich treffen
2. BDie Liste sortieren und nach Duplikaten suchen
3. CDie Knoten zählen, bis die Zahl das Längenfeld der Liste übersteigt
4. DJeden besuchten Knoten in einem Hash-Set speichern

Welche Laufzeit hat die Breitensuche auf einem Graphen mit V Knoten, der als Adjazenzmatrix gespeichert ist?

1. AO(V²)
2. BO(V)
3. CO(V + E)
4. DO(E log V)