b&e

Richtig oder falsch?

• Heapsort ist ein in-place-Verfahren

Richtig oder falsch?

Ist f ∈ O(g), dann wächst f nicht wesentlich schneller als g.

Richtig oder falsch?

1. Ist f ∈ O(g), dann wächst g nicht wesentlich schneller als f.

Richtig oder falsch?

Es gilt f ∈ O(g) genau dann, wenn g ∈ Ω(f)

Richtig oder falsch?

1. n log(n) ∈ O(n2)

R oder F

Prio Queue ist keine Datenstruktur?

R od. F?

Kosarajus Algorithmus berechnet starke ZHK?

Richtig oder falsch?

Ein perfekter Binärbaum hat Höhe log_2(n+1) - 1 ?

R oder F?

Ein Binärer Heap ist mit einem Array umsetzbar?

R od. F.?

Prims Algorithmus ist gierig?

Richtig oder falsch?

Selectionsort hat in der Praxis keine Bedeutung?

Welche der folgenden abstrakten Datentypen können effizient mittels einer einfach

oder doppelt verketteten Liste implementiert werden?

R od. F?

• Ein Heap entspricht immer einem perfekten Binärbaum.

R od. F?

• Ein Heap wird üblicherweise mithilfe eines Arrays implementiert.

R od. F?

• In einem maximum orientierten Heap ist die Reihenfolge der Elemente immer eindeutig bestimmt.

R od. F?

In einem maximum orientierten Heap entspricht das grösste Element immer der Wurzel des entsprechenden Binärbaums.

R od. F?

• Es gibt keine Datenstruktur, die sowohl für Suchen, Einfügen als auch Löschen eines Wertes logarithmische Laufzeit (im worst case) garantiert.

R od. F?

• Schlüsseltypen müssen eine Ordnungsrelation erfüllen, damit sie als Schlüssel für einen binären Suchbaum verwendet werden können.

R od. F?

Die durchschnittliche Anzahl von Operationen, um einen Schlüssel in einer Hashtabelle zu suchen, ist konstant.

Welche Verfahren sind stabil?

Was ist die Laufzeitkomplexität für die Methode set(n, v) in Abhängigkeit der Grösse des
Arrays?

Was ist die Laufzeitkomplexität für die Methode find, in Abhängigkeit der Array Grösse n?

Ordne zu! Zur Auswahl stehen:

O(1)

O(1) amortisiert

O(n log n)

O(n)

O(log n)

Bag, Stack und Queue können effizient mit ... implementiert werden?

1) Dynamisches Array

2) Verkettete Liste

3) Verkettete Liste oder Dynamisches Array (beide sind gleich effizient)

Erkläre "voller Binärbaum"

Erkläre "Vollständiger (oder kompletter) Binärbaum"

Erkläre "perfekter Binärbaum"

Start bei Knoten 0 - Traversierung in Preorderreihenfolge

Markieren Sie in den folgenden Graphen alle Kanten des induzierten Suchbaums einer Breitensuche die von Knoten 0 ausgeht.

Sei v ein Knoten eines Graphen G. Stimmt es, dass eine von v ausgehende Tiefensuche in G genau die gleichen Knoten besucht wie eine von v ausgehende Breitensuche in G? Nur eine Antwort

Wir haben in dem Algorithmus für kürzeste Pfade eine Breitensuche verwendet und ihn auf
gerichtete Graphen ohne Kantengewichte angewendet.
Ist das alles so notwendig? Welche der folgenden Aussagen sind wahr?
(Bei gewichteten Kanten ist ein kürzester Pfad, ein Pfad, der eine minimale Summe der
Kantengewichte aufweist.)

Bei der Berechnung einer topologischen Sortierung berechnen wir eine Folge P_1,..., P_k, wobei
jedes P_i die umgekehrte Postorderreihenfolge der i-ten Tiefensuche darstellt. Die
Aneinanderreihung Pk, ..., P_1 ergibt dann eine topologische Sortierung.
Ich schlage hiermit ein alternatives Vorgehen vor: führe die gleiche Folge von Tiefensuchen durch,
berechne aber in der i-ten Suche die (nicht umgekehrte) Postorderreihenfolge R_i. Reiht man diese
in der Reihenfolge R_1,...,R_k aneinander und dreht das Gesamtergebnis um, erhält man ebenfalls
eine topologische Sortierung des Graphen. Stimmt das?

Könnte man im Konstruktor von ConnectedComponents statt der Tiefensuche auch eine
Breitensuche verwenden?

Kann man die umgekehrte Postorderreihenfolge in Kosarajus Algorithmus auch mit einer
Breitensuche bestimmen?

Kann man im zweiten Teil von Kosarajus Algorithmus (die Explorationen im Originalgraphen) auch
eine Breitensuche verwenden?

Welche der folgenden Aussagen über Äquivalenzklassen sind wahr?

Ist a in [c] und b in [c], so ist a in [b].

Ist a in [b], so ist [a] = [b].

Ist a in [c] und b in [a], so gilt nicht immer, dass b~c ist.

Ist a in [b], so ist auch [b] in [a].

Markieren Sie in folgendem Graphen alle Kanten des induzierten Suchbaums einer Tiefensuche, die
von Knoten 0 ausgeht. Bei mehreren Nachfolgern betrachten Sie sie bitte wieder in aufsteigender
Reihenfolge ihrer Knotennummer.

QuickUnion, RankedQuickUnion und RankedQuickUnion mit Pfadkompression verwalten intern alle
einen Wald von Bäumen, wobei jeder Baum eine Zusammenhangskomponente repräsentiert.
Mal angenommen, du rufst für jede der Klassen den Konstruktor (für die gleiche Graphengrösse) und
die gleiche Sequenz von union-Operationen, jedoch keine anderen Operationen auf. Wie
unterscheiden sich dann die erzeugten Wälder?

Nur eine Antwort!

Markieren Sie in folgendem Graphen alle Kanten, die in dem von Knotenmenge {0, 1, 4} induzierten Schnitt liegen.